Соответствующая структура данных для таблицы, которая использует диапазоны

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

Структура базы данных:

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 3

Как насчет какой-то двумерной структуры данных.

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

Для этой цели, вероятно, подойдет двумерный массив.

Затем вам понадобится некоторая функция для сопоставления конкретных значений X и Y с диапазонами, но это не должно быть слишком сложно.

Answer 4

Ну, все остальные ответы используют 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)] </p>

Answer 5

Я неравнодушен к 2-мерному массиву с функцией "hash", которая отображает диапазоны в конкретные адреса в таблице.

Итак, ваша базовая структура данных будет двухмерным массивом:

    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

самый простой вариант: создать массив массивов, где каждый массив состоит из 5 элементов: minX, maxX, minY, maxY, value, в вашем случае это будет

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

с небольшим набором данных, это будет работать нормально, если ваш набор данных больше, вы должны рассмотреть возможность использования базы данных.