Есть ли эффективный способ перебора несортированного контейнера в определенном порядке без сортировки / копирования / ссылки на исходный контейнер?

Question

Я имею в виду SortedIterator, который принимает функцию Less, которая будет использоваться для сортировки контейнера со всеми известными алгоритмами.

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

Есть ли эффективный способ итерации в четко определенном порядке без фактической сортировки списка? Я спрашиваю об этом из алгоритмического любопытства, и я ожидаю, что ответ будет отрицательным (или да с большим , но ). Он задается из образа мышления в стиле C ++, но на самом деле это довольно общая не зависящая от языка предпосылка.

Answer 1

Если вы хотите O (1) памяти, то сложность O (n ^ 2) - единственный известный нам способ сделать это. В противном случае мы могли бы улучшить алгоритм выбора-сортировки таким же образом. Любой другой механизм сортировки полагается на возможность реструктуризации части массива (сортировка слиянием опирается на сортировку частей массива, qsort полагается на разбиение массива на основе оси вращения и т. Д.).

Теперь, если вы ослабите ограничение памяти, вы можете сделать что-то более эффективное. Например, вы можете хранить кучу, содержащую самые низкие значения x элементов. Таким образом, после одного прохода O (Nlog x) вы получаете x элементов для вашего итератора. Для следующего прохода ограничивайте только элементы больше, чем последний элемент, который вы выпустили до сих пор. Вам нужно будет сделать N / X проходов, чтобы получить все. Если x == 1, то решением является O (N ^ 2). Если x == N, решением является O (Nlog N) (но с большей константой, чем типичная qsort). Если данные находятся на диске, я бы установил в x столько памяти, сколько вы можете, минус несколько МБ, чтобы можно было читать большие куски диска.