OberonCore
https://forum.oberoncore.ru/

Сортировка, если массив почти отсортирован
https://forum.oberoncore.ru/viewtopic.php?f=27&t=2437		 Страница 2 из 2
Автор:  Сергей Губанов [ Понедельник, 15 Март, 2010 14:27 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован
Рестартуйте ББ. С чистого листа 1.2 гига непрерывного пространства он найдёт со значительно большей вероятностью. Но сделать это повторно сможет едва ли.
Автор:  Rifat [ Понедельник, 15 Март, 2010 14:29 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован
Мой тест не работает через раз, иногда он все-таки выделяет 1,2 Гбайта.
Автор:  Rifat [ Понедельник, 15 Март, 2010 14:31 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован
Сергей Губанов писал(а):
Рестартуйте ББ. С чистого листа 1.2 гига непрерывного пространства он найдёт со значительно большей вероятностью. Но сделать это повторно сможет едва ли.

Видимо придется сделать, что-то типа списка или дерева, раз большие массивы не всегда выделяются.
Автор:  Роман М. [ Вторник, 16 Март, 2010 12:15 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован
Советую ознакомиться с "Алгоритмами и структурами данных" Вирта. Глава 2.4. про сортировку последовательностей. На мой взгляд, материал отвечает требованиям задачи.
Автор:  Роман М. [ Четверг, 18 Март, 2010 20:28 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован
Добавлю ещё. Держать в памяти все 3.0е7 записей в памяти мне кажется неразумным решением. Полагаю, нужна БД. Пусть SQLite или RRD tool (если история). Создай индексы и производи себе нужные выборки. Зачем велосипед изобретать?
А за чрезмерное потребление памяти пора ввести систему штрафов.
Сортировать массив заново после каждого добавления мне кажется диким методом. А если есть мат. зависимость между числами, то и подавно.
Автор:  Rifat [ Пятница, 19 Март, 2010 09:15 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован
Не могу согласиться с последним высказыванием. Во-первых, есть знаменитая дилемма память - скорость. Мы можем сэкономить память, но потеряем в скорости, или же мы можем выиграть в скорости, но будем использовать больше памяти. И каждый уже сам выбирает что важнее память или скорость. Лично для меня скорость важнее.
Во-вторых, использовать БД, там где она не нужна, считаю не разумным в квадрате. К одной из книг видел, таблицу, где приводиться порядок времени для обращения к оперативной памяти, файлу или базе данных. Так вот, считывание из файла на порядок или на два порядка медленнее, чем считывать из памяти, а делать выборку из базы данных еще примерно на порядок медленнее, чем считывать из файла.
В-третьих, база данных тоже использует оперативную память. И возможно, что программа и база данных будут вместе требовать больше памяти, чем только программа.
Автор:  Роман М. [ Пятница, 19 Март, 2010 11:55 ]
Заголовок сообщения:  Re: Сортировка, если массив почти отсортирован
Можно не соглашаться со мной, однако,
  1. Использование памяти должно быть с умом, так как размер 2ГБ не является столь распространённым среди ПК. И не факт , что система сможет себе позволить отдать кусок памяти размером более 1.2 ГБ.
    Не стоит также забывать, что перерасход памяти ведёт к интенсивному использованию файла/раздела подкачки системой, что резко снизит её производительность вместе с программой.
  2. В БД используются различные техники оптимизации расхода памяти и быстродействия, использующие особенности систем, могущие оказаться гораздо эффективнее многочисленных сортировок с переразмещениями данных в памяти твоей программы по скорости и объёму потребляемой памяти. Создание индексов нужных полей позволит находить нужные записи одним запросом.
    Во всяком случае, не стоит отказывать себе в проверке БД на деле, особенно, если данные используются на продолжительный срок. Кроме того, SQLite, к примеру, позволяет держать данные полностью в памяти, если это так нужно (плюс она ещё и бесплатна).

Насчёт природы происхождения данных - ничего не было сказано. Будем считать, что данные случайны. Если это не так, то стоит перерассматривать дизайн программы.
Страница 2 из 2 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/