in_array()性能优化

Question

我有以下条件:

if(in_array($needle, $haystack) ||
    in_array($needle . "somePostfix", $haystack) ||
    in_array($needle . "someOtherPostfix", $haystack) ||
    // and some more) {
    // do something
}

我的草堆包含超过10k个元素,这个检查大约需要400ms.我知道必须in_array多次迭代整个数组.在我的情况下,常见的情况是找不到元素.我尝试通过创建以下方法来改进这一点,该方法只在haystack上迭代一次:

function wildcardInArray($needle, $haystack) {
    foreach ($haystack as $value) {
        if (true === fnmatch($needle . '*', $haystack)) {
            return true;
        }
    }
    return false;
}

但这更能降低我的表现,在我看来这fnmatch是瓶颈.

这种阵列搜索的情况有什么改进吗？

Answer 1

这是一个非常有趣的问题，但似乎没有很好的答案。我做了一些非常不科学的基准测试，但我无法获得比 100000 个元素更快的in_array速度$haystack。

PHP 5.5.9-1ubuntu4.14 (cli) (built: Oct 28 2015 01:34:46) 
Copyright (c) 1997-2014 The PHP Group
Zend Engine v2.5.0, Copyright (c) 1998-2014 Zend Technologies
    with Zend OPcache v7.0.3, Copyright (c) 1999-2014, by Zend Technologies
    with Xdebug v2.2.3, Copyright (c) 2002-2013, by Derick Rethans

Sorting Time*:    0.19367408752441
Imploding Time**: 0.0207359790802
preg_match:       0.10927486419678
needle ===:       0.083639144897461
in_array:         0.019428968429565
array_flip:       0.028955936431885
array_intersect:  0.15198707580566
array_diff:       0.15532493591309

//*sort without search (binary search wouldn't add much time)
//**time it took to implode the array 
//     (no search was performed, this search WOULD take significant time if implemented)

正如您所看到的，这些方法中只有 3 个花费了不到 100 毫秒needle ===，in_array和array_flip。在这三个人中，in_array显然是最快的。现在的问题是你有多少个 postfix-es？运行时间in_array将是O(n*m)（n是干草堆的大小，m是后缀的数量），如果m也很大，这就是一个问题。如果m非常大，则对数据进行一次排序并对排序后的列表执行二分搜索，O(m*log(n))其增长速度会慢得多，但初始开销较高，如上面的排序时间所示。更好的是，如果你有一个非常大的m可能，array_flip因为每次搜索应该只O(1)在初始翻转后进行查找。

代码

干草堆创作

$haystack = array();

function getRandomWord($len = 10) {
        $len = rand(3,10);
        $word = array_merge(range('a', 'z'), range('A', 'Z'));
            shuffle($word);
            return substr(implode($word), 0, $len);
}

$numWords = 100000;
for($i = 0; $i < $numWords; $i++) {
    $haystack[] = getRandomWord();
}

测试

//*Sorting*    
$copy = $haystack;
sort($copy);


//implode    
$copy = implode($haystack, " ");


//*preg_match_test*
function preg_match_test($regex, $haystack) {
    $matches = false;
    foreach($haystack as $value) {
        if (preg_match($regex, $value)) {
            $matches = true;
            break;
        }
    }
    return $matches;
}

//needle ===
function equalsNeedle($needles, $haystack) {
    $matches = false;
    foreach ($haystack as $value) {
        foreach($needles as $needle) {
            if ($needle === $value) {
                $matches = true;
                break 2;
            }
        }
    }
    return $matches;
}

//in_array
function baseCase($needles, $haystack) {
    $matches = false;
    foreach($needles as $needle) {
        if (in_array($needle, $haystack)) {
            $matches = true;
            break;
        }
    }
    return $matches;
}

//array_flip
function arrayFlipping($needles, $haystack) {
    $matches = false;
    $copy = array_flip($haystack);
    foreach ($needles as $needle) {
        if (array_key_exists($needle, $copy)) {
            $matches = true;
        }
    }
    return $matches;
}

//array_intersect
function arrayIntersect($needles, $haystack) {
    if (count(array_intersect($needles, $haystack)) > 0) {
        return true;
    }
    return false;
}

//array_diff
function arrayDiff($needles, $haystack) {
    if (count(array_diff($needles, $haystack)) !== count($needles)) {
        return true;
    }
    return false;
}

调用代码

$array = array("foo","foobar","foobazz","foobuzz");
$base = "foo";
$regex = "/^$base(bizz|bazz|buzz|)$/";

echo "preg_match: ";
preg_match_test($regex, $haystack);
echo "needle === ";
equalsNeedle($array, $haystack);
echo "in_array:  ";
baseCase($array, $haystack);
echo "array_flip:  ";
arrayFlipping($array, $haystack);
echo "array_intersect:  ";
arrayIntersect($array, $haystack);
echo "array_diff:  ";
arrayDiff($array, $haystack);

所有测试都使用microtime(true).