Я работаю над реализацией c # jquery и пытаюсь найти эффективный алгоритм для нахождения элементов в подмножестве всего DOM (например, подселектора). В настоящее время я создаю индекс общих селекторов: class, id и tag при построении DOM.
Базовая структура данных, как и следовало ожидать, представляет собой дерево Elements, которое содержит IEnumerable<Element> Children и Parent. Это просто при поиске по всему домену с использованием Dictonary<string,HashSet<Element>> для хранения индекса.
Мне не удалось найти наиболее эффективный способ поиска подмножеств элементов с помощью индекса. Я использую термин «подмножество» для обозначения начального набора, из которого будет запущен последующий селектор в цепочке. Вот методы, о которых я подумал:
- Извлечение совпадений из всего DOM для подзапроса и исключение тех, которые не являются частью подмножества. Это требует обхода родителей каждого соответствия до тех пор, пока не будет найден корень (и он исключен) или не будет найден член подмножества (и это дочерний элемент, следовательно, включенный)
- Ведение индекса отдельно для каждого элемента.
- Поддерживать набор родителей для каждого элемента (чтобы сделать № 1 быстрым, исключив обход)
- Перестроить весь индекс для каждого подзапроса.
- Просто ищите вручную, кроме первичных селекторов.
Стоимость каждой возможной техники в значительной степени зависит от конкретной выполняемой операции. # 1, вероятно, довольно хорошо в большинстве случаев, так как большую часть времени, когда вы делаете суб-выбор, вы ориентируетесь на определенные элементы. Требуемое количество итераций будет равно количеству результатов * средняя глубина каждого элемента.
2-й метод будет самым быстрым для выбора, но за счет требований к хранению, которые увеличиваются экспоненциально с глубиной, и трудного обслуживания индекса. Я в значительной степени устранил это.
Третий метод имеет довольно плохой след памяти (хотя и намного лучше, чем # 2) - он может быть разумным, но в дополнение к требованиям к хранилищу добавление и удаление элементов становится значительно более дорогим и сложным.
4-й метод требует обхода всего выбора в любом случае, поэтому он кажется бессмысленным, поскольку большинство подзапросов будут выполняться только один раз. Это было бы полезно, только если ожидалось, что подзапрос будет повторен. (В качестве альтернативы я мог бы просто сделать это при обходе подмножества в любом случае - за исключением того, что некоторые селекторы не требуют поиска по всему поддомену, например, селекторы ID и позиции).
5-й метод подходит для ограниченных подмножеств, но намного хуже, чем 1-й метод для подмножеств, являющихся большей частью DOM.
Есть мысли или другие идеи о том, как лучше всего это сделать? Я мог бы сделать гибрид № 1 и № 4, угадав, что более эффективно, учитывая размер искомого подмножества и размер DOM, но это довольно нечетко, и я бы предпочел найти какое-то универсальное решение. Прямо сейчас я просто использую # 4 (индекс использует только полнодомные запросы), что хорошо, но очень плохо, если вы решили сделать что-то вроде $('body').Find('#id')
Отказ от ответственности: это ранняя оптимизация. У меня нет узкого места, которое нужно решать, но как академическая проблема я не могу перестать думать об этом ...
Решение
Вот реализация структуры данных, предложенная ответом. Прекрасно работает в качестве замены словаря.
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
}
Код здесь: http://ideone.com/UIp9R