Как представить текстовый файл с произвольным доступом в памяти (C)

Question

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

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

Моя первая идея состояла в том, чтобы использовать связанный список большого буфера, который будет содержать символьные данные файла,Я также сделал бы массив, индекс которого - номера строки, а содержимое - адреса, соответствующие началу строки.Этот массив будет перераспределен при необходимости.

Вспомогательный вопрос: кто-нибудь имеет представление о среднем размере исходного файла?Я был удивлен, что не нашел этого в Google.

Чтобы уточнить:

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

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

Заключение:

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

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

Answer 1

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

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

Answer 2

Невозможно выполнить вставку, удаление и чтение по определенному адресу строки / столбца / символа одновременно O (1).Лучшее, что вы можете получить - это одновременный O (log n) для всех этих операций, и это может быть достигнуто с помощью различных видов сбалансированных двоичных деревьев для хранения файла в памяти.

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

Answer 3

1) Считать (или mmap) весь файл в один фрагмент памяти.

2) За второй проход создайте массив указателей или смещений, указывающих на начало строк (подсказка: один после '\ n') в эту память.

Теперь вы можете индексировать массив для доступа к определенной строке.

Answer 4

1. решение: если строки имеют одинаковый размер, сделайте все строки одинаковыми по длине, добавив необходимое количество метасимволов к каждой строке. Затем вы можете просто вычислить позицию fseek () по номеру строки, сделав поиск O (1).
2. Если строки отсортированы, то вы можете выполнить двоичный поиск, выполнив поиск O (log (nõLines)).
3. Если ни то, ни другое, вы можете хранить индексы начала строки. Но тогда у вас есть проблема, если вы много изменяете файл, потому что, если вы вставите, скажем, где-нибудь X символов, вы должны вычислить, какая это строка, а затем добавить этот X ко всем следующим строкам. Похоже с удалением. Ю, по сути, получить O (nõLines). И код становится некрасивым .

Если вы хотите сохранить весь файл в памяти, просто создайте массив строк * char []. Затем вы получите строку по первому разыменованию и символ по второму разыменованию.

Answer 5

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

Answer 6

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

Вы должны будете использовать дизайн типа ОО, чтобы это было управляемым.

Итак, структуры, которые вы, вероятно, захотите построить:

DynamicArray;

DynamicListOfArrays;

CharList;

Так и идет:

CharList (Получает символы / размер) -> (SetSize) DynamicArray -> (AddArray) DynamicListOfArrays

Если вы создадите подходящие вспомогательные функции для malloc и delete и сделаете так, чтобы структуры могли удалять себя автоматически или вручную. Использование вышеуказанных комбинаций не даст вам прочитать O (1) (что невозможно, если файлы не имеют статического формата), но даст вам хорошее время.

Если вам известна статическая длина файла (по крайней мере, для каждой отдельной строки), т.е. IE не превышает 256 символов в строке, то все, что вам нужно, - это DynamicListOfArries - запись непосредственно в массив (по умолчанию 256), создайте новый , повторение. Недостатком является то, что это пустая трата памяти.

Примечание. Вам потребуется преобразовать DynamicListOfArrays в «статический» ArrayOfArrays, прежде чем вы сможете получить прямой двухточечный доступ.

Если вам нужен исходный код, чтобы дать вам идею (хотя мой построен на C ++, переписывание не займет много времени), оставьте комментарий об этом. Как и любой другой код, который я предлагаю для stackoverflow, он может использоваться для любых целей, даже в коммерческих целях.