1

我正在寻找可用于从整数流中生成批次的哈希函数。具体来说，我想将整数xi从一个集合或流（比如X）映射到另一组整数或字符串（比如Y），以便将许多xi映射到一个yj。在这样做的同时，我想确保有 at maxn xi映射到单个yj. 与散列一样，我需要能够可靠地找到y给定的x.

我想确保大多数映射到它们的数量yj接近（以避免从to非常稀疏的映射）。nxiXY

我能想到的一个函数是商：

int BATCH_SIZE = 3;
public int map(int x) {
  return x / BATCH_SIZE;
}

对于连续整数流，它可以很好地工作。例如流 1..9 将被映射到

1 -> 0
2 -> 0
3 -> 1
4 -> 1
5 -> 1
6 -> 2
7 -> 2
8 -> 2
9 -> 3

等等。但是，对于非连续的大整数和小批量（我的用例），这可以生成超稀疏映射（每个批次大部分时间只有 1 个元素）。

是否有任何标准方法来生成这样的映射（批处理）

4

1 回答 1

0

在这些假设下，没有办法让它工作。

您需要知道流中有多少项目及其分布，或者您需要放松将项目精确映射到批次的能力。

假设您有来自流的项目 a 和 b。您是否要将它们放在同一批次中？除非您知道是否要获得更多物品来填充 2 个或更多批次（如果您决定将它们分成不同批次），否则您无法回答这个问题。

如果您知道会有多少（甚至是大约），您可以根据它们进行分发并构建批次。假设您有字符串哈希（32 位上的均匀分布）。如果您知道您将获得 100 万个项目并且您想要 100 个批次，您可以生成 2^32 / (1.000.000 / 100) 的间隔并将其用作批次 ID ( yj)。这并不能保证您获得的批次恰好是 batch_size，但它们应该大约是 batch_size。如果分布不均匀，事情就比较困难了，但还是可以做到的。

如果您放松将项目映射到批次的能力，那么只需在它们从流中出来时将它们分组为每个 batch_size。如果你有空间，你可以保留一张蒸汽物品的地图以进行批处理。

于 2017-07-21T09:37:12.813 回答