6

I've a set of integers each of which have 8,9 or 10 digits in size. I've millions of them. I want to map each one of them to an integer in the range of 1 to 1000. I cannot do a simple mod on the integers as there are systemic biases in the way these numbers have been issued (for example even numbers are more likely than odd numbers), so 

$id % 1000

would yield more frequent even numbers and less frequent odd numbers. Are there any simple functions (either mathematical or tricky functions that do bitwise operations) which would help me get to this mapping either in Perl or R? Thanks much in advance.

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

利用可能な数値の数学的特性を定義できない限り (たとえば、偶数、指数分布など) 、決定論的関数でこれらの数値を特定の範囲に均等にマップする方法はありません。

選択するすべての関数は、特定のクラスの数値を出力範囲の小さな領域にマップする必要があります。ハッシュ関数が複雑な場合、誤って処理されるクラスをアプリオリに判断するのが難しい場合があります。もちろん、これはハッシュ関数の一般的な問題です。入力で常に何かを想定する必要があります。

理論的には、唯一の解決策は (数値について何も知らないか、数値を分析できない場合)、入力数値を真にランダムなシーケンスで xor し、mod演算を使用することです。

実際には、Josh のソリューションはおそらくうまくいくでしょう。

注: 数値をハッシュしている間に結果の配列を分析できる場合は、ハッシュ関数を変更して結果を均等に分散できる場合があります。これは、後で検索するためのハッシュ テーブルを作成するのに役立つ場合があります。ただし、これはあなたのアプリケーションではないようです。

于 2013-01-16T20:05:57.897 に答える