Оптимизация Опции

[Caranthir]

блин....слабо пока, много получаетсся))
и....ээ...последние номера то не сортируются, кроме как по именам файлов, только первые


8971947
8962540
8916484
8912716
8941187
8915338
8971871
8923658
8938009
8929848
8910452
8982093
8940902
8941257
8942629
8961911
8985513
8948864
8976854
8953015
8960296
8933310
8987267
8987947
8982026
8912167
8950310
8938580
8982516
8981755
8987127
8936605
8994136

[hiv]

Есть т.н. ковшовая, или поразрядная сортировка...
Потом то же самое, но уже по второй с конца цифре (десятки), потом - с третьей и так до 10^8.

Думаю, что наверняка это будет долго.

А вот тут уже моя твоя
Что такое битовая сортировка?

Это когда сортируем неповторяющиеся числа. Мы можем однозначно сопоставить значеням этих чисел порядковые номера битов в битовом массиве, т.е. число 5432167 будет означать, что 5432167-й бит установлен в единицу. В итоге максимальный размер битового массива в байтах = максимальное значение числа / 8 бит. Потом проходим битовый массив с первого по последний и последовательно записываем номера битов установленных в единицу в сортируемый массив чисел. Допустим значения чисел не превышают 10^7, то размер битового массива в байтах (10^7)/8=1 250 000, что сопоставимо с размером массива хранения самих чисел (в нашей задаче 1 000 000 чисел * 4байта= 4Мб). Конечно если чисел немного, то данный алгоритм не эффективен с точки зрения потребляемой памяти, а если совсем мало - то и медленнее всех других алгоритмов, ибо размер битового массива никак не зависит от количества сортируемых чисел.

...8942629
8961911
8985513
8948864...

Не стесняйся - программу в студию

[Caranthir]

Не стесняйся - программу в студию

Это я твою смотрел и так отсортировалось_)

Могу только на С++ показать, на Pascal пока никак

[hiv]

Это я твою смотрел и так отсортировалось_)
Могу только на С++ показать, на Pascal пока никак

Так так... значит у тебя дубликаты номеров есть... Тогда переделай код так: замени count на j

    // запись результата сортировки в итоговый файл
    ps:=pbuff;
    pe:=pbuff+buff_count;
    for k:=0 to count-1 do
    begin

на

    // запись результата сортировки в итоговый файл
    ps:=pbuff;
    pe:=pbuff+buff_count;
    for k:=0 to j-1 do
    begin

и будет счастье

[Michael_Rybak]

Думаю, что наверняка это будет долго.

А я думаю что не будет

Это когда сортируем неповторяющиеся числа. Мы можем однозначно сопоставить значеням этих чисел порядковые номера битов в битовом массиве, т.е. число 5432167 будет означать, что 5432167-й бит установлен в единицу. В итоге максимальный размер битового массива в байтах = максимальное значение числа / 8 бит. Потом проходим битовый массив с первого по последний и последовательно записываем номера битов установленных в единицу в сортируемый массив чисел. Допустим значения чисел не превышают 10^7, то размер битового массива в байтах (10^7)/8=1 250 000, что сопоставимо с размером массива хранения самих чисел (в нашей задаче 1 000 000 чисел * 4байта= 4Мб). Конечно если чисел немного, то данный алгоритм не эффективен с точки зрения потребляемой памяти, а если совсем мало - то и медленнее всех других алгоритмов, ибо размер битового массива никак не зависит от количества сортируемых чисел.

Угу, понятно. Прикольно.

[klem4]

Что такое битовая сортировка?

Методы сортировок

[Michael_Rybak]

Вот битовой там, если не ошибаюсь, нет.

[hiv]

Вот второй вариант сортировки (просто супер):
1) Читаем исходный файл насколько влазиет в память, потом сортируем и сохраняем во временный файл, следующая итерация чтения исходного файла также сортируется и заносится в следующий временный файл. Т.о. чем меньше памяти на данные мы выделяем, тем больше временных файлов. Сортировка проводится методом "Быстрой сортировки" описанной в FAQ и взятой от туда
2) Сливаем все временные файлы в итоговый, каждый раз выбирая минимальное значение среди прочтенных из всех временных файлов.
Также везде буферный ввод вывод.
Спасибо Volvo за FAQ и Michael_Rybak за метод сортировки слияниями файлов. См. пост 26

Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 3,421 сек. Кто еще быстрее? cool.gif
Максимум выделяемой динамической памяти на данные не превысил 970372 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа -  telsort2.zip ( 2.98 килобайт ) Кол-во скачиваний: 536

Параметры машины: теже

