Здравствуйте, letsurf, Вы писали:

L>Здравствуйте, alsemm, Вы писали:

L>>>Примерно так я и сделал, но, видимо, это не самый быстрый способ.
A>>Это не способ небыстрый, а реализация кривая. Потому что если открыть исходный файл только один раз (static FileWrapper m_fileToSort), т.е. создать единственный дескриптор FILE*, то читать через него асинхронно из нескольких потоков очень тяжело.
A>>Мне вообще непонятно, что у тебя в коде происходит. Т.е. может оно конечно и выдает корректный результат, но асинхронностью тут и не пахнет.

L>Исходный файл читается цепочками по 64Mb, которые сортируются qsort'ом и складываются на диск. Этот процесс не занимает много времени, основное же время у меня уходит на слияние этих цепочек.
Стало мне любопытно и я написал свое решение задачки.
Исходный файл 1.9Gb сортируется за 10 минут.
Решение тупое до безобразия. Закодировать пришлось 2-а приложения:
— первое читает из заданного файла заданный кусок, сортирует его и сохраняет отсортированный кусок в отдельный файл;
— второе получает список остортированных файлов и сливает их в один.
Еще есть четыре bash скрипта, которые запускают эти приложения.
Все барахло лежит тут — http://files.rsdn.ru/30512/sorter.zip. В архиве скрипты, msvc60 dsp/dsw чтобы собрать приложения и собранные приложения. Для запуска нужен cygwin, ну или можно под Linux собрать и гонять там.
Использовать:
1. распаковать архив
2. запустить sort.sh <путь_к_исходному_файлу> <путь_к_отсортированному_файлу>

Как работает (в общих чертах).
Запускаем асинхронно N процессов. Каждому процессу задается фрагмент исходного файла. Каждый процесс читает выделенный ему фрагмент по частям и сортирует их. Каждая отсортированная часть записывается в отдельный временный файл. Далее запускаем один процесс, которые сортирует слиянием все остортированные фрагменты.
Выяснилось, что оптимальное значение N=<число процессоров>. А дальше нужно ловить баланс между количеством фрагментов для слияния и размером этих фрагментов. Эти параметры заданы в файле config.sh. Можно с ним поиграться.

Здравствуйте, vitali_y, Вы писали:

_>1) понадобится дополнительное место на диске объемом в исходный файл;
_>2) выбирается основание системы счисления — пусть N — чтобы хватило отведенных 256MB оперативки;
_>3) сортировка делается в несколько (точнее в N) проходов
_>проход 1:
_>a) пробежался по файлу — вычитал все младшие разряды в ОП (в отведенные 256MB)
_>b) отсортировал получившийся массив с помощью сортировки подсчетом;
_>c) выписал отсортированные по младшему разряду числа во вспомогательный файл;
_>проход 2:
_>a) пробежался по вспомогательному файлу — вычитал второй разряд в ОП (в отведенные 256MB)
_>b) отсортировал получившийся массив с помощью сортировки подсчетом;
_>c) выписал отсортированные по второму разряду числа во 1 файл;

Ну, идея-то понятна. Вместо двух чанков в памяти использовать вдвое больший чанк в памяти и такой же на диске. Концептуально ничего нового по сравнению с лобовым методом, к тому же, не понятно, как к такому решению можно прийти логически — выгрузить один чанк на диск, а не эмпирически.


_>в этом алгоритме в данной реализации — узкое место это диск,
_>какой бы многоядерный не был у тебя процессор — тут ты существенного ускорения не получишь —
_>тут в задаче "заковырка" — для любителей многопроцессорности.
_>хотя этап b) можно распараллелить — если бороться за каждую секунду.

Перманентная загрузка проца >0 — было условием задачи. К тому, же я не уверен, ускорения не получишь. Думаю, при наличии нескольких физических дисков все ровно наоборот. Академические решения шуршат по паре-тройке десятков гб/мин (сначала хотел написать сек., но видимо ошибаюсь) — по-моему на такие цифры я натолкнулся после 15 минут гугления.

A>Запускаем асинхронно N процессов. Каждому процессу задается фрагмент исходного файла. Каждый процесс читает выделенный ему фрагмент по частям и сортирует их.

Параллельное чтение из файла, к сожалению, плохая идея — проверял, тормозит-с. М.б. железо дерьмовое было

Здравствуйте, D14, Вы писали:


