Тестовое задание C++ - Этюды для программистов

Тестовое заданаие на языке C++:

За 4 часа написать программу, которая отсортирует числа формата double
хранящихся в текстовом файле размером 1Гб (одно число в одной строке).

Пример

Программа должна использовать не более 100Мб оперативной памяти, и
работать не дольше 25-30 минут (на 2Гц современном процессоре).
Обязательные параметры: <имя файла не отсортированного> <имя файла отсортированного> Также должен быть написан генератор не
отсортированного 1Гб файла с числами формата double

Алгоритм — блочная сортировка

В аттаче пример готового приложения пока только бинари.

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

[]

Алгоритм — различные сортировки слиянием.

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

D>В аттаче пример готового приложения пока только бинари.
Смешно. Этюд в том, чтобы телепатически выкачать этот аттач?

Ограничение на ОЗУ есть, а на дисковую память?

... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>

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

D>Тестовое заданаие на языке C++:

...

D>Алгоритм — блочная сортировка
D>В аттаче пример готового приложения пока только бинари.

блочная — имеется в виду сортировка слиянием?
не очень понял смысл этюда

L>блочная — имеется в виду сортировка слиянием?
L>не очень понял смысл этюда

Смысл уложиться в заданные требования. (за 4 часа, и 25-30 минут)

А для меня, сравнить со своим кодом чтоб понять плох ли он или нет.

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

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

D>>В аттаче пример готового приложения пока только бинари.
К>Смешно. Этюд в том, чтобы телепатически выкачать этот аттач?

К>

К>Ограничение на ОЗУ есть, а на дисковую память?

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

К>Смешно. Этюд в том, чтобы телепатически выкачать этот аттач?
Сорри вон он здесь

К>Ограничение на ОЗУ есть, а на дисковую память?
Нет

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

К>>Ограничение на ОЗУ есть, а на дисковую память?
D>Нет

Тогда заводим мега-своп-файл

1. Читаем из исходного файла по 100 мегабайт double'в или сколько влезет в память, сортируем эти пачки в памяти (квиксорт), сохраняем в файлы.
Всего получается порядка 10-20 файлов.

2. Открываем все эти 10-20 файлов и выполняем сортировку слиянием, результат записываем в результирующий файл.

ВСЁ!

... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>

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

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

К>>>Ограничение на ОЗУ есть, а на дисковую память?
D>>Нет

К>Тогда заводим мега-своп-файл

К>1. Читаем из исходного файла по 100 мегабайт double'в или сколько влезет в память, сортируем эти пачки в памяти (квиксорт), сохраняем в файлы.
К>Всего получается порядка 10-20 файлов.

К>2. Открываем все эти 10-20 файлов и выполняем сортировку слиянием, результат записываем в результирующий файл.

К>ВСЁ!

Наверное автор хочет чтобы написали пример

Причем мне кажется что при сортировке слиянием используя мега своп файл начнется тормозня.

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

К>>1. Читаем из исходного файла по 100 мегабайт double'в или сколько влезет в память, сортируем эти пачки в памяти (квиксорт), сохраняем в файлы.
К>>Всего получается порядка 10-20 файлов.

К>>2. Открываем все эти 10-20 файлов и выполняем сортировку слиянием, результат записываем в результирующий файл.

Да так я и сделал.

C>Наверное автор хочет чтобы написали пример

C>Причем мне кажется что при сортировке слиянием используя мега своп файл начнется тормозня.

Именно. Хочется пример того как написали бы другие программисты.
Уже есть свой код и хочется сравнить с тем что напишут другие за 4 часа.

Тормозни особой нет, ведь памяти есть 100Мб можно кешировать.

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

К>>Тогда заводим мега-своп-файл

C>Причем мне кажется что при сортировке слиянием используя мега своп файл начнется тормозня.

Это была шютка. Мега-своп-файла не требуется.

C>Наверное автор хочет чтобы написали пример

Ну, я думаю, четыре часа уже прошли, конкурс можно считать размороженным

Вот примерно такой эскиз. Компилировать даже не пробовал.

