कुशल तरीका पुनः आदेश देने के एक सी ++ मानचित्र आधारित संग्रह

Question

मैं एक बड़ी राशि (ish -> 100K) संग्रह है कि वे खरीदा है विभिन्न उत्पादों की गिनती (यह भी एक पूर्णांक के लिए एक उपयोगकर्ता पहचानकर्ता (किसी पूर्णांक) मानचित्रण।) मुझे डेटा को विभिन्न प्रकार के उत्पादों के बारे में जानने के लिए जितना संभव हो उतना कुशलतापूर्वक डेटा व्यवस्थित करने की आवश्यकता है। उदाहरण के लिए, कितने उपयोगकर्ताओं को 1 उत्पाद है, कितने उपयोगकर्ताओं को दो उत्पादों आदि

मैं एक std::multimap में एक std::map से मूल डेटा पीछे करके इस प्राप्त कर ली है है है (जहां कुंजी और मान बस उलट कर रहे हैं।) मैं तो एन उत्पादों count(N) का उपयोग कर होने उपयोगकर्ताओं की संख्या चुन सकते हैं (हालांकि मैं भी विशिष्ट एक सेट में मान संग्रहीत तो मैं मान की सही संख्या मैं पुनरावृत्ति किया गया था और उनके आदेश के बारे में सुनिश्चित किया जा सकता है)

कोड इस तरह दिखता है:

// uc is a std::map<int, int> containing the original 
// mapping of user identifier to the count of different 
// products that they've bought. 
std::set<int> uniqueCounts; 
std::multimap<int, int> cu; // This maps count to user. 

for (map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    cu.insert(std::pair<int, int>(it->second, it->first)); 
    uniqueCounts.insert(it->second); 
} 

// Now write this out 
for (std::set<int>::const_iterator it = uniqueCounts.begin(); 
     it != uniqueCounts.end(); ++it) 
{ 
    std::cout << "==> There are " 
      << cu.count(*it) << " users that have bought " 
      << *it << " products(s)" << std::endl; 
} 

मैं यह महसूस करने में मदद नहीं कर सकता कि यह करने का यह सबसे प्रभावी तरीका नहीं है। किसी को यह करने की एक चालाक विधि के बारे में पता है?

मैं उस में सीमित हूं, मैं करने के लिए बूस्ट या सी ++ 11 का उपयोग नहीं कर सकता।

ओह, अगर कोई सोच रहा है, तो यह न तो होमवर्क है, न ही एक साक्षात्कार प्रश्न है।

Answer 1

मान लीजिए कि आप एक ही उपयोगकर्ता द्वारा खरीदे गए उत्पादों की अधिकतम संख्या को जानते हैं, तो आप ऑपरेशन के परिणामों को संग्रहीत करने के लिए वेक्टर का उपयोग करके बेहतर प्रदर्शन देख सकते हैं। जैसा कि आपको मूल मानचित्र में हर प्रविष्टि के लिए आवंटन की आवश्यकता होगी, जो संभवतः सबसे तेज़ विकल्प नहीं है।

यह मानचित्र पर लुकअप ओवरहेड पर भी कटौती करेगा, मेमोरी इलाके के लाभ प्राप्त करेगा, और कॉल को प्रतिस्थापित करने के लिए मल्टीमैप (जो स्थिर समय ऑपरेशन नहीं है) पर गिनने के लिए कॉल को प्रतिस्थापित करेगा ।

तो तुम कुछ इस तरह कर सकता है:

std::vector<int> uniqueCounts(MAX_PRODUCTS_PER_USER); 

for (map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    uniqueCounts[ uc.second ]++; 
} 

// Now write this out 
for (int i = 0, std::vector<int>::const_iterator it = uniqueCounts.begin(); 
     it != uniqueCounts.end(); ++it, ++i) 
{ 
    std::cout << "==> There are " 
      << *it << " users that have bought " 
      << i << " products(s)" << std::endl; 
} 

भले ही आप उत्पादों की अधिकतम संख्या पता नहीं है, ऐसा लगता है जैसे तुम सिर्फ एक अधिकतम लगता है कि हो सकता है और का आकार बढ़ाने के लिए इस कोड को अनुकूलित यदि आवश्यक हो तो वेक्टर। वैसे भी आपके मूल उदाहरण की तुलना में कम आवंटन में परिणाम होना निश्चित है।

यह सब मानते हैं कि आपको वास्तव में इस डेटा को संसाधित करने के बाद उपयोगकर्ता आईडी की आवश्यकता नहीं है (और नीचे दी गई टिप्पणियों में बताया गया है कि प्रत्येक उपयोगकर्ता के लिए खरीदे गए उत्पादों की संख्या अपेक्षाकृत छोटी है & संगत सेट। अन्यथा आप वेक्टर के स्थान पर मानचित्र का उपयोग करना बेहतर हो सकते हैं - आप अभी भी मल्टीमैप :: गिनती फ़ंक्शन को कॉल करने से बचेंगे, लेकिन संभावित रूप से अन्य लाभों को खो देते हैं)

Answer 2

यदि आप कर सकते हैं, तो मैं हर समय डेटा के दोनों टुकड़ों को चालू रखने की अनुशंसा करता हूं। दूसरे शब्दों में, मैं एक दूसरा नक्शा बनाए रखूंगा जो उन उत्पादों की संख्या में खरीदे गए उत्पादों की संख्या मैपिंग कर रहा है जिन्होंने कई उत्पादों को खरीदा है। यदि आप इसे बनाए रखते हैं तो इस मानचित्र में आपके प्रश्न का सटीक उत्तर है। जब भी कोई ग्राहक कोई उत्पाद खरीदता है, तो इस ग्राहक ने अब खरीदे गए उत्पादों की संख्या बनें। कुंजी एन -1 पर मान से एक घटाएं। कुंजी एन पर मान में जोड़ें। यदि चाबियों की सीमा काफी छोटी है तो यह मानचित्र के बजाय एक सरणी हो सकती है। क्या आपने कभी एक ग्राहक को सैकड़ों उत्पादों को खरीदने की उम्मीद की है?

Answer 3

यह आपके पर निर्भर करता है कि आप क्या करते हैं "अधिक कुशल" से मतलब है। सबसे पहले, क्या यह वास्तव में एक बोतल गर्दन है?निश्चित रूप से, 100k प्रविष्टियां बहुत अधिक हैं, लेकिन अगर आपको केवल कुछ ही मिनटों में यह करना है, तो ठीक है अगर एल्गोरिदम में कुछ सेकंड लगते हैं।

सुधार के लिए एकमात्र क्षेत्र मेमोरी उपयोग है।

std::map<int, int> countFrequency; // count => how many customers with that count 

for (std::map<int, int>::const_iterator it = uc.begin(); 
     it != uc.end(); ++it) 
{ 
    // If it->second is not yet in countFrequency, 
    // the default constructor initializes it to 0. 
    countFrequency[it->second] += 1; 
} 

// Now write this out 
for (std::map<int, int>::const_iterator it = countFrequency.begin(); 
     it != countFrequency.end(); ++it) 
{ 
    std::cout << "==> There are " 
      << it->second << " users that have bought " 
      << it->first << " products(s)" << std::endl; 
} 

एक उपयोगकर्ता जोड़ा और खरीदता है, तो: यह एक चिंता का विषय है, तो आप मल्टीमैप की पीढ़ी को छोड़ सकते हैं और सिर्फ एक काउंटर नक्शा चारों ओर कुछ इस तरह रखने के लिए, (सावधान रहना, मेरे सी ++ कुछ पुरानी है) count आइटम, यदि आप एक मौजूदा उपयोगकर्ता oldCountnewCount करने के लिए आइटम से चला जाता है

countFrequency[count] += 1; 

साथ countFrequency अद्यतन कर सकते हैं, तो आप

countFrequency[oldCount] -= 1; 
countFrequency[newCount] += 1; 

साथ countFrequency अद्यतन कर सकते हैं

अब, एक तरफ के रूप में, मैं गिनती के लिए unsigned int का उपयोग करने की अनुशंसा करता हूं (जब तक नकारात्मक गणना के लिए कोई वैध कारण न हो) और userID प्रकार टाइप की गई पठनीयता के लिए टाइप किया गया हो।

Answer 4

बस लार्क्स के लिए, यहां एक मिश्रित दृष्टिकोण है जो vector का उपयोग करता है यदि डेटा छोटा है, और map उस मामले को कवर करने के लिए जहां एक उपयोगकर्ता ने वास्तव में बेतुका उत्पादों की संख्या खरीदी है। मुझे संदेह है कि आपको स्टोर स्टोर में बाद में वास्तव में आवश्यकता होगी, लेकिन समस्या का एक और सामान्य संस्करण इससे लाभ उठा सकता है।

typedef std::map<int, int> Map; 
typedef Map::const_iterator It; 

template <typename Container> 
void get_counts(const Map &source, Container &dest) { 
    for (It it = source.begin(); it != source.end(); ++it) { 
     ++dest[it->second]; 
    } 
} 

template <typename Container> 
void print_counts(Container &people, int max_count) { 
    for (int i = 0; i <= max_count; ++i) { 
     if contains(people, i) { 
      std::cout << "==> There are " 
       << people[i] << " users that have bought " 
       << i << " products(s)" << std::endl; 
     } 
    } 
} 


// As an alternative to this overloaded contains(), you could write 
// an overloaded print_counts -- after all the one above is not an 
// efficient way to iterate a sparsely-populated map. 
// Or you might prefer a template function that visits 
// each entry in the container, calling a specified functor to 
// will print the output, and passing it the key and value. 
// This is just the smallest point of customization I thought of. 
bool contains(const Map &c, int key) { 
    return c.count(key); 
} 
bool contains(const std::vector<int, int> &c, int key) { 
    // also check 0 < key < c.size() for a more general-purpose function 
    return c[key]; 
} 

void do_everything(const Map &uc) { 
    // first get the max product count 
    int max_count = 0; 
    for (It it = uc.begin(); it != uc.end(); ++it) { 
     max_count = max(max_count, it->second); 
    } 

    if (max_count > uc.size()) { // or some other threshold 
     Map counts; 
     get_counts(uc, counts); 
     print_counts(counts, max_count); 
    } else { 
     std::vector<int> counts(max_count+1); 
     get_counts(uc, counts); 
     print_counts(counts, max_count); 
    } 
} 

यहाँ से

आप refactor सकता है, एक वर्ग टेम्पलेट CountReOrderer है, जो एक टेम्पलेट पैरामीटर यह कह मायने रखता है के लिए एक vector या एक map उपयोग करने के लिए है कि क्या ले जाता है बनाने के लिए।