6

我有一组整数，每个整数的大小为 8,9 或 10 位。我有数以百万计的。我想将它们中的每一个映射到 1 到 1000 范围内的整数。我不能对整数做一个简单的 mod，因为这些数字的发布方式存在系统偏差（例如，偶数比奇数），所以

$id % 1000

将产生更频繁的偶数和不太频繁的奇数。是否有任何简单的函数（执行按位运算的数学或棘手的函数）可以帮助我在 Perl 或 R 中获得这种映射？提前非常感谢。

4

2 回答 2

8

您实际上是在要求将数字映射到 0 到 999 之间的值的哈希函数。

要构造它，您可以首先使用散列函数去除映射到值中的任何系统模式，然后使用 mod 将输出限制为 0 到 999 之间的值。

这是该想法的 R 实现：

library(digest)
set.seed(1)

(x <- sample(1e9, size=6))
# [1] 265508664 372123900 572853364 908207790 201681932 898389685

## To hash R's internal representation of these numbers
strtoi(substr(sapply(x, digest), 28, 32), 16L) %% 1e3
# [1] 552 511 233 293 607 819

## Or, for a hash mapping that's comparable to other programs' md5 hash 
## implementations
strtoi(substr(sapply(as.character(x), digest, serialize=FALSE),28,32),16L) %% 1e3
# [1] 153 180 892 294 267 807

将那条线分解成碎片应该使它的作用更清晰：

## Compute md5 hash of R representation of each input number
(sapply(x, digest))
# [1] "a276b4d73a46e5a827ccc1ad970dc780" "328dd60879c478d49ee9f3488d71a0af"
# [3] "e312c7f09be7f2e8391bee2b85f77c11" "e4ac99a3f0a904b385bfdcd45aca93e5"
# [5] "470d800a40ad5bc34abf2bac4ce88f37" "0008f4edeebbafcc995f7de0d5c0e5cb"

## Only really need the last few hex digits
substr(sapply(x, digest), 28, 32)
# [1] "dc780" "1a0af" "77c11" "a93e5" "88f37" "0e5cb"

## Convert hex strings to decimal integers
strtoi(substr(sapply(x, digest), 28, 32), 16L)
# [1] 903040 106671 490513 693221 560951  58827

## Map those to range between 0 and 999
strtoi(substr(sapply(x, digest), 28, 32), 16L) %% 1e3
# [1]  40 671 513 221 951 827
于 2013-01-16T19:46:50.800 回答
6

除非您可以定义可用数字的数学属性（例如，它们是偶数、指数分布等），否则任何确定性函数都无法将这些数字均匀地映射到任何给定范围内。

您选择的每个函数都必须将某一类数字映射到输出范围内的一个小区域。如果散列函数很复杂，则可能难以先验地确定将被错误处理的类。当然，这是散列函数的普遍问题。您总是必须对输入进行假设。

理论上，唯一的解决方案（如果您对数字一无所知或无法分析它们）是将输入数字与真正的随机序列进行异或，然后使用mod操作。

在实践中，乔希的解决方案可能会奏效。

注意：如果您可以在散列数字时分析结果数组，则可以更改散列函数以均匀分布结果。这可能适用于创建哈希表以供以后搜索。但是，这似乎不是您的应用程序。

于 2013-01-16T20:05:57.897 回答