Я работаю над реализацией алгоритма, который, учитывая массив четко определенных объектов, представляющих файлы, найденные в папке, должен сравнивать их, чтобы найти дублирующиеся клоны для удаления. Этот алгоритм, когда закончится, должен учитывать любой тип файла, но для упрощения давайте просто поговорим об изображениях для этого вопроса.
TL; DR этого вопроса: какой тип алгоритма / правил может Я реализую, чтобы минимизировать сложность моей большой (O) нотации при сравнении файлов внутри очень большого массива. Я не говорю о сравнении как таковом (я использую комбинацию расстояния Левенштейна / Хэмминга и коэффициента Дайса на основе сравниваемых двух файлов), но фактическое решение о подразделении массива миллионов файлов и применение некоторой логики c за частью «обработки» сравнения.
Когда я говорю, что объекты «хорошо определены», я имел в виду, что у меня уже есть основа информации, которая Я могу получить на быстрое сканирование. Такие вещи, как absolutePath, createDate, size в байтах, extension, а также MD5 га sh, которые содержат все, что я могу использовать в качестве идентификатора, поскольку даже два идентичных файла будут по крайней мере иметь разные даты так что ха sh будет достаточно хорошим. В случае изображений я также получаю pHash для сравнения. Все это приходит до фактического алгоритма, поэтому пока ничего не влияет на производительность.
Проблема начинается, когда у меня очень большой массив со всеми этими объектами (думаю, arr.length > 1000000) и всеми Внезапно идиотостойкие O (n log n) два цикла for просто перестают работать:
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 изображений это заняло более 4 ч. довольно хороший P C. Очевидно, я начал вносить некоторые улучшения, чтобы минимизировать издержки более чем 10000 ^ 2 сравнений Левенштейна. </p>
В произвольном порядке, вот что я сделал:
- Предварительно отсортировал массив так, чтобы файлы с одинаковыми размерами были ближе друг к другу
- Объединение массива в более мелкие куски и сериализованное их выполнение (с таким же алгоритмом)
- Приоритизация известных значений, таких как
fileName и size чтобы исключить явные дубликаты до того, как любой дорогой метод был вызван - Вместо двух точных циклов for внутри друг друга, я строго сравниваю еще не сравненный, удаляя первый элемент A из массива X, сравнивая его с каждым другим элементом B в массиве Y, и после этого добавление 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);
}
Но даже после всего этого заметные улучшения были недостаточно хорошими. Не только это, но и конкретная реализация имеет недостатки как есть. Скажем, у меня есть 2 видео, одно 480P и другое 1080p: каждое свойство будет отличаться; размер, имя (возможно), дата и т. д. c. Поскольку в настоящее время я сортирую по размеру, они будут заканчиваться в разных потоках, а , а не сравниваться напрямую, оставляя дубликат.
Если кто-то может предложить какой-то применимый алгоритм или предложение это может помочь мне повысить производительность, я использую JS ES6 с NodeJs, поэтому любая библиотека рекомендуется, если таковые имеются, пожалуйста, имейте это в виду. Спасибо всем, кто дочитал до конца.