struttura dati appropriata per la tabella che utilizza gli intervalli

Question

Ho una tabella che assomiglia a questo:

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

e si va avanti. Così mi piacerebbe occhiata un valore come questo:

lookup(11,25) 

e ottenere la risposta, in questo caso 2.8. Qual è la migliore struttura dati da usare per questo? Ho i dati in formato CSV.

Sto cercando di programmarlo in PHP.

Grazie.

Answer 1

che sto certamente non sostenendo questo è il migliore o più efficiente struttura dei dati, ma questo è come mi piacerebbe mappo i dati in un array PHP bidimensionale che ricorda molto da vicino i dati grezzi:

$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]; 
    } 
} 

Farebbe quindi bisogno di aggiungere un po 'di logica di analisi nella funzione lookup: struttura

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

Che ne dici di una sorta di struttura dati bidimensionale.

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

Una matrice bidimensionale probabilmente funzionerebbe per questo scopo.

Avrai quindi bisogno di una funzione per mappare gli specifici valori X e Y agli intervalli, ma ciò non dovrebbe essere troppo difficile.

Answer 3

l'opzione più semplice: creare array di array, dove ogni matrice composta da 5 elementi: minX, maxX, miny, maxy, valore, nel caso sarebbe

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

scrivere un ciclo che attraversa ogni elemento e lo confronta min & valori massimi con i tuoi argomenti:

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

con un piccolo set di dati questo funzionerà bene, se il set di dati è più grande si dovrebbe considerare l'utilizzo di un database.

Answer 4

Database:

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

Codice:

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 
    " 

    /---/ 
} 

suoi dati sarebbero mappare al database in questo modo:

 <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 
... 

Fondamentalmente memorizzare iniziano l'asse X e Y e numeri finali per ogni valore nella tabella.

Answer 5

Sono parziale all'array 2 Dimensional con una funzione "hash" che associa gli intervalli in indirizzi specifici nella tabella.

Così la vostra struttura dati sottostante sarebbe una matrice 2 dimensionale:

0  1 
0 1.3 1.8 
1 2.2 2.8 
2 3.2 3.8 

Poi si dovrebbe scrivere due funzioni:

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

che prendono gli argomenti originali e li converte in indici nel vostro array . Quindi xhash esegue la conversione:

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

Infine, l'operazione di ricerca diventa.

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

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

Answer 6

Bene, le altre risposte utilizzano tutti array 2D, che significa utilizzare un ciclo 2D per recuperarlo. Che, se le tue gamme sono di età o qualcosa di simile, può essere finito (ci sono solo così tante fasce di età!), E non un problema (cosa sono alcune centinaia di iterazioni?). Se ci si aspetta che i range si ridimensionino a numeri enormi, una giocata su una mappa hash può essere la soluzione migliore. Quindi, crei una funzione di hashing che trasforma qualsiasi numero nell'intervallo pertinente, quindi esegui ricerche dirette, anziché un ciclo. Sarebbe O (1) accesso invece di O (n^2).

Quindi la tua funzione di hash potrebbe essere: funzione hash (n) {if (n < 22) return 1; se (n < 25) restituisce 2; ritorno -1; }, e quindi puoi specificare i tuoi intervalli in termini di questi valori hash (1, 2, ecc.), e poi vai solo $ data [hash (11)] [hash (25)]