找到两个相同的文件行

我在亚马逊采访中被问到这个问题。找到两个相同的文件行

你有一个文件有许多行，但其中两行是相同的。找到这两条线。我给出了在N^2时间内运行的明显答案。然后我想出了一个使用哈希表的答案，但他们不喜欢那个答案，要么是因为他们说如果文件是千兆字节就不行。我想出的另一个答案是将哈希结果存储在内存中，创建一个与哈希值名称相同的文件，并将具有相同哈希值的行存储在文件中。要么他们不明白我的解决方案，或者他们不喜欢它。

有什么想法？

谢谢

来源

2012-12-06 John Smith

对于Linux，很容易'sort | uniq -c | grep'^ 2'' –

好吧，让我看看其他的解决方案，但是不会将这些文件sl into到内存中吗？ –

@JohnSmith：当数据不适合内存时，GNU'sort'知道如何进行外部排序（http://vkundeti.blogspot.co.uk/2008/03/tech-algorithmic-details-of-unix -sort.html）。 –

我能想到的解决方案的两个基本类别的这个问题：

概率的内存解决方案。您可以尝试通过在主内存中存储文件行的摘要来解决此问题。然后，您可以在主内存中执行计算以识别可能的重复项，然后通过回顾磁盘检查每个可能的重复项。这些解决方案可能是最好的，因为它们具有较低的内存使用率，较高的效率和较小的磁盘访问。此类别的解决方案包括：
1. 计算文件每一行的散列，然后存储散列。任何具有散列冲突的行代表可能发生碰撞的一对可能的行，并且可以探索这些行。
2. 使用Bloom Filter存储文件的所有行，然后只检查在Bloom Filter中发生冲突的对。这实质上是（1）的变体，它更节省空间。
确定性磁盘上解决方案。您可以尝试使用磁盘上的整个数据集进行计算，将主内存用作临时临时空间。这可以让你得到确切的答案，而不必将整个文件保存在内存中，但可能会更慢，除非你稍后进行一些处理并可以从数据重构中受益。此类别中的解决方案包括
1. 使用外部排序算法（外部快速排序，外部基数排序等）的文件进行排序，然后线性搜索它用于一对重复的元件。
2. 构建一个像B树一样的磁盘数据结构来存放所有的字符串，然后查询B树。这需要很多预处理时间，但是使得文件的未来操作速度更快。
3. 将所有内容放入数据库并查询数据库。

希望这有助于！

来源

2012-12-06 21:40:49 templatetypedef

外部排序似乎是最直接的解决方案。一种优化是当你排序时，你可以确定重复项，并合并块，因此可能不得不对整个文件进行排序。 –

我会把这个标记为正确的答案，因为它有很多正确的答案，我在那里学到了一些新东西，尤其是外部排序和Bloom Filters。 –

通过行和计算每一行的长度。你会得到类似的结果：

0: 4 
1: 6 
2: 10 
3: 4 
....

只比较具有相同长度的thoose行。使用这样的索引可以进一步优化（例如，不是将所有内容都存储在平面数组中，而是存储在某种树中，或者其他任何内容中）。

顺便说一下，由于性能原因，您对文件的第二个想法可能会被拒绝。在硬盘上频繁使用随机IO通常是个不好的主意：尽量在内存中存储。

来源

2012-12-06 21:34:06

我认为这是一个优雅的解决方案，但他们可能会抱怨说你不得不使用额外的内存。当然，如果文件有许多相同大小的行，则会遇到问题。 –

您可以使用Bloom过滤器：

http://en.wikipedia.org/wiki/Bloom_filter

然后你就可以检测（用几个假阳性）被重复的线，然后存储在内存中，然后经过文件再次。

两次通过该文件，很少的内存使用量，美丽

来源

2012-12-06 21:35:03 tjltjl

第二遍不一定是顺序的不是吗？如果我们存储每行的位置以及我相信的散列，就可以用一堆fseek（）调用完成。 –

不，重点在于，如果您存储位置，则存储的数量比Bloom过滤器存储的每个条目的位数要多。 – tjltjl

我明白了，我误解了布卢姆过滤器。谢谢！ –

找到两个相同的文件行

回答

相关问题