Производительность поиска карт C ++ и производительность поиска массивов PHP

Question

Я не могу понять следующее, и я надеюсь, что кто-то может пролить свет на это для меня:

В C ++, если я создаю вектор тестовых данных, содержащий 2M различных битов текста (testdata), затем создаю карту, используя эти строки в качестве значений индекса, а затем ищем все значения, например:

 //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 [] при компиляции в режиме отладки.

В PHP по-прежнему есть разница с оптимизированным кодом C ++, когда мы используем std :: map, из-за разницы в сложности поиска (см. Ответ n0rd), но C ++ быстрее при использовании Hashmap.

Answer 3

Согласно другому вопросу , ассоциативные массивы в PHP реализованы в виде хеш-таблиц , которые имеют сложность поиска в среднем O (1), тогда как std :: map в C ++ - это двоичное дерево со сложностью поиска O (log n), которое медленнее.