На всякий случай спрошу — проверялась ли корректность выполнения? То есть выхлоп от rpsort и sortir одинаковые?
rpsort смотрит не на один байт конца строки, а на оба два, то есть, поскольку изначально я данные генерировал в linux'e и концы строк были юниксовыми, rpsort честно считал, что в файле ровно одна строка.
Какие объемы временных файлов я точно не помню, но помню, что у sortir.exe это было много мелких файлов, а у rpsort было немного больших (3 может 4 файла).
Я пробовал еще сортировать 100 Мб файл, окончания работы sortir.exe я так и не дождался.
Просто если на тестовых (маленьких) файлах число сравнений сильно отличается у референсной реализации и у вашей, то это формальный повод сделать вывод, что ваша реализация не точна (например из за того, что не точно было описание алгоритма в статье).
Вот тут ( habr.com/en/post/448542/#comment_20044904 ) затестил оригинальную воронку на огромном (для доса) файле в 10 Мб и сравнил её скорость со скоростью другой (тоже внешней) сортировки.
Но конечно же остается нюанс, что, возможно, дело не в алгоритме а в реализации работы с файлами например.
Промежуточные файлы точно были (я их видел, да, они были и для sortir.exe и rpsort). Это же DOS-программа, в память все данные никак не влезут. Файл (FILE.I) был размером 10 Мб.
К сожалению NT-шной сортировки нам не было дадено, поэтому я сравнивал вашу DOS-сортировку с другой DOS-сортировкой (1992 года) в одинаковом окружении и на одинаковых данных.
А вы не пробовали запустить вашу программу под wine? Wine ведь не эмулятор и консольная NT-утилита должна отлично там работать без снижения производительности под линуксом (иногда даже быстрее чем на родной винде).
Самое смешное, что, скорее всего, дополнительные полосы в одну сторону скорее всего ухудшат ситуацию с транспортной доступностью — станет больше машин в обратном направлении, пропускная способность обратной (единственной) полосы начнет падать из за резкого падения средней скорости движения вызванного увеличением числа автомобилей, и, следовательно, уменьшением дистанции между автомобилями.
Но тут в модели это не было учтено, так как термин «дорога между районами города» был использован лишь для иллюстрации задачи на графе.
На десктопе скорее всего будет сортировать секунды за 2-4.
Сконвертируйте файл с помощью unix2dos.
rpsort смотрит не на один байт конца строки, а на оба два, то есть, поскольку изначально я данные генерировал в linux'e и концы строк были юниксовыми, rpsort честно считал, что в файле ровно одна строка.
Потом я это поправил.
Может оно конечно нашло extended/expanded memory и заюзало её. Я эту возможность тоже обрежу.
Файл тот сейчас на машине к которой до понедельника у меня нет доступа.
Но, безусловно, я бы с бОльшим удовольствием работал бы с чем-то более актуальным нежели DOS-версия проги :-)
Я пробовал еще сортировать 100 Мб файл, окончания работы sortir.exe я так и не дождался.
Но могу попробовать ещё.
Просто если на тестовых (маленьких) файлах число сравнений сильно отличается у референсной реализации и у вашей, то это формальный повод сделать вывод, что ваша реализация не точна (например из за того, что не точно было описание алгоритма в статье).
Референсный досовый бинарь ведь доступен и в процессе работы он показывает сколько было операций сравнения.
Но конечно же остается нюанс, что, возможно, дело не в алгоритме а в реализации работы с файлами например.
И поэтому я и нашел соперника для сравнения DOS-sortir.exe, чтобы было с чем сравнить — как другие справляются с большими (для ДОСа) файлами.
Я смогу что-то еще потестить примерно в понедельник.
Сравнивал с другой DOS-программой для внешней сортировки строк — с RPSORT.
На моих данных получились следующие результаты:
rpsort: 1.17 sec
sortir: 20.20 sec
Итого sortir получился примерно в 17 раз медленнее.
Но тут в модели это не было учтено, так как термин «дорога между районами города» был использован лишь для иллюстрации задачи на графе.
IMHO
PS. Вот тут есть симулятор пропускной способности полосы: traffic-simulation.de/ring.html