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

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

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

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

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

Ну и память занимаемую рекурсией тоже не забыть померять, читы нам не нужны

Корошо.

Что-то мне кажется что фундаментально тут не выкрутиться, эвристики, читы и подобное.

йопт, сделай новый массив и отсортируй.

Спасибо за совет, так каждый лох может.

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

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

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

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

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

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

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

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

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

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

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

n^2 это ужасная?

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

По памяти? Да. По времени? Нет, я пытаюсь только на минимуме памяти выехать

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

Думаю можно, только еще нужно запомнить последнюю позицию при дубликатах.

Можно ещё буфер сделать некоторой длины, должно в среднем соптимизировать.

А как кокретно вы предлагает буфер использовать?

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

Хотя у упорот. Можно вообще с начала не ходить и всё норм будет.

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

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

Но квадрат всё равно, тут ничего не поделаешь.

Да, все так, плюс позицию для того чтобы дубликаты не пропускать. Вот дальше думаем как ускорять )

Квадрат квадрату рознь.

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

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

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

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

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

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

сужать границы по ходу проходов

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

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

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

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

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

Ну это тоже имеет свой worst case

ТС, а расскажи, почему нельзя менять сам массив?

Спорт интерес.

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

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

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

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

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

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

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

Может быть, есть такой хитро-вывернутый View в Scalа? Не смотрел в тамошней библиотеке коллекций?

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

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

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

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

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

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

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

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

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

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

Если intы, то равносильно созданию нового массива