代码之家  ›  专栏  ›  技术社区  ›  thr

小集合的快速数据结构

  •  1
  • thr  · 技术社区  · 15 年前

    我需要一个数据结构,可以处理小集(10-20字符串,最多50个,不同长度)非常快。假阳性是可以的,但假阴性不是。

    最后一个要求使布卢姆过滤器似乎是一个很好的适合,但我不确定他们的速度,任何其他建议?

    7 回复  |  直到 15 年前
        1
  •  5
  •   Brian    15 年前

    使用一个字符串数组来循环检查成员资格怎么样 String.Equals ?

    对于这样小的集合,花哨的数据结构可能会产生太多的开销,而大的oh不适用。你试过做最简单的事情并测量过吗?

    (如果误报是可以的,您还可以保留一个1024个布尔值的数组,在这个数组中,您只需查看前两个字符的最低5位,就可以计算出一个糟糕的字符串“散列”,从而为布尔值数组提供一个10位索引。似乎这只是一些说明。)

        2
  •  1
  •   Thomas    15 年前

    根据您希望对集合执行的操作,最快的可能是 HashSet<string> . 看到了吗 HashSet

    加法 Bloom Filter function in C# HashSet .

        3
  •  1
  •   Niki Yoshiuchi    15 年前

    如果要检查成员身份的字符串集比有效字符串集大得多,那么Trie可能比HashSet提供更好的性能。哈希集中的查找速度取决于哈希算法的运行时间,通常是O(k),其中k是字符串的长度。无论字符串是否在哈希集中,都是这样。

        4
  •  0
  •   gradbot    15 年前

    为什么不使用 Radix Tree

        5
  •  0
  •   Espo    15 年前

    查看 System.Collections.Specialized Namespace 在MSDN上。

    我知道它们不是集合,但是可以对每个键使用空值。(Java对开箱即用的集合也做同样的事情,仍然是“快速的”。

        6
  •  0
  •   ssp    15 年前

    如果HashSet对您来说太慢,您可以使用经典的LZ压缩器技术:固定大小的哈希代码数组,其中每个入口指向字符串的链表。

    如果您知道数据的域,只需构造理想的哈希函数并使用它即可。 如果不是你的案子你可以用string.GetHashCode()类似于 Murmur hash

    我假设256-512个条目的数组大小足以满足50个字符串的数据结构。

        7
  •  0
  •   Oak    15 年前

    bloom过滤器相对于哈希表的主要优点是,它们的大小取决于数据库中对象的数量和允许的误报概率,但是 取决于物体本身的大小。由于你的数据库太小,我怀疑它的大小是你最关心的问题。

    哈希集是 最好的数据结构满足您的需求,但由于数据库太小,像SortedDictionary这样的O(log(n))结构通常更可取,甚至可能只是线性搜索(如前所述)。我记得有这样一个故事,从基于散列的集合切换到基于树的集合大大提高了小型集合的性能。

    最好的方法是在它们之间切换,并比较每种方法的性能。