我正在研究一种算法的实现，如果给定一组定义良好的对象表示文件夹中的文件，则应该对它们进行比较，以便找到重复的类似克隆进行删除。这个算法完成后，应该可以考虑任何类型的文件，但为了让事情变得更容易，让我们只讨论这个问题的图像。
TL；这个问题的DR是：当比较一个非常大的数组中的文件时，我可以实现什么类型的算法/规则来最大限度地降低大(O(表示法的复杂性。我不是在谈论比较本身(我使用的是基于被比较的两个文件的Levenstein/Hamming距离和Dice系数的组合(，而是细分一百万个文件数组并在比较的"处理"部分背后应用某种逻辑的实际决定。
当我说物体"定义良好"时，我的意思是我已经有了快速扫描所能获得的信息的基础。像absolutePath、createDate、size(以字节为单位(、extension，还有一个MD5哈希，它带来了我可以用作标识符的所有内容，因为即使是两个相同的文件也至少有不同的日期，所以哈希就足够了。在图像的情况下，我还得到了pHash进行比较。所有这些都出现在实际算法之前，所以还没有影响性能。
当我有一个包含所有这些对象的非常大的数组时(想想arr.length > 1000000(，问题就开始了，突然之间，循环的防白痴O(n log n(2不再切割：
for (var i = 0; i < arr.length; i++) {
var fileBeingCompared = arr[i];
for (var j = 0; j < arr.length; j++) {
var fileToCompare = arr[j];
if (methodThatComparesFiles(fileBeingCompared, fileToCompare)) { // files are similar
// do stuff
}
}
}
这实际上在<10000张图片，在一台相当好的电脑上。显然，我开始做一些改进，以最大限度地减少超过10000^2 Levenstein的比较开销。
没有特别的顺序，以下是我所做的：
- 对数组进行预排序，以便大小相似的文件能够更紧密地放在一起
- 将数组拼接成更小的块，并序列化它们的执行(到目前为止使用相同的算法(
- 在调用任何昂贵的方法之前，对
fileName和size等已知值进行优先级排序，以排除明显的重复 - 我不是将两个精确的for循环放在一起，而是通过从数组X中删除第一个元素A，将其与数组Y上的其他元素B进行比较，然后将A添加到数组Y中，来严格比较尚未比较的循环。这样，我就大大减少了像
a = b和b = a之类的冗余比较的数量。也许这个例子可以更好地启发我的方法：
var arrayX = []; // contains 1000 or so files
var arrayY = []; // starts empty but is filled with the already-compared elements
while (arrayX.length) {
var fileBeingCompared = arrayX.pop();
for (var i = 0; i < arrayY.length; i++) {
var fileToCompare = arrayY[j];
if (methodThatComparesFiles(fileBeingCompared, fileToCompare)) { // files are similar
// do stuff
}
}
arrayY.push(fileBeingCompared);
}
但即便如此，这些明显的改善还远远不够好。不仅如此，具体的实现也有缺陷。假设我有两个视频，一个是480P，另一个是1080p：每个属性都会不同；大小、名称(可能(、日期等。由于我目前正在按大小排序，它们最终会出现在不同的线程中，而不是被直接比较，留下重复。
如果有人能提出一些适用的算法或建议来帮助我获得性能，我将JS ES6与NodeJ一起使用，所以推荐的任何库，如果有的话，请记住这一点。感谢那些一直读到最后的人。
如果你的相似性计算没有什么结构，那么你就必须测试每一对。如果它(或它的某些变换(至少服从三角形不等式，你可以尝试建立某种结构来回答精确或近似的最近邻居搜索，并为每个点找到它的最近邻居。一种只需要距离计算的最近邻数据结构是https://en.wikipedia.org/wiki/Cover_tree，但除非你的点大多位于低维子空间附近，否则你可能看不到什么加速。