C ++ вставка строки в файл с определенным номером строки

Question

Я хочу иметь возможность читать из несортированного исходного текстового файла (по одной записи в каждой строке) и вставлять строку / запись в целевой текстовый файл, указав номер строки, в которую она должна быть вставлена.

Где вставить строку / запись в файл назначения, будет определено путем сравнения входящей строки из входящего файла с уже упорядоченным списком в файле назначения. (Файл назначения будет начинаться как пустой файл, и данные будут отсортированы и вставлены в него по одной строке за раз, когда программа выполняет итерацию по строкам входящего файла.)

Пример входящего файла:

1 10/01/2008 line1data
2 11/01/2008 line2data
3 10/15/2008 line3data

Пример требуемого файла назначения:

2 11/01/2008 line2data
3 10/15/2008 line3data
1 10/01/2008 line1data

Я мог бы сделать это, выполнив сортировку в памяти через связанный список или аналогичный, но я хочу разрешить это масштабировать до очень больших файлов. (И я получаю удовольствие, пытаясь решить эту проблему, так как я новичок в C ++:).)

Одним из способов сделать это может быть открытие 2 файловых потоков с fstream (1 вход и 1 выход или только 1 вход / выход), но затем я сталкиваюсь с трудностью, которую трудно найти и ищите позицию файла, потому что она, кажется, зависит от абсолютной позиции с начала файла, а не от номеров строк:).

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

Я использую Visual Studio 2008 Pro C ++ и только изучаю C ++.

Answer 1

Один из способов сделать это - не сохранять файл отсортированным, а использовать отдельный индекс, используя berkley db ( BerkleyDB ). Каждая запись в БД имеет ключи сортировки и смещение в основной файл. Преимущество этого состоит в том, что вы можете иметь несколько способов сортировки, не дублируя текстовый файл. Вы также можете изменить строки, не переписывая файл, добавив измененную строку в конце и обновив индекс, чтобы игнорировать старую строку и указывать на новую. Мы успешно использовали это для текстовых файлов размером в несколько ГБ, в которые нам пришлось внести множество небольших изменений.

Редактировать: код, который я разработал для этого, является частью более крупного пакета, который можно загрузить здесь . Конкретный код находится в файлах btree * в source / IO.

Answer 2

Основная проблема заключается в том, что в обычных ОС файлы представляют собой просто потоки байтов. На уровне файловой системы нет понятия линий. Эта семантика должна быть добавлена ​​как дополнительный слой поверх предоставляемых ОС средств. Хотя я никогда не использовал его, я считаю, что в VMS есть файловая система, ориентированная на записи, которая облегчит вам задачу. Но в Linux или Windows вы не можете вставить в середину файла, не переписав остальную часть файла. Это похоже на память: на самом высоком уровне это просто последовательность байтов, и если вы хотите что-то более сложное, например, связанный список, его нужно добавить сверху.

Answer 3

Решением [отчетливо-нет-c ++] будет использование инструмента * nix sort для сортировки по второму столбцу данных. Это может выглядеть примерно так:

cat <file> | sort -k 2,2 > <file2> ; mv <file2> <file>

Это не совсем на месте, и он не отвечает на запрос использования C ++, но работает:)

Может даже быть в состоянии сделать:

cat <file> | sort -k 2,2 > <file>

Хотя я не пробовал этот маршрут.
* http://www.ss64.com/bash/sort.html - сортировка справочной страницы

Answer 4

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

Обычный способ «без памяти» сделать то, что вы пытаетесь сделать, это скопировать файл из оригинала во временный файл, вставив данные в нужную точку, а затем выполнить переименование / замену исходный файл.

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

Answer 5

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

Вы не можете вставить содержимое в середину файла (т. Е. Без перезаписи того, что было ранее); Мне неизвестны файловые системы производственного уровня, которые его поддерживают.

Answer 6

Попробуйте модифицирован Bucket Sort . Предполагая, что значения идентификаторов хорошо себя зарекомендовали, вы получите гораздо более эффективный алгоритм сортировки. Возможно, вы сможете повысить эффективность ввода-вывода, фактически выписывая сегменты (используйте небольшие) во время сканирования, что потенциально уменьшает количество необходимого вам рандомизированного файла / ввода-вывода. Или нет.

Answer 7

Я думаю, что вопрос скорее в реализации, а не в конкретных алгоритмах, в частности, в обработке очень больших наборов данных.

Предположим, что исходный файл содержит 2 ^ 32 строки данных. Какой эффективный способ сортировки данных.

Вот как бы я это сделал:

1. Анализ исходного файла и извлечение следующей информации: ключ сортировки, смещение строки в файле, длина строки. Эта информация записывается в другой файл. Это создает набор данных элементов фиксированного размера, который легко индексировать, назовите его индексным файлом.

2. Использовать измененную сортировку слиянием. Рекурсивно делите индексный файл до тех пор, пока количество сортируемых элементов не достигнет некоторого минимального количества - истинная сортировка слиянием повторяется до 1 или 0 элементов, я предлагаю остановиться на 1024 или около того, для этого потребуется точная настройка. Загрузите блок данных из файла индекса в память и выполните быструю сортировку, а затем запишите данные обратно на диск.

3. Выполнить объединение в файле индекса. Это сложно, но можно сделать так: загрузить блок данных из каждого источника (скажем, 1024 записи). Слейте во временный выходной файл и напишите. Когда блок опустошен, заполните его. Если исходные данные больше не найдены, прочитайте временный файл с самого начала и перезапишите две объединяемые части - они должны быть смежными. Очевидно, что при окончательном слиянии не нужно копировать данные (или даже создавать временный файл). Думая об этом шаге, возможно, можно установить соглашение об именах для объединенных индексных файлов, чтобы данные не должны были перезаписывать не объединенные данные (если вы понимаете, что я имею в виду).

4. Считайте отсортированный индексный файл, извлеките из исходного файла строку данных и запишите в файл результатов.

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