1. घर
  2. सवाल और जवाब
  3. तेजी से यादृच्छिक अभिगम, खोज, सम्मिलन और हटाने के लिए कुशल डेटा संरचना

तेजी से यादृच्छिक अभिगम, खोज, सम्मिलन और हटाने के लिए कुशल डेटा संरचना

2009-05-20 10 views
10

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

मैं चार मुख्य संचालन की जरूरत है, कुशल होने का महत्व के किसी न किसी क्रम में:

  1. किसी दिए गए सूचकांक
  2. से मूल्य लेने किसी दिए गए मूल्य
  3. के सूचकांक एक पर एक मूल्य डालने की खोज सूचकांक
  4. किसी दिए गए सूचकांक

में एक मूल्य को हटाने में कोई सरणी हे (1) में मैं 1 है का उपयोग करते हुए दिए गए, लेकिन 2 हे है (एन) और सम्मिलन और हटाना महंगा है (ओ (एन) साथ ही, मुझे विश्वास है)।

एक लिंक्ड लिस्ट में ओ (1) सम्मिलन और हटाना (एक बार आपके पास नोड है), लेकिन 1 और 2 ओ (एन) इस प्रकार लाभ को अस्वीकार कर रहे हैं।

मैंने दो सरणी [इंडेक्स] = मान और बी [वैल्यू] = इंडेक्स को रखने की कोशिश की, जो 1 और 2 को ओ (1) में बदल देता है लेकिन 3 और 4 को और भी महंगा संचालन में बदल देता है।

क्या कोई डेटा संरचना इसके लिए बेहतर अनुकूल है?

स्रोत

2009-05-20 Leonel

+0

आप किस भाषा का उपयोग कर रहे हैं? –

+2

वास्तव में कोई फर्क नहीं पड़ता, लेकिन यह सी ++ – Leonel

+1

इससे कोई फर्क नहीं पड़ता; सभी भाषाएं समान डेटा संरचनाओं की पेशकश नहीं करती हैं। उदाहरण के लिए, इस विशेष समस्या को सी जूडी सरणी या सी # सीपीटीरी द्वारा बहुत कुशलता से हल किया जा सकता है। (या, निश्चित रूप से, कुछ प्रकार के संतुलित बाइनरी पेड़ के रूप में अयमान ने सुझाव दिया।) – Qwertie

उत्तर

12

मैं मानों की कुंजी को मैप करने के लिए red-black tree का उपयोग करूंगा। यह आपको 1, 3, 4 के लिए ओ (लॉग (एन)) देता है। यह क्रमबद्ध क्रम में कुंजी को भी बनाए रखता है।

2 के लिए, मैं कुंजी के लिए मूल्यों को मैप करने के लिए हैश तालिका का उपयोग करता हूं, जो आपको ओ (1) प्रदर्शन देता है। लाल-काले पेड़ में कुंजी जोड़ने और हटाने के दौरान हैश तालिका को अद्यतन रखने के लिए यह ओ (1) ओवरहेड भी जोड़ता है।

स्रोत

2009-05-20 21:39:02

+0

मुझे पता था कि मैंने कहीं कहीं पढ़ा है: http://www.cs.tau.ac.il/~wein/publications/pdfs/rb_tree.pdf – Javier

+0

अच्छा लगता है। मैं इसे आजमाउंगा – Leonel

+2

@ जेवियर: रेड-ब्लैक पेड़ बिल्कुल ओ (1) एक्सेस को अमूर्त नहीं किया है। जब आप पेड़ में एक तत्व पढ़ते हैं तो लाल-काले पेड़ वास्तव में * कुछ भी नहीं करते हैं, इसलिए कोई अमूर्तकरण नहीं होता है। कोई बाइनरी पेड़, गतिशील या नहीं, पेड़ में मनमानी तत्वों तक पहुंचने के लिए ओ (एन लॉग एन) प्राप्त कर सकता है। –

4

द्विआधारी खोज के साथ एक क्रमबद्ध सरणी का उपयोग करने के बारे में कैसे?

सम्मिलन और हटाना धीमा है। लेकिन इस तथ्य को देखते हुए कि डेटा सादा पूर्णांक को memcpy() पर कॉल के साथ अनुकूलित किया जा सकता है यदि आप सी या सी ++ का उपयोग कर रहे हैं। यदि आप सरणी के अधिकतम आकार को जानते हैं, तो आप सरणी के उपयोग के दौरान किसी भी स्मृति आवंटन से बच सकते हैं, क्योंकि आप इसे अधिकतम आकार में प्रीलाइकेट कर सकते हैं।

"सर्वश्रेष्ठ" दृष्टिकोण इस बात पर निर्भर करता है कि आपको कितनी वस्तुओं को स्टोर करने की आवश्यकता है और आपको खोजने के बजाय कितनी बार डालने/हटाने की आवश्यकता होगी। यदि आप ओ (1) मानों के साथ किसी क्रमबद्ध सरणी को शायद ही कभी डालें या हटा दें, तो निश्चित रूप से बेहतर होता है, लेकिन यदि आप अक्सर चीजों को सम्मिलित और हटाते हैं तो बाइनरी पेड़ सरणी से बेहतर हो सकता है। एक छोटे से पर्याप्त एन के लिए सरणी किसी भी मामले में पेड़ धड़कता है।

यदि भंडारण का आकार चिंता का विषय है, तो सरणी भी पेड़ों की तुलना में बेहतर है। पेड़ों को उनके द्वारा संग्रहीत हर आइटम के लिए स्मृति आवंटित करने की भी आवश्यकता होती है और स्मृति आवंटन का ओवरहेड महत्वपूर्ण हो सकता है क्योंकि आप केवल छोटे मान (पूर्णांक) को स्टोर करते हैं।

