Сообщение Re: Как правильно сортировать содержимое больших файлов? от 04.09.2022 11:57
Изменено 04.09.2022 12:17 artelk
Re: Как правильно сортировать содержимое больших файлов?
Здравствуйте, _FRED_, Вы писали:
_FR>Решение: https://github.com/ViIvanov/DataSort
Мое: https://github.com/artelk/RowsSort
Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
Последний пункт используется, чтобы примерно равномерно поделить строки по первым символам.
Агоритм:
1. Разбиваем строки на множество чанков. Критерий разбивки — первый символ плюс старшие 3 бита второго символа.
2. Строки в чанки пишутся в бинарном формате: <strLenByte><string><num8bytes>. Это нужно, чтоб размер файлов немного уменьшить. Первый символ у строк отрезается, т.к. он общий у всех строк чанка. Лишний пробел, точка и \r\n тоже не пишется. Экономим на спичках
3. По очереди читаем файлы чанков в лексикографическом порядке, сортируем их и записываем в результирующий файл.
Для сортировки чанков реализовал Radix Sort. Чанки открываются как memory mapped files. Много unsafe и указателей
На моем железе сортировшик FREDа на файле 1Гб работает за 2 минуты, а мой за 40 секунд.
Возможно, на другом железе будет обратная картина, т.к. я ничего не параллелил и на моем ноуте узкое место это HDD (хотя саму сортировку можно было бы как-то в параллель IO сделать).
На Очень больших файлах размер чанков может оказаться слишком большими не влезать в память, так что алгоритм разбивки придется доточить.
Просьба кому не лень погонять у себя и рассказать
_FR>Решение: https://github.com/ViIvanov/DataSort
Мое: https://github.com/artelk/RowsSort
Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
Последний пункт используется, чтобы примерно равномерно поделить строки по первым символам.
Агоритм:
1. Разбиваем строки на множество чанков. Критерий разбивки — первый символ плюс старшие 3 бита второго символа.
2. Строки в чанки пишутся в бинарном формате: <strLenByte><string><num8bytes>. Это нужно, чтоб размер файлов немного уменьшить. Первый символ у строк отрезается, т.к. он общий у всех строк чанка. Лишний пробел, точка и \r\n тоже не пишется. Экономим на спичках
3. По очереди читаем файлы чанков в лексикографическом порядке, сортируем их и записываем в результирующий файл.
Для сортировки чанков реализовал Radix Sort. Чанки открываются как memory mapped files. Много unsafe и указателей
На моем железе сортировшик FREDа на файле 1Гб работает за 2 минуты, а мой за 40 секунд.
Возможно, на другом железе будет обратная картина, т.к. я ничего не параллелил и на моем ноуте узкое место это HDD (хотя саму сортировку можно было бы как-то в параллель IO сделать).
На Очень больших файлах размер чанков может оказаться слишком большими не влезать в память, так что алгоритм разбивки придется доточить.
Просьба кому не лень погонять у себя и рассказать
Re: Как правильно сортировать содержимое больших файлов?
Здравствуйте, _FRED_, Вы писали:
_FR>Решение: https://github.com/ViIvanov/DataSort
Мое: https://github.com/artelk/RowsSort
Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
Последний пункт используется, чтобы примерно равномерно поделить строки по первым символам.
Агоритм:
1. Разбиваем строки на множество чанков. Критерий разбивки — первый символ плюс старшие 3 бита второго символа.
2. Строки в чанки пишутся в бинарном формате: <strLenByte><string><num8bytes>. Это нужно, чтоб размер файлов немного уменьшить. Первый символ у строк отрезается, т.к. он общий у всех строк чанка. Лишний пробел, точка и \r\n тоже не пишется. Экономим на спичках
Если размер алфавита маленький, можно было бы как-то меньшим числом битов символы кодировать, чтобы еще сильнее сжать.
3. По очереди читаем файлы чанков в лексикографическом порядке, сортируем их и записываем в результирующий файл.
Для сортировки чанков реализовал Radix Sort. Чанки открываются как memory mapped files. Много unsafe и указателей
На моем железе сортировшик FREDа на файле 1Гб работает за 2 минуты, а мой за 40 секунд.
Возможно, на другом железе будет обратная картина, т.к. я ничего не параллелил и на моем ноуте узкое место это HDD (хотя саму сортировку можно было бы как-то в параллель IO сделать).
На Очень больших файлах размер чанков может оказаться слишком большими не влезать в память, так что алгоритм разбивки придется доточить.
Просьба кому не лень погонять у себя и рассказать
_FR>Решение: https://github.com/ViIvanov/DataSort
Мое: https://github.com/artelk/RowsSort
Сделано в предположение, что файлы ASCII, числа укладываются в ulong, стоки длиной от 2 до 256 и строки случайны (!).
Последний пункт используется, чтобы примерно равномерно поделить строки по первым символам.
Агоритм:
1. Разбиваем строки на множество чанков. Критерий разбивки — первый символ плюс старшие 3 бита второго символа.
2. Строки в чанки пишутся в бинарном формате: <strLenByte><string><num8bytes>. Это нужно, чтоб размер файлов немного уменьшить. Первый символ у строк отрезается, т.к. он общий у всех строк чанка. Лишний пробел, точка и \r\n тоже не пишется. Экономим на спичках
Если размер алфавита маленький, можно было бы как-то меньшим числом битов символы кодировать, чтобы еще сильнее сжать.
3. По очереди читаем файлы чанков в лексикографическом порядке, сортируем их и записываем в результирующий файл.
Для сортировки чанков реализовал Radix Sort. Чанки открываются как memory mapped files. Много unsafe и указателей
На моем железе сортировшик FREDа на файле 1Гб работает за 2 минуты, а мой за 40 секунд.
Возможно, на другом железе будет обратная картина, т.к. я ничего не параллелил и на моем ноуте узкое место это HDD (хотя саму сортировку можно было бы как-то в параллель IO сделать).
На Очень больших файлах размер чанков может оказаться слишком большими не влезать в память, так что алгоритм разбивки придется доточить.
Просьба кому не лень погонять у себя и рассказать