C++映射查找性能与 PHP 数组查找性能

Question

我无法理解以下内容，我希望有人能为我解释一下：

在 C++ 中，如果我创建一个包含 2M 不同文本位（测试数据）的测试数据向量，然后使用这些字符串作为索引值，然后查找所有值，如下所示：

 //Create test data
for(int f=0; f<loopvalue; f++)
{   
    stringstream convertToString;
    convertToString << f;
    string strf = convertToString.str();
    testdata[f] = "test" + strf;
}

    time_t startTimeSeconds = time(NULL);

   for(int f=0; f<2000000; f++) testmap[ testdata[f] ] = f; //Write to map
   for(int f=0; f<2000000; f++) result = testmap[ testdata[f] ]; //Lookup

   time_t endTimeSeconds = time(NULL);
   cout << "Time taken " << endTimeSeconds - startTimeSeconds << "seconds." << endl;

需要 10 秒。

如果我在 PHP 中做看似至少相同的事情：

<?php
$starttime = time();
$loopvalue = 2000000;

//fill array
for($f=0; $f<$loopvalue; $f++)
{
    $filler = "test" . $f;
    $testarray[$filler] = $f;
}

//look up array
for($f=0; $f<$loopvalue; $f++)
{
    $filler = "test" . $f;
    $result = $testarray[$filler];
}

$endtime = time();
echo "Time taken ".($endtime-$starttime)." seconds.";
?>

...只需要 3 秒。

鉴于 PHP 是用 C 编写的，有谁知道 PHP 如何实现如此快速的文本索引查找？

谢谢 C

Answer 1

您的循环不是绝对等效的算法。
请注意，在 C++ 版本中，您有

1. testmap[ testdata[f] ] - 这实际上是一个查找 + 插入
2. testmap[ testdata[f] ] - 2 个查找

在 PHP 版本中，您只需在第一个循环中插入并在第二个循环中查找一。

PHP 是解释型的 - 一般来说，如果您用 PHP 编写代码速度更快，请先检查代码！ ;-)

Answer 2

我怀疑你对错误的事情进行了基准测试。
不管怎样，我使用了你的代码（必须对你的数据类型做出一些假设），这是我的机器的结果：

PHP：
耗时2秒。

C++（使用 std::map）：
耗时3秒。

C++（使用 std::tr1::unordered_map）：
耗时1秒。

C++ 编译如下

g++ -03

是我的测试 C++ 代码：

#include <map>
#include <sstream>
#include <string>
#include <vector>
#include <iostream>
#include <tr1/unordered_map>


int main(){
    const int loopvalue=2000000;
    std::vector<std::string> testdata(loopvalue);
    std::tr1::unordered_map<std::string, int> testmap;
    std::string result;
    for(int f=0; f<loopvalue; f++)
    {   
        std::stringstream convertToString;
        convertToString << f;
        std::string strf = convertToString.str();
        testdata[f] = "test" + strf;
    }

    time_t startTimeSeconds = time(NULL);

    for(int f=0; f<loopvalue; f++) testmap[ testdata[f] ] = f; //Write to map
    for(int f=0; f<loopvalue; f++) result = testmap[ testdata[f] ]; //Lookup

    time_t endTimeSeconds = time(NULL);
    std::cout << "Time taken " << endTimeSeconds - startTimeSeconds << "seconds." << std::endl;
}

结论：

您测试了未优化的 C++ 代码，甚至可能使用 VC++ 进行编译，默认情况下，在调试模式下编译时，它在 std::vector::operator[] 中进行边界检查。

当我们使用 std::map 时，由于查找复杂性的差异（参见 n0rd 的答案），PHP 与优化的 C++ 代码仍然存在差异，但是当您使用 Hashmap 时，C++ 速度更快。

Answer 3

根据另一个问题，PHP中的关联数组实现为哈希表，平均搜索复杂度为 O(1)，而 std::map 在 C++ 中是一棵二叉树，搜索复杂度为 O(log n ），速度较慢。