A>>Запускаем асинхронно N процессов. Каждому процессу задается фрагмент исходного файла. Каждый процесс читает выделенный ему фрагмент по частям и сортирует их.

D14>Параллельное чтение из файла, к сожалению, плохая идея — проверял, тормозит-с. М.б. железо дерьмовое было
Мои замеры говорят об обратном. Железо — Samsung R60, ОС — Vista.
Исходный файл ~ 140Mb.
Размер файла на который бъется исходный для сортировки — 40Mb. 40Mb выбрано с тем расчетом, чтобы исходный файл бился на равное количество фрагментов независимо о того, сколько процессов его читают одновременно.
Запускам 2 асинхронных процесса по чтению исходного файла и сортировки его частей. Получается такой config.sh:

max_async_sorters=2
...
chunk_bytes=$((40 * 1024 * 1024))

Измеряем время всего процесса от начала сортировки фрагментов до их слияния и выдачи отсортированного файла. Повторяем сортировку 4 раза, чтобы исключить погрешности от работы свопа и т.п.:

stol@computer /cygdrive/c/Users/stol/development/sorter
$ ls -l data
-rwx------ 1 stol None 140083200 Jun 17 12:20 data

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_580_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_580_chunk_111984640-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_580_chunk_41943040-70041600 /cygdrive/c/Users/stol/AppData/Local/Temp/data_580_chunk_70041600-111984640...
merge OK

real    0m14.051s
user    0m0.530s
sys     0m0.930s

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_14620_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_14620_chunk_111984640-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_14620_chunk_41943040-70041600 /cygdrive/c/Users/stol/AppData/Local/Temp/data_14620_chunk_70041600-111984640...
merge OK

real    0m14.362s
user    0m0.302s
sys     0m0.897s

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_17688_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_17688_chunk_111984640-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_17688_chunk_41943040-70041600 /cygdrive/c/Users/stol/AppData/Local/Temp/data_17688_chunk_70041600-111984640...
merge OK

real    0m15.479s
user    0m0.286s
sys     0m1.006s

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_18380_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_18380_chunk_111984640-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_18380_chunk_41943040-70041600 /cygdrive/c/Users/stol/AppData/Local/Temp/data_18380_chunk_70041600-111984640...
merge OK

real    0m14.285s
user    0m0.286s
sys     0m1.006s

Теперь убираем асинхронность в чтении исходного файла config.sh:

max_async_sorters=1

Запускаем 4-е сортировки, как и в первом случае:

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_14800_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_14800_chunk_125829120-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_14800_chunk_41943040-83886080 /cygdrive/c/Users/stol/AppData/Local/Temp/data_14800_chunk_83886080-125829120...
merge OK

real    0m18.709s
user    0m0.135s
sys     0m0.995s

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_16972_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_16972_chunk_125829120-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_16972_chunk_41943040-83886080 /cygdrive/c/Users/stol/AppData/Local/Temp/data_16972_chunk_83886080-125829120...
merge OK

real    0m17.487s
user    0m0.332s
sys     0m0.994s

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_17512_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_17512_chunk_125829120-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_17512_chunk_41943040-83886080 /cygdrive/c/Users/stol/AppData/Local/Temp/data_17512_chunk_83886080-125829120...
merge OK

real    0m18.175s
user    0m0.287s
sys     0m0.822s

stol@computer /cygdrive/c/Users/stol/development/sorter
$ time ./sort.sh data data.sorted
merging /cygdrive/c/Users/stol/AppData/Local/Temp/data_20052_chunk_0-41943040 /cygdrive/c/Users/stol/AppData/Local/Temp/data_20052_chunk_125829120-140083200 /cygdrive/c/Users/stol/AppData/Local/Temp/data_20052_chunk_41943040-83886080 /cygdrive/c/Users/stol/AppData/Local/Temp/data_20052_chunk_83886080-125829120...
merge OK

real    0m18.769s
user    0m0.380s
sys     0m0.884s

Имееющий глаза, да увидит

Такой алгоритм отлично подходит, например, для запуска его на кластере, позволяя загрузить все доступное железо.

Слабым местом в моем решении считаю финальную стадию слияния фрагментов в один файл. Но и тут можно ускорить за счет асинхронности.
Для этого запускаем M процессов, каждый из скоторых "собирает" числа в определенном диапазоне. Первый — [0,1000000), второй — [1000000, 2000000) и т.д. до [UINT_MAX-..., UINT_MAX)
Каждый процесс имеет доступ ко всем отсортированным фрагментам исходного файла. Ну и читает из них только те числа, которые попадают в его диапазон.
Получаем на вызоде M файлов, которые сливаем в один простым cat-ом.

