PHP：有效地搜索通過集合

我有一個數字集合（任意順序）存儲。PHP：有效地搜索通過集合

僞代碼：

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

我需要能夠通過所有的集合，以搜索和返回group_IDs。例如，如果我仰望5，我應該回去['id_a','id_x']。我想用某種映射有效地做到這一點，不通過所有集合的所有數字循環。 我也希望能夠直接映射到每個鍵和返回集合（例如，'id_x'返回[3,5,10,21]）;我更喜歡這樣做，有效地完成沒有循環通過鍵。

編輯： 我可以使用數字作爲鍵和有效收回的「ID_ 」。或者，我可以用另一種方法，並使用'id_'作爲關鍵字並有效地獲取數字數組。但是，我希望能夠在兩個方向上高效地進行。我想我可以維護兩個數組，但似乎很混亂。

來源

2012-09-01 John R

您通過值必須循環_somehow_找到，如果它的陣列（即使環隱藏在存在一個內置的PHP函數） – knittl

你是指通過數組搜索？ – EbinPaulose

@kniitt我可以使用這些數字作爲關鍵字並有效地取回'id_ *'。我可以走另一條路，並使用'id_ *'作爲鍵，並有效地取回數組。但是，我希望能夠在兩個方向上有效地進行。我想我可以有兩個結構，但看起來很亂。 –

你的例子都顯示在有序數組值。如果它們始終處於排序順序，那麼您可以使用binary search來查找已知值。此代碼：

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-01 15:46:13

+1謝謝你。是的，我可以指出維護數組的順序並使用其中的變體。請，如果你有一秒鐘，提醒我什麼「>>」（我不能谷歌它）。 –

''''是右移，相當於乘以兩個因子。 – knittl

實際上'>>'是*除以2，但總會給出整數結果。 –

PHP：有效地搜索通過集合

回答

相關問題