如何高效匹配大型集合

我有大量的foo类型的对象集合。 foo类型的每个对象都有100个属性（所有字符串）加上一个id。 bar类型的对象也具有这100个属性。如何高效匹配大型集合

我想从集合中找到类型为foo的匹配对象，其中所有这些属性都与bar匹配。

除了暴力方法，有没有一个优雅的算法，我们可以计算foo对象的签名一次，并为bar对象执行相同的操作并更有效地匹配？

foo s是在成千上万和bar是在百万。

来源

2011-10-25 Barka

[散列]（http://en.wikipedia.org/wiki/Hash_function）？ – brc

什么是上下文？ –

达斯维达在那里有一个点......我从来没有想过我会站在黑暗的一面！

我去了什么，我认为是行业的最佳工具：

嵌入式数据库：Google's LevelDB - 它比大多数数据库解决方案在那里快。
散列函数：Google's CityHash - 它是快速它提供了优秀的哈希！
JSON Serialization

嵌入式数据库

使用嵌入式数据库的目标是，你会得到的性能将优于大多数的数据库解决方案，你很可能会遇到。我们可以谈论LevelDB有多快，但plenty of other people have already talked about it quite a bit，所以我不会浪费时间。嵌入式数据库允许您存储键/值对，并快速在数据库中找到它们。

哈希函数

一个好的哈希函数将会很快，它会提供非重复散列的良好分布。 CityHash速度非常快，并且发行速度非常快，但同样如此：我不会浪费时间，因为lot of other people have already talked about the performance of CityHash。您可以使用散列函数来散列对象，然后使用唯一键在数据库中查找它们。

JSON序列化

JSON序列化是什么，我上面显示的对立面：它是非常缓慢的，它会降低任何性能增益你CityHash实现，但它给你一个很简单的方法来凑整个对象。您将对象序列化为JSON字符串，然后使用CityHash对字符串进行散列。尽管事实上你已经失去了CityHash的性能收益，因为你花了很多时间将对象序列化为JSON，但你仍然可以获得具有非常好的散列函数的好处。

的结论

您可以存储数十亿条记录的性LevelDB，你将能够为其提供哈希快速检索你要找的只是精确值。
为了生成密钥，可以使用JSON序列化和CityHash对JSON字符串进行哈希处理。
使用键找到匹配的对象！

享受！

来源

2011-10-25 05:22:50 Kiril

如果你有所有匹配的属性。这意味着它们实际上是相同的对象。那是对的吗？

在任何情况下，您都希望使用具有良好散列算法的Map/Dictionary/Table来查找匹配对象。

无论您使用哪种语言，您都应该重写gethashcode并等于实现它的方法。

如果你有一个很好的散列算法，你的访问时间将是O（1）。否则它可以达到O（n）。

根据您的内存限制，您想要在地图中存储foos，存储酒吧可能需要大量空间，您可能没有。

来源

2011-10-25 03:46:48 DarthVader

数百万条目的非平凡大小..我更希望他们被存储在数据库中。我可能会创建一个我索引列并使用现有对象的散列填充它。这会导致O（logn）运行时查找，但具有实际的内存使用情况。 – bdares

这就是我所说的，他/她会想要在Dictionary中存储数千个。 – DarthVader

地图，字典和表格是可以在用户应用程序（通常在RAM）或其他地方实现的数据结构，但是我想指出，使用DBMS的实现来说明大尺寸是最有意义的。 – bdares

哈希是非常好的，简单的实现。但我想建议你该算法：

地图的100个字符串属性，以一个大的字符串（例如，使用固定长度为每个属性串联）应此对象的唯一标识。所以我们第一组有1000个字符串，第二组有1毫升字符串。
如果第一组包含它，则问题将减少以找出第二组中的每个字符串。
制作trie第一组数据结构
检查trie中字符串S是否为O（| S |）的共同性。 | S | - 长度为S.

所以...算法的共同性是-o（Sum（| Ai |）+ Sum（| Bi |））= O（max（Sum（| Ai |），Sum |毕|））= O（总和（|毕|））为您的问题艾 - 对于第一套串唯一的ID，碧 - 串唯一的ID为第二组

UPDATE：。 特里需要O（ Sum（| Ai |）* | Alphabet |）空间最差

来源

2011-10-25 06:24:15

尝试不太友善。他可以有一个非常大的特洛伊木马，可能会消耗大量的内存，哈希码，你代表一个单一的数字实体。 – DarthVader

@DarthVader，一般 - 是的。但有时候我们有小字母或小首字母，但很多查询，比如“如果字符串包含在第一组”。并且字符串S的搜索共谋是**明确** O（| S |）。 –

如何高效匹配大型集合

回答

相关问题