0

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

Вроде все работает, но я задумался о скорости т.к. такой метод должен быть весьма затратный и решил проверить его на jsperf. К моему удивлению тесты показали что мой метод выигрывает у метода, который я нашел в jquery (сначала отсортировать массив, а потом удалять все повторения, проходясь по всему массиву).

Но мне кажется что jsperf где то ошибается и по этому хочу поинтересоваться у более опытных коллег почему получаются такие странные результаты:

http://jsperf.com/unique-test

2 ответа 2

3

@MrFranke, у Вас массив

var arr = [2,3,1,3,4,2,7,92,4];

очень маленький.

По сути, когда Вы ищете дубликат в массиве, Вы делаете простую сорировку (с квадратичной сложностью). Широкоизвестно, что для маленьких (десятки элементов) массивов такой вид сортировки быстрее, чем любая "серьезная" (quicksort, mergesort (все виды, включая timsort) и т.п.) сортировка (из-за простоты алгоритма во внутреннем цикле сорировки исполняется мало команд).

Более того, во всех серьезных реализациях подобных сортровок в определенный момент (когда нужно отсортировать очередной небольшой отрезок данных) происходит переключение на квадратичную (Д. Кнут советует используют сортировку вставками) сортировку. Но в любом случае, обычно перед этим приходится совершать "массу телодвижений", которых в Вашем специфическом случае, естественно, нет.

Вот, собственно, и объяснение наблюдаемого эффекта. Вы видите, что O(n * n) < O(n * log n)

3
  • Большое спасибо за объяснение! Может быть вы тогда подскажите как лучше всего организовать удаление одинаковых элементов в массиве без его сортировки? Т.е. что бы элементы остались на своих первоначальных местах.
    – MrFranke
    16 дек 2013 в 14:27
  • В смысле, что из arr = [2,3,1,3,4,2,7,92,4]; получается arr2 = [2,3,1,4,7,92]; так? На С int j = 0, k; arr2[j++] = arr[0]; for (int i = 1; i < n_arr; i++) { for (k = 0; k < j; k++) if (arr[i] == arr2[k]) break; if (k == j) arr2[j++] = arr[i]; } теперь j это количество элементов в arr2.
    – avp
    16 дек 2013 в 14:41
  • @MrFranke, без сортировки (ну или без создания хэш-множества) быстрее квадрата не получится.
    – dzhioev
    16 дек 2013 в 17:52
2

Наиболее быстрым будет способ с использованием вспомогательного объекта:

function returnUnique(arr) {
  var obj = new Object;
  for (var i = 0, i_max = arr.length; i < i_max; i++) {
    obj[arr[i]] = ''; // запоминаем элемент как свойство объекта
  }
  return Object.keys(obj);
}

Но этот способ работает корректно только с массивами из простых однородных элементов.

1
  • Использование объекта как словаря с ключами? Неплохо)
    – Mi Ke Bu
    1 янв 2016 в 21:05

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.