Лучший способ предварительной обработки и поиска текстового файла в .NET CF

Question

У меня есть текстовый файл с примерно 100 000 строк (5 МБ), который обновляется один раз в день. Он растет со скоростью около 30 линий в день. Строки никак не сортируются. Каждая строка длиной 50 шестнадцатеричных символов выглядит следующим образом:

ABCDE9DAF1F66C10C02F25A1685821F8428422F5870F39A3FE

Учитывая одну из этих строк, мне нужно выяснить, существует ли она в этом файле. Я работаю с C # (.NET CF 2.0) на портативном устройстве, поэтому память ограничена. У меня есть возможность обработать файл перед рукой на сервере Windows. Какой самый быстрый способ сделать это? Вот некоторые из моих первоначальных идей: сортировка файла, сравнение строк за строкой, создание двоичного файла для поиска или использование SQLite.

Из комментариев ОП (важный, который был изначально исключен из вопроса):

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

Answer 1

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

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

Answer 2

Храните данные в базе-256 DAWG - вы получите достаточно компактное представление данных и быстрый поиск.

Answer 3

Сохраните файл отсортированным на сервере ((c) LorenVS), но выполните двоичный поиск непосредственно по файлу, используя длину записи (50 шестнадцатеричных символов + 2 для Cr Lf), чтобы переместить указатель файла (поиск) средние позиции и читать строки для сравнения. Это должно минимизировать объем памяти, необходимой на устройстве.

Хорошо, теперь я вижу, что вторая часть идеи (с) LorenVS тоже.

Answer 4

Уже есть некоторые предложения по сортировке файла.

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

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

Answer 5

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

Учтите, что даже при использовании SQLite или SQL CE вы занимаетесь встроенной базой данных, и я думаю 5Мб больше никого не пугает.