LINUX.ORG.RU

Сортирующий итератор

 ,


1

4

Кто знает как сделать ленивый итератор по существующему массиву, который не меняя сам массив и используя минимальное количество памяти будет выдавать элементы в отсортированом порядке? Под минимальным можно считать «не порядка размера самого массива». Или на крайняк не в худшем случае

Мне абсолютно не приходит ничего в голову кроме полной пересортировки или совсем всяких дурацких алгоритмов. Может таки нельзя так?

Производительность желательно чтобы хоть и не обязательно n log n, но не совсем ужасная, главное памяти поменьше. Let the battle begin

★★★★☆

На правах /dev/random, использовать быструю сортировку, но держать только самый край. По необходимости досортировывая.

anonymous ()
Ответ на: комментарий от anonymous

Ну так не понятно, я собрал 10 элементов, они разбросаны хрен знает где. Я или храню все 10 или просто не знаю видел я элемент уже или нет.

Ну или третий вариант - магия о которой стоит узнать в этом треде. Уже приходят в голову всякие фильтры Блума и битовые вектора

vertexua ★★★★☆ ()
Последнее исправление: vertexua (всего исправлений: 1)
Ответ на: комментарий от vertexua

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

anonymous ()
Ответ на: комментарий от vertexua

не реально, особенно для произвольных данных.

qnikst ★★★★★ ()
Ответ на: комментарий от vertexua

Угу. Но по дороге к max/min можно же попробовать выстроить часть цепочки. Но худший случай будет давать по рукам.

anonymous ()
Ответ на: комментарий от vertexua

Хотя, ты же жабокодер... Ладно, вот тебе рецепт: делаешь поток ввода-вывода и N тредов, по количеству элементов массива. Каждый тред ждёт M секунд, где M - значение элемента массива, соответствующее данному треду, после чего выплёвывает это самое M в поток. А собственно сам итератор возвращает значения из потока.

http://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort#Java

вот тебе даже примерная реализация.

anonymous ()
Ответ на: комментарий от vertexua

Ну так не понятно, я собрал 10 элементов, они разбросаны хрен знает где. Я или храню все 10

Зачем? Чем тебя хранение только одного крайнего не устраивает?

Suntechnic ★★★★★ ()
Ответ на: комментарий от anonymous

делаешь поток ввода-вывода и N тредов, по количеству элементов массива. Каждый тред ждёт M секунд, где M - значение элемента массива, соответствующее данному треду, после чего выплёвывает это самое M в поток

Где-то я уже такое видел... Причем реализацию. Зачем издеваешься над ТС?

Suntechnic ★★★★★ ()
Ответ на: комментарий от Suntechnic

Зачем издеваешься над ТС?

Чтобы чувака, который потом будет поддерживать этот код, не посадили за убийство ТС.

anonymous ()
Ответ на: комментарий от Suntechnic

Вся задача - спортивный интерес, в голову взбрело. На работе только годные и эффективные штуки

vertexua ★★★★☆ ()
Ответ на: комментарий от vertexua

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

xeiph ()
Ответ на: комментарий от vertexua

Если в массиве есть отсортированная подпоследовательность, то можно выловить её за один проход. Естественно, если он, например, отсортирован наоборот, то никакой оптимизации не будет.

xeiph ()
Ответ на: комментарий от xeiph

Я думаю если уже есть буфер, то что-то можно похитрее запилить. Да хоть даже подумать о heap sort кусочка.

vertexua ★★★★☆ ()
Ответ на: комментарий от vertexua

Ну по минимуму памяти тебе уже предложили, назвав почему-то это «пузырьком», самый примитивный метод - держать последний выданный и сравнивать весь массив с ним. Выйдет по проходу на каждый элемент зато памяти действительно минимум. Думаю кстати что можно доказать что это так.

Suntechnic ★★★★★ ()
Ответ на: комментарий от vertexua

Если у тебя там дубли... То даже в этом случае не нужно ничего запоминать. Вообще тебе достаточно помнить только последний элемент!

Suntechnic ★★★★★ ()
Ответ на: комментарий от vertexua

Не надо! Выбрасывай все дубликаты подряд сразу - и позицию хранить не надо и устойчивость на халяву получаешь.

Suntechnic ★★★★★ ()
Ответ на: комментарий от vertexua

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

Suntechnic ★★★★★ ()
Ответ на: комментарий от vertexua

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

Можно ещё предположить такой вариант. Если данные хоть немного близки к равномерному распределению, то находим число минимум + (максимум - минимум) / (размер_массива / размер_буфера), забираем те элементы, что меньше этого числа (но не больше размера буфера) в буфер, сортируем.

xeiph ()
Ответ на: комментарий от xeiph

Забираем не больше размера буфера, а не элементы меньше размера буфера, естественно.

xeiph ()
Ответ на: комментарий от Suntechnic

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

Тут в зависимости от допущений о характеристиках чисел можно делать по разному

vertexua ★★★★☆ ()
Ответ на: комментарий от xeiph

можно ходить от этой позиции по кругу

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

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

vertexua ★★★★☆ ()
Ответ на: комментарий от vertexua

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

Да, я затупил.

xeiph ()
Ответ на: комментарий от xeiph

По поводу распределения, можно ещё его оценить, то есть держать ещё массив на (размер_массива / размер_буфера) + 1 чисел, у которого в первом элементе минимум, в последнем максимум, а остальные каким-либо образом подобрать так, чтобы они делили исходный массив на равные части. Это может быть долго, но на сложность не повлияет, потому что делается один раз.

Это если в массиве числа, конечно...

xeiph ()
Ответ на: комментарий от xeiph

Учитывая что пишем итератор, то долгие операции вначале лучше попытаться избегать. Вдруг кто-то 3 элемента возьмет и все

vertexua ★★★★☆ ()

Кстати вот вполне реальный пример использования сабжа: есть неотсортированый массив, занимающий почти всю память, порядок важен именно такой какой там есть. Иногда нужно сделать сортированый дамп по каким-то причинам. Так что сабж не совсем ненужен.

Альтернатива - external sort

vertexua ★★★★☆ ()
Последнее исправление: vertexua (всего исправлений: 1)
Ответ на: комментарий от dave

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

Думаю в Scala рубят с плеча, а в построении такого View так и нужно в большинстве случаев. Так как сабж в такой формулировке быстро работать не будет, следовательно такое пихать в дефолт грешно

vertexua ★★★★☆ ()
Последнее исправление: vertexua (всего исправлений: 3)
Ответ на: комментарий от vertexua

Я или храню все 10 или просто не знаю видел я элемент уже или нет.

Если элемент меньше текущего - видел, больше текущего - не видел;-)

Проход за O(N^2) пишется тупо в лоб. Дальше начинаются изыски... а размер элемента какой вообще говоря, и сколько элементов в массиве?

AIv ★★★★★ ()

Сортировка массива указателей на элементы исходного массива. По памяти N * sizeof_ptr. Т.е. ~4-8 Мб для миллиона элементов.

nerdogeek ()
Ответ на: комментарий от vertexua

Я бы не хотел идти дальше

но я запомню позицию 50 и начну искаьб следующий 28 начиная с него

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

Suntechnic ★★★★★ ()
Ответ на: комментарий от Suntechnic

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

vertexua ★★★★☆ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.