第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號安全，請及時綁定郵箱和手機立即綁定
已解決430363個問題，去搜搜看，總會有你想問的

哈希表的性能，為什么C++最慢？

哈希表的性能，為什么C++最慢？

Go
函數(shù)式編程 2021-11-22 19:43:13
對 hash 進(jìn)行了一個簡單的性能測試，看起來 C++ 版本比 perl 版本和 golang 版本都慢。perl 版本用了大約 200 毫秒，C++ 版本用了 280 毫秒。golang 版本用了 56 毫秒。在我的帶有 Core(TM) i7-2670QM CPU @ 2.20GHz、Ubuntu 14.04.3LTS 的 PC 上，有任何想法嗎？perl 版本use Time::HiRes qw( usleep ualarm gettimeofday tv_interval nanosleep                      clock_gettime clock_getres clock_nanosleep clock                      stat );sub getTS {    my ($seconds, $microseconds) = gettimeofday;    return $seconds + (0.0+ $microseconds)/1000000.0;}my %mymap;$mymap{"U.S."} = "Washington";$mymap{"U.K."} = "London";$mymap{"France"} = "Paris";$mymap{"Russia"} = "Moscow";$mymap{"China"} = "Beijing";$mymap{"Germany"} = "Berlin";$mymap{"Japan"} = "Tokyo";$mymap{"China"} = "Beijing";$mymap{"Italy"} = "Rome";$mymap{"Spain"} = "Madrad";$x = "";$start = getTS();for ($i=0; $i<1000000; $i++) {    $x = $mymap{"China"};}printf "took %f sec\n", getTS() - $start;C++版本#include <iostream>#include <string>#include <unordered_map>#include <sys/time.h>double getTS() {    struct timeval tv;    gettimeofday(&tv, NULL);    return tv.tv_sec + tv.tv_usec/1000000.0;}using namespace std;int main () {  std::unordered_map<std::string,std::string> mymap;  // populating container:    mymap["U.S."] = "Washington";    mymap["U.K."] = "London";    mymap["France"] = "Paris";    mymap["Russia"] = "Moscow";    mymap["China"] = "Beijing";    mymap["Germany"] = "Berlin";    mymap["Japan"] = "Tokyo";    mymap["China"] = "Beijing";    mymap["Italy"] = "Rome";    mymap["Spain"] = "Madrad";    double start = getTS();  string x;  for (int i=0; i<1000000; i++) {      mymap["China"];  }  printf("took %f sec\n", getTS() - start);  return 0;}
查看完整描述

3 回答

?
達(dá)令說

TA貢獻(xiàn)1821條經(jīng)驗 獲得超6個贊

從您的 Perl 代碼（在您嘗試修復(fù)它之前）：


@mymap = ();

$mymap["U.S."] = "Washington";

$mymap["U.K."] = "London";

這不是地圖而是數(shù)組。哈希映射的語法是：


  %mymap;

  $mymap{"U.S."} = ....

因此，您有效地做的是創(chuàng)建一個數(shù)組而不是哈希映射并始終訪問元素 0。請使用use strict;和use warnings;所有用Perl的時候，甚至有警告簡單的語法檢查會顯示你的問題：


perl -cw x.pl

Argument "U.S." isn't numeric in array element at x.pl line 9.

Argument "U.K." isn't numeric in array element at x.pl line 10.

除此之外，基準(zhǔn)測試的主要部分實際上沒有任何用處（分配一個變量并且從不使用它）并且一些編譯器可以檢測到它并簡單地將其優(yōu)化掉。


如果您檢查 Perl 程序生成的代碼，您會看到：


$ perl -MO=Deparse x.pl

@mymap = ();

$mymap[0] = 'Washington';

$mymap[0] = 'London';

...

for ($i = 0; $i < 1000000; ++$i) {

    $x = $mymap[0];

}

也就是說，它在編譯時檢測到問題，并用對數(shù)組索引 0 的訪問來替換它。

因此，無論何時進(jìn)行基準(zhǔn)測試，您都需要：

  • 檢查您的程序是否確實執(zhí)行了它應(yīng)該執(zhí)行的操作。

  • 檢查編譯器是否不優(yōu)化，也不在編譯時執(zhí)行其他語言將在運行時執(zhí)行的內(nèi)容。任何沒有結(jié)果或可預(yù)測結(jié)果的語句都易于進(jìn)行這種優(yōu)化。

  • 驗證您實際測量的是您打算測量的內(nèi)容，而不是其他內(nèi)容。即使對程序進(jìn)行很小的更改也會影響運行時間，因為需要分配內(nèi)存，而這些更改可能與您打算測量的內(nèi)容無關(guān)。在您的基準(zhǔn)測試中，您一次又一次地測量對同一哈希元素的訪問，而沒有對其他元素的訪問。這是一項可以很好地與處理器緩存配合使用的活動，但可能無法反映現(xiàn)實世界的使用情況。

而且，使用簡單的計時器并不是一個現(xiàn)實的基準(zhǔn)。系統(tǒng)上還有其他進(jìn)程，有調(diào)度程序，有緩存垃圾......而對于今天的 CPU，它高度依賴于系統(tǒng)上的負(fù)載，因為也許 CPU 會以比其他基準(zhǔn)測試更低的功耗模式運行一個基準(zhǔn)測試，即使用不同的 CPU 時鐘。例如，同一“基準(zhǔn)”的多次運行在我的系統(tǒng)上的測量時間在 100 毫秒到 150 毫秒之間變化。

基準(zhǔn)是謊言，而像您這樣的微觀基準(zhǔn)則是雙重的。


