查找8GB +文本文件中的"密钥"

Question

我有一些'小'文本文件,包含大约500000个条目/行.每行还有一个"键"列.我需要在一个大文件中找到这个密钥(8GB,至少2.19亿条目).找到后,我需要将大文件中的'Value'附加到小文件中,在行的末尾作为新列.

像这样的大文件:

KEY                 VALUE
"WP_000000298.1"    "abc"
"WP_000000304.1"    "xyz"
"WP_000000307.1"    "random"
"WP_000000307.1"    "text"
"WP_000000308.1"    "stuff"
"WP_000000400.1"    "stuffy"

简单地说,我需要在大文件中查找"密钥".

显然我需要在RAM中加载整个表(但这不是我有32GB可用的问题).大文件似乎已经排序了.我得检查一下.
问题是我无法使用类似TDictionary的快速查找,因为正如您所看到的,密钥并不是唯一的.

注意:这可能是一次性计算.我将使用该程序一次,然后扔掉它.因此,它不一定是最佳算法(难以实现).它只需要在适当的时间内完成(如1-2天).PS:我更喜欢没有DB这样做.

我正在考虑这个可能的解决方案:TList.BinarySearch.但似乎TList仅限于134,217,727(MaxInt div 16)项目.所以TList不会工作.

---

结论:
我选择了Arnaud Bouchez解决方案.他的TDynArray令人印象深刻!如果你需要处理大文件,我完全推荐它.
AlekseyKharlanov提供了另一个不错的解决方案,但TDynArray已经实现.

Answer 1

不要重新发明二进制搜索或B-Tree的轮子,而是尝试使用现有的实现.

将内容提供给SQLite3内存数据库(使用正确的索引,并且每10,000次INSERT执行一次事务),您就完成了.确保您定位Win64,以便在RAM中有足够的空间.您甚至可以使用基于文件的存储:创建速度稍慢,但使用索引时,按键查询将是即时的.如果您的Delphi版本中没有SQlite3支持(通过最新的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,我猜您会哭.;)

Answer 2

另一个答案,因为它是另一个解决方案.

我使用了TDynArray包装器及其排序和二进制搜索方法,而不是使用SQLite3数据库.

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

它比SQLite3内存解决方案快10倍以上.1000万行保留在Win32进程的内存中没有问题.

并且很好地了解了TDynArray包装器在实践中的工作原理,以及SSE4.2优化的字符串比较功能如何提供良好的结果.

我们的github存储库中提供了完整的源代码.

编辑:在Win64下有100,000,000行(1亿行),在此过程中使用超过10GB的RAM:

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

Answer 3

由于这是一次性任务.最快的方法是将整个文件加载到内存中,逐行扫描内存,解析密钥并将其与搜索键(键)进行比较并打印(保存)找到的位置.

UPD:如果您在源文件中已排序列表.并假设您有411000个键来查找.您可以使用此技巧:按源文件的顺序对搜索键进行排序.从两个列表中读取第一个密钥并进行比较.如果它们不同,请从源头读取,直到它们相等.保存位置,如果源中的下一个键也相等,也保存它.等等.如果下一个键不同,请从搜索键列表中读取下一个键.继续直到EOF.