合適的數據結構，使用範圍

Question

我有一個表，看起來像這樣：

 <22 23-27 
8-10 1.3 1.8 
11-13 2.2 2.8 
14-16 3.2 3.8 

，並繼續下去。所以我想查找這樣的值：

lookup(11,25) 

並得到響應，在這種情況下爲2.8。什麼是最好的數據結構用於這個？我有CSV格式的數據。

我正在尋找這個在PHP編程。

謝謝。

Answer 1

我當然不是說這是最好的，最有效的數據結構，但是這是我如何將數據映射到一個二維PHP數組非常近似於原始數據：

$fp = fopen('data.csv', 'r'); 
$cols = fgetcsv($fp); 
array_shift($cols); // remove empty first item 
$data = array(); 
while ($row = fgetcsv($fp)) { 
    list($min, $max) = explode('-', $row[0]); 
    // TODO: Handle non-range values here (e.g. column header "<22") 
    $data["$min-$max"] = array(); 
    for ($x = 0; $x < count($cols); $x++) { 
    $data["$min-$max"][$cols[$x]] = $row[$x + 1]; 
    } 
} 

你會再需要添加一些分析邏輯在lookup功能：

function lookup($row, $col) { 
    $return = null; 
    // Loop through all rows 
    foreach ($data as $row_name => $cols) { 
    list($min, $max) = explode('-', $row_name); 
    if ($min <= $row && $max >= $row) { 
     // If row matches, loop through columns 
     foreach ($cols as $col_name => $value) { 
     // TODO: Add support for "<22" 
     list($min, $max) = explode('-', $col_name); 
     if ($min <= $col && $max >= $col) { 
      $return = $value; 
      break; 
     } 
     } 
     break; 
    } 
    } 
    return $return; 
} 

Answer 2

如何處理某種二維數據結構。

X "coordinates" being <22, 23-27 
Y "coordinates" being ... 

一個二維數組可能會用於此目的。

然後，您需要一些函數將特定的X和Y值映射到範圍，但這不應該太難。

Answer 3

最簡單的選擇：創建陣列，其中每個陣列由5個元素的陣列：其minX，maxX的，MINY，MAXY，值，在你的情況下，將

$data = array(
     array(8, 10, 0, 22, 1.3), 
     array(8, 10, 23, 27, 1.8), 
     array(11, 13, 0, 22, 2.2), etc 

寫一個循環，通過去用一個小的數據集，這將很好地工作，如果你的數據集是更大的，你應該考慮使用一個數據庫

function find($x, $y) { 
     foreach($data as $e) { 
     if($x <= $e[0] && $x >= $e[1] && $y <= $e[2] && $y >= $e[3]) 
       return $e[4]; 
} 

：每一個元素和最小&最大值與你的論點進行比較。

Answer 4

數據庫結構：

values 
------ 
value 
x_range_start 
x_range_end 
y_range_start 
y_range_end 

代碼：

function lookup(x, y) { 
    sql = " 
     SELECT * FROM values 
     WHERE 
      x >= x_range_start 
      AND 
      x <= x_range_end 

      AND 
      y >= y_range_start 
      AND 
      y <= y_range_end 
    " 

    /---/ 
} 

你的數據將映射到數據庫中，像這樣：

 <22 23-27 
8-10 1.3 1.8 
11-13 2.2 2.8 
14-16 3.2 3.8 

(value, x start, x end, y start, y end) 
1.3, 0, 22, 8, 10 
1.8, 23, 27, 8, 10 
2.2, 0, 22, 11, 13 
... 

基本上存儲x和y軸的開始和結束號碼錶中的每個值。

Answer 5

我偏愛二維數組，其中包含一個「散列」函數，該函數將範圍映射到表中的特定地址。

所以你的基礎數據結構將是一個2維數組：

0  1 
0 1.3 1.8 
1 2.2 2.8 
2 3.2 3.8 

那麼你就寫兩個功能：

int xhash(int); 
int yhash(int); 

那把原來的參數，並將其轉換成索引到你的數組。所以xhash執行轉換：

8-10 0 
11-13 1 
14-16 2 

最後，您的查找操作變爲。

function lookup($x, $y) 
{ 
    $xIndex = xhash($x); 
    $yIndex = yhash($y); 
    // Handle invalid indices! 

    return $data[$xIndex][$yIndex]; 
} 

Answer 6

那麼，其他答案都使用2D數組，這意味着使用2D循環來檢索它。其中，如果你的範圍是年齡範圍或類似的東西，可能是有限的（只有這麼多的年齡段！），而不是一個問題（什麼是幾百次迭代？）。如果你的範圍預計會擴大到巨大的數字，那麼在哈希映射上玩一玩可能是你最好的選擇。所以，你創建了一個哈希函數來將任何數字轉換成相關的範圍，然後你直接查找，而不是循環。這將是O（1）訪問而不是O（n^2）。所以你的哈希函數可能是這樣的：function hash（n）{if（n < 22）return 1;如果（n < 25）返回2;返回-1; }，然後你可以根據這些散列值（1,2等）來指定你的範圍，然後去$ data [hash（11）] [hash（25）]