我有两个无序的整数数组,我需要知道这些数组有多少个整数

Question

我在LAMP环境中工作,所以PHP是语言; 至少我可以使用python.

正如标题所说,我有两个无序的整数数组.

$array_A = array(13, 4, 59, 38, 9, 69, 72, 93, 1, 3, 5)

$array_B = array(29, 72, 21, 3, 6)

我想知道这些数组有多少个整数; 在示例中,您看到结果是2.我对整数的共同点不感兴趣,如(72,3).

我需要一个更快的方法,而不是采取数组B的每个元素,并检查它是否在数组A(O(nxm))

数组可以通过asort或sql排序进行排序(它们来自sql结果).

我想到的一个想法是为每个数组创建一个"向量",其中整数是一个获得值为1且不存在的整数获得0的位置.

那么,对于数组A(从pos 1开始)

(1, 0, 1, 1, 1, 0, 0, 0, 1, 0, ...)

对于数组B也是如此

(0, 0, 1, 0, 0, 1, ...)

然后将这两个向量与一个周期进行比较.问题是以这种方式,矢量长度约为400k.

Answer 1

根据您的数据(大小),您可能希望使用array_intersect_key()而不是array_intersect().显然,array_intersect(测试php 5.3)的实现不使用任何优化/缓存/但是循环遍历数组并逐个比较数组A中每个元素的值.哈希表查找比这快得多.

<?php
function timefn($fn) {
    static $timer = array();
    if ( is_null($fn) ) {
        return $timer;
    }
    $x = range(1, 120000);
    $y = range(2, 100000);
    foreach($y as $k=>$v) { if (0===$k%3) unset($y[$k]); }

    $s = microtime(true);
    $fn($x, $y);
    $e = microtime(true);

    @$timer[ $fn ] += $e - $s; 
}

function fnIntersect($x, $y) {
    $z = count(array_intersect($x,$y));
}

function fnFlip($x, $y) {
    $x = array_flip($x);
    $y = array_flip($y);
    $z = count(array_intersect_key($x, $y));
}


for ($i=0; $i<3; $i++) {
    timefn( 'fnIntersect' );
    timefn( 'fnFlip' );
}

print_r(timefn(null));

版画

Array
(
    [fnIntersect] => 11.271192073822
    [fnFlip] => 0.54442691802979
)

这意味着我的笔记本上的array_flip/intersect_key方法快了约20倍.(像往常一样:这是一个临时测试.如果你发现错误,告诉我......我期待那个;-))