问题
在服务器上，我在json文件中托管id。从客户端，我需要命令服务器与这些id相交，有时甚至否定这些id(即使客户端指示服务器执行其操作，这些id也不会传播到客户端)。
我通常有1000个ID，通常有100000个ID，最多有56000000个ID，其中每个值都是唯一的，在-1000000到+10000000之间。
这些id文件是稳定的，不会更改(因此，如果需要，可以为其生成不同的表示，以便更好地适应计算)。
样本ID
最大文件大小
我需要一个算法，在大多数情况下，会在亚秒范围内与id相交。你有什么建议？我用java编写代码，但为了解决这个问题，我并不局限于java(我可以使用JNI桥接到本地语言)。
需要考虑的潜在解决方案
尽管你们不能仅限于以下解决方案的广泛考虑，但以下是我为解决这一问题而进行的内部辩论。
- 神经网络预限定符：为每个接受另一个id列表的id列表训练一个神经网络，以对其交叉点潜力进行评分(0表示绝对没有交叉点，1表示绝对有交叉点)。由于神经网络在模式识别方面既好又高效，我正在考虑在其背后预先确定一个更耗时的算法
- 汇编语言：在Linux服务器上，编写一个执行此类算法的汇编模块。我知道汇编在维护和编码方面是一团糟，但有时需要高度优化算法的速度，而不需要高级编译器的开销。也许这个用例足够简单，可以从直接在Linux服务器上执行的汇编语言例程中获益(然后我会一直注意使用相同的处理器，以避免经常重写)？或者，也许C离汇编足够近，可以生成干净优化的汇编代码，而不需要维护汇编代码的开销
- 图像和GPU:可以使用GPU和图像处理，而不是比较id，我可以BITAND图像。也就是说，我创建了一个B&每个ID列表的W图像。由于每个id都有在-10000000到+100000000之间的唯一值(其中最多使用56000000个)，因此图像将主要是黑色的，但如果设置了相应的id，则像素将变为白色。然后，我不保留id列表，而是保留图像，并对这两个图像执行BITAND操作以使它们相交。这可能确实很快，但将生成的图像转换回id可能是瓶颈。此外，每个图像都可能非常大(可能太大了，这不是一个可行的解决方案)。200000000比特序列的估计值为23MB，仅将其加载到内存中就相当苛刻
- 字符串匹配算法：字符串比较有许多经过调整的算法，这些算法通常在执行任务时非常高效。为每个id集创建一个二进制文件。每个id的长度为4个字节。相应的二进制文件会将每个id作为其4个字节的等价物进行排序。然后，算法可以处理最小的文件，将每个4个字节序列作为字符串匹配到另一个文件中
我遗漏了什么吗？还有其他可能的解决方案吗？这些方法中的任何一种都值得深入研究吗？
我还没有尝试任何东西，因为我想在投入我认为将花费大量时间之前确保一个策略。
编辑#1：
解决方案可能是列表中每个扇区的哈希图吗？如果信息的结构使每个id都位于其相应的哈希密钥中，那么，可以顺序运行id集中较小的id，并且首先将id匹配到较大的id集中需要对要匹配的值进行哈希，然后将相应的id顺序匹配到该密钥匹配中？
这应该使算法成为一个基于O(n)时间的算法，并且由于我会选择最小的id集作为顺序运行的id集，因此n很小。这有道理吗？这就是解决方案吗？
类似这样的东西(其中H条目是散列)：
{"H780"：【45902780、46062780、-42912780、-19812780、25323780、40572780、-301131780、60266780、-26203780、46152780、67216780、71666780、67146780、46162780、67226780、67781780、47021780、46122780、19973780、22113780、67876780、42692780、-1843780、30993780、67711780、67791780、44036780、45904780、-42142780、18703780、60276780、46182780、63600780、63680780、-704 86780、-68290780、-18493780、-68210780、67731780、46092780、63450780、30074780、24772780、26483780、68371780、18483780、18723780、29834780、46202780、67821780、29594780、46082780、44632780、68406780、68310780、44056780、67751780、45912780、40842780、44642780、18743780、68220780、44066780、46142780、26193780、67681780、46222780、67761780]，"H782"：【27343782、67456782、18693782、43322782、-378732782、46152782、19113782、68411782、18763782、67466782、68400782、68320782、34031782、45056782、26713782、61776782、67791782、44176782、44096782、34041782、39324782、21873782、67961782、18703782、44186782、-3143782、67721782、68340782、36103782、19143782、19223782、31711782、66350782、433】6278218733782、-29233782、67811782、-4407782、-19623782、68290782、31721782、19233782、65726782、27313782、43352782、68280782、67346782、44086782、67741782、19203782、19363782、29583782、67911782、6751782、26663782、67910782、19213782、45992782、17201782、43372782、19992782、44066782、46142782、29993782]，"H540"：[…
您可以将每个文件(id列表)转换为长度为200_000_0001的位数组，如果列表包含值j-100_000_000，则设置索引j处的位。这是可能的，因为id值的范围是固定的并且很小。
然后，您可以简单地使用逐位and和not操作来交叉和否定id列表。根据所使用的语言和库，它需要按元素进行操作：在数组上迭代，并将相应的操作应用于每个索引。
最后，您应该衡量您的性能，并决定是否需要进行一些优化，例如并行化操作(您可以在不同处理器上处理阵列的不同部分)、将一些阵列(或所有阵列)预加载到内存中、使用GPU等
首先，位图方法将以巨大的内存开销产生所需的性能。您需要对其进行基准测试，但我预计时间可能为0.2秒，这几乎完全取决于从磁盘加载数据，然后读取结果的成本。
然而，还有另一种方法值得考虑。在大多数情况下，它将使用较少的内存。对于您所声明的大多数文件，它将表现良好。
首先，让我们使用Cap‘n Proto作为文件格式。类型可以是这样的：
struct Ids {
is_negated @0 :Bool;
ids @1 :List(Int32);
}
关键是ID始终保持排序。因此，列表操作是一个并行运行它们的问题。现在：
- 应用
not只是翻转is_negated - 如果两者都不否定，则需要在两个列表中查找ID
- 如果第一个没有取反，而第二个取反，您只想在第一个中找到不在第二个中的ID
- 如果第一个被否定，而第二个没有，那么您只想在第二个中找到不在第一个中的ID
- 如果两者都被否定，您只想在任一列表中找到所有id
如果您的列表有100k个条目，那么该文件大约为400k。not需要拷贝400k的数据(非常快)。与另一个同样大小的列表相交需要进行20万次比较。整数比较在一个时钟周期内完成，分支预测失误大约需要10-20个时钟周期。因此，您应该能够在0-2毫秒的范围内完成此操作。
在最坏的情况下，56000000个文件将占用超过200 MB的空间，其中两个文件相交可能需要大约2亿次操作。这在0-2秒的范围内。
对于5600万个文件和1万个文件，您的时间几乎都花在5600万文件中的数字上，而不是10万文件中。你可以通过添加一个"；"飞驰"；在该模式下，您在较大的文件中进行二进制向前搜索，寻找下一个匹配的数字并选择其中的大部分。请注意，此代码往往很棘手，并且包含许多预测错误。您必须对其进行基准测试，以了解需要多大的尺寸差异。
一般来说，这种方法会对最大的文件造成损失。但对于您所谈到的大多数文件大小来说，这将是一个巨大的胜利。