_>>1) понадобится дополнительное место на диске объемом в исходный файл;
_>>2) выбирается основание системы счисления — пусть N — чтобы хватило отведенных 256MB оперативки;
_>>3) сортировка делается в несколько (точнее в N) проходов
_>>проход 1:
_>>a) пробежался по файлу — вычитал все младшие разряды в ОП (в отведенные 256MB)
_>>b) отсортировал получившийся массив с помощью сортировки подсчетом;
_>>c) выписал отсортированные по младшему разряду числа во вспомогательный файл;
_>>проход 2:
_>>a) пробежался по вспомогательному файлу — вычитал второй разряд в ОП (в отведенные 256MB)
_>>b) отсортировал получившийся массив с помощью сортировки подсчетом;
_>>c) выписал отсортированные по второму разряду числа во 1 файл;

D14>Ну, идея-то понятна. Вместо двух чанков в памяти использовать вдвое больший чанк в памяти и такой же на диске. Концептуально ничего нового по сравнению с лобовым методом, к тому же, не понятно, как к такому решению можно прийти логически — выгрузить один чанк на диск, а не эмпирически.


_>>в этом алгоритме в данной реализации — узкое место это диск,
_>>какой бы многоядерный не был у тебя процессор — тут ты существенного ускорения не получишь —
_>>тут в задаче "заковырка" — для любителей многопроцессорности.
_>>хотя этап b) можно распараллелить — если бороться за каждую секунду.

D14>Перманентная загрузка проца >0 — было условием задачи. К тому, же я не уверен, ускорения не получишь. Думаю, при наличии нескольких физических дисков все ровно наоборот. Академические решения шуршат по паре-тройке десятков гб/мин (сначала хотел написать сек., но видимо ошибаюсь) — по-моему на такие цифры я натолкнулся после 15 минут гугления.

после твоих комментариев, я не уверен, что идея и алгоритм были поняты

Здравствуйте, vitali_y, Вы писали:

_>после твоих комментариев, я не уверен, что идея и алгоритм были поняты
т.е. таблицу распределений хранить в памяти (256 мб), а сортировать на диске? И огрести random access доступ по здоровому временному файлу, либо я опять не так понял?

_>>после твоих комментариев, я не уверен, что идея и алгоритм были поняты
D14>т.е. таблицу распределений хранить в памяти (256 мб), а сортировать на диске? И огрести random access доступ по здоровому временному файлу, либо я опять не так понял?

да мое предыдущее описание не верно — когда доходит до реализации — приходится еще подумать — правильно ли понята теория .
2^30 даже байт не поместится в отведенных 256MB...

Правильный алгоритм:
имеется файл данных — это f0;
алгоритм состоит в следующем:
требуется N дополнительных файлов — пронумерованы от 0 до N-1;
проход 0:
a) идем по рассматриваемому файлу (f0), вычитываем числа, обрабатываем 0 младший разряд в выбранной системе счисления;
b) в соответствии с этим разрядом (это число x от 0 до N-1) — записываю рассматриваемое число в соответствующий доп. файл с номером x;
c) исходный файл (f0) на диске стираем;
проход 1:
0) требуется еще N дополнительных файлов — пронумерованы от 0 до N-1;
a) рассматриваем доп. файлы полученные на предыдущем шаге в порядке от 0 до N-1;
b) идем по рассматриваемому файлу, вычитываем числа, обрабатываем 1 младший разряд в выбранной системе счисления;
с) в соответствии с этим разрядом (это число x от 0 до N-1) — записываю рассматриваемое число в соответствующий доп. файл с номером x;
...
после последнего шага выписываю результат в файл — числа отсортированы.

дополнительные 256MB не нужны, много процесорность не нужна.

если в качестве основания системы счисления выбрать N := 256 — то понадобится 4 прохода для сортировки.
по памяти алгоритм требует доп. места на диске равного размеру исходного файла, размер оперативной памяти незначительный,
используемый процессор — безразлично. время работы алгоритма оценивается в 5 раз вычитать объем исходных данных с диска.
т.е. быстрый диск — это здесь хорошо.
можно использовать эту задачу в качестве тестирования оборудования на производительность с доказательством того что человек,
поддавшийся рекламе и купивший самый последний процессор был обманут на деньги

