![]() |
![]() ![]() |
![]() |
Caranthir |
![]()
Сообщение
#21
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
При сливании сравниваются только номера самих файлов.
Возможный вариант: в каждом файле иммется упорядоченный массив из чисел, таких как <само число>-<номер файла>, а в файл-результат записываются последовательно все числа из файлов +номер файла в порядке прочтения файла |
Michael_Rybak |
![]()
Сообщение
#22
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
А как ты разбросаешь по файлам, чтобы в первом файле шли подряд с первого по q-й, во втором - с q+1 по 2q-й и так далее?
|
Caranthir |
![]()
Сообщение
#23
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
прочитать весь массив, создать дополнительные файлы и разбрасать по ним числа(в процессе чтения), различающиеся первыми 2 цифрами
а читать с 1 по 2500000 и тд |
Michael_Rybak |
![]()
Сообщение
#24
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
А если все номера начинаются на одни и те же две цифры? Не, если номера случайные, тогда конечно. Я говорю про решение, работающее в худшем случае.
|
Caranthir |
![]()
Сообщение
#25
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
Хм...Ты прав.
Если одинаковых чисел >250000 брать эти чсла с меньшими разрядами)) |
Michael_Rybak |
![]()
Сообщение
#26
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
Чтобы работало в любом случае, надо
1) разбить просто подряд: первые q номеров - в первую группу, следующие q - во вторую и т.д. 2) по очереди каждую группу отсортировать и записать в файл 3) идти по файлам одновременно, выбирая на каждом шагу наименьший из текущих номеров в файлах Это похоже на сортировку слияниями (точнее, это и есть сортировка слияниями), только сливаем мы не два списка, а больше. Сообщение отредактировано: Michael_Rybak - 11.12.2006 23:39 |
Caranthir |
![]()
Сообщение
#27
|
![]() Новичок ![]() Группа: Пользователи Сообщений: 48 Пол: Мужской Репутация: ![]() ![]() ![]() |
Интересно... попробую
Спасибо |
hiv |
![]()
Сообщение
#28
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
Ну хорошо. Можно попробовать обоими способами и сравнить результаты
![]() Сообщение отредактировано: hiv - 12.12.2006 9:19 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Malice |
![]()
Сообщение
#29
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: ![]() ![]() ![]() |
Вот вам генератор файлов для экспериментов:
procedure generate; |
hiv |
![]()
Сообщение
#30
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
Вот вам генератор файлов для экспериментов: Входной формат файла - текстовый. Данные не должны повторяться. Я сам уже нагенерил файло, конечно ![]() -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Malice |
![]()
Сообщение
#31
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: ![]() ![]() ![]() |
|
Altair |
![]()
Сообщение
#32
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
ИМХО (по основной задаче)
Портируем текстовый файл в типизированный из longint'ов. (10^7 вместит), причем "на лету". (в памяти есть longint переменная, куда суммируем каждый раз текущую цифру * на 10 в соотв. степени, и обнуляем этот long при переходе через разделитель, записывая его при этом в long file) Никаких сортировок не производим! В момент сбрасывания очередного longint в типизированный файл, скидываем его, позиционировав указатель (seek) на его номер! (для этого заранее стоит выделить место под файл, это - 1 действие) Далее просто тупо копируем типизированный файл в текстовый, причем если место пусто, то пропускаем номер. Данный метод позволит получить результат без сортировки вообще. Метод применяют при ограниченных вычислительных способностях и больших объемах памяти (в нашем случае внешняя память доступна) Кратко я показал данный алгоритм на схеме: ![]() -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Michael_Rybak |
![]()
Сообщение
#33
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
Круто, риспект
![]() Только опять непонятно, как быть с номерами "009" и "000009" Но эту проблему, как я уже писал, можно решить дописыванием в начало длины. |
Altair |
![]()
Сообщение
#34
|
![]() Ищущий истину ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 4 824 Пол: Мужской Реальное имя: Олег Репутация: ![]() ![]() ![]() |
Цитата Только опять непонятно, как быть с номерами "009" и "000009" А такие номера могут существовать? Если да, дописывать после них 0 а не до! Я точно знаю, что 100 и 1000000 это один номер (проверял ![]() АТС работает "посимвольно" как только номер совпал - ура, соединили! Так что 100 и 100xxxx это одно! -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
hiv |
![]()
Сообщение
#35
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
Вот первый вариант.
Номера разбрасываются по 90 временным файлам в соответствии с первыми двумя цифрами номера. Везде буферный ввод вывод. Сортировка типа radix битовая (оказалась самой быстрой, ускоренный пузырек более 40сек работал). Итого: Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров). Время работы 4,157 сек. Кто быстрее? ![]() Максимум выделяемой динамической памяти на данные не превысил 742900 байт. Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров). Программа - ![]() (обновлена) Параметры машины: ОС - WinXP Процессор - Pentium4 1.8ГГц ОЗУ - 512 Мб Винт - 40Гб 7200об/мин ЗЫ: Берусь теперь за второй вариант, предложенный Michael_Rybak. Если у кого есть предложения по оптимизации готового кода - буду рад ![]() Сообщение отредактировано: hiv - 15.12.2006 10:17 -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Malice |
![]()
Сообщение
#36
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: ![]() ![]() ![]() |
|
hiv |
![]()
Сообщение
#37
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
Т.е. Все числа выровнены и добиты в начале 0-ми ? А как же пожарные/милиция ? ![]() Неа ![]() А на самом деле в телефонии нумерация символьная, и "добивать" слева нулями нельзя - тогда разные номера получаться. 01 и 001 - разные. Да и справа тоже нехорошо. На одной станции можно такой номер прописать 0101, а на другой 01010 - это тоже разное. Так что сказано 7-значка без нулей в начале, так и сделано. -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Michael_Rybak |
![]()
Сообщение
#38
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
Вот первый вариант. Номера разбрасываются по 90 временным файлам в соответствии с первыми двумя цифрами номера. Везде буферный ввод вывод. Сортировка типа radix битовая (оказалась самой быстрой, ускоренный пузырек более 40сек работал). Итого: Входной файл текстовый без повторяющихся номеров - 9 000 000 байт (1 000 000 номеров). Время работы 4,157 сек. Кто быстрее? ![]() Максимум выделяемой динамической памяти на данные не превысил 742900 байт. Выходной файл текстовый с отсортированными номерами - 9 000 000 байт (1 000 000 номеров). Программа - Параметры машины: ОС - WinXP Процессор - Pentium4 1.8ГГц ОЗУ - 512 Мб Винт - 40Гб 7200об/мин ЗЫ: Берусь теперь за второй вариант, предложенный Michael_Rybak. Если у кого есть предложения по оптимизации готового кода - буду рад ![]() Еще можно попробовать поразрядную сортировку (т.е. по 10 файликов разибвать и сливать 8 раз). Напишешь? |
hiv |
![]()
Сообщение
#39
|
![]() Профи ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 660 Пол: Мужской Реальное имя: Михаил Репутация: ![]() ![]() ![]() |
Еще можно попробовать поразрядную сортировку (т.е. по 10 файликов разибвать и сливать 8 раз). Напишешь? Поподробнее, а то твоя моя не понимай... ![]() Подумал на счет твоих постов 14 и 20 - с битовой сортировкой не получится: 7-мизначка = 9 000 000 номеров делим на 8 бит = 1125000 байт что больше 1Мбайта ![]() А использовать пузырек - не поможет (по объему около 40 сек выйдет). -------------------- Никогда не жадничай. Свои проблемы с любовью дари людям!
|
Michael_Rybak |
![]()
Сообщение
#40
|
Michael_Rybak ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: ![]() ![]() ![]() |
Цитата Поподробнее, а то твоя моя не понимай... ![]() Есть т.н. ковшовая, или поразрядная сортировка. Ковши = файлы. Есть 1 исходный ковш (большой), и 10 малых, пронумерованных от 0 до 9. Идем по большому ковшу, разбрасываем по малым все числа, в зависимости от последней цифры (младшего разряда). Потом сливаем малые ковши в порядке возрастания в большой ковш. Потом то же самое, но уже по второй с конца цифре (десятки), потом - с третьей и так до 10^8. Цитата Подумал на счет твоих постов 14 и 20 - с битовой сортировкой не получится: 7-мизначка = 9 000 000 номеров делим на 8 бит = 1125000 байт что больше 1Мбайта ![]() А использовать пузырек - не поможет (по объему около 40 сек выйдет). А вот тут уже моя твоя ![]() Что такое битовая сортировка? |
![]() ![]() |
![]() |
Текстовая версия | 22.06.2025 11:02 |