@WebNerd
It's time to hunt

Какой алгоритм быстрее и почему?

Есть такая задача на сайте codewars:
Create a function that returns the sum of the two lowest positive numbers given an array of minimum 4 positive integers. No floats or non-positive integers will be passed.

For example, when an array is passed like [19, 5, 42, 2, 77], the output should be 7.


Смысл здесь в том, что нам нужно создать функцию, которая выведет сумму двух самых маленьких чисел в массиве.

Так как я только новичок в кодинге, я написал следующий код:

function sumTwoSmallestNumbers(numbers) {  
  let arr = [numbers[0], numbers[1]]; 

  for (let i = 2; i < numbers.length; i++) {
    if (numbers[i] < arr[0] && arr[0] > arr[1]) {
      arr = [numbers[i], arr[1]]
    } else if (numbers[i] < arr[1]) {
      arr = [arr[0], numbers[i]];
    }
  }

    return arr[0] + arr[1];
}


Здесь я пытался создать сложность алгоритма O(n), ведь не знаешь сколько элементов может быть в массиве. Когда я решил, мне показали решения других людей. Многие проголосовали за лаконичный и куда более понятный код:

function sumTwoSmallestNumbers(numbers){  
  numbers = numbers.sort(function(a, b){return a - b; });
  return numbers[0] + numbers[1];
};


И в целом, мне понятно, почему такой вид решения в топе... Однако, меня смутило то, что здесь используется метод sort, который перебирает массив. Представим, что у нас 10000000 элементов, разве будет такой код хорошим? Или я чего-то не понимаю в встроенном методе sort? И если последняя функция действительно долгая, то есть ли решение этой задачи самым оптимальным путем?
  • Вопрос задан
  • 233 просмотра
Решения вопроса 2
sergiks
@sergiks Куратор тега JavaScript
♬♬
Ваш алгоритм хорош.
Лучше «лаконичного» тем, что не занимается сортировкой там, где это не нужно.
Представьте массив [1, 2, 1000, 1001,...] далее все 100500 элементов больше 1000.
Совсем незачем сортировать весь этот максимальный хвост между собой, когда интересуют только минимальные значения.

Вот разбор проблемы поиска двух наименьших значений в массиве. Там ешё предлагается вариант в 2 прохода по массиву: найти наименьшее, и вторым проходом найти наименьшее, большее найденного. Тоже O(n), но можно и за 1 проход, как вы и предложили.
вариант

Без пересоздания массива. Держать две переменные, значения, которых по возрастанию. Максимум две проверки условий на итерации.
const sumTwoSmallestNumbers = arr => {
  let a = arr[0];
  let b = arr[1];
  if (a > b) {
    [a, b] = [b, a];
  }

  for (let i = 2; i < arr.length; i++) {
    const v = arr[i];
    if (v < a) {
      b = a;
      a = v;
    } else if (v < b) {
      b = v;
    }
  }

  return a + b;
};

sumTwoSmallestNumbers([55, 44, 1, 99, 2]); // 3
Ответ написан
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Ваш алгоритм быстрее. Но в задаче часто бывает сработает не только самый быстрый код. Например, если там чисел всего 10 в массиве, то вы никакими измерениями разницу между сортировкой и вашим решением не намеряете (если только не запустите оба решения миллионы раз. Но это же уже другая задача. Ваша задача - найти минимальные 2 числа в одном массиве и ограничение по времени, если и есть, будет считаться по одному массиву)

Поэтому иногда имеет смысл написать не самый быстрый алгоритм, но зато гораздо более простой. Если он проходит, то зачем кодить больше?

В вашем алгоритме еще проблема, что не очевидно, почему он работает. Надо аккуратно рассматреть все 6 случев расположения arr[0], arr[1] и numbers[i] и убедиться, что инваринат "2 минмальных числа лежат в arr" поддерживается. Тут легко накосячить, перепутать 0 и 1, не там проверку поставить и все.

Обычно, когда такой алгортм реализуют, поддерживают более строгий инвариант "минимальное число в arr[0], следующее минимальное число в arr[1]". Тогда проверки чуть чуть упрощаются и за логикой решения следить проще.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
mayton2019
@mayton2019
Bigdata Engineer
Тебе не нужно сортировать все 10 000 000 элементов чтоб взять два минимальных. Достаточно одного прохода
с отслеживанием двух наименьших {m1,m2} . И кейсов сравнений будет немного. Новый элемент больше - игнорируем. Новый элемент меньше обоих - вставляем в голову. Новый между ними - вставляем в центр.
Ответ написан
@res2001
Developer, ex-admin
Ваш алгоритм быстрее. Но не лаконичнее. Это нормальное явление. Регулярно скорость достигается усложнением алгоритма. Но если раскрыть тему sort, то второй алгоритм уже не покажется таким уж простым.
Еще ваш алгоритм не портит входные данные - часто это бывает важно.
Ответ написан
Fragster
@Fragster
помогло? отметь решением!
В зависимости от условий (уникальность, сортировка выходного и прочее) можно упростить до подобного: https://codepen.io/FragsterAt/pen/vYaBNam
предложенный вариант без sort действительно быстрее, но менее читаем. Реальная обоснованность зависит от условий. Может быть там до 100 элементов. Зато сразу понятно, что происходит (при рефакторинге).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы