Паровые комбинации массива в Javascript

Я написал функцию Javascript, которая, похоже, успешно сгенерирует уникальные попарные комбинации списка:

function pairwise(list) {
  var pairs = [];
  list
    .slice(0, list.length - 1)
    .forEach(function (first, n) {
      var tail = list.slice(n + 1, list.length);
      tail.forEach(function (item) {
        pairs.push([first, item])
      });
    })
  return pairs;
}

pairwise('abcd'.split(''))
// [["a","b"],["a","c"],["a","d"],["b","c"],["b","d"],["c","d"]]

Я проверил его, используя комбинаторную формулу:

$$ комбинаций = \ frac {n (n-1)} {2} $$

var alpha = [ "a", "b", "c", "d", "e", "f", "h", "i", "j" ];

for(var n=1;n<7;n++){ 
  console.log(
    n,                                 // number of items
    pairwise(alpha.slice(0,n)).length, // how many pairs from function?
    n*(n-1)/2                          // double check with formula above
  ); 
} 

// 1 0 0
// 2 1 1
// 3 3 3
// 4 6 6
// 5 10 10
// 6 15 15

Что выглядит правильно: есть 6 способов выбрать пары из 4 элементов и т. д.

Это работает, но мне трудно читать, и я не уверен, как сделать его более читаемым. Я бы приветствовал предложения.

11 голосов | спросил pat 4 Jpm1000000pmSun, 04 Jan 2015 23:39:24 +030015 2015, 23:39:24

3 ответа


11

Ваше решение отлично работает, и оно довольно эффективно. Вы используете петли и мутацию, которые бывают быстрыми, но также не очень читаемыми. Этот алгоритм может быть выражен более функционально с точки зрения рекурсии и отображения, что может сделать его несколько читабельным, хотя и немного менее эффективным.

 function pairwise(list) {
  if (list.length < 2) { return []; }
  var first = list[0],
      rest  = list.slice(1),
      pairs = rest.map(function (x) { return [first, x]; });
  return pairs.concat(pairwise(rest));
}

var result = pairwise(['a', 'b', 'c', 'd', 'e']);
console.log(result);
document.getElementById('output').innerHTML = JSON.stringify(result);
 <pre id="output"></pre>

Кроме того, если вы хотите использовать внешнюю библиотеку, это эквивалентное решение, использующее Lo-Dash. Это идентичный алгоритм, но он может помочь с читабельностью использовать библиотеку, предназначенную для функционального программирования.

 function pairwise(list) {
  if (list.length < 2) { return []; }
  var first = _.first(list),
      rest  = _.rest(list),
      pairs = _.map(rest, function (x) { return [first, x]; });
  return _.flatten([pairs, pairwise(rest)], true);
}

var result = pairwise(['a', 'b', 'c', 'd', 'e']);
console.log(result);
document.getElementById('output').innerHTML = JSON.stringify(result);
 <script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/2.4.1/lodash.min.js"></script>

<pre id="output"></pre>
ответил Alexis King 5 Jam1000000amMon, 05 Jan 2015 00:45:37 +030015 2015, 00:45:37
14

Сочетание сочетаний, подобных этому, является очень распространенным явлением на любом языке. Существует очень «идиоматический» способ выполнить этот тип операции:

for (int i = 0; i < length; i++) {
    for (int j = i + 1; j < length; j++) {
        // do something with pair (i,j)
    }
}

Вы увидите и узнаете этот шаблон где угодно.

Поскольку этот шаблон настолько узнаваем, я предпочитаю его видеть, а не нарезать и нарезать ваш код.

Кроме того, поскольку формула для количества итераций настолько доступна, имеет смысл предварительно настроить выходной массив, который вы используете. Предварительная калибровка выходного массива приведет к существенной разнице в производительности.

Кроме того, хотя здесь используется «классический» цикл, производительность будет прекрасной. Другие системы, требующие срезов или карт подмножеств списка, потребуют дополнительной работы, которая, несмотря на «идиоматику», не обязательно будет быстрее:

 function pairwise(list) {

    var pairs = new Array((list.length * (list.length - 1)) / 2),
        pos = 0;

    for (var i = 0; i < list.length; i++) {
        for (var j = i + 1; j < list.length; j++) {
            pairs[pos++] = [list[i], list[j]];
        }
    }
    return pairs;
}

var result = pairwise(['a', 'b', 'c', 'd', 'e']);
document.getElementById('output').innerHTML = JSON.stringify(result);  
 <pre id="output"></pre>
ответил rolfl 5 Jam1000000amMon, 05 Jan 2015 01:13:54 +030015 2015, 01:13:54
1

Спасибо за оба очень интересных и содержательных ответа ниже, я многому научился с вашей помощью.

Я пошел с рекурсивным решением, так как я так сильно подчеркнул удобочитаемость в вопросе. Я нахожу ответ Алексиса Кинга удивительно ясным:

function pairwise(list) {
  if (list.length < 2) { return []; }
  var first = list[0],
      rest  = list.slice(1),
      pairs = rest.map(function (x) { return [first, x]; });
  return pairs.concat(pairwise(rest));
}

(Лично я считаю, что это гораздо более читаемый, чем вариант lodash /underscore.)

Тем не менее, в производстве я, вероятно, использовал бы решение rolfl, учитывая очень убедительное сравнение производительности. Я стараюсь избегать циклов, но не потому, что думаю, что они плохие, а потому, что мне очень трудно держать индексы прямо в голове.

Одна заметка по вопросу о предварительном распределении массива: я не уверен, что увеличивает скорость. В jsperf, добавленном rolfl, метод for-loop был самым быстрым, но я добавил еще один тест без предварительного использования, и он был еще быстрее: http://jsperf.com/pairwise/2

Takehomes для меня:

  • для циклов может быть не так хорошо, как функциональные подходы, но они быстры.
  • преимущества скорости при превалировании массива не обязательно очевидны.
  • рекурсия красивая, но медленная
  • читаемость сравнима с опытом (я уверен, что пример for loop гораздо читабельнее для более опытных программистов, чем для меня).
ответил rolfl 5 Jam1000000amMon, 05 Jan 2015 01:13:54 +030015 2015, 01:13:54

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132