// генератор имён временных файлов
string make_up_temp_filename(int);

// будем считать, что оба файла - вход и выход - уже открыты
ifstream srcfile;
ofstream dstfile;

vector< shared_ptr<fstream> > tempfiles; // временные файлы - будем создавать по ходу дела

////////////////////////////
// читаем-сортируем-пишем...

vector<double> block; // для сортировки в памяти
block.reserve(100000000 / sizeof(double)); // ну или сколько там памяти доступно
while(srcfile)
{
    block.resize(0);

    // читаем
    while(block.size() < block.capacity() && srcfile)
    {
        double x; srcfile >> x;
        if(srcfile.failbit())
            break;
        block.push_back(x);
    }
    
    if(block.size()==0)
        break;
    
    // сортируем
    sort(block.begin(), block.end());
    
    // записываем
    shared_ptr<fstream> tempfile (new fstream(make_up_temp_filename(tempfiles.size()), ios_base::in|ios_base::out|ios_base::binary));
    tempfile->write((const char*)&block[0], block.size()*sizeof(double));
    
    tempfiles.push_back(tempfile);
}

////////////////////////
// выполняем слияние

vector<double> inputs (tempfiles.size());

// заполняем первый ряд
for(int i=0, n=tempfiles.size(); i!=n; ++i)
    tempfiles[i]->read((char*)&inputs[i], sizeof(double));

while(inputs.size() != 0)
{
    int best = distance(inputs.begin(), min_element(inputs.begin(), inputs.end()));
    
    dstfile << inputs[best] << endl;
    
    // читаем новое значение из файла номер best
    if(!*tempfiles[best])
    {
        inputs.erase(inputs.begin()+best);
        tempfiles.erase(tempfiles.begin()+best);
    }
    else
    {
        tempfiles[best]->read((char*)&inputs[i], sizeof(double));
    }
}

... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>

Если использовать сторониие либы тогда можно и быстрее.

http://stxxl.sourceforge.net/

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

К>Вот примерно такой эскиз. Компилировать даже не пробовал.

Потоки — зло, надо заменить на scanf/printf. В разы быстрее работает.

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

Красивее чем я сделал, но я еще и покешировал при слиянии(чуть скорости добавило).
Если можешь посмотри код — архив с кодом.
Что в нем плохо?

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

// генератор имён временных файлов
string make_up_temp_filename(int);

функция с таким назначением уже есть в стандарте, изобретение велосипеда, однако

shared_ptr<fstream> tempfile (new fstream(make_up_temp_filename(tempfiles.size()), ios_base::in|ios_base::out|ios_base::binary));

не догоняю, зачем использовать shared_ptr

 int best = distance(inputs.begin(), min_element(inputs.begin(), inputs.end()));

а что, std::max_element тут нельзя применить?

сорри, насчет shared_ptr догнал

Здравствуйте, <Аноним>, Вы писали:

А>Здравствуйте, Кодт, Вы писали:

А>

А>// генератор имён временных файлов
А>string make_up_temp_filename(int);
А>

А>функция с таким назначением уже есть в стандарте, изобретение велосипеда, однако

Есть очень похожие функции — tmpnam (а в VC CRT — ещё и _tempnam). Никто не мешает определить make_up_temp_filename через них. Или сделать свою.

А>

А>shared_ptr<fstream> tempfile (new fstream(make_up_temp_filename(tempfiles.size()), ios_base::in|ios_base::out|ios_base::binary));
А>

А>не догоняю, зачем использовать shared_ptr

Затем, чтобы поместить fstream в вектор.
Поскольку поток не является типом-значением, непосредственно с ним такой фокус — vector<fstream> — не пройдёт.
Можно, конечно, повыкручиваться и сделать отложенную инициализацию пула потоков

fstream tempfiles[ENOUGH_COUNT]; int num_tempfiles = 0;
.....
fstream& tempfile = tempfiles[num_tempfiles++];
tempfile.open(make_up_temp_name(),......);

А>

А> int best = distance(inputs.begin(), min_element(inputs.begin(), inputs.end()));
А>

