Проверить равенство между N> 2 массивами с максимальной производительностью? - PullRequest
Новая
       9

Проверить равенство между N> 2 массивами с максимальной производительностью?

0 голосов
/ 03 октября 2018

Я хотел бы проверить, все ли массивы n содержат одинаковые целые числа в JavaScript?Какой самый эффективный способ?

Ответы [ 2 ]

0 голосов
/ 03 октября 2018

В этом решении не используется sort, что делает алгоритм O (n²), где n - это число и длина массивов.Он имеет дополнительное преимущество: он не изменяет массивы, а также позволяет передавать массивы, содержащие любые типы, а не только числа.Он работает, вычисляя пакет частот для каждого элемента массива, а затем оценивает, все ли они содержат одинаковые данные.Функции toBag и bagsEqual являются O (n).Это делает основной алгоритм arraysSame O (n²).Использование sort вместо частотных пакетов сделало бы решение O (n²log (n)), что не так выгодно. 

function arraysSame(...arrays) {
  if(arrays.length < 2) return true;

  let bag1 = toBag(arrays[0]);
  for(let i = 1; i < arrays.length; i++) {
    const bag2 = toBag(arrays[i]);
    if(!bagsEqual(bag1, bag2)) return false;
  }

  return true;
}

function bagsEqual(bag1, bag2) {
  if(bag1.size != bag2.size) return false;

  for(const [key, value] of bag1) {
    if(!bag2.has(key)) return false;
    if(value != bag2.get(key)) return false;
  }

  return true;
}

function toBag(array) {
  const bag = new Map();

  for(const val of array) {
    const count = bag.get(val) || 0;
    bag.set(val, count + 1);
  }

  return bag;
}
0 голосов
/ 03 октября 2018

если у вас есть только числа в массивах - используйте некоторые вариации базового алгоритма CRC - сложность составляет O (n) на массив, так что это будет максимально быстро https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Аналогичная идея, рассчитатьсумма (массив) и произведение (массив), вы можете вычислить оба значения с помощью O (n).Например: 

   1, 5, 6, 7 ,8      sum=27, prod=1680
   7, 8, 1, 5, 6      sum=27, prod=1680

, но 

   3, 8, 5, 5, 6      sum=27, prod=3600

ПРИМЕЧАНИЕ особый случай равен 0!Так как это приведет к аннулированию продукта, следует использовать все значения + 1.

NOTE2 Имейте в виду, что идея алгоритмов CRC состоит в том, чтобы использовать одну переменную байта или двойного слова для итогового значения ипеременная будет в конечном итоге переполнена.

Например, в случае байта: 250 + 10 = 5, поскольку байт переполняется на 255. Однако это нормально, поскольку оба массива переполняются, и вероятность ложного отчета очень мала.Я верю, что если мы можем изо всех сил стараться, мы можем доказать это математически, это нормально.

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

ПРИМЕЧАНИЕ3: Просто понял, что вы используете JS, а JS немного запутан с большими числами и не переполняется арифметическимиопераций.

Однако он переполняется логическими операторами, а алгоритм CRC использует xor, так что вы хороши.Это алгоритм CRC: https://en.wikipedia.org/wiki/Cyclic_redundancy_check

И это реализация с открытым исходным кодом: https://github.com/emn178/js-crc/blob/master/src/crc.js На prima vista, кажется, следует алгоритм, однако я не уверен, насколько оно качественное, поэтомуваша должная осмотрительность!

...