使用有限内存检查字符串冲突的运行时高效算法
Runtime Efficient Algorithm to check string collision with limited memory
我有一个很大但有限的字符串集，这些字符串中的任何两个不太可能相同，但这正是我想要检查的。
所有字符串的长度大约相同 +/- 1 个字符。
让我们假设作为一个例子（但数字可能会改变），我有一组 300 亿个字符串，每个大约 30 个字符长。在一种天真的方法中，我会把它们全部塞进一个散列中并检查冲突。这实际上是 O(n) 运行时间。
由于内存是限制因素，我无法将所有字符串都塞入内存，因此我必须对数据集进行分区。假设我可以在内存中填充 1 亿个字符串，并针对这 1 亿个字符串检查另一个字符串基本上是 O(1) 运行时间。
我的高效算法（在运行时方面）会是什么样子？
如果你有 N 个字符串并且你可以将 k 保存在内存中，那么你应该有 N/k 个分区并且每个字符串应该只被散列一次但比较 N/k - 1 次。因此，复杂度应为 O(N^2 / k).
我有一个很大但有限的字符串集，这些字符串中的任何两个不太可能相同，但这正是我想要检查的。 所有字符串的长度大约相同 +/- 1 个字符。
让我们假设作为一个例子（但数字可能会改变），我有一组 300 亿个字符串，每个大约 30 个字符长。在一种天真的方法中，我会把它们全部塞进一个散列中并检查冲突。这实际上是 O(n) 运行时间。
由于内存是限制因素，我无法将所有字符串都塞入内存，因此我必须对数据集进行分区。假设我可以在内存中填充 1 亿个字符串，并针对这 1 亿个字符串检查另一个字符串基本上是 O(1) 运行时间。
我的高效算法（在运行时方面）会是什么样子？
如果你有 N 个字符串并且你可以将 k 保存在内存中，那么你应该有 N/k 个分区并且每个字符串应该只被散列一次但比较 N/k - 1 次。因此，复杂度应为 O(N^2 / k).