А>а что, std::max_element тут нельзя применить?

А при чём тут max_element?
Я выбираю из inputs наименьший элемент и получаю его индекс с помощью distance.

... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>

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

К>Есть очень похожие функции — tmpnam (а в VC CRT — ещё и _tempnam). Никто не мешает определить make_up_temp_filename через них. Или сделать свою.
ИМХО это затрудняет понимание и все такое.... Нарушение принципа Оккама... Можно вообще сделать что-то вроде:

 #define BEGIN { #define END }

И дальше писать вместо скобок BEGIN и END, и это будет работать — только нафига?

А>>

А>>shared_ptr<fstream> tempfile (new fstream(make_up_temp_filename(tempfiles.size()), ios_base::in|ios_base::out|ios_base::binary));
А>>

А>>не догоняю, зачем использовать shared_ptr

К>Затем, чтобы поместить fstream в вектор.
Я в принципе догнал уж и сам... Правда объяснение дал бы другое — чтобы корректно закрыть все файлы при любом (вт.ч. аварийном) завершении кода. Потому как, ИМХО, никто не мешает хранить в векторе указатели на fstream — разве нет? Но это усложняет cleanup ( a propos — в коде не хватает, ИМХО, уничтожения созданных на диске временных файлов.... Если только ты не используешь стандартные функции, не только генерирующие имя, но и создающие временный файл, гарантированно уничтожающийся при окончании работы — в Unix такие вещи есть, в Win — не уверен, но вроде тоже)

К>А при чём тут max_element?
К>Я выбираю из inputs наименьший элемент и получаю его индекс с помощью distance.
Хорошо, используем min_element

P.S. Не воспринимай, плиз, разбор твоего кода как наезд на тебя лично. Если человек даже действительно нашел в твоем коде какие-то огрехи — это не значит, что ты дурак, и не значит, что он умный. ИМХО, чужие ошибки находить — ума много не требутся

Здравствуйте, <Аноним>, Вы писали:

К>>Есть очень похожие функции — tmpnam (а в VC CRT — ещё и _tempnam). Никто не мешает определить make_up_temp_filename через них. Или сделать свою.
А>ИМХО это затрудняет понимание и все такое.... Нарушение принципа Оккама...

Это не нарушение принципа Оккама, а введение точки абстрагирования.
Кроме того, сишная функция работает с сишными же строками, а это всегда несколько стрёмно. Что там с потокобезопасностью, например? Опять же, для защиты от переполнения буфера MS рекомендует использовать другую функцию — tmpnam_s. Вот тут и пригодится абстрагирование.

string tempname()
{
    // прячем всё низкоуровневое внутрь
    char buf[L_tmpnam_s];
    return tmpnam_s(buf, L_tmpnam_s);
}

А>>>не догоняю, зачем использовать shared_ptr

К>>Затем, чтобы поместить fstream в вектор.
А>Я в принципе догнал уж и сам... Правда объяснение дал бы другое — чтобы корректно закрыть все файлы при любом (вт.ч. аварийном) завершении кода. Потому как, ИМХО, никто не мешает хранить в векторе указатели на fstream — разве нет? Но это усложняет cleanup ( a propos — в коде не хватает, ИМХО, уничтожения созданных на диске временных файлов.... Если только ты не используешь стандартные функции, не только генерирующие имя, но и создающие временный файл, гарантированно уничтожающийся при окончании работы — в Unix такие вещи есть, в Win — не уверен, но вроде тоже)

Если мы сделаем локальный массив fstream'ов — то у его элементов тоже вызовутся деструкторы и позакрывают файлы.
А вот про удаление файлов — замечание верное! Это я забыл.

... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>

	От:	digger51
	Дата:	09.09.08 07:50
	Оценка:

	От:	Константин Л.
	Дата:	09.09.08 08:35
	Оценка:

	От:	Кодт
	Дата:	09.09.08 12:48
	Оценка:

	От:	Leonidze
	Дата:	09.09.08 18:57
	Оценка:

	От:	Аноним
	Дата:	10.09.08 10:12
	Оценка: