Алгоритм внешней сортировки. Что не так? , Кто хочет сделать code review?

[hopen]

Привет!

Делал я тут, значиться, тестовое задание для одной забугорной конторы.
Смысл такой: есть 200 Gb текстовый файл, строки разделены \n. Нужно их сортировать, считая, что памяти много больше, чем самая длинная строка.

Собственно, код

Задание я провалил, получив такой комментарий: commented parts, big functions, deeply nested blocks, code duplication.

Вот мне интересно у опытных разработчиков мнение узнать. Придрались или по делу?

Добавлено 21.12.16, 12:51
Да... совсем забыл. Еще написали, что мое решение работает медленнее, чем стандартное...
Вот мне интересно, что за стандартное решение такое...? И как можно ускорить мое

Сообщение отредактировано: hopen - 21.12.16, 12:51

[Pacific]

hopen
Думаю, им не понравилось if (true) { ... } и

std::string MergeFiles(StringContainer filelist)
{
    return __mergeFiles(std::move(filelist));
}

но это уже придирки. "deeply nested blocks" я там не увидел, после того как убрал if (true) { ... }

Цитата hopen @ 21.12.16, 12:48

commented parts, big functions, deeply nested blocks, code duplication.

Не увидел там сильно страшных примеров перечисленного. Придирки.

Думаю, главная претензия - скорость работы. В идеале твой код должен сделать все за 2 прохода:
1) Разбить исходный файл на куски размером с доступную память, куски перед записью сразу сортировать: 200 Гб считывание, 200 Гб запись
3) Сливать сразу все куски в выходной файл, буферизуя их, например, по 1 Мб: 200 Гб считывание, 200 Гб запись

Для ускорения еще можно сделать overlapped I/O, но это сильно усложнит код.

Добавлено 21.12.16, 13:27
Ну еще TBuffer там непонятно зачем, по сути он только обертка. Если его убрать, код __merge2Files практически не увеличится.

[hopen]

Pacific, спасибо большое за ответ!

Цитата Pacific @ 21.12.16, 13:24

3) Сливать сразу все куски в выходной файл, буферизуя их, например, по 1 Мб: 200 Гб считывание, 200 Гб запись

А как в выходной сразу?
Сейчас куски заливаются в разные файлы, затем эти файлы мержатся между собой

Сообщение отредактировано: hopen - 21.12.16, 13:41

[Pacific]

Цитата hopen @ 21.12.16, 13:41

А как в выходной сразу?
Сейчас куски заливаются в разные файлы, затем эти файлы мержатся между собой

Есть N кусков, соответственно брать N первых строк из N файлов для сравнения вместо двух при слиянии. Обычно все упирается в скорость чтения/записи, так что для небольших N (10 - 50) это будет быстрее. Для больших N время на сравнение N строк на каждом шаге станет заметным. Короче, надо параметры подбирать под конкретный случай - размер файла, объем памяти, скорость диска.

[Flex Ferrum]

Я так понимаю, что суть задачи была в том, чтобы реализовать сортировку файла методом слияния. В принципе, можно было бы обойтись двумя целевыми файлами - один "текущий", другой - "новый". И алгоритм тогда выглядит так: из исходного файла читаем очередную порцию строк, сортируем, после чего объединяем полученный массив с тем, что уже записано в текущий файл. Результат записываем в новый. После этого новый файл делаем "текущим", повторяем до тех пор, пока исходный файл не кончится. Вроде всё просто.

Добавлено 21.12.16, 16:02
И да. Для такого алгоритма код сильно перегружен.

[Cfon]

hopen тебе надо было сделать рефакторинг кода

Добавлено 21.12.16, 18:10
забугорные конторы ценят локаничность и ясность кода, читай Фаулера

[hopen]

Спасибо всем за оценки! Обязательно учту их

[Cfon]

что за контора если не секрет?

[hopen]

Какая то вьетнамская. Название не помню, было 2 месяца назад))

[Flex Ferrum]

Цитата hopen @ 22.12.16, 09:44

Какая то вьетнамская. Название не помню, было 2 месяца назад))

Как-то многовато гонору для вьетнамской. Я бы такое от какой-нибудь крупной, с западного побережья США ожидал бы скорее...

[Cfon]

http://www.youtube.com/watch?v=Gnp8G1_kO3I

[olok900]

Цитата hopen @ 22.12.16, 09:44

Какая то вьетнамская. Название не помню, было 2 месяца назад))

а ну ясно во въетнам много переехало аутсорса в последнее время