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

Объект - код Лемера, определяющий перестановку исходного массива, итерация - декодирование следующего числа и взятие его из массива.

ORLY?

Тогда довольствоваться T=C*(n*(n-1)/2), O(N^2).

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

Зависит от алгоритма его построения. Лень формально размышлять, но что-нибудь вроде любого in-place sort'а за n log n с сохранением в одном целом беззнаковом числе индекса перестановки (феерически большое число, до n! - 1), один проход с возвращением в исходное состояние (так как перестановка у нас уже есть).

Не-а. Если не ходить по кругу то мой вариант выдаст массив из одинаковых элементов вообще за один проход и не надо никуда ходить.

Это O(n) по памяти, не проще тогда отсортировать копию массива?

Где O(n)? А так очевидно, гораздо проще отсортировать копию.

естественный алгоритм «в лоб»:

• на первом шаге ищешь минимальный элемент,
• на каждом следующем шаге ищешь элемент мин, но больший чем предыдущий

работает? работает, при условии отсутствия дубликатов в массиве..добавляешь пару оптимизаций:

• запоминаешь позиции вытащенных элементов (например в битовом поле или в коллекции или в дереве диапозонов) - каждый проход становится покороче и сравнений меньше; алгоритм начинает работать с дубликатами
• на первом шаге делаешь частичный битовый индекс: B=1 еcли X>X[i+1], и на каждом следующем его поддерживаешь.- каждый проход становится ещё короче

получаешь свой n log n ;-)

почему нельзя вместо массива использовать сортированный список/коллекцию?

вот что жаба с мозгом делает!

все логично - только жабий мозг выбирает жабу

А сколько в асимптотике понадобится памяти для хранения числа n! ?

Количество бит, необходимых для хранения числа х - верхняя граница lg(2, x).

O(lg(n!)) = O(n*log(n)). fail. Выгоднее (по памяти) хранить отсортированный массив.

А как тебе такой вариант:

Примем, что все элементы различны(для дублей там небольшое усложнение, но несущественное).

Пусть необходимо потратить O(m) памяти. Выберем m минимальных элементов и поместим их в красно-чёрное дерево. Это можно сделать за время O(n logm). Теперь следующие m запросов к массиву будут выполняться за O(logm) каждый. Когда красно-чёрное дерево опустеет (после m запросов), выберем следующие m элементов из массива(опять за время O(n logm)) и сможем удовлетворить следующие m запросов.

Таких пачек по n чисел будет n/m.

На весь массив потратим O(n/m(n logm) + n logm) = O(n^2logm/m).

И тут уж выбирай компромисс между скоростью и памятью =)

m=1: Память O(1), время O(n^2)

m=n: Память O(n), время O(nlogn)

m=sqrt(n): Память O(sqrt(n)), время O(n sqrt(n) log n)

Это поинтереснее, а m-минимальных находить кучей фиксированого размера, пропуская те, которые уже отданы клиенту?

Да, именно так.

Похоже норм решение, попропую покодить на досуге

Это можно сделать за время O(n logm).

с чего бы это? в неотсортированном то массиве

Я написал, как это сделать.

просто реализуй вставку новых таким образом, чтобы уже в момент добавления новых элементов массив оказывался отсортированным ;)

//это, конечно, если тебе не надо по разным параметрам сортировать ;)

Я написал, как это сделать.

Что ты написал? «Выберем m минимальных элементов» как ты думаешь за какое время ты будешь выбирать m минимальных элементов в не отсортированном массиве?

Что ты написал? «Выберем m минимальных элементов» как ты думаешь за какое время ты будешь выбирать m минимальных элементов в не отсортированном массиве?

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

Поскольку в дереве никогда не бывает больше m+1 элемента, каждое добавление и удаление занимает O(log m)

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

небольшая критика, а то ТС сейчас накодит и удивится результату :)

Выберем m минимальных элементов и поместим их в красно-чёрное дерево. Это можно сделать за время O(n logm)

как только фиксируется объём RB-Tree, операция добавления состоит из двух: удаление максимального э-лта, добавление нового элемента. Асимтотика O(log n) на элементарную операцию останется, но при большем множителе.

и что-то мне сдаётся что заполнение бинарного дерева n элементов ближе к O(n^2) а не n log n; не помню точно, а выводить лень

уж выбирай компромисс между скоростью и памятью

не стоит забывать, что IRL сортируемые эл-ты (void *), узел бинарного дерева в 3 раза больше, а в RB и ещё поле на цвет.

Я это операцию собирался делать через heap размера m и все еще пока не могу понять почему будет не n log m

Да. Что поделать?

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

и что-то мне сдаётся что заполнение бинарного дерева n элементов ближе к O(n^2) а не n log n; не помню точно, а выводить лень

красно-черного таки nlog n

А чем будет лучше чем heap? Просто heap можно компактно в массив запихнуть, хотя можно и красночерное в принципе

красно-черного таки nlog n

да, посчитал :)

Для вас будет удивительно и много попцов ринутся в бой, неся своё красное знамя, но с вероятность 95% самым быстрым решением будет min() по массиву, при нормальной его реализации.

Стоит ноль памяти. Работает рективно, хотя с вашей точки зрения n^n. Дерзайте.

У нас пока фаза дизайна, предлагаем разные решения. А бенчмаркать имплементации, это потом

идет рождение очередной никому не нужно жалкой кучи быдлокода на жабе))))))))))))))))

Ты уже опозорился вначале с пузырьковой сортировкой (других не знаешь), еще хочешь?

А что ты вынесешь из этого «дизайна»? Все эти разговоры об решениях обстрактных задач никак тебе не помогут.

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

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

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

Я там выше по треду обьяснил, что не решаю задачу которая мне нужна по работе, а просто заинтересовался непосредственно сферическим сортированым итератором в вакууме.

А чем будет лучше чем heap? Просто heap можно компактно в массив запихнуть, хотя можно и красночерное в принципе

хм... просто в красно-чёрном дереве всегда легко ищется как минимальный, так и максимальный элемент. Но ты можешь сперва все совать в heap с максимальным корнем при проходе массива, а потом переделать его в heap с минимальным уже для выдачи элементов при запросе.

Так, кажется, даже лучше. Нет лишнего расхода памяти на rbtrea

А не пойдёт вариант, что ищем минимальное, сдвигаем указатель по массиву на следующий элемент и на следующий вызов опять ищем минимальное значение от хвоста массива? Если массив изменился - итератор протух.

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

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

А чем будет лучше чем heap?

и там и там дерево. Обход O(n) формирование O(n log n). Чуть разные накладные расходы.

Резюмируя: Общая оценка O(n log m * n/m) = O(n^2 * log m/m), где n-размер массива, m-кеша; предложеный оптимум выбора (цене память/скорость) m=sqrt n, наверное близок к истине; Огрихи в реализации легко сведут всё к O(N^2).

если оценить тупой выбор очередного минимума, там хоть и O(N^2), но получаемый как sum(1..N,N)~O(N*(N-1))=O(N^2-N), он тоже стремится снизу,оптимизируется и его в реализации придётся ещё обогнать;

Imho овчинка с кешем стоит выделки только при очень значительном N и дорогих операциях сравнения. И наличия оплачиваемого времени конечно :-)

И наличия оплачиваемого времени конечно :-)

ну решение даже подобных вычурных задач все равно более интеллектуально чем говнокодерство на жабе)))

Верно, асимптотически это лишь немного лучше хранения всей перестановки, как массива целых, что требует эквивалентно разрешению n^n чисел.

Выгоднее (по памяти) хранить отсортированный массив.

Для n > количество чисел, разрешаемых представлением данных. То есть для n > 4294967296 для 4-байтов. Для всех же меньших это сравнение вида n! vs m^n, где m > n.

На самом деле n должно быть даже больше, потому что факториал меньше m^m.

Для таких случаев ясно, что сравнения не нужны, а нужен классический тривиальный перебор за O(n).

Фак мой мозг, почему я не додумался до этого сразу?

1) Разбиваем массив на sqrt(n) частей по sqrt(n) элементов.

2) В каждой части находим минимальный элемент - O(n). Запоминаем этот элемент для каждой части - O(sqrt n) памяти

3) При каждом запросе находим минимальный из минимальных за O(sqrt n) и выдаем его. Находим в соответствующем подмассиве следующий элемент еще за O(sqrt n).

Надеюсь, понятно объяснил, а то голова после работы мутная.

Итог:

Дополнительная память O(sqrt n)

Время _каждого_ запроса O(sqrt n) (только перед первым запросом нужно выполнить O(n) операций пред.обработки)

Весь массив можно выдать за O(n sqrt n)

Никаких сложных структур данных, все сплошные массивчики. Кеш - ня, поиск - ня, все - ня, Ня, ня, ня!

Все круто, но алгоритм не корректно отсортирует

Merge sort? )) Логично. Только минимальный постоянно за sqrt n

Где? Вроде все норм, боян бобоян вариация merge sort, просто не бинарный

{1,2,3,11,22,33,111,222,333}
На выходе будет: 1,11,111,2,22,222,3,33,333
Тут mergesort и не пахнет. Хотя бы потому как... где merge?

После того, как мы выбрали 1, ищем в первой части следующее чилсо.

{1,22,333,2,11,222,3,33,111}
Точно в первой?