फास्ट सी ++ कंटेनर जैसे सी # हैशसेट <T> और शब्दकोश <K,V>?

Question

मैंने हैशसेट और डिक्शनरी को बहुत सी # में उपयोग किया है, और उन्हें बहुत तेज़ पाया है ...

मैंने std :: map और std :: hash_map का उपयोग करने का प्रयास किया है और तुलना में उन्हें बहुत धीमा कर रहा हूं। क्या यह अपेक्षित व्यवहार की तरह लगता है? क्या std :: hash_map के उपयोग में कुछ गलत हो सकता है?

या, क्या वहां कोई बेहतर सी ++ हैश कंटेनर है?

मैं हैशिंग int32s, आमतौर पर उनमें से लगभग 100,000।

अद्यतन: मैंने सी # और सी ++ में एक रेपो बनाया। यह दो परीक्षण चलाता है, वे सी # में 1 9एमएस और 13ms लेते हैं, और सी ++ में लगभग 11,000ms।

Found 511 values in the intersection, in 19 ms 
Found 508 values in the intersection, in 13 ms 

सी ++ आउटपुट::

Found 308 values in the intersection, in 11764.7ms 
Found 316 values in the intersection, in 11742.8ms 

वहाँ कुछ वास्तव में मेरे सी ++ कोड :) (के रूप में रिलीज बनाता है दोनों का संचालन किया गया दोनों कंसोल क्षुधा हैं)

सी # आउटपुट के साथ गलत किया जाना चाहिए

सी ++ आउटपुट (stdxt :: std :: मैप के बजाय हैश_मैप का उपयोग करके)

Found 300 values in the intersection, in 383.552ms 
Found 306 values in the intersection, in 2277.02ms 

सी ++ आउटपुट (का उपयोग कर stdext :: hash_map, एक रिलीज 64 निर्माण)

Found 292 values in the intersection, in 1037.67ms 
Found 302 values in the intersection, in 3663.71ms 

नोट्स:

• SET2 काफी आबादी हो रही नहीं है के रूप में मैं सी ++ में करना चाहता था, मैं यह उम्मीद कर रहा था के लिए SET1 के साथ एक 50% चौराहे (के रूप में यह सी # में करता है), लेकिन मैं किसी कारण भी पाने के लिए 10 से मेरी यादृच्छिक संख्या गुणा करने के लिए किया था उन्हें आंशिक रूप से एक दूसरे को काटना नहीं करने के लिए

सी #:

static void Main(string[] args) 
    { 
     int start = DateTime.Now.Millisecond; 
     int intersectionSize = runIntersectionTest(); 
     int duration = DateTime.Now.Millisecond - start; 

     Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration)); 

     start = DateTime.Now.Millisecond; 
     intersectionSize = runIntersectionTest(); 
     duration = DateTime.Now.Millisecond - start; 

     Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration)); 

     Console.ReadKey(); 
    } 

    static int runIntersectionTest() 
    { 
     Random random = new Random(DateTime.Now.Millisecond); 

     Dictionary<int,int> theMap = new Dictionary<int,int>(); 

     List<int> set1 = new List<int>(); 
     List<int> set2 = new List<int>(); 

     // Create 100,000 values for set1 
     for (int i = 0; i < 100000; i++) 
     { 
      int value = 1000000000 + i; 
      set1.Add(value); 
     } 

     // Create 1,000 values for set2 
     for (int i = 0; i < 1000; i++) 
     { 
      int value = 1000000000 + (random.Next() % 200000 + 1); 
      set2.Add(value); 
     } 

     // Now intersect the two sets by populating the map 
     foreach(int value in set1) 
     { 
      theMap[value] = 1; 
     } 

     int intersectionSize = 0; 

     foreach (int value in set2) 
     { 
      int count; 
      if (theMap.TryGetValue(value, out count)) 
      { 
       intersectionSize++; 
       theMap[value] = 2; 
      } 
     } 

     return intersectionSize; 
    } 

सी ++:

