Добрый вечер.

Столкнулся с проблемой. Вроде и знаю как решить, но не слишком красиво получается.

Вопрос такой: Дано N файлов общим размером более 100 мегабайт. В файлах находятся отсортированные номера. Например, семи- или восьмизначные. Номера разделены между собой пробелами.
Нужно слить все файлы в один. Внутри файла-результата номера тоже должны быть отсортированы. При этом, нежелательно использовать оперативной памяти более 20-30 мегабайт.

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

А что здесь некрасивого?

Возможно, паранойя. Опыта мало.

Тогда уточню.
Ну вот скажем файлов оказалось 500 или 2000 или больше.
Предполагается, что открываются все файлы сразу и из каждого файла берется первый номер, в полученном массиве ищется меньший и кладется в выходной. Место найденного меньшего занимает следующий номер из того же файла, что и найденный меньший. Это хороший вариант? В плане производительности.

Это сообщение отредактировал(а) Merovingean - 8.7.2015, 22:50

Это называется '[внешняя] сортировка слиянием'. Вполне стандартный метод. Подробности ищите в Гугле   

Это хороший вариант. 


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

Возможно, Вам не нужно на каждом этапе искать (среди имеющихся 1...500-2000 номеров) наименьший номер (это как раз потеря производительности), Вам нужно хранить уже считанные (но несброшенные в окончательный файл из-за их ненаименьшести) из файлов номера в отсортированном списке. Когда Вы сбрасываете наименьший из номеров (который при отсортированности списка легко определяется), то вместо него (если файл ещё не закончился) Вы в список добавляете следующий номер из этого же файла, но не на старое место, а согласно сортировке. Если файл закончился, то он как бы выпадает из этого списка, уменьшая размер списка.

Возможно, и это все ерунда, а попарное слияние самое быстрое. Не знаю. Нужно ставить эксперименты, нужно анализировать, считать количество сравнений и т.д. И ещё, просто одновременная работа с тысячей файлов (вне зависимости от сравнений) может сильно подтормаживать.

Вопрос решил примерно следующим образом:





Это сообщение отредактировал(а) Merovingean - 28.7.2015, 08:47

Merovingean, красиво же)))

PS А вдруг пустой input-файл попадётся?

Добавлено через 4 минуты и 23 секунды
Туплю, но почему second'ы сравниваются?

Поправил.
Писал на память и упустил пару моментов. В моем случае все немного сложнее и вместо номеров UUID. Но смысл не меняется.

Куда более серьезная проблема в том, что код не универсален - система не даст открыть любое количество файлов.

Это не большая проблема - сливайте по несколько файлов зараз (сколько даст открыть система), потом сливайте файлы результаты от первого шага. Если их будет слишком много - опять делите на пачки и сливаете. Получается дерево слияния файлов.