Здравствуйте, vitali_y, Вы писали:

_>по памяти алгоритм требует доп. места на диске равного размеру исходного файла, размер оперативной памяти незначительный,
_>используемый процессор — безразлично. время работы алгоритма оценивается в 5 раз вычитать объем исходных данных с диска.
_>т.е. быстрый диск — это здесь хорошо.
_>можно использовать эту задачу в качестве тестирования оборудования на производительность с доказательством того что человек,
_>поддавшийся рекламе и купивший самый последний процессор был обманут на деньги
Не поленитесь, напишите реализацию. Можно будет сравнить с моим решением — http://rsdn.ru/forum/cpp.applied/3846359.1.aspx

Автор: alsemm
Дата: 17.06.10

Идея такова.

1. Создаем на диске N отсортированных подмножеств размером 256M. Банально нарезаем файл на куски по 256M , сортируем их в памяти и сбрасываем на диск.

2. Используем сортировку подсчетом от 0 до 256M значений (и дальше в цикле двигаясь вверх по 256м), делаем это проходя каждый из N отсортированных подмножеств.

3. Сортировать подсчетом будем только значения лежащие в нужном диапазоне , тем самым избегая лишние проходы по файлам.

4. подсчитанные значения скидываем на диск последовательно записывая значения.


Преимущества , везде используется последовательный доступ к данным. каждое из данных проходятся с диска только 2 раза.

Вроде все операции можно распаралелить, но боюсь проблемы будут с одновременным чтением из файла .

_>>по памяти алгоритм требует доп. места на диске равного размеру исходного файла, размер оперативной памяти незначительный,
_>>используемый процессор — безразлично. время работы алгоритма оценивается в 5 раз вычитать объем исходных данных с диска.
_>>т.е. быстрый диск — это здесь хорошо.
_>>можно использовать эту задачу в качестве тестирования оборудования на производительность с доказательством того что человек,
_>>поддавшийся рекламе и купивший самый последний процессор был обманут на деньги
A>Не поленитесь, напишите реализацию. Можно будет сравнить с моим решением — http://rsdn.ru/forum/cpp.applied/3846359.1.aspx

Автор: alsemm
Дата: 17.06.10

нет желания. сомневаюсь в работоспособности вами написанного — даже тестировать не захотелось и разбираться
в вашем алгоритме — 2 exe для меня все слишком сложно.

_>если в качестве основания системы счисления выбрать N := 256 — то понадобится 4 прохода для сортировки.
_>по памяти алгоритм требует доп. места на диске равного размеру исходного файла, размер оперативной памяти незначительный,
_>используемый процессор — безразлично. время работы алгоритма оценивается в 5 раз вычитать объем исходных данных с диска.
_>т.е. быстрый диск — это здесь хорошо.
_>можно использовать эту задачу в качестве тестирования оборудования на производительность с доказательством того что человек,
_>поддавшийся рекламе и купивший самый последний процессор был обманут на деньги

если в качестве основания системы счисления выбрать N := 65536 — то понадобится 2 прохода для сортировки.
если в качестве основания системы счисления выбрать N := 4294967296 — то это будет чистая сортировка подсчетом.
интуитивно, похоже что N := 256 — оптимальное значение.
реализуемый алгоритм должен воспринимать N в качестве параметра, чтобы узнать, что лучше работает на практике.

Здравствуйте, vitali_y, Вы писали:

_>нет желания. сомневаюсь в работоспособности вами написанного — даже тестировать не захотелось и разбираться
В работоспособности моего решения убедиться проще простого:
1. возьмем некий файл 'foo' и отстортируем его моим решением:

./sort.sh foo foo.sorted

2. преобразуем foo.sorted в текстовый файл так, чтобы в каждой строке было было одно 32-битное целое и сохраним в файл foo.sorted.txt:

hexdump -ve '1/4 "%08x " "\n"' foo.sorted > foo.sorted.txt

3. преобразуем исходный файл foo аналогично тому, как это сделали для foo.sorted:

hexdump -ve '1/4 "%08x " "\n"' foo > foo.txt

4. сортируем foo.txt:

sort foo.txt > foo.sorted2.txt

5. сравниваем foo.sorted.txt и foo.sorted2.txt (файлы должны быть одинаковыми):

cmp foo.sorted.txt foo.sorted2.txt