int runIntersectionTest() 
{ 
    std::map<int,int> theMap; 

    vector<int> set1; 
    vector<int> set2; 

    // Create 100,000 values for set1 
    for (int i = 0; i < 100000; i++) 
    { 
     int value = 1000000000 + i; 
     set1.push_back(value); 
    } 

    // Create 1,000 values for set2 
    for (int i = 0; i < 1000; i++) 
    { 
     int random = rand() % 200000 + 1; 
     random *= 10; 

     int value = 1000000000 + random; 
     set2.push_back(value); 
    } 

    // Now intersect the two sets by populating the map 
    for (vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++) 
    { 
     int value = *iterator; 

     theMap[value] = 1; 
    } 

    int intersectionSize = 0; 

    for (vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++) 
    { 
     int value = *iterator; 

     map<int,int>::iterator foundValue = theMap.find(value); 

     if (foundValue != theMap.end()) 
     { 
      theMap[value] = 2; 

      intersectionSize++; 
     } 
    } 

    return intersectionSize; 

} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    srand (time(NULL)); 

    Timer timer; 
    int intersectionSize = runIntersectionTest(); 
    timer.Stop(); 

    cout << "Found " << intersectionSize << " values in the intersection, in " << timer.GetMilliseconds() << "ms" << endl; 

    timer.Reset(); 
    intersectionSize = runIntersectionTest(); 
    timer.Stop(); 

    cout << "Found " << intersectionSize << " values in the intersection, in " << timer.GetMilliseconds() << "ms" << endl; 

    getchar(); 

    return 0; 
} 

Answer 1

हैश_मैप और हैश_सेट गैर-मानक हैं, unordered_map और unordered_set मानक संस्करण होने की संभावना सबसे अधिक संभावना है। एक पुनरुत्पादक के बिना, मुझे नहीं लगता कि यह अभी तक दूर जा रहा है।हुड के तहत, वे एक ही डेटा संरचनाएं हैं, इसलिए उनके पास समान प्रदर्शन होना चाहिए।

---

मैं संकलित एमएस विजुअल स्टूडियो 2008 v9.0.30729.1, विज़ुअल सी के रूप में के तहत प्रदान की नमूना ++ -> Win32 -> कंसोल आवेदन (हालांकि मैं अपने खुद के टाइमर वर्ग लुढ़का क्योंकि मुझे नहीं सुनिश्चित करें कि आप क्या थे का उपयोग)। डीबग के तहत, मुझे 1000 एमएस के समय मिल गए, लेकिन रिलीज के तहत संकलन 50 एमएस था।

#include <vector> 
#include <iostream> 
#include <map> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#include <windows.h> 

typedef struct { 
    LARGE_INTEGER start; 
    LARGE_INTEGER stop; 
} stopWatch; 

class CStopWatch { 

private: 
    stopWatch timer; 
    LARGE_INTEGER frequency; 
    double LIToSecs(LARGE_INTEGER & L); 
public: 
    CStopWatch(); 
    void startTimer(); 
    void stopTimer(); 
    double getElapsedTime(); 
}; 

double CStopWatch::LIToSecs(LARGE_INTEGER & L) { 
    return ((double)L.QuadPart /(double)frequency.QuadPart) ; 
} 

CStopWatch::CStopWatch(){ 
    timer.start.QuadPart=0; 
    timer.stop.QuadPart=0; 
    QueryPerformanceFrequency(&frequency) ; 
} 

void CStopWatch::startTimer() { 
    QueryPerformanceCounter(&timer.start) ; 
} 

void CStopWatch::stopTimer() { 
    QueryPerformanceCounter(&timer.stop) ; 
} 

double CStopWatch::getElapsedTime() { 
    LARGE_INTEGER time; 
    time.QuadPart = timer.stop.QuadPart - timer.start.QuadPart; 
    return LIToSecs(time) ; 
} 

using namespace std; 
int runIntersectionTest() 
{ 
    std::map<int,int> theMap; 

    vector<int> set1; 
    vector<int> set2; 

    // Create 100,000 values for set1 
    for (int i = 0; i < 100000; i++) 
    { 
     int value = 1000000000 + i; 
     set1.push_back(value); 
    } 

    // Create 1,000 values for set2 
    for (int i = 0; i < 1000; i++) 
    { 
     int random = rand() % 200000 + 1; 
     random *= 10; 

     int value = 1000000000 + random; 
     set2.push_back(value); 
    } 

    // Now intersect the two sets by populating the map 
    for (vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++) 
    { 
     int value = *iterator; 

     theMap[value] = 1; 
    } 

    int intersectionSize = 0; 

    for (vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++) 
    { 
     int value = *iterator; 

     map<int,int>::iterator foundValue = theMap.find(value); 

     if (foundValue != theMap.end()) 
     { 
       theMap[value] = 2; 

       intersectionSize++; 
     } 
    } 

    return intersectionSize; 

} 