查看完整回答
反對 回復(fù) 2021-11-22
?
縹緲止盈

TA貢獻(xiàn)2041條經(jīng)驗 獲得超4個贊

我稍微修改了您的示例以獲取有關(guān)哈希表結(jié)構(gòu)的一些詳細(xì)信息：


#include <iostream>

#include <string>

#include <unordered_map>

#include <sys/time.h>

#include <chrono>


using namespace std;

int main()

{

    std::unordered_map<std::string, std::string> mymap;


    // populating container:

    mymap["U.S."] = "Washington";

    mymap["U.K."] = "London";

    mymap["France"] = "Paris";

    mymap["Russia"] = "Moscow";

    mymap["China"] = "Beijing";

    mymap["Germany"] = "Berlin";

    mymap["Japan"] = "Tokyo";

    mymap["China"] = "Beijing";

    mymap["Italy"] = "Rome";

    mymap["Spain"] = "Madrad";


    std::hash<std::string> h;

    for ( auto const& i : mymap )

    {


        printf( "hash(%s) = %ud\n", i.first.c_str(), h( i.first ) );

    }


    for ( int i = 0; i != mymap.bucket_count(); ++i )

    {

        auto const bucketsize = mymap.bucket_size( i );

        if ( 0 != bucketsize )

        {

            printf( "size of bucket %d = %d\n", i, bucketsize );

        }

    }


    auto const start = std::chrono::steady_clock::now();


    string const x = "China";

    std::string res;


    for ( int i = 0; i < 1000000; i++ )

    {

        mymap.find( x );

    }


    auto const elapsed = std::chrono::steady_clock::now() - start;

    printf( "%s\n", res );

    printf( "took %d ms\n",

            std::chrono::duration_cast<std::chrono::milliseconds>( elapsed ).count() );

    return 0;

}

在我的系統(tǒng)上運行它，我得到了 ~68ms 的運行時間，輸出如下：


hash(Japan) = 3611029618d

hash(Spain) = 749986602d

hash(China) = 3154384700d

hash(U.S.) = 2546447179d

hash(Italy) = 2246786301d

hash(Germany) = 2319993784d

hash(U.K.) = 2699630607d

hash(France) = 3266727934d

hash(Russia) = 3992029278d

size of bucket 0 = 0

size of bucket 1 = 0

size of bucket 2 = 1

size of bucket 3 = 1

size of bucket 4 = 1

size of bucket 5 = 0

size of bucket 6 = 1

size of bucket 7 = 0

size of bucket 8 = 0

size of bucket 9 = 2

size of bucket 10 = 3

事實證明，哈希表沒有得到很好的優(yōu)化，并且包含一些沖突。進(jìn)一步打印bucket中的元素顯示西班牙和中國在bucket 9。bucket可能是一個鏈表，節(jié)點分布在內(nèi)存中，解釋了性能下降。


如果您選擇另一個哈希表大小，這樣就不會發(fā)生沖突，您可以獲得加速。我通過添加對其進(jìn)行了測試，mymap.rehash(1001)并在 44-52 毫秒之間將速度提高了 20-30%。


現(xiàn)在，另一點是計算“中國”的哈希值。該函數(shù)在每次迭代中執(zhí)行。當(dāng)我們切換到常量純 C 字符串時，我們可以消除這種情況：


#include <iostream>

#include <string>

#include <unordered_map>

#include <sys/time.h>

#include <chrono>


static auto constexpr us = "U.S.";

static auto constexpr uk = "U.K.";

static auto constexpr fr = "France";

static auto constexpr ru = "Russia";

static auto constexpr cn = "China";

static auto constexpr ge = "Germany";

static auto constexpr jp = "Japan";

static auto constexpr it = "Italy";

static auto constexpr sp = "Spain";


using namespace std;

int main()

{

    std::unordered_map<const char*, std::string> mymap;


    // populating container:

    mymap[us] = "Washington";

    mymap[uk] = "London";

    mymap[fr] = "Paris";

    mymap[ru] = "Moscow";

    mymap[cn] = "Beijing";

    mymap[ge] = "Berlin";

    mymap[jp] = "Tokyo";

    mymap[it] = "Rome";

    mymap[sp] = "Madrad";


    string const x = "China";

    char const* res = nullptr;

    auto const start = std::chrono::steady_clock::now();

    for ( int i = 0; i < 1000000; i++ )

    {

        res = mymap[cn].c_str();

    }


    auto const elapsed = std::chrono::steady_clock::now() - start;

    printf( "%s\n", res );

    printf( "took %d ms\n",

            std::chrono::duration_cast<std::chrono::milliseconds>( elapsed ).count() );

    return 0;

}

在我的機器上，這將運行時間減少了 50% 到大約 20 毫秒。不同之處在于，它不是從字符串內(nèi)容計算散列值，而是將地址轉(zhuǎn)換為散列值，這要快得多，因為它只是將地址值作為 size_t 返回。我們也不需要重新散列，因為與cn.



查看完整回答
反對 回復(fù) 2021-11-22
?
瀟湘沐

TA貢獻(xiàn)1816條經(jīng)驗 獲得超6個贊

這只是表明對于這個特定用例，Go 哈希映射實現(xiàn)優(yōu)化得非常好。

mymap["China"]調(diào)用專門針對字符串鍵優(yōu)化的mapaccess1_faststr。特別是對于小型單桶映射，甚至不為短（小于 32 字節(jié)）字符串計算哈希碼。


查看完整回答
反對 回復(fù) 2021-11-22
  • 3 回答
  • 0 關(guān)注
  • 339 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學(xué)習(xí)伙伴

 公眾號

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號