Какой самый маленький элемент оперативной памяти
Обновлено: 21.11.2024
Сегодняшняя маленькая программа — это даже не программа. Это просто функция.
Постановка задачи такова: по заданному непустому массиву чисел в JavaScript найдите индекс наименьшего значения. (Если наименьшее значение встречается более одного раза, допустим любой такой индекс.)
Одним из решений является просто выполнить операцию вручную, имитируя то, как вы выполняете операцию с бумагой и карандашом: вы начинаете с того, что первый элемент является победителем, а затем переходите к остальным элементам. Если следующий элемент меньше, чем тот, который у вас есть, вы объявляете этот элемент новым предварительным победителем.
Еще одно решение — использовать встроенную функцию сокращения для запуска цикла, поэтому вам просто нужно предоставить бизнес-логику начального предположения и оператора if.
Третье решение – использовать встроенные функции JavaScript для поиска наименьшего элемента и последующего преобразования элемента в его индекс.
Какой из них самый быстрый?
Хорошо, во-первых, прежде чем решить, какой из них самый быстрый, нужно убедиться, что все они верны. Одна вещь, которую вы обнаружите, заключается в том, что метод min/indexOf дает сбой, когда массив становится очень, очень большим, или, по крайней мере, это происходит в Internet Explorer и Firefox. (В моем случае Internet Explorer и Firefox отказались примерно от 250 000 и 500 000 элементов соответственно.) Это потому, что вы начинаете сталкиваться с ограничениями движка на количество параметров, которые вы можете передать одной функции. Вызов применения для массива из 250 000 элементов эквивалентен вызову min с 250 000 параметров функции.
Поэтому мы ограничимся массивами длиной не более 250 000.
Прежде чем я поделюсь результатами, я хочу, чтобы вы предположили, какой алгоритм, по вашему мнению, будет самым быстрым, а какой — самым медленным.
Я ожидал, что ручная версия окажется на последнем месте, потому что, в конце концов, все делается вручную. Я ожидал, что редуцирующая версия будет немного быстрее, потому что она перекладывает часть работы на встроенную функцию (хотя накладные расходы на вызов функции могли свести на нет любое из этих улучшений). Я ожидал, что версия min/indexOf будет самой быстрой, потому что почти вся работа выполняется во встроенных функциях, а стоимость выполнения двух проходов по данным будет компенсирована улучшенной производительностью встроенных функций.
Вот тайминги трех версий с массивами разного размера, работающими на случайных данных. Я нормализовал время выполнения, чтобы результаты не зависели от скорости процессора.
| Элементы | вручную | уменьшить | min/indexOf |
|---|---|---|---|
| Internet Explorer 9 | |||
| 100 000 | 1,000 | 2,155 | 2,739 | < /tr>
| 200 000 | 1,014 | 2,324 | 3,099 |
| 250 000 | 1,023 | 2,200 | 2.330 |
| Internet Explorer 10 | |||
| 100 000 | 1,000 | 4,057 | 4,302 |
| 200 000 | 1,028 | 4,057 | 4,642 |
| 250 000 | 1,019 | 4.091 | 4.068 |
Вы удивлены? Я точно был!
Мало того, что у меня все было наоборот, но и преимущество ручной версии было намного больше, чем я себе представлял.
(Это показывает, что единственный способ точно узнать характеристики производительности вашей программы — это сесть и измерить ее.)
Я думаю, что происходит то, что оптимизатор JavaScript может действительно хорошо оптимизировать код вручную, поскольку он очень прост. Здесь нет вызовов функций, тело цикла — всего одна строка, все прямо там, в открытом доступе. Версии, использующие встроенные функции, в конечном итоге скрывают часть информации от оптимизатора. (В конце концов, оптимизатор не может заранее предсказать, переопределил ли кто-то стандартную реализацию Array.prototype.reduce или Math.prototype.min , поэтому он не может слепо встроить вызовы.) В результате ручная версия может работать слишком долго. вдвое быстрее в IE9 и более чем в четыре раза быстрее в IE10.
Я ошибся, потому что думал о JavaScript как об интерпретируемом языке. В чисто интерпретируемом языке накладные расходы интерпретатора примерно пропорциональны количеству вещей, которые вы просите его сделать, в отличие от того, насколько сложно было сделать любую из этих вещей. Это похоже на фиксированную комиссию за каждую транзакцию, независимо от того, была ли транзакция на 100 долларов или 50 центов.Таким образом, вы пытаетесь сделать одну большую покупку (назвать комплексную внутреннюю) вместо множества мелких (прочитать элемент массива, сравнить два значения, увеличить переменную, скопировать одну переменную в другую).
Дополнительная болтовня: я также провел тест в Firefox, потому что он оказался у меня под рукой.
| Элементы | вручную | уменьшить | min/indexOf |
|---|---|---|---|
| Firefox 16 | |||
| 100 000 | 1,000 | 21,598 | 3,958 |
| 200 000 | 0,848 | 21,701 | 2,515 |
| 250 000 | 0,839 | 21,788< /td> | 2.090 |
Те же данные, собранные в Firefox 16 (звучит смехотворно старым, потому что к тому времени, когда эта статья достигнет начала очереди, Firefox будет иметь версию 523), показывают другой профиль, хотя победитель тот же. Ручной цикл и min/indexOf становятся более эффективными по мере увеличения размера массива. Это говорит о наличии фиксированных накладных расходов, которые постепенно становятся менее значительными по мере увеличения размера набора данных.
Одна вещь, которая бросается в глаза, это то, что метод сокращения уступает другим. Я предполагаю, что настройка вызова функции (для перехода между встроенной функцией и сценарием) очень дорогая, и что разработчики движков JavaScript не тратят время на оптимизацию этого случая, потому что в реальной жизни редукция почти не используется. мировой код.
Обновление: я преувеличил свою наивность, чтобы улучшить повествование. Как я указываю в предисловии к своей книге, мои истории могут быть не совсем правдивы, но они достаточно правдивы. Конечно, я знаю, что в настоящее время JavaScript перегружен, и это меняет исчисление. (Также скрытая копия массива.)
Вопрос. Напишите эффективную программу для вывода k самых больших элементов массива. Элементы в массиве могут быть в любом порядке.
Например, если задан массив [1, 23, 12, 9, 30, 2, 50] и вас просят указать 3 самых больших элемента, т. е. k = 3, то ваша программа должна напечатать 50, 30 и 23.
Метод 1 (используйте Bubble k раз)
Спасибо Shailendra за предложение этого подхода.
1) Измените сортировку пузырьком, чтобы внешний цикл выполнялся не более k раз.
2) Распечатать последние k элементов массива, полученного на шаге 1.
Временная сложность: O(n*k)
Подобно пузырьковой сортировке, другие алгоритмы сортировки, такие как сортировка выбором, также могут быть изменены для получения k самых больших элементов.
Способ 2 (использовать временный массив)
K самых больших элементов из arr[0..n-1]
1) Сохраните первые k элементов во временном массиве temp[0..k-1].
2) Найдите наименьший элемент в temp[], пусть наименьший элемент будет min.
3-a) Для каждого элемента x в массиве от arr[k] до arr[n-1]. O(n-k)
Если x больше min, удалите min из temp[] и вставьте x.
3-b) Затем определите новое значение min из temp[]. O(k)
4) Напечатать последние k элементов temp[]
Временная сложность: O((n-k)*k). Если мы хотим, чтобы выходные данные были отсортированы, тогда O((n-k)*k + k*log(k))
Спасибо nesamani1822 за предложение этого метода.
Метод 3 (использовать сортировку)
1) Отсортировать элементы в порядке убывания в O(n*log(n))
2) Вывести первые k чисел отсортированного массива O(k) .
Ниже приведена реализация вышеизложенного.
Питон
JavaScript
Временная сложность: O(n*log(n))
Метод 4 (использование максимальной кучи)
1) Построить дерево максимальной кучи за O(n)
2) Использовать Максимальное извлечение k раз, чтобы получить k максимальных элементов из максимальной кучи O(k* лог(п))
Временная сложность: O(n + k*log(n))
Метод 5 (Использование статистики порядка)
1) Используйте алгоритм статистики порядка, чтобы найти k-й наибольший элемент. См. выбор темы в наихудшем случае линейного времени O(n)
2) Используйте алгоритм QuickSort Partition для разделения вокруг k-го наибольшего числа O(n).
3) Отсортируйте элементы k-1 (элементы больше k-го по величине элемента) O (k * log (k)). Этот шаг необходим только в том случае, если требуется отсортированный вывод.
Временная сложность: O(n), если нам не нужен отсортированный вывод, иначе O(n+k*log(k))
Спасибо Шилпи за предложение первых двух подходов.
Метод 6 (использовать минимальную кучу)
Этот метод в основном представляет собой оптимизацию метода 1. Вместо использования массива temp[] используйте минимальную кучу.
1) Создайте минимальную кучу MH из первого k элементов (от arr[0] до arr[k-1]) данного массива. O(k*log(k))
2) Для каждого элемента после k-го элемента (от arr[k] до arr[n-1]) сравните его с корнем MH.
……a) Если элемент больше корня, сделайте его корневым и вызовите heapify для MH
……b) В противном случае проигнорируйте его.
// Шаг 2 — O((nk)*log(k))
3) Наконец, MH имеет k самых больших элементов, и корень MH является k-м по величине элементом.
Временная сложность: O(k*log(k) + (nk)*log(k)) без отсортированного вывода. Если требуется отсортированный вывод, то O(k*log(k) + (nk)*log(k) + k*log(k)) так что в целом это O(k*log(k) + (nk)*log( к))
Все вышеперечисленные методы также можно использовать для поиска k-го по величине (или наименьшего) элемента.
Предположим, что мы читаем последовательность из $n$ чисел, одно за другим. Как найти $k$-й наименьший элемент всего за $O(k)$ памяти ячеек и за линейное время ($O(n)$). Я думаю, мы должны сохранить первые $k$ членов последовательности, а когда получим $k+1$-й член, удалить член, который, как мы уверены, не может быть $k$-м наименьшим элементом, а затем сохранить $k+1 $-й срок. Таким образом, у нас должен быть индикатор, который показывает этот неиспользуемый термин на каждом этапе, и этот индикатор должен быстро обновляться на каждом этапе. Я начал с "max"; но не может быстро обновляться; Означает, что если мы рассматриваем max, то при первом удалении мы пропускаем max и должны искать max в $O(k)$ и его причину $(nk)\times O(k)$ раз, что это не линейно. Возможно, нам следует более разумно сохранять первые $k$ членов последовательности.
Как решить эту проблему?
$\begingroup$ Если $k = \theta(n)$, то это можно сделать с помощью алгоритма статистики заказов. Если $k = o(n)$, то вы можете сделать это за $O(k)$ памяти и $O(n\log k)$ времени, используя любые сбалансированные по высоте деревья. $\endgroup$
$\begingroup$ Существуют алгоритмы линейного времени на месте, которые вы можете найти в Google, но они несколько сложны. $\endgroup$
$\begingroup$ @xavierm02 точно не проблема выбора. Потому что есть ограничение на ограничение памяти. $\endgroup$
2 ответа 2
Создайте буфер размером $2k$. Прочитать из массива $2k$ элементов. Используйте алгоритм выбора с линейным временем, чтобы разбить буфер так, чтобы $k$ наименьших элементов были первыми; это занимает $O(k)$ времени. Теперь прочитайте еще $k$ элементов из вашего массива в буфер, заменив $k$ самых больших элементов в буфере, разделите буфер, как и раньше, и повторите.
Для этого требуется $O(k * n/k) = O(n)$ времени и $O(k)$ пространства.
$\begingroup$ +1, это соответствует заданной асимптотике. При этом я не верю, что это быстрее, чем выполнение одного алгоритма выбора с линейным временем. за исключением тех случаев, когда $k$ — небольшая константа, это дает интересную перспективу. Например, для $k = 1$ этот алгоритм выдает функцию min. $\endgroup$
$\begingroup$ Иногда алгоритм выбора с линейным временем занимает слишком много места. Например, он не подходит для использования в контексте потоковой передачи или когда входной массив неизменяем. $\endgroup$
Вы можете сделать это за $O(k)$ памяти и $O(n \log k)$ времени, сформировав max-heap фиксированного размера из первых $k$ элементов за $O(k)$ времени, затем итерация по остальной части массива и добавление нового элемента, а затем извлечение для $O(\log k)$ для каждого элемента, что дает общее время $O(k + n\log k)$ = $O(n \log k )$.
Это можно сделать за $O(\log n)$ вспомогательной памяти и за $O(n)$ времени, используя алгоритм выбора медианы медиан, выбирая в $k$ и возвращая первое $k$ элементы. Без изменения асимптотики вы можете использовать introselect для ускорения среднего случая. Это канонический способ решить вашу проблему.
Теперь технически $O(\log n)$ и $O(k)$ несравнимы. Однако я утверждаю, что $O(\log n)$ на практике лучше, так как он фактически постоянен, учитывая, что ни одна компьютерная система не имеет более $2^$ байтов памяти, $\log 2^= 64$. При этом $k$ может вырасти до $n$.
k1 — это k1 th самый большой элемент, поэтому я выбираю меньшее из k и k1.
Тем не менее, я не смог передать ошибку ограничения времени в онлайн-судье. Я не знаю, будет ли еще большая сложность, учитывая, что мне нужно создать массив размером не более k; может быть меньше, чем k возможно? Или есть другой способ решить эту проблему, кроме использования структуры кучи.
Пожалуйста, не могли бы вы помочь найти лучшую временную сложность?
Ограничение памяти: 256 МБ.
Ограничение времени: 1 с.
Ввод: input.txt
Вывод: output.txt
Вам дан массив из n целых чисел и натурального k.
Вы должны найти k-й самый большой элемент массива.
Вы не можете создать массив, состоящий из более чем k элементов.
Ввод:
В первой строке записано натуральное n (1 ≤ n≤10 5 ) — количество элементов массива, и натуральное k.
Вторая строка содержит n чисел — элементы массива.
Вывод:
k-й самый большой элемент массива.
Пример:
Я вижу пару неправильных ошибок, которые могут дать неправильный ответ, и очевидную утечку памяти, но ничего, что занимало бы слишком много времени. Вы уверены, что правильно обрабатываете ввод? Кроме того, я почти уверен, что поведение freopen(. stdin) не определено — возможно, оно не работает в среде онлайн-судьи.
Я посмотрю, но не могли бы вы также просмотреть ответы здесь и отметить один из них как принятый? Это топливо, которое заставляет этот сайт работать. Вы когда-нибудь выясняли, были ли тесты в испытании каким-то образом испорчены, или (иным образом) находили кого-то, кто прошел тесты?
2 ответа 2
Временная сложность оптимальна, но вы можете сделать свой код чуточку эффективнее:
- Используйте не рекурсию, а итеративное решение.
- Не используйте swap , а сохраните исходное значение в памяти при копировании дочерних значений в родительские и сохраните исходное значение только после того, как вы достигнете соответствующего слота.
- Не выполняйте дважды 2 * i : другой дочерний узел будет просто следующим.
- Пусть функции heapify принимают дополнительный аргумент, который может быть либо текущим значением по индексу i, либо заменяющим его значением. Это экономит одно задание.
Вот как это будет выглядеть для двух функций heapify:
В основной функции вы можете сделать особый случай, когда k == 1 или k == n, поэтому куча не нужна, просто min() или max () .
Одна странность заключается в том, что в задании, на которое вы ссылаетесь, говорится "k-е самое большое", а вы говорите "k-е наименьшее". Возможно, вы перепутали.
Итак, вот код, когда задание должно вернуть k-й наименьший. Но, пожалуйста, проверьте задание, не нужно ли было делать это для k-го крупнейшего:
Да, я просто иногда смешиваю их, извините, потому что у меня есть две задачи: одна для самых маленьких и одна для самых больших
Подходит для сглаженного if . else if , но я вернул в случае, когда k1 == 1 и нужно сделать макс. Я не сторонник использования заглавной буквы слова «куча», поскольку это не класс, а экземпляр. Поэтому я вернул и это.
Это еще не прошло. Итак, в принципе, я протестировал этот код для этого конкретного случая. В чем может быть проблема? Может быть, онлайн-судья не мог пройти более 10 ^ 7 за одну секунду? Это будет очень странно!
Вы делаете предположение, что использование кучи меньшего размера всегда является лучшим выбором. Возможно, вы захотите переосмыслить это.
Например, представьте, что вы хотите выбрать 96-е наименьшее число из списка 100. Если вы используете кучу размером 96, вы должны сделать следующее:
- Создайте кучу из 96 элементов. buildHeap равен O(n), и в данном случае n равно 96.
- Выполнить до 4 вставок в кучу из 96 элементов. Это будет 4*log(96).
Если вы используете кучу размером 4, вы сделаете следующее:
- Создайте кучу из 4 элементов.
- Выполнять до 96 вставок в кучу из 4 элементов. Это будет 96*log(4).
Первый вариант: 96 + 4*log(96). Логарифм по основанию 2, равный 96, составляет около 6,58. Таким образом, вставки будут стоить 26,32, всего 122,32.
Второй вариант с меньшей кучей: 4 + 96*log(4). log(4) равен 2, поэтому в итоге получается 4 + 196, или всего 196.
Меньшая куча здесь — большой проигрыш.
Как правило, вы хотите использовать большую кучу, когда (k + (n-k)*log(k)) .
Реальное время работы алгоритма выбора кучи зависит от порядка представления элементов. Например, если вы ищете 1000-е наименьшее число в массиве из 100 000, он будет работать намного быстрее, если массив находится в порядке возрастания, чем если он в порядке убывания. Причина?
Потому что в случае возрастания вы строите свою начальную кучу из первых 1000 элементов, а затем вам больше не придется изменять кучу, потому что ни один из следующих элементов не меньше самого большого элемента в куче.
Но если массив находится в порядке убывания, то каждый элемент, который вы просматриваете, будет меньше, чем самый большой элемент в куче, что означает, что вы будете выполнять вставку в куче для всех 99 000 оставшихся элементов.
Представьте, как будет работать ваш код, если один из тестовых случаев представляет собой большой массив в порядке убывания.
Если вы еще не доказали, что ваш способ выбора размера кучи явно лучше, вы можете рассмотреть вариант "выбрать k-е наименьшее", используя maxheap размера k, независимо от этого.
Читайте также: