c# - 子集索引搜索的数据结构

Question

我正在研究 c# jquery implementation并试图找出一种有效的算法来定位整个 DOM 的子集中的元素(例如子选择器)。目前我正在创建常用选择器的索引:构建 DOM 时的类、id 和标签。

基本数据结构如人们所料，一棵Elements的树其中包含 IEnumerable<Element> Children和一个 Parent .这在使用 Dictonary<string,HashSet<Element>> 搜索整个域时很简单。存储索引。

我一直无法理解使用索引搜索元素子集的最有效方法。我使用术语“子集”来指代链中的后续选择器将从中运行的起始集。以下是我想到的方法:

1. 从子查询的整个 DOM 中检索匹配项，并消除不属于子查询的匹配项。这需要向上遍历每个匹配项的父项，直到找到根(并消除它)或找到子集的成员(并且它是一个子项，因此包括在内)
2. 为每个元素单独维护索引。
3. 为每个元素维护一组父元素(通过消除遍历使#1 更快)
4. 为每个子查询重建整个索引。
5. 除了主要选择器之外，只需手动搜索。

每种可能技术的成本在很大程度上取决于所进行的确切操作。大多数时候 #1 可能相当不错，因为大多数时候当你进行子选择时，你的目标是特定元素。所需的迭代次数为结果数 * 每个元素的平均深度。

第二种方法是迄今为止最快的选择方法，但代价是存储需求随深度呈指数增长，并且索引维护困难。我几乎已经消除了这一点。

第三种方法的内存占用量相当低(虽然比 #2 好得多)- 这可能是合理的，但除了存储要求之外，添加和删除元素变得更加昂贵和复杂。

第四种方法无论如何都需要遍历整个选择，所以它看起来毫无意义，因为大多数子查询只会运行一次。仅当期望重复子查询时才会有益。 (或者，我可以在遍历一个子集时这样做——除了一些选择器不需要搜索整个子域，例如 ID 和位置选择器)。

第五种方法适用于有限的子集，但对于包含大量 DOM 的子集来说比第一种方法差得多。

关于如何最好地完成此任务的任何想法或其他想法？我可以混合#1 和#4，方法是根据正在搜索的子集的大小与 DOM 的大小猜测哪个更有效，但这是非常模糊的，我宁愿找到一些通用的解决方案。现在我只使用#4(只有完整的 DOM 查询使用索引)这很好，但如果你决定做类似 $('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

Answer 1

如果您怀疑名称冲突并不常见，那么它可能足够快，可以直接沿着树往上走。

如果冲突很常见，那么使用在有序前缀搜索方面表现出色的数据结构(例如树)可能会更快。您的各种子集构成了前缀。然后，您的索引键将包括选择器和总路径。

对于 DOM:

<path>
  <to>
    <element id="someid" class="someclass" someattribute="1"/>
  </to>
</path>

您将拥有以下索引键:

<element>/path/to/element
#someid>/path/to/element
.someclass>/path/to/element
@someattribute>/path/to/element

现在如果您根据前缀搜索这些键，您可以将查询限制为您想要的任何子集:

<element>           ; finds all <element>, regardless of path
.someclass>         ; finds all .someclass, regardless of path
.someclass>/path    ; finds all .someclass that exist in the subset /path
.someclass>/path/to ; finds all .someclass that exist in the subset /path/to
#id>/body           ; finds all #id that exist in the subset /body

一棵树可以在 O(log n) 中找到下界(第一个元素 >= 到你的搜索值)，因为它是从那里排序的，你简单地迭代直到找到不再匹配前缀的键。会很快的!

.NET 没有合适的树结构(它有 SortedDictionary 但遗憾的是没有公开所需的 LowerBound 方法)，因此您需要自己编写或使用现有的第三方之一。优秀C5 Generic Collection Library具有合适的 Range 方法的特征树。