PHP中的in_array和数组末尾快速搜索

Question

PHP中的in_array和数组末尾快速搜索

7

我对在数组中进行快速搜索的方法有疑问（我说的是一个特定的情况）。

假设我有一个数组L = [A, B, C]（开始时）。当程序运行时，可能L会增长（但最终），我将要搜索的一个可能情况是L = [A，B，C，D，E]。

事实上，当我搜索时，我想要找到的值只能是D和E。现在我正在使用find_array(elem, array)函数，但这个函数不能被“调整”以从结尾开始减少索引进行搜索，而且我“担心”在所有搜索中，in_array函数将在找到我正在搜索的值之前检查所有具有较低索引的元素。

是否有另一个搜索函数更适合我的问题？ in_array函数内部如何工作？

提前致谢

- castarco

顺便提一下：如果您事先知道只会搜索新值？那么将这些新值存储在单独的数组中是否可能，这样数组会更小，因此搜索速度更快？（如果 kenforces 的答案对您不可行） - Yoshi

我正在使用get_declared_classes()函数，需要确定特定的类是否已加载... - castarco

PHP手册中没有提到find_array()函数。所以我想知道你是想要找到元素的键还是只想知道该元素是否存在。 - Leif

我只想验证它是否存在...但也许我所做的不是正确的方式。我将尝试使用class_exists()函数。 - castarco

3个回答

4

优化 Kasim Kochkin 在 GitHub 上发布的关于使用以下函数进行数字和字符串搜索的广泛比较测试的结果：

在 PHP 7.3.11 中进行以下调整后，得出以下结果：

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

对于单个到少量搜索，in_array和array_search更快。
对于字符串搜索，flip（一次）+ isset在200次以上的搜索中变得更快。
对于数字搜索，flip（一次）+ isset在10次以上的搜索中变得更快。

字符串搜索结果（以秒为单位）

N (数组大小)	in_array	flip	isset	array_search	array_key_exists
1,000,000	0.00845003	0.17343211	2.86E-6	0.00835395	5.01E-6
100,000	0.00854707	0.12469196	7.15E-6	0.00861216	6.2E-6
10,000	0.00854087	0.10549212	6.91E-6	0.00846505	4.05E-6

数字搜索结果（单位为秒），

N (数组大小)	in_array	flip	isset	array_search	array_key_exists
1,000,000	0.01197696	0.06217289	6.2E-6	0.01673698	4.05E-6
100,000	0.01191092	0.06582093	6.91E-6	0.01637983	4.05E-6
10,000	0.01375008	0.07185006	5.01E-6	0.01485705	4.05E-6

- Aurovrata

你的帖子看起来非常有用 @Aurovrata，但目前它很难阅读。你能否使用表格格式化它，以更易读的方式显示基准测试结果？ - Basj

没问题，我会尽量找时间来改进它。 - Aurovrata

这是一个Markdown表格生成器@Aurovrata: https://www.tablesgenerator.com/markdown_tables - Basj

哇，这真的很方便。我会更新我的答案，利用这个表格格式。 - Aurovrata

有些不对劲，in_array函数在一百万和一万之间的时间没有增加？ - allan.simon

你在你的电脑上运行了它吗？ - Aurovrata

2

内部如何处理in_array函数？

在内部，in_array()函数从数组开头到结尾进行搜索。因此，在您的情况下，这是比较慢的。

根据数据的性质，您可以更改搜索策略。如果您只有非重复值，并且所有值都是字符串或整数（不是NULL），一个常见技巧是通过{{link2：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的建议去做。

如果你有大量数据，并且不仅仅是从开头或结尾查看，你可能想要自己实现一种搜索算法，比如既不从开头也不从结尾开始，而是在随机位置开始搜索以分配搜索时间。

此外，你可以在添加到数组时保持元素排序，这样就可以使用适当的算法更快地进行搜索。

- hakre

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthew · Accepted Answer

我假设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);
}

你可以进行基准测试来确认哪个更快。