Блог

Главная - Вопросы по программированию - Поиск похожих значений в нескольких массивах объектов

Поиск похожих значений в нескольких массивах объектов

#javascript #node.js #arrays #performance #logic

Вопрос:

Данные:

 array1 = [{"location": "The Green Lion", "postcode": "E1 6QE"}, {"location": "Diners Inn", "postcode": "E6 5FD"}]
array2 = [{"location": "Green Lion", "postcode": "E1 6QE"}, {"location": "Diner's Inn", "postcode": "E6 5FD"}]
array3 = [{"location": "The Green Lion", "postcode": "E1 6QE"}, {"location": "Diner Inn", "postcode": "E6 5FD"}]
//array1 size - 350 | array2 size - 544 | array3 size - 88

Я использую функцию нечеткого сравнения, чтобы найти похожие элементы в массиве. Проблема, с которой я сталкиваюсь, заключается в том, что мой текущий способ достижения этой цели включает объединение 3 массивов в 1 и повторное их повторение, а затем нечеткое сравнение location .

 combined.forEach(function (x) {
        combined.forEach(function (y) {
            if (fuzz.token_sort_ratio(x.location, y.location) > 80) {
                //Logic 
            }
        });
    });

Есть ли более эффективный способ добиться этого вместо вложенного цикла for? Объединенный размер массива составляет 958, что означает, что выполняется 917 764 итерации, это не кажется эффективным способом достижения этой цели, но поскольку значение location не всегда гарантированно будет одинаковым, я не могу использовать .find() функцию (или могу?).

Ответ №1:

Я бы рекомендовал создать карту местоположений и сохранить результаты в дереве квадрата. Quadtree поддерживается JavaScript — см.

https://github.com/timohausmann/quadtree-js

Я успешно использовал quadtree в своей практике (реализовано на C ). Для больших наборов данных это оказалось по крайней мере в 10 раз быстрее, чем квадратичный алгоритм.

Метки: