php - 在 10 个数字的未排序整数数组中搜索第一个重复值的最快方法？

Question

在 10 个数字的未排序整数数组中搜索第一个重复值的最快方法是什么？

如果数组有 1000 万条记录，答案应该是什么？

Answer 1

我能想到的唯一方法是使用 2 数组，因为你想要first repetitive value in an unsorted integer

千万 ？？？不确定内存含义

PHP 文档注释

splFixedArray 的内存占用大约是相同大小的常规“数组”的 37%。我希望有更多，但这也很重要，这就是您应该期望看到差异的地方，而不是“性能

PHP 数组（和值）到底有多大？（提示：大！）

例子

$array =  SplFixedArray::fromArray(array(1,2,4,6,4,2,7,7,3,3,1));
$list = array();
foreach ($array as $value ) {
    if (in_array($value, $list)) {
        echo $value;
        break;
    }
    $list[] = $value;
}

输出

 4

Answer 2

如果你想要最小的重复数，那么

• 在 O(n) 时间内使用基数排序对数组进行排序

• 遍历排序后的数组并找到第一个重复

如果你想要第一个重复的数字以数组已经在的任何顺序

• 循环遍历数组，将数字添加到哈希集中，直到达到一个无法添加到哈希集中的数字，因为它已经存在。

Answer 3

这是基准代码。它太大了，无法评论，所以我把它作为单独的答案。

<?php
$array = range(0, 10000);


$time_start = microtime(true);
$list = array();
foreach ( $array as $value ) {
    if (in_array($value, $list)) {
        echo $value;
        break;
    }
    $list[] = $value;
}
printf("Using foreach loop:<br/>%0.10f<br/><br/>", microtime(true)-$time_start);


$time_start = microtime(true);
$list = array();
foreach ( new ArrayIterator($array) as $value ) {
    if (in_array($value, $list)) {
        echo $value;
        break;
    }
    $list[] = $value;
}
printf("Using ArrayIterator:<br/>%0.10f<br/><br/>", microtime(true)-$time_start);

foreach循环比ArrayIterator.

我尝试了 10000 个元素。元素是使用range函数生成的，这确保了我有“最差”的输入数组，其中所有元素都是不同的。

100 万条记录的数组生成在我的机器上花费了太长时间。