Как и планировал, опробовал второй способ сортировки, а именно сортировку подсчетом. Кода в разы меньше, сам код куда проще, но… Крайне плохо масштабируемое решение с сильной зависимостью от количества доступной памяти. Так при использовании максимального количества доступной памяти в 256 Мб, приходится делать 64 прохода по файлу. Если же попытаться разнести чтение и запись (как я писал раньше, асинхронная запись дает ускорение приблизительно в 10-15%) то количество проходов вырастает до 128 и итоговая скорость оказывается даже меньше чем при последовательной обработке. Так же, мое решение не будет корректно работать в том случае, если количество одинаковых элементов превысит максимальное значение помещающееся в size_t.
Тем не менее, сортирует довольно быстро: 1 Гб, в среднем, обрабатывается за 108 секунд.
P.S. а вообще, я выдохся с данной задачкой (как делать ясно, побочные эффекты алгоритмов тоже очевидны), так что вернусь ней… через еще пару лет?
Приветствую… Дай, угадаю – у тебя 32-х битная система? Ибо если sizeof(size_t) == 8 то вторая версия крашится.
И если я ее верно пофиксил, то у меня получает она даже медленее чем первое решение – первое твое решение у меня за 4 минуты отрабатывает на 1gb, второе работает 10+ минут.
У меня получилось решение которое у меня срабатывает за 1.5 минуты примерно – плюс его потенциальное еще можно на процентов 10-15 думаю ускорить.
Все в рамках упрощенной задачи – в один поток, синхронно, без обработок ошибок
Подсказать решение, или самому еще повозиться хочется?
Кстати, мне мое самое быстрое решение сразу в голову пришло, но в процессе я также вспомнил о counting sort и отвлекся на него – но получилось медлено.
Кстати, интересна следующая вещь – а не может ли быть пары решений, таких что одно будет быстрее на SSD, а другой будет быстрее на HDD.
Я проверяю на SSD кстати, чуть поже проверю на HDD.
Да, я не запускал вторую версию на 64 битах, а зря…
Если говорить про первый случай, то думаю что в первом случае ты просто сливаешь все файлы одновременно. Так как при последовотельном слиянии у меня все работает где-то за 100 секунд (то что я писал про 3 минут фигня, т.к. все было собранно с отладочной информацией ).
Кстати, ты свое решение куда-нибудь выложи, интересно же как другие сделали
Ну вот такой пруф оф концепт получился – https://github.com/yunoshev/big-file-sort
Учти только, что он 5x места требует – я там не чищу временные файлы (хотя если дописать всего 2x будет)
Ну и если паралелить – то понятно как, можно на каждой интерации забирать часть буферов и сортировать их в памяти (выделить на это скаежем 15% памяти) – пока другие обрабатываются как файлы. Нужно придумать только изящный способ – определить сколько брать – чтобы завершилось все одновременно.
У тебя красивое решение. Круто
Погонял твое решение. У меня оно отрабатывает за 41.347s против 35.38 в случае моего первого варианта (если замерять время через функцию time). Похоже что ты запускал отладочную версию моего решения, как и я в первый раз
Тут смотри что получается – у меня с оптимизациями (-O3) все равно твое первое решение получаетя медленее.
70 секунд супротив 100 секунд, но при этом time говорит что у меня проц в моем варианте 30% загружен, в твоем 50%.
Т.е. похоже что твой вариант быстрее если хороший проц (я проверяю на мобильном i7), а мой вариант если хороший диск (я опять же проверяю на SSD). Ну что логично – у тебя там все же сортировка в памяти, а у меня только чтение и запись фактически.
Короче, задачу нужно уточнять
Чуть поже нужно проверить на не мобильном i7+HHD – тогда твой вариат скорее будет быстрее.
Ну или конечно нужно сделать микс моего – но это уже будет с потоками.
Честно сказать, не очень понял почему твоя реализация работает
Да, у тебя в run-скрипте запускается приложение сортировки без замера времени, как-то так: ./$EXEC_OUT $1, это нормально? У меня такое ощущение, что замеряется только лишь время на слияние файлов. :roll:
Уточни что не понял? Если сам алгоритм – это классический radix sort
Я запускаю всегда time ./_run.sh – и измеряю время выполнения скрипта целиком. Так как время компиляции обычно меньше секунды, и удаление файлов старый не больше пару секунд – то просто забиваю на это и смотрю время выполнения скрипта целиком.
Но в целом нужно добавить конечно – удаление файлов и конечное слияние в код.