ЗЫ: К стати обновил первую версию - теперь повторяющихся номеров в итоговом файле не будет, даже если они были в исходном. См. пост 35.
Во втором методе повторяющиеся номера не удаляются.

Что такое битовая сортировка?

В принципе это то что говорил Altair в посте 32, только индексом является просто 1 бит. Именно поэтому это избавляет от дубликатов номеров при сортировке. А битовой я ее сам назвал из-за того, что индексный массив - битовый. Только не бейте меня за это, я еще учусь

Сообщение отредактировано: hiv - 15.12.2006 16:13

[Michael_Rybak]

Круто, спасибо, что пробуешь

У меня еще вот какая идея возникла: можно твою битовую модифицировать, чтобы в память влезло. У тебя получилось (10^7)/8=1 250 000, что немного больше позволенного. Тогда можно пройтись по входному файлу два раза: первый раз обрабатывая только числа, меньшие 10^7/2, а остальные пропуская, а второй раз - наоборот; памяти тогда понадобится в 2 раза меньше.

[hiv]

2Michael_Rybak
Стыдно что сам до этого не додумался... Конечно попробую сделать этот вариант. Ну и ковшовую тоже попробуем

[Michael_Rybak]

Давай, ждем

[Caranthir]

немного переделал твою первую версию hiv:
(с) и результат прилагается)
 telsort1.zip ( 2.12 килобайт ) Кол-во скачиваний: 430


PS/ самому плохо думается

[hiv]

немного переделал твою первую версию hiv:

Плохо переделал
Во первых использование меток считается плохим тоном программирования на паскале и может вызывать кучу завуалированных ошибок.
В вторых теряется смысл битовой сортировки, ты по индексу [tel[k]-sdvig] массива rad производишь обычный подсчет количества дубликатов номера tel[k], а потом еще их распечатываешь в итоговом файле в том же дублированном количестве... А как же условие задачи?

Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой.

Так что подумай на досуге

Сообщение отредактировано: hiv - 18.12.2006 14:27

[hiv]

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

Сообщение отредактировано: hiv - 18.12.2006 14:27

[hiv]

Вот третий вариант сортировки (супер твикс):
1) Определяем диапазон номеров которые будем читать и сразу сортировать битовой сортировкой.
2) Прочитываем весь файл и обрабатываем только те номера, которые входят в диапазон.
3) Сохраняем результат сортировки текущего диапазона в итоговый файл.
4) Берем следующий диапазон чисел и заново перечитываем исходный файл, т.е. переходим к пункту 2 Заканчиваем тогда, когда диапазон рассматриваемых чисел выходит за максимальный номер, в данном случае 10^7.
Никаких временных файлов на диске не создается. В данной задаче исходный файл прочитывается всего два раза. Также везде буферный ввод вывод.
Спасибо Michael_Rybak за подсказку. См. пост 49

Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 3,657 сек. Что почти догнало метод быстрой сортировки cool.gif
Максимум выделяемой динамической памяти на данные не превысил 978556 байт.
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа -  telsort3.zip ( 2.32 килобайт ) Кол-во скачиваний: 459

Параметры машины: теже

Сообщение отредактировано: hiv - 18.12.2006 17:31

[Michael_Rybak]

Прикольно

[hiv]

Вот четвертый вариант сортировки (всем по ковшу):
Метод довольно подробно описан Michael_Rybak в этой теме (см. пост 40). Добавлю, что не использовал слитие номеров в общий ковш, как рассказывал Michael_Rybak, а просто считывал последовательно из 10 временных файлов и одновременно записывал в другие 10 временных файлов. Потом на каждом шаге просто менял эти две группы временных файлов местами, т.е. то что записывал - начинал читать от туда и наоборот. 20 временных файлов - это не так много
Также везде буферный ввод вывод.

Итого:
Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров).
Время работы 3,765 сек. Что обогнало первый метод я в шоке думал что медленнее будет.
Максимум выделяемой динамической памяти на данные не превысил 376 404 байт. (в принципе ничего кроме буферов чтения записи)
Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров).
Программа -  telsort4.zip ( 2.67 килобайт ) Кол-во скачиваний: 442

Параметры машины: теже

ЗЫ: Все я выдохся... Да и надоело уже...

[Michael_Rybak]

а просто считывал последовательно из 10 временных файлов и одновременно записывал в другие 10 временных файлов

ЗЫ: Все я выдохся... Да и надоело уже...

Ничего себе выдохся Перепробовал столько Супер!

[hiv]

Спасибо!

[Caranthir]

Спасибо!!!

Всем кто развивал тему.

Особо признателен Michael_Rybak и hiv. Молодцы!