Ich arbeite an einem c# jquery-implementierung und versuche, einen effizienten Algorithmus zum Auffinden von Elementen in einer Teilmenge des gesamten DOM (z. B. ein Subselektor) herauszufinden. Derzeit erstelle ich einen Index der gemeinsamen Selektoren: class, id und tag, wenn das DOM erstellt wird.
Die grundlegende Datenstruktur ist, wie zu erwarten, ein Baum aus Elements die enthalten IEnumerable<Element> Children und eine Parent . Dies ist einfach, wenn die gesamte Domäne mit einer Dictonary<string,HashSet<Element>> um den Index zu speichern.
Ich habe noch nicht herausgefunden, wie man Teilmengen von Elementen mit einem Index am effektivsten durchsuchen kann. Ich verwende den Begriff "Teilmenge", um die Ausgangsmenge zu bezeichnen, anhand derer ein nachfolgender Selektor in einer Kette ausgeführt wird. Die folgenden Methoden habe ich mir überlegt:
- Abrufen von Übereinstimmungen aus dem gesamten DOM für eine Unterabfrage und Eliminieren derjenigen, die nicht Teil der Untermenge sind. Dazu müssen die übergeordneten Elemente jeder Übereinstimmung durchlaufen werden, bis die Wurzel gefunden (und eliminiert) oder ein Mitglied der Teilmenge gefunden wird (und es ist ein untergeordnetes Element, daher eingeschlossen)
- Pflegen Sie den Index für jedes Element separat.
- Beibehaltung eines Satzes von Eltern für jedes Element (um #1 schnell zu machen, indem Traversal eliminiert wird)
- Bauen Sie den gesamten Index für jede Unterabfrage neu auf.
- Suchen Sie einfach manuell, außer nach Primärselektoren.
Die Kosten jeder möglichen Technik hängen stark von der genauen Operation ab, die durchgeführt wird. #Nr. 1 ist wahrscheinlich die meiste Zeit ziemlich gut, da man bei einer Unterauswahl meistens auf bestimmte Elemente abzielt. Die Anzahl der erforderlichen Iterationen ergibt sich aus der Anzahl der Ergebnisse * der durchschnittlichen Tiefe der einzelnen Elemente.
Die zweite Methode wäre bei weitem die schnellste für die Auswahl, aber auf Kosten des Speicherbedarfs, der mit der Tiefe exponentiell ansteigt, und der schwierigen Indexpflege. Ich habe dies so gut wie ausgeschlossen.
Die 3. Methode hat einen ziemlich schlechten Speicherplatzbedarf (wenn auch viel besser als Methode Nr. 2) - sie mag vernünftig sein, aber zusätzlich zu den Speicheranforderungen wird das Hinzufügen und Entfernen von Elementen wesentlich teurer und komplizierter.
Die 4. Methode erfordert das Durchlaufen der gesamten Auswahl sowieso, so dass es sinnlos erscheint, da die meisten Unterabfragen nur einmal ausgeführt werden. Es wäre nur von Vorteil, wenn eine Unterabfrage voraussichtlich wiederholt wird. (Alternativ könnte ich dies einfach tun, während eine Teilmenge sowieso durchlaufen - außer einige Selektoren erfordern nicht die Suche der gesamten Subdomain, z. B. ID und Position Selektoren).
Die 5. Methode ist gut für begrenzte Teilmengen, aber viel schlechter als die 1. Methode für Teilmengen, die einen Großteil des DOM ausmachen.
Haben Sie eine Idee, wie man dies am besten bewerkstelligen kann? Ich könnte einige Hybrid von #1 und #4 tun, indem Sie erraten, welche effizienter angesichts der Größe der Teilmenge gesucht vs. die Größe des DOM ist, aber das ist ziemlich unscharf und ich würde lieber einige universelle Lösung finden. Im Moment verwende ich nur #4 (nur vollständige DOM-Abfragen verwenden den Index), die in Ordnung ist, aber wirklich schlecht, wenn Sie beschlossen, etwas wie tun $('body').Find('#id')
Haftungsausschluss: Dies ist eine frühe Optimierung. Ich habe keinen Engpass, der gelöst werden muss, aber als akademisches Problem kann ich nicht aufhören, darüber nachzudenken...
Lösung
Hier ist die Implementierung für die Datenstruktur, wie sie in der Antwort vorgeschlagen wird. Funktioniert perfekt als nahezu vollständiger Ersatz für ein Wörterbuch.
interface IRangeSortedDictionary<TValue>: IDictionary<string, TValue>
{
IEnumerable<string> GetRangeKeys(string subKey);
IEnumerable<TValue> GetRange(string subKey);
}
public class RangeSortedDictionary<TValue> : IRangeSortedDictionary<TValue>
{
protected SortedSet<string> Keys = new SortedSet<string>();
protected Dictionary<string,TValue> Index =
new Dictionary<string,TValue>();
public IEnumerable<string> GetRangeKeys(string subkey)
{
if (string.IsNullOrEmpty(subkey)) {
yield break;
}
// create the next possible string match
string lastKey = subkey.Substring(0,subkey.Length - 1) +
Convert.ToChar(Convert.ToInt32(subkey[subkey.Length - 1]) + 1);
foreach (var key in Keys.GetViewBetween(subkey, lastKey))
{
// GetViewBetween is inclusive, exclude the last key just in case
// there's one with the next value
if (key != lastKey)
{
yield return key;
}
}
}
public IEnumerable<TValue> GetRange(string subKey)
{
foreach (var key in GetRangeKeys(subKey))
{
yield return Index[key];
}
}
// implement dictionary interface against internal collections
}Der Code ist hier: http://ideone.com/UIp9R
