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

[in_array函数内部如何工作？

Internally，in_array()从数组的开头到结尾搜索。因此，根据您的情况，这很慢。

根据数据的性质，您可以更改搜索策略。如果您只有非重复值并且所有值都是字符串或整数（不是NULL），则常见的窍门是array_flip()快速运行数组，然后检查是否存在是通过array_flip()在数组哈希中作为键的值的条目：

isset()

如果不满足这些前提条件，则可以按照建议的[[konforce进行操作。

[如果您确实有很多数据，不仅是从头开始或从头开始查看，您可能希望自己实现一种搜索算法，例如既不是从头开始也不是从头开始，而是要包装和/或从随机位置开始以分配搜索时间。

另外，您可以在添加到数组的同时使元素保持排序，然后可以通过拟合算法更快地搜索它们。

Answer 3

调整之间的广泛比较测试

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

• in_array + array_flip
• isset
• array_search

对于数字和字符串搜索，Kasim Kochkin发表在array_key_exists，我发现以下结果

使用php 7.3.11

使用一次array_flip并进行多次搜索，

• 对于单个到很少的搜索，in_array和array_search更快。
• 对于字符串搜索，翻转（一次）+ isset会在200次搜索以上变得更快。
• 对于数字搜索，翻转（一次）+ isset会比10个搜索快。

字符串搜索结果

N = 1000000（百万）in_array：0.00845003翻转：0.17343211isset：2.86E-6array_search：0.00835395array_key_exists：5.01E-6

N = 100000in_array：0.00854707翻转：0.12469196isset：7.15E-6array_search：0.00861216array_key_exists：6.2E-6

N = 10000in_array：0.00854087翻转：0.10549212isset：6.91E-6array_search：0.00846505array_key_exists：4.05E-6

数字搜索结果，

N = 1000000in_array：0.01197696翻转：0.06217289isset：6.2E-6array_search：0.01673698array_key_exists：4.05E-6

N = 100000in_array：0.01191092翻转：0.06582093isset：6.91E-6array_search：0.01637983array_key_exists：4.05E-6

N = 10000in_array：0.01375008翻转：0.07185006isset：5.01E-6array_search：0.01485705array_key_exists：4.05E-6