Как вернуть первые N максимальных элементов из массива без сортировки массива?

Question

[V Sh.]

Доброе утро!
Возник вопрос как решить следующую задачу.
Есть массив с объектами. После некоей операции к каждому объекту из массива прибавляется новое поле distance, в котором лежит целое число. Необходимо вернуть первые N элементов из массива, упорядоченного по возрастанию поля distance.

Решение в лоб:

const arr = [{id:1, name: "object1"}, {id:1, name: "object1"}, ...];
const n = 5;
let resultArr = arr.map(obj => Object.assign({}, obj, {distance : setDistance(obj)}));
resultArr = resultArr.sort((a,b) => b.distance - a.distance);
console.log(resultArr.slice(0, n));

Меня смущает, что при очень большом количестве элементов в массиве я буду терять много времени на сортировке, хотя мне нужны буквально первые N элементов (т.е. хвост массива можно и не упорядочивать).

Comments

[Сергей Соколов]

Вот несколько подходов и их сложность (на англ.)
https://www.geeksforgeeks.org/k-largestor-smallest...

[Rsa97]

т.е. хвост массива можно и не упорядочивать

А если самые маленькие значения distance находятся именно там?

[V Sh.]

Сергей Соколов, спасибо, выглядит как то, что мне нужно! Есть интересные решения.

Rsa97, речь про то, что как только я нашел и поместил в начало K элементов, то остальные N-K меня вообще не интересуют и могут располагаться как хотят.

[Alexej Simakov]

А, типа мы сначала имеем список магазинов и из геоданных рассчитываем расстояния до них, а потом нам нужно представить данные по удаленности. Можно ведь сразу при запросе дистанции ставить ответ в нужном порядке.
У меня стопка карточек с именами, я спрашиваю человека его рост, он говорит 1.83, я записываю и кладу карточку в новую стопку. Следующий говорит 1.76, я записываю и кладу его карточку сверху первой (по возрастанию) третий говорит 1.85, я записываю, кладу карточку в самы низ, потому что он теперь самый высокий. Insertion Sort по-моему это называется.

Answer 1

[Wataru]

Есть такой алгоритм. Называется quickSelect. Фактически, это обрезанный quickSort, где после выбора ведущего элемента и разбивки массива работа продолжается только в той половине, где находится раздел между первыми K элементами и остальными N-K.

Пусть у вас N элементов в массиве и надо вернуть K минимальных. Тогда сортировка будет работать за O(N log N), а quickselect за O(N) в среднем*. В худшем случае может быть и квадратичное время работы, но этот случай практически невозможен, если реализация испольует случайные числа для выбора ведущего элемента.

Если же вы боитесь этого худшего случая, или считаете себя самим невезучим человеком за всю историю человечества (или боитесь, что злой хакер взломает генератор случайных чисел и передаст вашей программе специально составленный массив, чтобы ее подвесить), то есть другой алгоритм, всегда работающий за O(n log k). При маленьких k - может быть даже быстрее первого алгоритма.

Суть его в том, чтобы в куче (heap aka priority queue) поддерживать пока найденные K минимальных элементов. При этом куча будет на максимум. Сначала туда кладутся первые k элементов массива, а потом каждый следующий вытесняет максимальный элемент в куче, если он его меньше.

* Вообще говоря, можно заставить quickselect и quicksort работать идеально всегда, если использовать алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна, который ищет медиану за O(n). Но на практике этот алгоритм не применятеся, потому что у него такая константа, что там на логарифм хватит и еще на квадрат останется.

Comments

[dollar]

Мне кажется, что это читерство какое-то.
Ведь если мы два раза пройдёмся по массиву, то сложность останется O(N), но количество вычислений всё же удвоится. А если K тоже считать за константу, то также получается O(N), хотя на самом деле должно быть O(N*K). Так что когда мы начнём учитывать "константу", магия испарится.

[Wataru]

dollar, Нет, не читерство. Оно проходит по массиву в среднем 2 раза, каким бы большим K не было.

Сначала вы делаете partition всего массива за один проход. Потом разбиваете левую половину, потом четверть и т.д. В итоге N+N/2+N/4 <= 2N.

Если K считать за константу, то практически любой метод будет работать за O(N), да. Но константа будет очень разная.

Answer 2

[res2001]

Вместо сортировки можно использовать алгоритм выборки k-той статистики (quik select).
Алгоритм не полностью сортирует массив, а только те элементы, которые необходимо для получения k-ой статистики. Для вашей задачи алгоритм надо вызывать N раз (с параметром от 1 до N).
Чтоб не портить оригинальный массив можно сделать копию, содержащую ссылки на элементы оригинального массива и вызывать алгоритм на копии.

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

Comments

[Wataru]

Не надо quickSelect вызвать N раз. После вызова с параметром N первые N элементов уже будут минимальными. N-ый будет на своем месте, а вот все пердыдущие могут быть и перемешаны. Ведь quickselect гарантирует правильность N-ого элемента именно тем, что все левее его - меньше его, а все правее - больше.

А выбор минимума N раз - это самое плохое, что можно сделать.
Если массив маленький, то тупо сортировка будет быстрее чем N раз искать минимум. Если N маленькое, то алгоритм с кучей из моего ответа будет гораздо быстрее.

[res2001]

Wataru, Согласен.
1.Значит надо вызывать quick select сразу для Nого элемента, тогда получаем нужные первые N элементов за один проход. Правда они будут не отсортированы.
2.Ну да, самый тупой и медленный вариант. Но, возможно, самый простой. А при малых N и небольшом размере массива, возможно, эти недостатки не будут иметь значения.

[Wataru]

