OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Суббота, 07 Декабрь, 2019 06:45

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Понедельник, 15 Март, 2010 11:04 

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 11:16 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 858
Откуда: Казань
Сейчас подумал, о том, что можно 1 миллион записей в конце отсортировать, а затем попытаться слить 2 отсортированных блока.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 11:16 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9161
Откуда: Россия, Орёл
Сортируете последний миллион любым алгоритмом.

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 11:26 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 858
Откуда: Казань
Если один 15 миллионый блок отсортирован, а затем 1 миллионный блок тоже отсортирован, наверно, можно применить пузырьковую сортировку, которая 1 раз пройдет и все расставит на свои места (хочется так думать, надо реализовать и посмотреть, что получится).

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 11:57 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2318
Откуда: Россия, Томск
Многое зависит от задачи, от того, что за данные добавляются в конец, и от того, что "дешевле" - сравнение или обмен элементов местами.

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 12:25 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 12:42 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3121
Откуда: Астрахань
"Диффузия" - это нормальный алгоритм слияния двух отсортированных массивов. В С++ такое стандартно есть.
А можно сделать просто вставку в дерево обоих массивов, а потом из дерева обходом - опять массив.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 12:45 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2318
Откуда: Россия, Томск
Валерий Лаптев писал(а):
А можно сделать просто вставку в дерево обоих массивов, а потом из дерева обходом - опять массив.
Что такое "вставка в дерево" и сколько это потребует памяти?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 12:48 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 858
Откуда: Казань
Валерий Лаптев писал(а):
"Диффузия" - это нормальный алгоритм слияния двух отсортированных массивов. В С++ такое стандартно есть.
А можно сделать просто вставку в дерево обоих массивов, а потом из дерева обходом - опять массив.


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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:07 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Если Вы используете именно массив, то для того чтобы добавить в него элементы Вам всё-равно придётся разместить в памяти другой массив -- большего размера. А раз Вам всё равно придётся размещать в памяти массив большего размера, то для сортировки используйте слияние двух отсортированных массивов.

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:12 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 858
Откуда: Казань
Сергей Губанов писал(а):
Однако вызывает недоумение почему для 30-миллионных контейнеров выбран именно массив, а не список. В случае списка реаллокация данных была бы не нужна вовсе. Вы больше времени угрохаете на реаллокацию, чем на слияние как таковое.


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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:14 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Кроме того, если у нас 30 миллионов ЧИСЕЛ (int'ы скажем), то накладные расходы (по памяти) списка будут слишком большие. В отличие от массива.

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:19 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:42 

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


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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:50 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8209
Откуда: Троицк, Москва
Rifat писал(а):
Дерево - это конечно тоже вариант, но он сложнее в реализации.
Да ладно... возьмите с диска "Алгоритмов...", там всё работает прямо на КП. Подпилите чуток. Делов-то.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:52 
Аватара пользователя

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 13:59 
Аватара пользователя

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 14:03 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 858
Откуда: Казань
Сергей Губанов писал(а):
Как резко меняется постановка задачи.

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

На самом деле сейчас проблема в другом. Я уже решил, что проще будет не экономить компьютерную память, а выделить дополнительный блок в 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 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Потому что массив - непрерывный блок памяти. Не удивительно, что в (32-битной) системе не всегда найдётся непрерывный блок памяти размером 1.2 Гб. Для таких объёмов Вы вынуждены будете использовать списки, а не массивы.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 15 Март, 2010 14:14 

Зарегистрирован: Пятница, 13 Март, 2009 16:36
Сообщения: 858
Откуда: Казань
Насколько я понимаю, BlackBox делает VirtualAlloc 1,5 Гбайт, а затем выделяет требуемые куски начиная с начала этого пространства. Пусть при загрузке BlackBox он использует и возможно фрагментирует первые 10 Мегабайт, но еще должно остаться 1526 Мегабайт. Этого должно быть достаточно чтобы выделить массив размером примерно 1145 Мегабайт.
Поправьте меня, если я ошибаюсь.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB