Поиск "ключа" в текстовом файле 8 ГБ +

Ответ 1

Другой ответ, так как это с другим решением.

Вместо использования базы данных SQLite3 я использовал нашу оболочку TDynArray и методы сортировки и двоичного поиска.

type
  TEntry = record
    Key: RawUTF8;
    Value: RawUTF8;
  end;
  TEntryDynArray = array of TEntry;

const
  // used to create some fake data, with some multiple occurences of Key
  COUNT = 1000000; // million rows insertion !
  UNIQUE_KEY = 1024; // should be a power of two

procedure Process;

var
  entry: TEntryDynArray;
  entrycount: integer;
  entries: TDynArray;

  procedure DoInsert;
  var i: integer;
      rec: TEntry;
  begin
    for i := 0 to COUNT-1 do begin
      // here we fill with some data
      rec.Key := FormatUTF8('KEY%',[i and pred(UNIQUE_KEY)]);
      rec.Value := FormatUTF8('VALUE%',[i]);
      entries.Add(rec);
    end;
  end;

  procedure DoSelect;
  var i,j, first,last, total: integer;
      key: RawUTF8;
  begin
    total := 0;
    for i := 0 to pred(UNIQUE_KEY) do begin
      key := FormatUTF8('KEY%',[i]);
      assert(entries.FindAllSorted(key,first,last));
      for j := first to last do
        assert(entry[j].Key=key);
      inc(total,last-first+1);
    end;
    assert(total=COUNT);
  end;

Вот результаты синхронизации:

one million rows benchmark:
INSERT 1000000 rows in 215.49ms
SORT ARRAY 1000000 in 192.64ms
SELECT 1000000 rows per Key index in 26.15ms

ten million rows benchmark:
INSERT 10000000 rows in 2.10s
SORT ARRAY 10000000 in 3.06s
SELECT 10000000 rows per Key index in 357.72ms

Это более чем в 10 раз быстрее, чем решение SQLite3 в памяти. 10 миллионов строк остаются в памяти процесса Win32 без проблем.

И хороший пример того, как обертка TDynArray работает на практике, и как оптимизированные функции сравнения строк в SSE4.2 дают хорошие результаты.

Полный исходный код доступен в нашем репозитории github.

Изменить: с 100 000 000 строк (100 миллионов строк) под Win64 для более 10 ГБ оперативной памяти, используемых во время процесса:

INSERT 100000000 rows in 27.36s
SORT ARRAY 100000000 in 43.14s
SELECT 100000000 rows per Key index in 4.14s

Ответ 2

Вместо того, чтобы повторно изобретать колесо бинарного поиска или B-Tree, попробуйте с существующей реализацией.

Загрузите содержимое в базу данных SQLite3 в памяти (с соответствующим индексом и с транзакцией каждые 10 000 INSERT), и все готово. Убедитесь, что вы нацеливаете Win64, чтобы иметь достаточно места в ОЗУ. Вы даже можете использовать файловое хранилище: немного медленнее создавать, но с индексами запросы Key будут мгновенными. Если у вас нет поддержки SQlite3 в вашей версии Delphi (через последнюю версию FireDAC), вы можете использовать наш модуль OpenSource и связанных с документацией.

Использование SQlite3 будет окончательно быстрее и будет использовать меньше ресурсов, чем обычная база данных SQL-клиента-клиента - BTW "бесплатная" версия MS SQL не сможет обрабатывать столько необходимых данных, AFAIR.

Обновление. Я написал несколько примеров кода, чтобы проиллюстрировать, как использовать SQLite3 с нашим уровнем ORM для вашей проблемы - см. этот файл исходного кода в github.

Вот несколько эталонных сведений:

  with index defined before insertion:
    INSERT 1000000 rows in 6.71s
    SELECT 1000000 rows per Key index in 1.15s

  with index created after insertion:
    INSERT 1000000 rows in 2.91s
    CREATE INDEX 1000000 in 1.28s
    SELECT 1000000 rows per Key index in 1.15s

  without the index:
    INSERT 1000000 rows in 2.94s
    SELECT 1000000 rows per Key index in 129.27s

Таким образом, для огромного набора данных индекс стоит того, и создание индекса после вставки данных уменьшает используемые ресурсы! Даже если вставка будет медленнее, коэффициент усиления индекса будет огромным при выборе каждого ключа. Вы можете попытаться сделать то же самое с MS SQL или использовать другой ORM, и я думаю, вы будете плакать.;)

Ответ 3

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

UPD: если вы отсортировали список в исходном файле. И предположим, что у вас есть 411000keys для поиска. Вы можете использовать этот трюк. Сортируйте поисковые ключи в том же порядке с исходным файлом. Прочитайте первый ключ из обоих списков и сравните его. Если они отличаются, читайте дальше от источника до тех пор, пока они не равны. Сохраните позицию, если следующая клавиша в источнике тоже равна, сохраните ее тоже..etc. Если следующий ключ отличается, прочитайте следующий ключ из списка ключей поиска. Продолжайте до EOF.

Ответ 4

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

• https://en.wikipedia.org/wiki/Memory-mapped_file
• https://msdn.microsoft.com/en-us/library/ms810613.aspx
• fooobar.com/questions/418878/...
• fooobar.com/questions/32353/...
• http://msdn.microsoft.com/en-us/library/aa366761%28VS.85.aspx
• https://msdn.microsoft.com/en-us/library/windows/desktop/aa366537.aspx

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

http://torry.net/quicksearchd.php?String=memory+mapped+files&Title=No

Ответ 5

Метод, который нуждается в сортировке файла, но полностью исключает структуры данных:

Вам всего лишь нужна одна строка, поэтому зачем читать основную часть файла?

Откройте файл и переместите "get pointer" (извинения за разговор C) на полпути через файл. Вам нужно будет выяснить, есть ли у вас число или слово, но рядом должно быть рядом. Как только вы узнаете ближайший номер, вы знаете, если он выше или ниже, чем вы хотите, и продолжайте бинарный поиск.

Ответ 6

Идея, основанная на ответе Алексея Харланова. Я принял его ответ. Я только копирую его идею здесь, потому что он не уточнил (без псевдокода или более глубокого анализа алгоритма). Я хочу подтвердить, что он работает до его реализации.

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

Код:
В приведенном ниже коде sKey является текущим ключом в Small file. bKey - текущий ключ в файле Big:

LastPos:= 0
for sKey in SmallFile do 
 for CurPos:= LastPos to BigFile.Count do 
  if sKey = bKey 
  then 
    begin 
     SearchNext  // search (down) next entries for possible duplicate keys
     LastPos:= CurPos
    end
  else 
    if sKey < bKey 
    then break

Это работает, потому что я знаю последнюю позицию (в Большом файле) последнего ключа. Следующий ключ может быть только где-то на последней позиции; ON СРЕДНИЙ должен быть в следующих 440 записях. Тем не менее, мне даже не нужно всегда читать 440 записей ниже LastPos, потому что если мой sKey не существует в большом файле, он будет меньше, чем bKey, поэтому я быстро нарушу внутренний цикл и двигаюсь дальше.

Мысли?

Ответ 7

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

Вкратце, алгоритм:

mySet = dictionary of keys to look up
for each line in the file
    key = parse key from line
    if key in mySet
        output key and value
end for

Так как Delphi не имеет общего набора, я бы использовал TDictionary и проигнорировал значение.

Словарь поиска - O (1), поэтому он должен быть очень быстрым. Ваш ограничивающий фактор будет временем ввода-вывода файлов.

Я полагаю, что потребуется около 10 минут для кодирования и менее 10 минут для запуска.