2.Ну да, самый тупой и медленный вариант. Но, возможно, самый простой. А при малых N и небольшом размере массива, возможно, эти недостатки не будут иметь значения.

По-моему, вызов одного sort() будет проще.

Answer 3

[dollar]

Строго - никак.

Есть разные алгоритмы частичной сортировки с минимальной сложность O(N+KlogN), где K - количество максимумов, а N - размер массива, но совсем без сортировки не получится в общем случае.

Если не строго, то сильно зависит от специфики задачи, из которой нужно взять какие-то доп. условия и допущения. Именно они позволят оптимизировать алгоритм.

Например, если K не строгое, а лишь примерное, то можно прикинуть некий порог, выше которого эти элементы будут расположены. Скажем, K=10, N=1000 элементов, и в каждом случайное число от 1 до 1000. Тогда можно почти уверенно заявить, что все искомые элементы больше 970. Пробегаем массив один раз и находим все элементы больше 970. Их окажется около 30 плюс-минус. Главное, что не менее 10. Далее этот маленький массив можно отсортировать, но это снова сортировка.

Comments

[Wataru]

Есть, есть строгие алгоритмы. Работающие за линейную сложность, гарантрованно возвращающие первые N элементов. Правда на практике используются скорее алгоритмы, которые или работют за O(M log N) или за O(M) в среднем (где M - размер массива).

[dollar]

Wataru, так я тоже предлагаю за линейную сложность, причём с самой маленькой константой, где в качестве действия - просто сравнение. Но с поблажками.

А строго - это значит строго. Это значит, что даже нельзя вынуть из рукава дополнительное условие, что элементы распределены равномерно. Как только вы накладываете эти дополнительные условия, ими и правда можно пользоваться для оптимизации, но это уже получается не строго, то есть нет гарантии, что количество вычислений будет не больше O(N) в общем случае.

[Wataru]

dollar, Ваши поблажки (предположения о распределении чисел) весьма серъезные. Плюс даже с ними ваш алгоритм работает линейно лишь в среднем. Ведь может так оказаться, что все числа в массиве больше 970.
А приведенный мной, работающий за линию в среднем, алгоритм без поблажек - имеет константу примерно 2.

И его модификация с алгоритмом Блюма-Флойда-Пратта-Ривеста-Тарьяна будет работать за O(N) всегда, вне зависимости от размера K. Да, там мделенная константа, но это не важно. Этот алгоритм уже опровергает ваше "строго - никак".

[dollar]

Wataru, вообще-то, сказав "в среднем", вы как раз сделали поблажку. Примерно такую же, как и я - предположение о равномерном распределении. Разница лишь в том, что вы это считаете строгим, а я - нет.

Я же оговариваю, что поблажки могут быть разными, это может быть условие не только равномерности, а, например, неравномерности. А если в качестве условия будет ограничение значений элементов целыми числами от 1 до 100, то весь массив можно за O(N) и немного доп. памяти упаковать в массив счётчиков, и там вообще элементарно делается, а главное - гарантированно (т.е. строго). Какая бы ни была поблажка, оптимизация на неё найдётся, скорее всего. А вот если поблажек нет, то увы, никак не выжать O(N).

Насчёт quick select'a - там разве речь не про select? Ну то есть выбрать 2 максимальных элемента за 2*N можно и без quickselect (очевидно). А если нужно K элементов, то уже не получится так просто.

[Wataru]

dollar, QuickSelect'ом надо взять только N-ый элемент один раз. Тогда первые N элементов будут в начале массива (ведь именно так quickselect и гарантирует, что N-ый элемент будет где надо).

Еще раз, quickselect (хоть и с большой константой) работет за линию в худшем случае без каких-либо допущений.

Наличие random'а позволяет на практике получить быстрый линейный алгоритм.

Или есть также алгоритмы быстрее O(n log n), хоть и не линейные, но работающие быстро и не в среднем.

[dollar]

Wataru, минимальная сложность в общем случае - O(N + K log K), как ни называй, и это не совсем "линия".

Ну просто не может быть такого, что K максимумов можно найти за O(N) при любом K.

[Wataru]

dollar, Если порядо максимумов неважен, как в этой задаче - то K log K исчезает.

Answer 4

[Rsa97]

const littleN = (arr, N) => arr.reduce(
  (acc, cur) => {
    const idx = acc.findIndex((el) => el.distance > cur.distance);
    if (idx !== -1) {
      acc.pop();
      acc.splice(idx, 0, cur);
    }
    return acc;
  },
  Array(N).fill(arr[0])
);

Но не уверен, что такая функция будет быстрее штатной сортировки, особенно при небольших массивах.

Comments

[Wataru]

Этот ваш алгоритм по скорости равен "N раз найти минимум в массиве". Работает за O(M N), где M - длина массива.

Но вы почти додумались до хорошего алгоритма. Надо в acc использовать не массив, а кучу или приоритетную очередь на максимум. Тогда поиск вытесняемого элемента будет за O(log n).

[Rsa97]

Wataru, Не факт, что при малом требуемом размере массива-результата, использование кучи или очереди даст выигрыш в скорости. Алгоритмическая сложность - это всё таки не про абсолютную скорость, а про изменение скорости с ростом объёма данных.

[Wataru]

Rsa97, Ну, куча достаточно простая структура, что даже для минимального размера она досаточно быстра.

Вот пусть N=1, Тогда куча выродится в тупо один элемент. Один максимум. Тоже самое, что у вас. Не медленнее.

Может, при N=2? Да нет. Все те же N..2N сравнений, и до 2 перемещений на элемент. как у вас.

А вот уже при больших N в куче будет меньше и сравнений и присваиваний.

Answer 5

[Akina]

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