PHP, in_array и быстрый поиск (в конце) в массивах

Question

У меня есть сомнения по поводу того, как лучше выполнить быстрый поиск в массивах (я говорю о конкретном случае).

Предположим, у меня есть массив L = [A, B, C] (когда я начинаю). В то время как программа работает, может быть L будет расти (но к концу), один из возможных случаев, когда я буду выполнять поиск, это L = [A, B, C, D, E].

Дело в том, что при поиске значения, которые я хочу найти, могут быть только D и E. Теперь я использую find_array (elem, array), но эту функцию нельзя «настроить» для поиска начиная с конца и уменьшая индекс, и я «боюсь», что для всех поисков функция in_array проверит все элементы с более низкими индексами, прежде чем найдет искомое значение.

¿Есть еще одна функция поиска, которая лучше подходит для моей проблемы? ¿Как внутренне работает функция in_array?

Заранее спасибо

Answer 1

Я предполагаю, что in_array - это линейный поиск от 0 до n-1.

Самый быстрый поиск будет состоять в том, чтобы сохранить значения в качестве ключей и использовать array_key_exists.

$a['foo'] = true;
$a['bar'] = true;

if (array_key_exists('foo', $a)) ...

Но если это не вариант, вы можете легко создать свой собственный для индексированных массивов:

function in_array_i($needle, array $a, $i = 0);
{
  $c = count($a);
  for (;$i < $c; ++$i)
    if ($a[$i] == $needle) return true;
  return false;
}

Он начнется с $i, который вы можете отслеживать, чтобы пропуститьпервые элементы.

Или альтернативно ...

function in_array_i($needle, array $a, $i = 0);
{
  return in_array($needle, $i ? array_slice($a, $i) : $a);
}

Вы можете проверить, какой из них быстрее.

Answer 2

Что касается вашего комментария, вы можете сделать:

$classes = array_flip(get_declared_classes());
$check = isset($classes['%someClassName%']);

Что, вероятно, будет намного быстрее, чем любой поиск значения.

Answer 3

Как внутренне работает функция in_array?

Внутренне in_array() выполняет поиск от начала до конца массива. Так что в вашем случае это медленно.

В зависимости от характера ваших данных вы можете изменить стратегию поиска. Если у вас есть только неповторяющиеся значения и все значения являются либо строковыми, либо целыми (не NULL), обычным трюком является array_flip() массив, который работает довольно быстро, а затем проверьте, есть ли запись для вашего значения в качестве ключа в хэше массива через isset():

  $array = array( ... non-duplicate string and integer values ... );
  $needle = 'find me!';
  $lookup = array_flip($array);
  $found = isset($lookup[$needle]) ? $lookup[$needle] : false;
  if (false === $found) {
    echo "Not found!\n";
  } else {
    echo "Found at {$found}!\n";
  }

Если эти предварительные условия не выполняются, вы можете сделать то, что предложено konforce .

Если у вас действительно много данных, и вы смотрите не только с начала или с конца, вам может потребоваться реализовать один алгоритм поиска самостоятельно, например, не начиная с начала и не заканчивая, а оборачивая и / или начать со случайной позиции, чтобы распределить время поиска.

Кроме того, вы можете сохранять элементы отсортированными при добавлении в массив, возможно, который затем можно будет найти намного быстрее с помощью алгоритма подбора.