代码之家  ›  专栏  ›  技术社区  ›  Michiel Borkent

从符合字符串成员条件的集合中查找对象的最快方法

  •  1
  • Michiel Borkent  · 技术社区  · 16 年前

    假设我有一个集合(无论是数组、泛型列表还是 最快的 这个问题的解决方法)在某个类中,我们称之为 ClassFoo :

    class ClassFoo
    {
        public string word;
        public float score;
        //... etc ...
    } 
    

    假设集合中有50000个项目,都在内存中。 现在,我想尽快获取集合中遵守其酒吧成员条件的所有实例,例如:

    List<ClassFoo> result = new List<ClassFoo>();
    foreach (ClassFoo cf in collection)
    {
        if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
            result.Add(cf);
    }
    

    如何尽快获得结果?我应该考虑一些高级索引技术和数据结构吗?

    这个问题的应用程序域是一个自动完成器,它获取一个查询并给出一组建议。假设条件不会变得比这更复杂。同时假设会有很多搜索。

    9 回复  |  直到 16 年前
        1
  •  2
  •   Will Hartung    16 年前

    有了条件子句可以是“任何”的约束,那么您就只能扫描整个列表并应用条件。

    如果条件子句有限制,那么您可以考虑组织数据以更有效地处理查询。

    例如,带有“byfirstletter”字典的代码示例对于“endswith”查询根本没有帮助。

    所以,归根结底就是要对这些数据执行什么查询。

    在数据库中,这个问题是“查询优化器”的负担。在典型的数据库中,如果您有一个没有索引的数据库,显然每个查询都是表扫描。在向表中添加索引时,优化器可以使用这些数据制定更复杂的查询计划,以更好地获取数据。这就是你所描述的问题。

    一旦您有了更具体的查询类型子集,那么您就可以更好地决定什么结构是最好的。此外,还需要考虑数据量。如果你有一个每少于100字节的10个元素的列表,那么扫描所有的东西可能是你能做的最快的事情,因为你有如此少量的数据。显然,这并不能扩展到一百万个元素,但即使是聪明的访问技术也会在设置、维护(如索引维护)和内存方面带来成本。

    编辑 ,基于评论

    如果它是自动完成的,如果数据是静态的,那么对它进行排序并使用二进制搜索。你真的不会比这更快。

    如果数据是动态的,那么将其存储在平衡树中,然后搜索它。这实际上是一个二进制搜索,它允许你随机添加数据。

    其他任何事情都是对这些概念的专门化。

        2
  •  1
  •   Quintin Robinson    16 年前

    var answers=mylist.where(item=>item.bar.startswith(query)item.bar.endswith(query));

    在我看来,这是最简单的,应该执行得相当快。

        3
  •  0
  •   Aaron Jensen    16 年前

    不确定我明白…你真正能做的就是优化规则,这是最快的部分。如果不增加硬件,就无法加速循环。

    如果有多个内核或机器,则可以并行化。

        4
  •  0
  •   Morikal    16 年前

    我现在不在我的Java上,但我会考虑下面的事情。

    如何创建列表?也许你可以用一种减少比较时间的方式来创建它。

    如果您只是在集合中执行一个直接循环,那么将它存储为数组或链接列表之间不会有太大的区别。

    为了存储结果,取决于您是如何收集它们的,结构可能会有所不同(但假设Java的通用结构是智能的,则不会)。正如我所说的,我不依赖于Java,但我假设通用链表将保留一个尾指针。在这种情况下,这不会有什么区别。对于底层数组与链表的实现以及如何在字节代码中查找,了解更多的人可能会告诉您使用尾部指针附加到链表还是插入到数组中更快(我猜是数组)。另一方面,您需要知道结果集的大小,或者牺牲一些存储空间,使其与要使用数组时正在迭代的整个集合一样大。

    通过找出哪一个比较最有可能是正确的来优化比较查询,并且先做一个也会有所帮助。例如:如果集合中某个成员开始查询的时间通常为10%,而某个成员结束查询的时间通常为30%,则您需要首先进行结束比较。

        5
  •  0
  •   moonshadow    16 年前

    对于您的特定示例,对集合进行排序会有所帮助,因为您可以对第一个以查询开始的项进行二元剪切,并在到达下一个不需要的项时提前终止;您还可以生成指向集合项的指针表,该表按照第二个子句中每个字符串的相反顺序进行排序。

    一般来说,如果事先知道查询的结构,则可以对集合进行适当的排序(如果有多个子句,则可以为集合生成多个已排序的索引);如果不知道,则无法比线性搜索做得更好。

        6
  •  0
  •   Jon Turner    16 年前

    如果您在列表中填充一次然后进行多次查找(数千次或更多次),那么您可以创建某种查找字典,将以值开头/结尾的值映射到它们的实际值。这将是一个快速查找,但将使用更多的内存。如果你不做那么多的查找或者知道你将至少半频繁地重新填充列表,我将使用cq建议的linq查询。

        7
  •  0
  •   Hallgrim    16 年前

    您可以创建某种索引,它可能会更快。

    我们可以建立这样的索引:

    Dictionary<char, List<ClassFoo>> indexByFirstLetter;
    foreach (var cf in collection) {
      indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
      indexByFirstLetter[cf.bar[0]].Add(cf);
      indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
      indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
    }
    

    然后像这样使用它:

    foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
      if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
        result.Add(cf);
    }
    

    现在,我们可能不需要像您的示例中那样循环访问那么多的classfoo,但是我们必须再次保持索引的最新性。不能保证它更快,但它确实更复杂。

        8
  •  0
  •   kervin    16 年前

    视情况而定。您的所有对象都将被加载到内存中吗?您对可能加载的对象有有限的限制吗?您的查询是否必须考虑尚未加载的对象?

    如果集合变大,我肯定会使用索引。

    实际上,如果集合可以增长到任意大小,并且您不确定是否能够将其全部放入内存中,那么我将研究一个ORM、一个内存中的数据库或另一个嵌入的数据库。我想到了来自devexpress的xpo,用于ORM或sqlite.net,用于内存数据库。

    如果您不想这么做,可以创建一个简单的索引,该索引由映射到类引用的“bar”成员引用组成。

        9
  •  0
  •   Alexander    16 年前

    如果一组可能的条件是固定的并且很小,则可以为列表中的每个元素分配一个位掩码。位掩码的大小是一组条件的大小。当您创建一个元素/将其添加到列表中时,您可以检查它满足的条件,然后在该元素的位掩码中设置相应的位。匹配列表中的元素就像匹配目标位掩码一样简单。更一般的方法是布卢姆过滤器。