0

6つの一意の文字列の配列(事前にはわからず、常にランダムな順序で与えられます)が与えられた場合、これらの文字列をマップして、各文字列に1〜6(または0〜5)の番号を割り当てることができるようにするにはどうすればよいですか? . 次回のスクリプト実行時に同じ番号が割り当てられますか?

また、スクリプトを実行するたびにすべての文字列が渡されるわけではないことも付け加えておきます。

例えば

// Script Run 1: 
string1 => 2
string2 => 6
string3 => 5
string6 => 1


// Script Run 2: 
string3 => 5
string4 => 4
string2 => 6
string5 => 3

// Note how strings 2 and 3 have the same mapping

ハッシングと mod(6) の線に沿って何かを想定していますが、実装方法がわかりません。助言がありますか？

注: これはスクリプト内にあり、セッションは利用できません

前もって感謝します

4

1 に答える 1

1

数値を割り当てるモジュラスの使用例

各文字列を 0 ～ 5 または 1 ～ 6 の数値に制限し、変化するデータ セットや不完全なデータ セットを使用する必要がある場合、目的の最終結果を達成することは不可能です。6 つの文字列を取り、それらを crc し、モジュラス 6 を実行して結果を表示するとします。入力:

Array
(
    [0] => string1
    [1] => string2
    [2] => string3
    [3] => string4
    [4] => string5
    [5] => string6
)

(crc32を使用してsprintf('%u', crc32('string')):

Array
(
    [0] => 742935113
    [1] => 3040943091
    [2] => 3259378533
    [3] => 1545780934
    [4] => 723881552
    [5] => 2989285354
)

の結果crc32 % 6:

Array
(
    [0] => 5
    [1] => 1
    [2] => 1
    [3] => 4
    [4] => 2
    [5] => 1
)

ご覧のとおり、「string2」、「string3」、および「string6」はすべてバケットとの衝突があり、その結果、「1」が割り当てられました。衝突検出では+1、空のバケットを見つけるまでの単純な方法が使用されます。この例。したがって、bucket配列は次のようになります。

Array
(
    [0] => string6
    [1] => string2
    [2] => string3
    [3] => string5
    [4] => string4
    [5] => string1
)

次回、元の入力から取り除くと[1] => string2、6 つの結果の配列は次のようになります。

Array
(
    [0] => 
    [1] => string3
    [2] => string5
    [3] => string6
    [4] => string4
    [5] => string1
)

これは、少数のキーでデータセットが不完全な場合に何が起こるかを示しています。

問題は、load. 6 つの可能なテキストがあり、6 つしかないため、これの負荷は 100%bucketsです。ハッシュ テーブルを作成するときは、負荷を 0 に近づけたいと考えています。また、6 つのエントリで負荷が 50% の場合、12 個のバケットが利用可能である必要があります。

覚えておいてください

PHP でa を使用している間modulusは、最大整数サイズにも注意する必要があります。これは、モジュラス操作に使用される値が整数にキャストされるためです。

モジュラスのオペランドは、処理前に (小数部分を取り除くことによって) 整数に変換されます。

システムに応じて、32 ビットまたは 64 ビットのいずれかになります。署名されていない crc32 は 32 ビット システムの最大キャップを超え、int キャップを返します。これは、数値の半分が (統計的に) 同じバケットで終わることを意味します。 '。

私たちは何ができる？

問題は、選択できる数の範囲です。異なる文字列番号を割り当てるための目的のアプリケーションに応じてcrc32、結果からの衝突の数が小さなデータセットの場合は最小限になるため、実数を使用できます - ただし、入力テキスト (または説明されているように小さな範囲)、割り当てられた数値を各実行で一定に保ちながら、部分的なデータセットを許可するソリューションはありません。スクリプトが実行されるたびに入力文字列がランダムな順序で並べられているため、実行ごとに異なる時間に処理されると、衝突によって順序が逆になる可能性があるため、結果の整数を毎回同じに保つ方法はまったくありません。

目的がファイルにラベルを付けること、または何かにアクセスする手段である場合は、より大きなハッシュを使用し、modサイズに合わせないようにしてください。

于 2013-02-13T04:05:12.463 に答える