通过散列来改进集合比较(过于聪明......？)

Question

在我最后一次失败后,尝试在这里提出一个问题,这次我正在尝试一个更精确的问题:

是)我有的:

1. 一个巨大的数据集(有限的,但我浪费了多天的多核处理时间来计算它......)ISet<Point>.
2. 输入值列表,范围为0到2 ⁿ,n≤17

我需要的:

3)[1],[2]的表格,其中我将[2]的每个值映射到值[1]

处理:

对于这个计算,我有一个公式,它取一个位值(来自[2])和一组位置(来自[1])并创建一个新的ISet<Point>.我需要找出哪个原始集合等于结果集合(即"A7"表中的"单元格"可能指向"B").

天真的方式:

在[1]的值列表中计算new ISet<Point>和use .Contains(mySet)或类似的东西.我在此概念验证/宠物项目的先前版本中做到了这一点,当我开始提供大量数据时,它已经死了.是的,我使用了一个分析器.不,这不是系统中唯一缓慢的部分,但是我在这个天真的查找/映射中浪费了相当多的时间.

问题,最后:

由于我基本上只需要重新映射到输入,我考虑为列表创建一个散列值列表ISet<Point>,对我的处理结果做同样的事情,因此避免比较整个集合.

这是一个好主意吗？你会称之为过早的优化(我知道上面的天真的方式太慢了,但我应该先实现一些不那么聪明的东西吗？性能在这里非常重要,再想想运行时间)？任何其他建议,以缓解这里的burdon或想法我应该阅读？

---

更新:很抱歉没有提供更好的解释或样品.

[1]的样本(注意:这些是真正可能的数据点,但显然它是有限的):

new List<ISet<Point>>() {
  new HashSet() {new Point(0,0) },
  new HashSet() {new Point(0,0), new Point(2,1) },
  new HashSet() {new Point(0,1), new Point(3,1) }
}

[2]只是长度为n的布尔矢量.对于n = 2,它是

• 0,0
• 0,1
• 1,0
• 1,1

基本上我可以使用int或long来做那个.

现在我有一个函数,它接受一个向量和一个ISet<Point>并返回一个新的ISet<Point>.这不是1:1的转换:一组5可能会导致一组11或其他.将所得的ISet<Point> 被然而保证是输入的一部分.

使用字母表示位向量的一组点和数字,我从这开始

  A  B  C  D  E  F
1
2
3
4
5
6
7

我最终需要的是

  A  B  C  D  E  F
1 -  C  A  E  -  -
2 B  C  E  F  A  -
3 ................
4 ................
5 ................
6 F  C  B  A  -  - 
7 E  -  C  A  -  D

在这些项目中有几个代价高昂的操作,一个是准备点集([1]).但是这个问题是关于现在的匹配:我可以轻松地(或多或少,现在不那么重要)计算给定位向量和源ISet的目标ISet.现在我需要在原始集中匹配/找到它.

整个野兽将成为状态机,其中点集是有效状态.后来我不关心各个州,我实际上可以通过任何东西(一封信,一个索引,等等)来引用它们.我只需要保持联想:

1,B => C.

---

更新:Eric询问是否可以使用HashSet.答案是肯定的,但前提是数据集足够小.我的问题(哈希)是:对于这个哈希集,可能采用哈希算法是否可能/一个好主意？我的想法是这样的:

• 走(懒洋洋地生成)列表/序列ISet<Point>(我可以改变这种类型,我只想强调它是一组数学点,没有重复).

  • 创建一个更简单的输入表示(一个哈希？)并存储它(在一个哈希集？)
  • 计算此输入的所有目标集,但仅再次存储简单表示(参见上文)
  • 丢弃该套装

• 修复映射(等于hash = equal state)

好主意？有这个问题？我能想出的一个是碰撞(这有多大可能？) - 我不会知道一个好的哈希函数开始......

Answer 1

好吧，我想我至少现在明白了这个问题。让我看看是否可以改写。

让我们首先将集合排除在外。我们将保持抽象。

您有一个大列表 L，其中包含引用类型 S（表示“集合”）的实例。这样的列表在逻辑上当然是从自然数 N 到 S 的映射。

L: N --> S

S 具有可以比较两个实例的引用相等性和值相等性的属性。也就是说，可以有两个 S 实例，它们的引用不相等，但逻辑上表示相同的值。

您有一个函数 F，它采用 V 类型的值（“向量”）和 S 类型的实例，并生成 S 类型的另一个实例。

F: (V, S) --> S

此外，您知道如果从 L 给 F 一个 S 实例，那么 S 的结果实例将是值等于列表中的某个值，但不一定是引用 equals。

您面临的问题是：给定 S 的实例 s（它是调用 F 的结果），哪个成员 L(n) 的值等于 s？

是的？

简单的方法——沿着 L(1), L(2), ... 一路测试集合相等性会非常慢。它至少与 L 的大小成线性关系。

我可以想到几种不同的方法来进行。最简单的是你最初的想法：让 L 成为一个列表以外的东西。你能把它HashSet<S>改为 吗List<S>？如果你在 S 上实现哈希算法和相等方法，那么你可以构建一个快速查找表。

如果这不适合，那么我们将探索其他选择。

更新：

好的，我可以看到两种基本的方法来处理你的记忆问题。(1) 使用比当前实现小得多的数据结构将所有内容保留在内存中，或者 (2) 更改在磁盘上存储内容的方式，以便可以在内存中存储“索引”并快速转到正确的“页面”磁盘文件以提取您需要的信息。

您可以将一个点表示为一个短整型，其中顶部字节是 x，底部字节是 y，而不是将其表示为两个 int；节省 75%。

一组点可以实现为短裤的排序数组，这非常紧凑并且易于为其编写哈希算法。

这可能是我会采用的方法，因为您的数据非常可压缩。