<h2>没什么想法</h2>
<p><strong>BK树</strong><br/>
感谢本·霍伊特和他与<a href="https://github.com/benhoyt/pybktree/issues/5" rel="nofollow noreferrer">issue</a>的联系,我将从中吸取教训。话虽如此,上述问题的第一个观察结果是BK树不是完全对数的。根据你告诉我们的,你通常的d是~6,这是你绳子长度的3/10。不幸的是,这意味着,如果我们从问题中查看表格,您将得到介于O(N^0.8)到O(N)之间的复杂性。在乐观的情况下
指数为0.8(可能会稍微差一点),您的10B条目的改善系数约为100。因此,如果你有一个相当快的BK树实现,那么使用它们或将它们作为进一步优化的基础仍然是值得的</p>
<p>这样做的缺点是,即使并行使用1000棵树,也只能从并行化中得到改进,因为树的性能取决于<strong>d</strong>,而不是树中的节点数量。然而,即使你用一台大型机器同时运行所有1000棵树,我们的节点数/棵数也达到了约10M,而你报告的速度很慢。不过,从计算角度来看,这似乎是可行的</p>
<p><strong>暴力手段</strong><br/>
如果你不介意付一点钱的话,我会研究谷歌云大查询之类的东西,如果这不与某种数据保密性冲突的话。他们将为您强制执行解决方案-收取费用。当前的查询费率为每TB 5美元。您的数据集是~10B行*20chars。每个字符占用一个字节,如果您采取懒惰的方式,一个查询将占用200GB,因此每个查询大约需要1美元。<br/>
但是,由于费用是按列中数据的每个字节计算的,而不是按问题的复杂程度计算的,因此您可以通过将字符串存储为每字母2比特的方式对此进行改进,这将为您节省75%的费用。<br/>
进一步改进,您可以以这样一种方式编写查询,它将一次请求十几个字符串。为了查询的目的,您可能需要小心使用一批类似的字符串,以避免使用过多的一次性字符串阻塞结果</p>
<p><strong>对BK树的暴力强制</strong><br/>
由于如果您按照上述路线进行,您将不得不根据数量付费,因此所需计算量的~100倍下降将变成价格的~100倍下降,这可能非常有用,特别是如果您有大量查询要运行。<br/>
但是,您需要找到一种方法,将此树存储在多层数据库中,以便递归查询,因为Bigquery定价取决于查询表中的数据量<br/>
构建一个用于递归处理查询以最小化成本的智能批处理引擎可能是一个有趣的优化练习</p>
<p><strong>语言选择</strong><br/>
还有一件事。虽然我认为Python是一种很好的快速原型设计、分析和思考代码的语言,但总体而言,您已经过了那个阶段。您目前正在寻找一种方法,以尽可能快地执行<strong>特定、定义明确且经过深思熟虑的操作。正如<a href="https://codegolf.stackexchange.com/questions/197565/can-you-calculate-the-average-levenshtein-distance-exactly">this example</a>所示,Python并不是一种很好的语言。虽然我使用了Python中我能想到的所有技巧,但Java和C解决方案的速度仍然快了好几倍。(更不用说打败我们所有人的rust了——但他在算法上也打败了我们,所以很难比较。)因此,如果你从python转向更快的语言,你可能会获得另一个、十个甚至更多的性能提升。这可能是另一个有趣的优化练习。<br/>
<strong>注意</strong>:我对这个估计相当保守,因为FuzzyWuzy已经提供在后台使用C库,所以我不太确定有多少工作仍然依赖于python。我在类似情况下的经验是,从纯python(或者更糟糕的是,纯R)到编译语言,性能增益可以是100倍</p>