सम्मिलन

Question

के लिए कुशल डेटा संरचना मैं डेटा संरचना (सरणी जैसी) की तलाश में हूं जो तेजी से (ओ (एन) से तेज) संरचना में मूल्यों के मनमाने ढंग से सम्मिलन की अनुमति देता है। डेटा संरचना को डालने के तरीके में अपने तत्वों को प्रिंट करने में सक्षम होना चाहिए। यह List.Insert() (जो बहुत धीमा है क्योंकि इसे हर तत्व को स्थानांतरित करना है) के समान है, सिवाय इसके कि मुझे यादृच्छिक पहुंच या हटाने की आवश्यकता नहीं है। सम्मिलन हमेशा 'सरणी' के आकार के भीतर होगा। सभी मूल्य अद्वितीय हैं। कोई अन्य परिचालन की आवश्यकता नहीं है।

उदाहरण के लिए, यदि सम्मिलित करें (x, i) इंडेक्स i (0-अनुक्रमणिका) पर मान x डालता है। तब:

• सम्मिलित (1, 0) {1}
• सम्मिलित देता है (3, 1) देता है {1,3}
• सम्मिलित (2, 1) देता है {1,2,3}
• सम्मिलित (5, 0) {5,1,2,3}

देता है और यह अंत में बाहर {5,1,2,3} मुद्रित करने के लिए सक्षम होने के लिए की आवश्यकता होगी।

मैं सी ++ का उपयोग कर रहा हूं।

Answer 1

skip list का उपयोग करें। एक और विकल्प tiered vector होना चाहिए। स्किप सूची कॉन्स्ट ओ (लॉग (एन)) पर आवेषण करती है और संख्याओं को क्रम में रखती है। टायर वेक्टर O (sqrt (n)) में डालने का समर्थन करता है और फिर क्रम में तत्वों को प्रिंट कर सकता है।

संपादित करें:

प्रत्येक तत्व आप अगले तत्वों के लिए और प्रत्येक के लिए लिंक पर एक टावर है के लिए लिंक आप जानते हैं: अमित की टिप्पणी प्रति मैं कैसे आप एक को छोड़ सूची का k- वां तत्व मिल रहा है समझा जाएगा यह कितने तत्व कूदता है। तो सूची के शीर्ष के साथ शुरू होने वाले के-वें तत्व की तलाश करें और टावर को तब तक नीचे जाएं जब तक आपको एक ऐसा लिंक न मिल जाए जो कि के तत्वों पर आगे नहीं बढ़ता। आप इस नोड द्वारा इंगित नोड पर जाते हैं और आपके द्वारा जंप किए गए तत्वों की संख्या के साथ k को कम करते हैं। जारी कर कि आप k = 0.

Answer 2

क्या आपने std::map या std::vector का उपयोग करने पर विचार किया था?

आप std::map का उपयोग कुंजी के रूप में सम्मिलन के रैंक के साथ कर सकते हैं। और vector में reserve सदस्य फ़ंक्शन है।

Answer 3

C++ तुम सिर्फ वैक्टर के नक्शे का उपयोग कर सकते हैं, तो जैसे में है जब तक:

int main() { 
    map<int, vector<int> > data; 
    data[0].push_back(1); 
    data[1].push_back(3); 
    data[1].push_back(2); 
    data[0].push_back(5); 
    map<int, vector<int> >::iterator it; 
    for (it = data.begin(); it != data.end(); it++) { 
    vector<int> v = it->second; 
    for (int i = v.size() - 1; i >= 0; i--) { 
     cout << v[i] << ' '; 
    } 
    } 
    cout << '\n'; 
} 

यह प्रिंट:

5 1 2 3 

वैसे ही जैसे आप चाहते हैं

, और आवेषण ओ (लॉग एन) हैं।

Answer 4

आप std::map मैपिंग (इंडेक्स, सम्मिलन-समय) जोड़ों को मानों पर जोड़ सकते हैं, जहां सम्मिलन-समय एक "ऑटोइनक्रिकमेंट" पूर्णांक (SQL शर्तों में) है।जोड़े पर आदेश होना चाहिए

(i, t) < (i*, t*) 

i < i* or t > t* 

कोड में iff:

struct lt { 
    bool operator()(std::pair<size_t, size_t> const &x, 
        std::pair<size_t, size_t> const &y) 
    { 
     return x.first < y.first || x.second > y.second; 
    } 
}; 

typedef std::map<std::pair<size_t, size_t>, int, lt> array_like; 

void insert(array_like &a, int value, size_t i) 
{ 
    a[std::make_pair(i, a.size())] = value; 
} 

Answer 5

अपनी टिप्पणी के बारे में:

List.Insert() (जो बहुत धीमी है क्योंकि इसे हर तत्व को स्थानांतरित करना है),

सूचियां उनके मूल्यों को स्थानांतरित नहीं करती हैं, वे उस स्थान को ढूंढने के लिए पुन: प्रयास करते हैं, जिसे आप सम्मिलित करना चाहते हैं, सावधान रहें जो आप कहते हैं। यह मेरे जैसे नए लोगों को भ्रमित कर सकता है।

Answer 6

डिफ़ॉल्ट रूप से जीसीसी के साथ शामिल एक समाधान रस्सी डेटा संरचना है। यहां documentation है। आम तौर पर, पात्रों के लंबे तारों के साथ काम करते समय रस्सियों को ध्यान में आता है। यहां हमारे पास वर्णों की बजाय int एस है, लेकिन यह वही काम करता है। टेम्पलेट पैरामीटर के रूप में बस int का उपयोग करें। (pair एस, आदि भी हो सकता है)

यहां description of rope on Wikipedia है।

असल में, यह एक द्विआधारी पेड़ का कहना है कि कितने तत्वों बाएँ और दाएँ subtrees में हैं (या समतुल्य जानकारी है, जो क्या रूप आदेश आँकड़े कहा जाता है) है, और ये मायने रखता अपडेट किया जाता है उचित रूप से के रूप में subtrees घुमाया जाता है जब तत्वों को सम्मिलित और हटा दिया जाता है। यह ओ (एलजी एन) संचालन की अनुमति देता है।