OberonCore
https://forum.oberoncore.ru/

Сортировка, если массив почти отсортирован
https://forum.oberoncore.ru/viewtopic.php?f=27&t=2437
Страница 1 из 2

Автор:  Rifat [ Понедельник, 15 Март, 2010 11:04 ]
Заголовок сообщения:  Сортировка, если массив почти отсортирован

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

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

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

Автор:  Rifat [ Понедельник, 15 Март, 2010 11:16 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Автор:  Илья Ермаков [ Понедельник, 15 Март, 2010 11:16 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

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

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

Автор:  Rifat [ Понедельник, 15 Март, 2010 11:26 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

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

Автор:  Александр Ильин [ Понедельник, 15 Март, 2010 11:57 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

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

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

Автор:  Александр Ильин [ Понедельник, 15 Март, 2010 12:25 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Автор:  Валерий Лаптев [ Понедельник, 15 Март, 2010 12:42 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Автор:  Александр Ильин [ Понедельник, 15 Март, 2010 12:45 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

Валерий Лаптев писал(а):
А можно сделать просто вставку в дерево обоих массивов, а потом из дерева обходом - опять массив.
Что такое "вставка в дерево" и сколько это потребует памяти?

Автор:  Rifat [ Понедельник, 15 Март, 2010 12:48 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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


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

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

Автор:  Сергей Губанов [ Понедельник, 15 Март, 2010 13:07 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

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

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

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

Автор:  Rifat [ Понедельник, 15 Март, 2010 13:12 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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


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

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

Автор:  Alexey Veselovsky [ Понедельник, 15 Март, 2010 13:14 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

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

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

Автор:  AVC [ Понедельник, 15 Март, 2010 13:19 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Автор:  Rifat [ Понедельник, 15 Март, 2010 13:42 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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


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

Автор:  Info21 [ Понедельник, 15 Март, 2010 13:50 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Автор:  Сергей Губанов [ Понедельник, 15 Март, 2010 13:52 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Автор:  AVC [ Понедельник, 15 Март, 2010 13:59 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

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

Автор:  Rifat [ Понедельник, 15 Март, 2010 14:03 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

Сергей Губанов писал(а):
Как резко меняется постановка задачи.

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

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

   IMPORT Log;

   TYPE
      Rec = RECORD
         f0, f1, f2: INTEGER;
      END;
   
   VAR Mas: POINTER TO ARRAY OF Rec;
   
   PROCEDURE Do*;
   VAR i: INTEGER;
   BEGIN
      NEW(Mas, 100000000);
      FOR i := 0 TO LEN(Mas)-1 DO
         Mas[i].f0 := i;
      END;
      Log.String("Finish"); Log.Ln;
   END Do;

END TestMemory.

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

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

Автор:  Сергей Губанов [ Понедельник, 15 Март, 2010 14:09 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Автор:  Rifat [ Понедельник, 15 Март, 2010 14:14 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован

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

Страница 1 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/