有效地在文件中构建一组唯一行，而不在集合中存储实际行
Building a set of unique lines in a file efficiently, without storing actual lines in the set
最近我正在尝试解决以下问题：
我有一个非常大的文件，包含很长的行，我需要找到并打印出其中所有不同的行。
我不想使用 map 或 set 来存储实际的行，因为文件很大而且行很长，所以这会导致 O(N) space 的复杂度常量（其中 N 是行数）。最好，我宁愿生成一个集合来存储指向文件中唯一行的指针。显然，这种指针的大小（我相信在 64 位机器上是 8 个字节）通常比内存中的行大小（我相信每个字符 1 个字节）小得多。虽然 space 复杂度仍然是 O(N)，但现在常量好多了。使用此实现，文件永远不需要完全加载到内存中。
现在，假设我将逐行检查文件，检查唯一性。要查看它是否已经在集合中，我可以比较到目前为止集合指向的所有行，逐个字符进行比较。这给出了 O(N^2*L) 复杂度，其中 L 是一行的平均长度。当不关心在集合中存储完整行时，可以实现 O(N*L) 复杂度，这要归功于散列。现在，当改用一组指针（以减少 space 要求）时，我怎样才能做到这一点？有没有一个巧妙的方法来做到这一点？我唯一能想到的就是这种方法：
- 散列句子。将散列值存储到映射（或者实际上：unordered_multimap 无序以获得散列映射样式，在 'false matches' 的情况下可以插入多个双键）。
- 对于每个新句子：检查它的哈希值是否已经在映射中。如果没有，请添加它。如果是，逐个字符比较完整的句子（新句子和无序映射中具有相同散列的句子），确保没有'false match'。如果是'false match'，还是加上
这是正确的方法吗？或者有更好的方法吗？欢迎所有建议！
我可以使用一些聪明的 'comparison object'（或类似的东西，我对此还不是很了解）在每个 unordered_map::find( ) 电话？
你的解决方案对我来说很好，因为你存储的是 O(unique lines) 哈希而不是 N，所以这是一个下限。
既然你逐行扫描文件，你不妨对文件进行排序。现在重复的行将是连续的，您只需要检查前一行的散列。此方法使用 O(1) space 但您必须先对文件进行排序。
如果文件中没有您可以利用的特殊结构，那么一定要对行进行哈希处理。这将比实际将文件中的每一行与其他行进行比较要快几个数量级。
如果您的实际实施仍然太慢，您可以例如将散列限制在每行的第一部分。这将产生更多的误报，但假设大多数行在前几个词中已经偏离，它将显着加快文件处理速度（特别是，如果你是 I/O-bound）。
正如@saadtaame 的回答所说，您的 space 实际上是 O(unique lines) - 根据您的用例，这可能是可以接受的，也可能不是。
虽然散列当然有其优点，但可以想象它会遇到很多冲突问题 - 如果你不能有误报，那么它是不行的，除非你实际上保留行的内容以供检查.
您描述的解决方案是维护一个基于散列的集合。这显然是最直接的事情，是的，它需要在内存中维护所有唯一行。不过，这可能是也可能不是问题。该解决方案也是最容易实现的——您正在尝试做的正是（基于哈希的）集合的任何实现都会做的事情。您可以只使用 std::unordered_set，并将每一行添加到集合中。
由于我们是在抛出想法，您也可以使用 trie 作为集合的替代品。您可能会节省一些 space，但它仍然是 O（唯一行）。
最近我正在尝试解决以下问题：
我有一个非常大的文件，包含很长的行，我需要找到并打印出其中所有不同的行。
我不想使用 map 或 set 来存储实际的行，因为文件很大而且行很长，所以这会导致 O(N) space 的复杂度常量（其中 N 是行数）。最好，我宁愿生成一个集合来存储指向文件中唯一行的指针。显然，这种指针的大小（我相信在 64 位机器上是 8 个字节）通常比内存中的行大小（我相信每个字符 1 个字节）小得多。虽然 space 复杂度仍然是 O(N)，但现在常量好多了。使用此实现，文件永远不需要完全加载到内存中。
现在，假设我将逐行检查文件，检查唯一性。要查看它是否已经在集合中，我可以比较到目前为止集合指向的所有行，逐个字符进行比较。这给出了 O(N^2*L) 复杂度，其中 L 是一行的平均长度。当不关心在集合中存储完整行时，可以实现 O(N*L) 复杂度，这要归功于散列。现在，当改用一组指针（以减少 space 要求）时，我怎样才能做到这一点？有没有一个巧妙的方法来做到这一点？我唯一能想到的就是这种方法：
- 散列句子。将散列值存储到映射（或者实际上：unordered_multimap 无序以获得散列映射样式，在 'false matches' 的情况下可以插入多个双键）。
- 对于每个新句子：检查它的哈希值是否已经在映射中。如果没有，请添加它。如果是，逐个字符比较完整的句子（新句子和无序映射中具有相同散列的句子），确保没有'false match'。如果是'false match'，还是加上
这是正确的方法吗？或者有更好的方法吗？欢迎所有建议！
我可以使用一些聪明的 'comparison object'（或类似的东西，我对此还不是很了解）在每个 unordered_map::find( ) 电话？
你的解决方案对我来说很好，因为你存储的是 O(unique lines) 哈希而不是 N，所以这是一个下限。
既然你逐行扫描文件，你不妨对文件进行排序。现在重复的行将是连续的，您只需要检查前一行的散列。此方法使用 O(1) space 但您必须先对文件进行排序。
如果文件中没有您可以利用的特殊结构，那么一定要对行进行哈希处理。这将比实际将文件中的每一行与其他行进行比较要快几个数量级。
如果您的实际实施仍然太慢，您可以例如将散列限制在每行的第一部分。这将产生更多的误报，但假设大多数行在前几个词中已经偏离，它将显着加快文件处理速度（特别是，如果你是 I/O-bound）。
正如@saadtaame 的回答所说，您的 space 实际上是 O(unique lines) - 根据您的用例，这可能是可以接受的，也可能不是。
虽然散列当然有其优点，但可以想象它会遇到很多冲突问题 - 如果你不能有误报，那么它是不行的，除非你实际上保留行的内容以供检查.
您描述的解决方案是维护一个基于散列的集合。这显然是最直接的事情，是的，它需要在内存中维护所有唯一行。不过，这可能是也可能不是问题。该解决方案也是最容易实现的——您正在尝试做的正是（基于哈希的）集合的任何实现都会做的事情。您可以只使用 std::unordered_set，并将每一行添加到集合中。
由于我们是在抛出想法，您也可以使用 trie 作为集合的替代品。您可能会节省一些 space，但它仍然是 O（唯一行）。