Ну что, надо размять мозги!

Задача:

Есть некий файл размером 1,000,000 строк, строки представляют из себя числа от 0 до того же 1,000,000, разделитель - "\n". Надо сделать сортировку по возрастанию чисел и записать результат в отдельный файл с тем же разделителем.

Вот мой результат:

Read time: 0.230653 sec (чтение файла)
Sort time: 0.482544 sec (сортировка)
Write time: 0.096485 sec (запись выходного файла)
Железо: Mac OS, i5, SSD 128, 4GB mem

Я делал через векторы, знакомый делал через qsort, результаты, примерно, совпали, может кто предложит свой более быстрый вариант? Хотя, boost я пока не рассматриваю, но вариант на нем бы тоже был не лишним.

Ниже исходник генератора исходного файла big,txt:

Сообщение от :
//
// main.cpp
// CBigFileGenerator
//

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <ctime>

using namespace std;

int main() {

ofstream file ("big.txt");
unsigned int digit;
srand(static_cast <unsigned int> (time(0)));

for (int i = 0; i<1000000; i++)
{
digit = rand() * (rand() % 100 + 1);
file << digit << endl;
}

return 0;
}

[Ответ]

Сообщение от lemial:
может кто предложит свой более быстрый вариант?

http://vk.com/doc88269559_213737504?...8f043e267a973f
"более быстрых" вариантов не существует. Нужно смотреть на данные, и подбирать или проверять алгоритмы. [Ответ]

Сообщение от Spectator:
http://vk.com/doc88269559_213737504?...8f043e267a973f
"более быстрых" вариантов не существует. Нужно смотреть на данные, и подбирать или проверять алгоритмы.

Spectator, согласен насчет разных данных, в моем примере мы работаем с целочисленными типами. Ну и да, кроме сортировки есть еще как минимум чтение и запись файлов, тут тоже можно много вариантов протестировать, с кешем или без и т.д. [Ответ]

При данной постановке задачи -классическая поразрядная сортировка будет быстрее.
См Д.Кнут. Его тебе камрады выслали.
Поразрядная сортировка O(n) без ухудшения
Быстрая сортировка O(n log(n)) с худшим вариантом O(n^2) + накладные расходы на преобразование строк в числа а это как минимум ДКА со сложностью O(n); [Ответ]

Сообщение от MadFish:
При данной постановке задачи -классическая поразрядная сортировка будет быстрее.
См Д.Кнут. Его тебе камрады выслали.
Поразрядная сортировка O(n) без ухудшения
Быстрая сортировка O(n log(n)) с худшим вариантом O(n^2) + накладные расходы на преобразование строк в числа а это как минимум ДКА со сложностью O(n);

Да это все в теории Будут ваши варианты? Я покажу свой, погоняем на разном железе, сравним. [Ответ]

Это что, шутка юмора такая? [Ответ]

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

Вопрос немного сложнее, чем Вам кажется. Полистайте Кнута, если хотите разобраться. [Ответ]

Сообщение от Spectator:
Вопрос немного сложнее, чем Вам кажется. Полистайте Кнута, если хотите разобраться.

Где его купить? Я в воронежских магазинах не нашел [Ответ]

Сообщение от lemial:
Где его купить? Я в воронежских магазинах не нашел

Вижу постоянно в книжном за Никитинской библиотекой, недалеко от ВГУ, на Платонова.
Второй книжный на самой площади. Там тоже может быть, оба магазина торгуют для студентов, такие книги бывают в Воронеже только там.
На ozon.ru, если не найдете в городе, тоже есть.
Ну и в саму библиотеку вход с собаками тоже вроде не охраняют, там она быть обязана, в читальном как минимум. [Ответ]

Сообщение от Spectator:
Вижу постоянно в книжном за Никитинской библиотекой, недалеко от ВГУ, на Платонова.
Второй книжный на самой площади. Там тоже может быть, оба магазина торгуют для студентов, такие книги бывают в Воронеже только там.

Не нашел сегодня книжных возле никитинки, только Амиталь, но там что-то очень тоскливо с такой литературой. Можете сказать точный адрес или хотя бы на карте указать где находится указываемый вами книжный?

ЗЫ. Чисто случайно купил сегодня в читай городе вот такое чудо:

[Ответ]

lemial, методы внешней сортировки описаны ещё и в Седжвике. Но он там тоже на Кнута ссылается.

По интернету закажи или на авито Кнута поищи.
http://www.ozon.ru/context/detail/id/2527036/ [Ответ]

Сообщение от lemial:
Не нашел сегодня книжных возле никитинки, только Амиталь, но там что-то очень тоскливо с такой литературой. Можете сказать точный адрес или хотя бы на карте указать где находится указываемый вами книжный?

Амиталь я и имел в виду. Если там тоскливо, то в Воронеже навряд ли еще что-то найдете. Но оно, к счастью, абсолютно и не нужно.
http://www.ozon.ru/context/detail/id/2527036/
Если денег жалко, то рядом с Амиталем есть небольшая библиотечка. В ней, по крайней мере 15 лет назад, Кнут точно был. Сдается мне что и сейчас найдется.
Мейерс - собственно. не сказать чтобы чудо) Достаточно известная книга) Насчет современности возникают, правда, некоторые сомнения))) [Ответ]