PS Свои сомнения держите при себе, или приводите веские аргументы, которые их могут обосновать.

_>>нет желания. сомневаюсь в работоспособности вами написанного — даже тестировать не захотелось и разбираться
A>В работоспособности моего решения убедиться проще простого:
A>1. возьмем некий файл 'foo' и отстортируем его моим решением:
A>

A>./sort.sh foo foo.sorted
A>

A>2. преобразуем foo.sorted в текстовый файл так, чтобы в каждой строке было было одно 32-битное целое и сохраним в файл foo.sorted.txt:
A>

A>hexdump -ve '1/4 "%08x " "\n"' foo.sorted > foo.sorted.txt
A>

A>3. преобразуем исходный файл foo аналогично тому, как это сделали для foo.sorted:
A>

A>hexdump -ve '1/4 "%08x " "\n"' foo > foo.txt
A>

A>4. сортируем foo.txt:
A>

A>sort foo.txt > foo.sorted2.txt
A>

A>5. сравниваем foo.sorted.txt и foo.sorted2.txt (файлы должны быть одинаковыми):
A>

A>cmp foo.sorted.txt foo.sorted2.txt
A>

A>PS Свои сомнения держите при себе, или приводите веские аргументы, которые их могут обосновать.

тогда вам техническое задание. программа должно работать следующим образом:
программа обрабатывает следующие параметры входной строки:
-g N -> генерирует файл заполненный рандомно сгенерированными числами размером N GB;
-generate N -> то же что и выше;
-c filename -> проверяет идут ли числа заполняющие файл в порядке возрастания;
-check filename -> то же что и выше;
-s filename -> сортирует входной файл, на выходе filename.s;
-sort filename -> то же что и выше;
-help -> показывает данную справку;
-h -> то же что и выше;
-? -> то же что и выше;

ну почему я должен держать свои сомнения при себе — я скачал ваш исходник посмотрел его, попытался понять ваше описание,
а уж потом засомневался.
вы вероятно заметили, что у нас немного разное понятие простоты...
у меня нету bash и прочих подобных прелестей и знаете это меня даже не расстраивает.
мне не ясно что вы сравниваете в п.5, что вы преобразуете в п.3 и в п.2 — вы что в ручную проверяете 4GB файл ?!

Здравствуйте, vitali_y, Вы писали:

_>ну почему я должен держать свои сомнения при себе — я скачал ваш исходник посмотрел его, попытался понять ваше описание,
_>а уж потом засомневался.
Исходников там два. Еще несколько баш-скриптов. Что именно вызывает сомнения? Конкретно, в формате "имя файла:номер строки"

_>мне не ясно что вы сравниваете в п.5, что вы преобразуете в п.3 и в п.2 — вы что в ручную проверяете 4GB файл ?!
1. п.2, п.3 — преобразование бинарного файла в текстовый с заданным форматом, см. hexdump
2. п5. — сравнение файлов, см. cmp &mdash; compare two files byte by byte

>>ну почему я должен держать свои сомнения при себе — я скачал ваш исходник посмотрел его, попытался понять ваше описание,
_>>а уж потом засомневался.
A>Исходников там два. Еще несколько баш-скриптов. Что именно вызывает сомнения? Конкретно, в формате "имя файла:номер строки"

два исходника — мне 1 достаточно — зачем 2 exe — я написал вам как нормальная программа должна выглядеть.
у вас — ненормальная — конечно с оговоркой — для моих средних способностей.
мне вас — гениев — не понять — потомки поймут — не расстраивайтесь.

_>>мне не ясно что вы сравниваете в п.5, что вы преобразуете в п.3 и в п.2 — вы что в ручную проверяете 4GB файл ?!
A>1. п.2, п.3 — преобразование бинарного файла в текстовый с заданным форматом, см. hexdump
A>2. п5. — сравнение файлов, см. cmp &mdash; compare two files byte by byte

зачем мне текстовый файл?
зачем мне cygwin? зачем мне cmp?

где оценка времени работы вашего алгоритма? она линейная, квадратичная? вы с оценкой работы алгоритма знакомы
или образование гения кулинарный техникум?

Здравствуйте, vitali_y, Вы писали:

>>>ну почему я должен держать свои сомнения при себе — я скачал ваш исходник посмотрел его, попытался понять ваше описание,
_>>>а уж потом засомневался.
A>>Исходников там два. Еще несколько баш-скриптов. Что именно вызывает сомнения? Конкретно, в формате "имя файла:номер строки"

