OberonCore

Есть такая задачка:
Дано 15 миллионов неотсортированных записей, требуется их отсортировать и обработать.
Затем, в конец 15 миллионного массива добавляется еще 1 миллион записей, требуется, чтобы весь 16 миллионный массив был отсортирован (первые 15 уже отсортированы, а последний миллион нет) и нужно его обработать.
Затем к 16 миллионному массиву добавляется еще 1 миллион, требуется, чтобы весь 17 миллионный массив был отсортирован и так далее, до тех пор пока массив не станет 30 миллионным.

Пока я сортирую с помощью алгоритма, QuickSort, сортировка занимает порядка 1 минуты, есть еще преимущество, что не требуется дополнительный массив (все записи занимают порядка 500 Мегабайт памяти). Но недостаток в том, что QuickSort пересортировывает весь массив и не учитывает, что, например, первые 15 миллионов записей уже отсортированы.

Может кто-нибудь посоветует более эффективную сортировку? Желательно еще, чтобы не требовался дополнительный массив, но это условие не обязательное.

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

Сортируете последний миллион любым алгоритмом.

Затем присоединяете его. Получается массив из двух отсортированных частей.

Затем подбираете какой-то алгоритм второй... Так и просится какое-то "просачивание", диффузия.

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

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

Многое зависит от задачи, от того, что за данные добавляются в конец, и от того, что "дешевле" - сравнение или обмен элементов местами.

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

Если обмен дорогой, а сравнения дешёвые, то можно составить карту индексов с тем, чтобы через максимум 1 млн. обменов получить отсортированный массив. Под картой индексов подразумевается массив с 16 млн. целочисленных значений, каждое i-e его значение - это индекс элемента исходного массива, который должен оказаться на i-м месте в результирующем массиве. Для получения карты индексов, очевидно, добавляемый массив надо предварительно отсортировать тем же QuickSort'ом.

Тоже подумал про диффузию, но нормального алгоритма что-то не выдумывается. Сдаётся мне, что проще будет отсортировать добавляемый массив, затем увеличить основной массив на необходимую величину и просто заполнить, начиная с хвоста, содержимым из обоих массивов. Это гарантированный и простой способ. Используется временный буфер из массива на 1 млн. записей (тот, что добавляем). Если нужно ужаться по памяти ещё сильнее, то поможет только карта индексов, а если дело только в скорости, то превосходство над полным QuickSort может быть существенным, а может и вовсе не быть, в зависимости от конкретных данных (к сожалению, конкретные формулы трудоёмкости выдавать я не обучен).

"Диффузия" - это нормальный алгоритм слияния двух отсортированных массивов. В С++ такое стандартно есть.
А можно сделать просто вставку в дерево обоих массивов, а потом из дерева обходом - опять массив.

Что такое "вставка в дерево" и сколько это потребует памяти?

Я на Компонентном Паскале эту задачку делаю, поэтому вещи из C++, там не доступны.

В любом случае мне ,скорее всего, придется дополнительную память в 500 мегабайт выделить, тогда для моей задачи можно будет только 1 раз отсортировать и 15 раз использовать линейный алгоритм. И не задумываться о том, как ускорить "быструю сортировку".

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

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

В случае списка - слияние "по месту", без реаллокации.

Короче, большой контейнер (на 30 миллионов) -- список, а маленький контейнер (на 1 миллион) -- массив. Массив сортируете по обычному, затем сливаете его в список.

"Это же очевидно Ватсон" Шерлок Хомс

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

Кроме того, если у нас 30 миллионов ЧИСЕЛ (int'ы скажем), то накладные расходы (по памяти) списка будут слишком большие. В отличие от массива.

Вообще, что мешает обернуть оба массива в список? в списке будет ровно два элемента -- первый 30 миллионный массив и втрой миллионный
+ логика для определения к какому массиву обращаться в случае операции индексации.

Т.е. доп. прослойка.

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

Да максимальный размер массива известен заранее.
Дерево - это конечно тоже вариант, но он сложнее в реализации.

Да ладно... возьмите с диска "Алгоритмов...", там всё работает прямо на КП. Подпилите чуток. Делов-то.

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

Согласен с Info21.
Обратите внимание, что для дерева достаточен стандартный алгоритм из учебника, а для массива алгоритм ещё надо изобретать.
А если ещё добавить хэширование (т.к. объём данных велик), то первоначальный бинарный поиск в массиве покажется улиткой.

Ещё один момент. Постановка задачи -- очень важный этап.
IMHO, Вы поторопились, решив для себя, что (сортированный) массив -- "очевидное" решение для поиска.

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

На самом деле сейчас проблема в другом. Я уже решил, что проще будет не экономить компьютерную память, а выделить дополнительный блок в 500 Мегабайт. Я пытаюсь, выделить еще памяти, но в BlackBox 1.6 и 1.5 не хватает памяти, почему-то, хотя общий размер выделяемой памяти меньше 1,5 Гигабайт.
Я сделал упрощенный тест:

Здесь массив должен быть размером 1,2 Гигабайта.

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

Потому что массив - непрерывный блок памяти. Не удивительно, что в (32-битной) системе не всегда найдётся непрерывный блок памяти размером 1.2 Гб. Для таких объёмов Вы вынуждены будете использовать списки, а не массивы.

Насколько я понимаю, BlackBox делает VirtualAlloc 1,5 Гбайт, а затем выделяет требуемые куски начиная с начала этого пространства. Пусть при загрузке BlackBox он использует и возможно фрагментирует первые 10 Мегабайт, но еще должно остаться 1526 Мегабайт. Этого должно быть достаточно чтобы выделить массив размером примерно 1145 Мегабайт.
Поправьте меня, если я ошибаюсь.