आप जो तेजी से प्रोफाइल करना चाहते हैं, पूर्णांक की प्रतिलिपि बनाना चाहते हैं यदि आप सॉर्ट किए गए सरणी या पेड़ के साथ पेड़ (डी) आवंटन से सम्मिलित/हटाते हैं।

स्रोत

2009-05-20 21:32:28 lothar

+1

उस मामले में सम्मिलन भयानक है ... –

+0

सम्मिलन और हटाना ओपी की सूची में आखिरी था, और पूर्णांक होने के कारण memcpy() को कॉल के साथ अनुकूलित किया जा सकता है। । – lothar

+0

"आदेश दिया गया" भाग महत्वपूर्ण है, इसलिए मैं डेटा को सॉर्ट नहीं कर सकता। – Leonel

1

ट्रेमैप कैसे करें? वर्णित संचालन के लिए लॉग (एन)।

स्रोत

2009-05-20 21:35:25 CookieOfFortune

1

मुझे संतुलित बाइनरी पेड़ पसंद हैं। वे कभी-कभी हैश टेबल या अन्य संरचनाओं से धीमे होते हैं, लेकिन वे अधिक अनुमानित होते हैं; वे सभी परिचालनों के लिए आम तौर पर O(log n) होते हैं। मैं Red-black tree या AVL tree का उपयोग करने का सुझाव दूंगा।

स्रोत

2009-05-20 21:36:00 Zifre

+0

हैश तालिका डेटा आदेश जारी नहीं रखेगी। –

+0

ओह, मुझे आदेशित भाग नहीं दिखाई दिया ... मैंने इसे ठीक किया हालांकि। – Zifre

2

मुझे नहीं पता कि आप किस भाषा का उपयोग कर रहे हैं, लेकिन यदि यह जावा है तो आप LinkedHashMap या इसी तरह के संग्रह का लाभ उठा सकते हैं। इसे सूची और मानचित्र के सभी लाभ मिलते हैं, अधिकांश परिचालनों के लिए निरंतर समय प्रदान करते हैं, और हाथी की स्मृति पदचिह्न है। :)

यदि आप जावा का उपयोग नहीं कर रहे हैं, तो LinkedHashMap का विचार शायद आपकी समस्या के लिए उपयोग करने योग्य डेटा संरचना के लिए उपयुक्त है।

स्रोत

2009-05-20 21:43:35

+0

आप LinkedHashMap का उपयोग करके यादृच्छिक तत्व कैसे प्राप्त कर रहे हैं? – Hengameh

0

आप .NET में काम कर रहे हैं, तो एमएस डॉक्स के अनुसार यदि http://msdn.microsoft.com/en-us/library/f7fta44c.aspx

  • SortedDictionary और SortedList दोनों हे है (लॉग n) पुनर्प्राप्ति
  • SortedDictionary हे (लॉग है n के लिए) संचालन को सम्मिलित करने और हटाने के लिए, जबकि सॉर्टेडलिस्ट में ओ (एन) है।

दोनों मेमोरी उपयोग और सम्मिलन/हटाने की गति से भिन्न होते हैं। SortedList SortedDictionary की तुलना में कम स्मृति का उपयोग करता है। अगर सॉर्टेडलिस्ट को सॉर्ट किए गए डेटा से एक बार में पॉप्युलेट किया जाता है, तो यह सॉर्टेड डिक्शनरी से तेज़ है। तो यह उस स्थिति पर निर्भर करता है जिसके लिए वास्तव में आपके लिए सबसे अच्छा है।

इसके अलावा, लिंक्ड लिस्ट के लिए आपका तर्क वास्तव में मान्य नहीं है क्योंकि यह सम्मिलित करने के लिए ओ (1) हो सकता है, लेकिन आपको सम्मिलन बिंदु खोजने के लिए सूची को पार करना होगा, इसलिए यह वास्तव में नहीं है।

स्रोत

2009-05-20 21:49:07 BenAlabaster

1

आरबी-पेड़ों के साथ 2 कैसे प्राप्त करें? हम उन्हें अपने बच्चों को हर डालने/हटाने के कार्यों के साथ गिन सकते हैं। यह इन ऑपरेशनियों को काफी लंबा नहीं बना देता है। फिर लॉग एन समय में i-th तत्व को खोजने के लिए पेड़ को नीचे करना संभव है। लेकिन मुझे जावा और न ही इस विधि का कोई कार्यान्वयन नहीं दिखता है।

स्रोत

2010-04-28 06:50:54

3

सरणी पहुंच के लिए वेक्टर का उपयोग करें।

वेक्टर में सबस्क्रिप्ट में एक खोज अनुक्रमणिका के रूप में एक मानचित्र का उपयोग करें।

  • कोई सबस्क्रिप्ट वेक्टर हे (1)
  • एक कुंजी दी से मूल्य लाने मानचित्र का उपयोग मूल्य की सबस्क्रिप्ट लगाने के लिए दिए गए। ओ (LNN)
  • एक मूल्य डालें, वेक्टर हे (1) परिशोधित पर वापस धक्का, नक्शा हे में सबस्क्रिप्ट सम्मिलित (LNN)
  • एक मूल्य हटाने के लिए, मानचित्र हे से हटाना (एलएनएन)

स्रोत

2012-10-21 09:57:35 EvilTeach

संबंधित मुद्दे

 संबंधित मुद्दे