0

保存する番号のコレクション（任意の順序）があります。

擬似コード：

id_a:[3,5,7,11]
id_x:[3,5,10,21]
id_b:[12,24,25,26]
etc.

すべてのコレクションを検索してgroup_IDを返すことができる必要があります。たとえば、5を検索すると、戻る必要があります['id_a','id_x']。すべてのコレクションのすべての数をループするのではなく、ある種のマッピングを使用してこれを効率的に実行したいと思います。また、各キーに直接マップして、コレクションを取得できるようにしたい（たとえば、'id_x'returns [3,5,10,21]） ; 繰り返しますが、私はこれがキーをループすることなく効率的に行われることを好みます。

編集： 数字をキーとして使用して、効率的に「id_」を取り戻すことができます。または、逆に「id_」をキーとして使用して、数値の配列を効率的に取得することもできます。でも、両方向に効率よく行けるようになりたいです。2つの配列を維持できると思いますが、それは面倒なようです。

4

1 に答える 1

3

例はすべて、配列値をソートされた順序で示しています。それらが常にソートされた順序である場合は、バイナリ検索を使用して既知の値を見つけることができます。このコード：

function binarySearch($needle, array $haystack) {
    $high = count($haystack) - 1;
    $low = 0;
    $mid = false;
    while ($high >= $low) {
        $mid = ($high + $low) >> 1;
        $t = $needle - $haystack[$mid];
        if ($t < 0) {
            $high = $mid - 1;
        } elseif ($t > 0) {
            $low = $mid + 1;
        } else {
            return $mid;
        }
    }

    return $mid;
}

function searchArrays($needle) {
    static $id_a = array(3,5,7,11);
    static $id_x = array(3,5,10,21);
    static $id_b = array(12,24,25,26);
    static $arrayNames = array('id_a', 'id_x', 'id_b');

    $rv = array();
    foreach ($arrayNames as $arrayName) {
        $array = $$arrayName;
        $index = binarySearch($needle, $array);
        if ($array[$index] == $needle) {
            $rv[] = $arrayName;
        }
    }

    return $rv;
}

$needles = range(3,8);
foreach ($needles as $needle) {
    $result = searchArrays($needle);
    printf("searchArrays(%s)=%s\n", $needle, join(', ', $result));
}

以下を出力します。

searchArrays(3)=id_a, id_x
searchArrays(4)=
searchArrays(5)=id_a, id_x
searchArrays(6)=
searchArrays(7)=id_a
searchArrays(8)=
于 2012-09-01T15:46:13.787 に答える