сортировка данных в очень больших файлах(больше 4 гиг)
Вощем тема, и раскрыла всю задачу. Если кто-то уже такое делал или есть идеи - можете плиз поделиться. Заранее благодарю :)
Вобщем я нашла кой-чего, но если можно поподробнее. или ссылку;)
Вобщем я нашла кой-чего, но если можно поподробнее. или ссылку;)
Глядя на вопрос у меня предложение только одно - делать сортировку в несколько потоков.
1. Описываете функцию сортировки для одного фрагмента данных в большом файле:
DWORD __stdcall DataThread (void *param). Что будет внутри - чтение фрагмента данных из файла, алгоритм сортировки, запись отсортированных данных обратно в файл. Запись, я думаю, должна производиться с той же позиции, с которой производилось чтение необработанных данных.
2. Открываете большой файл с помощью CreateFile с флагом FILE_SHARE_READ.
3. Запускаете несколько параллельных потоков, описанных функцией DataThread, с помощью CreateThread. В качестве параметра для DataThread можно передать структуру. Поля этой структуры должны указывать смещение относительно начала большого файла и длинну обрабатываемого фрагмента.
В итоге получится что большой файл обрабатывается не целиком от начала до конца в одном потоке, а сразу делится на несколько частей, данные которых обрабатываются параллельно.
1. Описываете функцию сортировки для одного фрагмента данных в большом файле:
DWORD __stdcall DataThread (void *param). Что будет внутри - чтение фрагмента данных из файла, алгоритм сортировки, запись отсортированных данных обратно в файл. Запись, я думаю, должна производиться с той же позиции, с которой производилось чтение необработанных данных.
2. Открываете большой файл с помощью CreateFile с флагом FILE_SHARE_READ.
3. Запускаете несколько параллельных потоков, описанных функцией DataThread, с помощью CreateThread. В качестве параметра для DataThread можно передать структуру. Поля этой структуры должны указывать смещение относительно начала большого файла и длинну обрабатываемого фрагмента.
В итоге получится что большой файл обрабатывается не целиком от начала до конца в одном потоке, а сразу делится на несколько частей, данные которых обрабатываются параллельно.
Цитата: OpenMind
Глядя на вопрос у меня предложение только одно - делать сортировку в несколько потоков.
С одним файлом не поможет. Узкое место - не процессор. Диск.
Сортировать нужно в несколько этапов.
1) Разбиваем исходный файл на несколько меньших по размерам (200МБ) и сортируем их (можно быстрой сортировкой, можно сортировкой Шелла).
2) Производим объединение всех упорядоченных последовательностей (наших 200МБ-фйлов).
На каждом этапе в принципе допускается распараллеивание.
При таких объемах стоит использовать базы данных...
А по существу: я бы даже сказал, что узкое место оператива+диск. Целиком массив в оперативку мы закинуть не можем (по крайней мере на 32 битных системах), следовательно надо делать, что предлагает Hardcase: дробить файл, а потом совмещать... Например просматривая поочередно по одному элементу в кусках собирать общий файл.
А по существу: я бы даже сказал, что узкое место оператива+диск. Целиком массив в оперативку мы закинуть не можем (по крайней мере на 32 битных системах), следовательно надо делать, что предлагает Hardcase: дробить файл, а потом совмещать... Например просматривая поочередно по одному элементу в кусках собирать общий файл.
Самое сложное - аккуратно слить. Самым эффективным является использование сетей сортировки (иногда также называется "сетью компараторов слияния"). Отлично описано в Искусстве программирования Кнута.
Добавление
Оговорился. Сети эффективно использовать, когда невозможно на одном вычислительном узле хранить весь объем данных. Поэтому в данном случае, как сказал GreenRiver, можно поочередно просматривать все файлы. Точнее, открыть сразу все и считывать по элементу. Записывать в результат наименьший.
Добавление
Оговорился. Сети эффективно использовать, когда невозможно на одном вычислительном узле хранить весь объем данных. Поэтому в данном случае, как сказал GreenRiver, можно поочередно просматривать все файлы. Точнее, открыть сразу все и считывать по элементу. Записывать в результат наименьший.
Спасиб всем. Буду начинать, что т делать... мдя...над еще как-то придумать подробить этот файлик правильно на части, отсортировать эти части, а потом как-то их меж собой... лана, что т придумаю. еще раз пасиб ;)
[QUOTE=charizma]над еще как-то придумать подробить этот файлик правильно на части[/QUOTE]Спроецировать его в память
