расчет для каждого элемента массива

Question

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

У меня есть массив массивов:

var all = [[1,2], [3,4], [4,5]]; 

У меня также есть объект, который имеет текущее минимальное расстояние и текущий массив:

var cur_min = {'current_min': 10, 'point': [9,10]}; 

Я хочу найти минимальное расстояние между всеми точки в моем массиве, и если это расстояние меньше текущего_min в моей переменной cur_min, оно будет обновляться. Я пришел со следующим:

function find_new_min(current, arr) { 
    return _.transform(arr, function(result, a) { 
       _.forEach(arr, function(b) { 
        if (!_.isEqual(a,b)) { 
         var d = get_distance(a,b); 
         if (d<result.current_min) { 
          result.current_min = d; 
          result.point = a; 
         } 
        } 
       }); 
      }, _.clone(current)); 
} 

Я ожидал 6 различных пар массивов, так как получение расстояния между точкой и сам по себе является 0.

Я не могу себе представить, зацикливание за тот же массив в два раза является эффективный способ решения этой проблемы. Я попытался переписать эту функцию, используя различные функции lodash, такие как _.forEach и _.reduce, но я не могу найти способ не зацикливать дважды над одним и тем же массивом. Есть ли более быстрый способ решить эту проблему?

пример вывода для приведенного выше кода:

{ current_min: 1.222450611061632, loc: [ 1, 2 ] } 

Answer 1

Ваша проблема одна из самых старых: как наиболее эффективно сортировать массив значений, основанный на некоторой функциональной клавиши. Тем не менее, вы также хотите записать кратчайшее расстояние и для этого вам нужно сравнить с каждым другим значением. Из-за этого вы не можете эффективно сортировать, вам нужно пробежать весь массив array.length раз.

Учитывая, что вы ожидаете всего шесть пар очков, это похоже на серьезный случай premature optimization.

Удобство чтения, к сожалению, lodash не предлагает функциональности для создания декартова продукта, который вы могли бы затем _.sortBy, а также не предлагает функцию сортировки, которая позволяет сравнивать вручную влево и вправо и изменять значения. Я думаю, что ваша текущая реализация в настоящее время так же хороша, как и с lodash.