int main(int argc, char* argv[]) 
{ 
    srand (time(NULL)); 
    int tests = 2; 
    while(tests--){ 
     CStopWatch timer; 
     timer.startTimer(); 
     int intersectionSize = runIntersectionTest(); 
     timer.stopTimer(); 

     cout << "Found " << intersectionSize << " values in the intersection, in " << timer.getElapsedTime() << "s\r\n"; 
    } 

    getchar(); 

    return 0; 
} 

(मैं unordered_map के साथ प्रयास करता हूं लेकिन मेरे संस्करण में यह नहीं है)। मुझे संदेह है कि सी ++ के लिए आपके सेटअप में कुछ समस्या है।

Answer 2

यह उम्मीद नहीं करता है ध्वनि, लेकिन आप इससे पहले कि हम वास्तव में मदद कर सकते हैं कुछ और जानकारी इकट्ठा करने के लिए की आवश्यकता होगी। आप किस हैश_मैप कार्यान्वयन का उपयोग कर रहे हैं? क्या आपने उस पर एक प्रोफाइलर इंगित किया था, और यदि ऐसा है तो यह आपको क्या बताता है?

सामान्य रूप से, यदि कोई हैश तालिका कार्यान्वयन किसी स्पष्ट कारण के लिए खराब प्रदर्शन कर रहा है, आमतौर पर ऐसा इसलिए होता है क्योंकि तालिका का उपयोग करने वाले हैश फ़ंक्शन आपके विशेष इनपुट के लिए बुरी तरह प्रदर्शन करते हैं। यह आपकी समस्या हो सकती है - C++ हैश_मैप एक हैश फ़ंक्शन का उपयोग करने के लिए होता है जो आपकी चाबियों को बाल्टी की एक छोटी सी श्रृंखला में मैप करता है, और सी # हैशसेट नहीं करता - या यह कुछ अलग हो सकता है।

std :: नक्शा आम तौर पर एक पेड़ के रूप में लागू किया जाता है, और इसलिए विभिन्न प्रदर्शन विशेषताओं का होगा। फिर, कार्यान्वयन और इनपुट डेटा मामले का विवरण।

Answer 3

मैं इसे इस्तेमाल कभी नहीं किया लेकिन Google Sparcehash एक अच्छा फिट

Answer 4

आप अपने सी ++ कोड है, जो (लॉग (एन)) हे की प्रविष्टि और देखने गुना है में std :: मानचित्र का उपयोग कर रहे हो सकता है। बेहतर तुलना प्राप्त करने के लिए हैश_मैप के साथ परीक्षण करने का प्रयास करें।

Answer 5

हम इस की तह तक पहुंचने में कामयाब रहे, देखें:

Why does my STL code run so slowly when I have the debugger/IDE attached?

क्या होता है जब आप डिबगर एक अलग (डीबग) स्मृति ढेर प्रयोग किया जाता है संलग्न है - आप इसे बदल सकते हैं बंद अगर आप चाहते हैं।

Answer 6

क्या तुम सच में तुलना कर रहे हैं है

सी # हैश सेट जो हे (1), लगभग निरंतर और इनपुट आकार के स्वतंत्र अर्थ है,

सी बनाम ++ वेक्टर .... जिसका अर्थ है (इनपुट का आकार) बार स्थिर ...

इससे थोड़ा व्यावहारिक अर्थ होता है।

आप सी में HashSet के बराबर ++ है जो (2007 में tr1 के बाद मुझे लगता है कि) का उपयोग कर प्रयास करना चाहिए std :: tr1 :: unordered_set < ...> (और std :: tr1 :: unordered_set < ... >)

wikipedia link on TR1

भी ध्यान रखें कि this page दृश्य स्टूडियो के अनुसार अपने स्वयं के करने से इनकी एसटीएल tr1 कार्यान्वयन है। (कोई व्यक्तिगत अनुभव नहीं है, इसे here मिला)