_>два исходника — мне 1 достаточно — зачем 2 exe — я написал вам как нормальная программа должна выглядеть.
Каждая программа должна делать что-то одно. От этого она получается простая. А вся система в целом более гибкая и настраиваемая. В такой системе шелл (bash) — это "клей", который собирает мелкие программы в одну. unix way и все такое.

_>>>мне не ясно что вы сравниваете в п.5, что вы преобразуете в п.3 и в п.2 — вы что в ручную проверяете 4GB файл ?!
A>>1. п.2, п.3 — преобразование бинарного файла в текстовый с заданным форматом, см. hexdump
A>>2. п5. — сравнение файлов, см. cmp &mdash; compare two files byte by byte

_>зачем мне текстовый файл?
Задача: убедиться, что программа сортировки работает корректно. Можно конечно и на C++ слепить программу для этого или добавить в основную программу сортировки еще один параметр командной строки. А можно использовать стандартные средства, например, unix-овые (впрочем, другими я и не владею
Убедиться, что самопальная сортировка работает корректно можно если отсортировать исходный файл какими-то стандартными средствами, которые дают 100% корректный результат и сравнить с выводом нашей сортировки. Для сортировки текстовых файлов в unix есть команда sort. Но она работает с текстом и сортирует строки. А у нас исходные данные — бинарные. Значит перед сортировкой данные надо перевести в текст. Для этого есть команда hexdump. Настроим hexdump так, что в текстовом файле каждое 32-битное целое будет записано на отдельной строке. Теперь запускаем sort и получаем отсортированный текстовый файл. Остается напустить hexdump на отсортированный нашей сортировкой файл и сравнить результат с результатом, который выдал sort. Для сравнения файлов есть команды diff и cmp. Нам хватит cmp.

_>зачем мне cygwin? зачем мне cmp?
Затем чтобы не писать идиотскте тех. задания и не строить велосипеды.

_>где оценка времени работы вашего алгоритма? она линейная, квадратичная? вы с оценкой работы алгоритма знакомы
Прошу прощения, вы видимо имели ввиду оценку сложности алгоритма. Понятие "оценка времени" в теории алгоритмов я чего-то не припонимаю.
А оценка сложности получается как для сортировки слиянием, но несколько лучше, т.к. сортировку фрагментов мы распараллеливаем.

_>или образование гения кулинарный техникум?
Держите себя в руках

1) unix way у словии задачи не оговаривался.
2) вы переводите 4-16 GB бинарный в текстовый формат — какого размера у вас текстовый файл в результате?
3) оценку сложности вы не можете сделать. оценка времени — это примерно сколько времени в часах минутах секундах будет работать ваша программа. я оценил работу моего алгоритма по времени — зависит от выбора N — столько раз придется вычитать заданный объем с диска.

Здравствуйте, vitali_y, Вы писали:

_>1) unix way у словии задачи не оговаривался.
Вас что не устраивает в моем решении, что там два екзешника получилось? Ну солью я их в один, получу С++ простыню на тыщу строк с запуском потоков, их ожиданием и т.п. За лесом деревья потеряются. На фик эти сложности, если часть работы проще в шеле сделать.

_>2) вы переводите 4-16 GB бинарный в текстовый формат — какого размера у вас текстовый файл в результате?
А зачем на таких объемах проверять корректность мой сортировки? Взять любой zip на десяток мегов и проверить — этого будет достаточно.

просто шутка в картинках:

вы:
я:
я побщался с вами:
виртуально, для общего спокойствия:

ни времени оценки, ни сложности алгоритма вашего я не получил и запускать его я не буду в вашем виде.
все — давайте прекратим бесполезный разговор.

На кой черт здесь вообще потоки нужны? Операции с диском съедят выигрыш в производительности, если только функция сравнения двух элементов (а тут всего лишь сравнение чисел) не требует длительных вычислений.

По коду. Очень много букв. Можно было написать короче. Зачем-то классы притянуты за уши, хотя задача довольно процедурная.

По поводу алгоритма. Куски по 256 Мб можно отсортировать в памяти любым понравившися алгоритмом. Далее сортировкой слиянием в каждом проходе по файлу объединять 2 соседних куска данных.
Примерно получится log2(16 Гб / 256 Мб) + 1 = 7 проходов по файлу на диске.