Оптимизация |
Оптимизация |
Caranthir |
13.12.2006 22:32
Сообщение
#41
|
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 0 |
блин....слабо пока, много получаетсся))
и....ээ...последние номера то не сортируются, кроме как по именам файлов, только первые 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 |
14.12.2006 9:54
Сообщение
#42
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Есть т.н. ковшовая, или поразрядная сортировка... Думаю, что наверняка это будет долго.Потом то же самое, но уже по второй с конца цифре (десятки), потом - с третьей и так до 10^8. А вот тут уже моя твоя Это когда сортируем неповторяющиеся числа. Мы можем однозначно сопоставить значеням этих чисел порядковые номера битов в битовом массиве, т.е. число 5432167 будет означать, что 5432167-й бит установлен в единицу. В итоге максимальный размер битового массива в байтах = максимальное значение числа / 8 бит. Потом проходим битовый массив с первого по последний и последовательно записываем номера битов установленных в единицу в сортируемый массив чисел. Допустим значения чисел не превышают 10^7, то размер битового массива в байтах (10^7)/8=1 250 000, что сопоставимо с размером массива хранения самих чисел (в нашей задаче 1 000 000 чисел * 4байта= 4Мб). Конечно если чисел немного, то данный алгоритм не эффективен с точки зрения потребляемой памяти, а если совсем мало - то и медленнее всех других алгоритмов, ибо размер битового массива никак не зависит от количества сортируемых чисел.Что такое битовая сортировка? ...8942629 Не стесняйся - программу в студию 8961911 8985513 8948864... -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Caranthir |
14.12.2006 12:41
Сообщение
#43
|
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 0 |
|
hiv |
14.12.2006 13:16
Сообщение
#44
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Это я твою смотрел и так отсортировалось_) Так так... значит у тебя дубликаты номеров есть... Тогда переделай код так: замени count на j
Могу только на С++ показать, на Pascal пока никак // запись результата сортировки в итоговый файлна // запись результата сортировки в итоговый файл и будет счастье -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Michael_Rybak |
14.12.2006 16:06
Сообщение
#45
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата Думаю, что наверняка это будет долго. А я думаю что не будет Это когда сортируем неповторяющиеся числа. Мы можем однозначно сопоставить значеням этих чисел порядковые номера битов в битовом массиве, т.е. число 5432167 будет означать, что 5432167-й бит установлен в единицу. В итоге максимальный размер битового массива в байтах = максимальное значение числа / 8 бит. Потом проходим битовый массив с первого по последний и последовательно записываем номера битов установленных в единицу в сортируемый массив чисел. Допустим значения чисел не превышают 10^7, то размер битового массива в байтах (10^7)/8=1 250 000, что сопоставимо с размером массива хранения самих чисел (в нашей задаче 1 000 000 чисел * 4байта= 4Мб). Конечно если чисел немного, то данный алгоритм не эффективен с точки зрения потребляемой памяти, а если совсем мало - то и медленнее всех других алгоритмов, ибо размер битового массива никак не зависит от количества сортируемых чисел. Угу, понятно. Прикольно. |
klem4 |
14.12.2006 19:06
Сообщение
#46
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Michael_Rybak |
14.12.2006 19:11
Сообщение
#47
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Вот битовой там, если не ошибаюсь, нет.
|
hiv |
15.12.2006 11:45
Сообщение
#48
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Вот второй вариант сортировки (просто супер):
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 килобайт ) Кол-во скачиваний: 357 Параметры машины: теже ЗЫ: К стати обновил первую версию - теперь повторяющихся номеров в итоговом файле не будет, даже если они были в исходном. См. пост 35. Во втором методе повторяющиеся номера не удаляются. Цитата Что такое битовая сортировка? В принципе это то что говорил Altair в посте 32, только индексом является просто 1 бит. Именно поэтому это избавляет от дубликатов номеров при сортировке. А битовой я ее сам назвал из-за того, что индексный массив - битовый. Только не бейте меня за это, я еще учусь Сообщение отредактировано: hiv - 15.12.2006 12:13 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Michael_Rybak |
15.12.2006 14:20
Сообщение
#49
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Круто, спасибо, что пробуешь
У меня еще вот какая идея возникла: можно твою битовую модифицировать, чтобы в память влезло. У тебя получилось (10^7)/8=1 250 000, что немного больше позволенного. Тогда можно пройтись по входному файлу два раза: первый раз обрабатывая только числа, меньшие 10^7/2, а остальные пропуская, а второй раз - наоборот; памяти тогда понадобится в 2 раза меньше. |
hiv |
15.12.2006 16:30
Сообщение
#50
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
2Michael_Rybak
Стыдно что сам до этого не додумался... Конечно попробую сделать этот вариант. Ну и ковшовую тоже попробуем -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Michael_Rybak |
15.12.2006 17:32
Сообщение
#51
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Давай, ждем
|
Caranthir |
17.12.2006 21:53
Сообщение
#52
|
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 0 |
немного переделал твою первую версию hiv:
(с) и результат прилагается) telsort1.zip ( 2.12 килобайт ) Кол-во скачиваний: 307 PS/ самому плохо думается |
hiv |
18.12.2006 9:42
Сообщение
#53
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
немного переделал твою первую версию hiv: Плохо переделал Во первых использование меток считается плохим тоном программирования на паскале и может вызывать кучу завуалированных ошибок. В вторых теряется смысл битовой сортировки, ты по индексу [tel[k]-sdvig] массива rad производишь обычный подсчет количества дубликатов номера tel[k], а потом еще их распечатываешь в итоговом файле в том же дублированном количестве... А как же условие задачи? Цитата Файл содержит не более n (от1 до 1.000.000) положительных чисел, каждое из которых не превышает 10^7 (телефонный номер). Все номера в файле уникальны. Присутствие дубликата считается ошибкой. Так что подумай на досуге Сообщение отредактировано: hiv - 18.12.2006 10:27 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
hiv |
18.12.2006 10:01
Сообщение
#54
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
В третьих: функция setlength() - не обнуляет массив, в итоге у тебя могут появиться номера, которых в твоем исходном никогда небыло... (сравни размеры твоего исходного файла и файла с результатами сортировки - первый признак наличия ошибки).
Сообщение отредактировано: hiv - 18.12.2006 10:27 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
hiv |
18.12.2006 13:31
Сообщение
#55
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Вот третий вариант сортировки (супер твикс):
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 килобайт ) Кол-во скачиваний: 326 Параметры машины: теже Сообщение отредактировано: hiv - 18.12.2006 13:31 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Michael_Rybak |
18.12.2006 14:57
Сообщение
#56
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Прикольно
|
hiv |
19.12.2006 17:13
Сообщение
#57
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Вот четвертый вариант сортировки (всем по ковшу):
Метод довольно подробно описан 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 килобайт ) Кол-во скачиваний: 300 Параметры машины: теже ЗЫ: Все я выдохся... Да и надоело уже... -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Michael_Rybak |
19.12.2006 17:22
Сообщение
#58
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
|
hiv |
19.12.2006 17:58
Сообщение
#59
|
Профи Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: 11 |
Спасибо!
-------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Caranthir |
21.12.2006 23:02
Сообщение
#60
|
Новичок Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: 0 |
Спасибо!!! Всем кто развивал тему. Особо признателен Michael_Rybak и hiv. Молодцы! |
Текстовая версия | 26.05.2024 11:43 |