 Сортировка большого кол-ва элементов., >10000 |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
  |
| iRish88 |
 30.09.2007 15:28
Сообщение
#1
|
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Реальное имя: Николай Репутация:  0   |
День добрый.
Столкнулся с такой проблемой, нужно отсортировать 100000 (сто тысяч) элементов. В массив не лезет. Организовал работу с файлом (с 2-я, если быть точным) - работает очень медленно. Подумал на постоянные read/write, оптимизировал, считывает из файла сразу большое кол-во элементов в массив, сортирует, сливает в файл. Быстрее почти не стало. Я так понимаю такой варинт оптимизировать для работы со 100000 эл-ми не удастя... В памяти сортировать тоже не получается, грешит на нехватку места. Поискал, увидел, что паскаль дает не больше 640 кб на всю программу. Подскажите, какие есть варианты сортировки такой большой штуковины? Спасибо. |
   |
 
|
| volvo |
30.09.2007 15:33
Сообщение
#2
|
|
Гость |
100000 элементов какого типа?
|
|
|
|
| мисс_граффити |
30.09.2007 15:54
Сообщение
#3
|
 просто человек  Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
внешние сортировки....
поищи по форуму (вроде было) сортировку слиянием, например. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
|
|
|
| volvo |
30.09.2007 15:56
Сообщение
#4
|
|
Гость |
Цитата внешние сортировки.... Это и есть: Цитата Организовал работу с файлом (с 2-я, если быть точным) - работает очень медленно Для того, чтобы ускорить - надо знать, ЧТО сортируется... Иначе Google -> "Форум телепатов" |
|
|
|
| hardcase |
30.09.2007 18:35
Сообщение
#5
|
 code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Цитата(iRish88 @ 30.09.2007 16:28)  Подскажите, какие есть варианты сортировки такой большой штуковины? Сто тысяч элементов (при размере 1 элемента ~100 байт) это не так уж и много. Переходи на 32-битный компилятор, и будет тебе щщастье! -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
|
|
|
| мисс_граффити |
30.09.2007 18:49
Сообщение
#6
|
|
просто человек Группа: Модераторы Сообщений: 3 641 Пол: Женский Реальное имя: Юлия Репутация: 55 |
Цитата(volvo @ 30.09.2007 16:56) Это и есть... Ну, можно на файлах сортировку вставками реализовать. Или пузырьком. Выбором - используя 2 файла. Работать будет.... К сожалению, автор не уточнил, каким алгоритмом пользуется. -------------------- Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения! |
|
|
|
| iRish88 |
30.09.2007 19:41
Сообщение
#7
|
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Реальное имя: Николай Репутация: 0 |
Прошу прощения, в голове туча мыслей, поэтому пост такой сумбурный. Пока что применял метод пузырька, потому что в работе с отдельными "блоками" другими известными мне алгоритмами (правда не так много я их знаю) будет пользоваться, как мне кажется, неудобно.
Элемент - вещественная переменная. Попробовал загонять в нетипизированный файл сразу по 10000 эл-тов за раз... в ходе написания кода, понял что могу ограничить элементы типом single (4 байта) и уложиться в отведенные 500+ Кб.  Всем спасибо, кажется проблем возникнуть больше не должно. По крайней мере с общим объемом. Сообщение отредактировано: iRish88 - 30.09.2007 19:42 |
|
|
|
| volvo |
30.09.2007 19:59
Сообщение
#8
|
|
Гость |
Цитата кажется проблем возникнуть больше не должно Проблемы возникнут с тем, что ты не сможешь за один раз выделить блок больше 64К (ни статически, ни динамически), но это решается довольно просто... |
|
|
|
| iRish88 |
30.09.2007 20:34
Сообщение
#9
|
|
Группа: Пользователи Сообщений: 3 Пол: Мужской Реальное имя: Николай Репутация: 0 |
Ну я сейчас реализовываю массив из 10 нетипизированных указателей по 40 Кб. Как раз на 100000 синглов хватит.
|
|
|
|
| hardcase |
30.09.2007 21:19
Сообщение
#10
|
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Цитата(iRish88 @ 30.09.2007 20:41) Элемент - вещественная переменная. Сомневаюсь, что за приемлемое время можно отсортировать 100000 элементов пузырьком через файлы... Есть алгоритм Быстрой сортировки. Результаты сортировки каждого блока можно попарно слить как упорядоченные последовательности. Сообщение отредактировано: hardcase - 30.09.2007 21:22 -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
|
|
|
| volvo |
30.09.2007 21:28
Сообщение
#11
|
|
Гость |
Во-первых, кто сказал, что будет использоваться именно метод пузырька? hardcase, тебе что, автор об этом сообщил? Или это чья-то творческая придумка? Так вот не надо ничего придумывать...
Кстати, ничего более НЕкорректного, чем посоветовать для сортировки 100000 (СТА ТЫСЯЧ!!!) элементов РЕКУРСИВНУЮ быструю сортировку я не видел...  Тем более НЕ в разделе 32-битных компиляторов (хотя и там тоже ресурсы не безграничны)(Только не надо ничего говорить об избавлении от рекурсии в QuickSort... Это потребует ЕЩЕ дополнительной памяти, которая и так на пределе...) |
|
|
|
| Michael_Rybak |
3.10.2007 3:26
Сообщение
#12
|
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата(iRish88 @ 30.09.2007 19:41) Пока что применял метод пузырька, потому что в работе с отдельными "блоками" другими известными мне алгоритмами (правда не так много я их знаю) будет пользоваться, как мне кажется, неудобно. крайней мере с общим объемом. Цитата(volvo @ 30.09.2007 21:28) Во-первых, кто сказал, что будет использоваться именно метод пузырька? hardcase, тебе что, автор об этом сообщил? |
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 20.07.2025 17:36 |