तेजी से संगत श्रेणियों के साथ डेटा संरचना पुनर्प्राप्ति

Question

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

struct Block 
{ 
    size_t begin; 
    size_t end; 
} 

, हमारे डेटा संरचना अपडेट ब्लॉक:

array view   blocks [begin, end] 
-------------------------------------------------------------- 
0 1 2 3 4 5 6 7 8 9  [0, 9] 

pop 2     block 1 splitted 

0 1 _ 3 4 5 6 7 8 9  [0, 1] [3, 9] 

pop 7, 8    block 2 splitted 

0 1 _ 3 4 5 6 _ _ 9  [0, 1] [3, 6] [9, 9] 

push 7     changed end of block 3 

0 1 _ 3 4 5 6 7 _ 9  [0, 1] [3, 7] [9, 9] 

push 5     error: already in 

0 1 _ 3 4 5 6 7 _ 9  [0, 1] [3, 7] [9, 9] 

push 2     blocks 1, 2 merged 

0 1 2 3 4 5 6 7 _ 9  [0, 7] [9, 9] 

भी रूपरेखा से पहले, हम जानते हैं कि ब्लॉक पुनर्प्राप्ति गति आवेदन प्रदर्शन की आधारशिला हो जाएगा । मूल रूप से उपयोग है:

काफी दुर्लभ सम्मिलन/विलोपन

• बहुत बार सन्निहित ब्लॉक की बहाली
• सबसे अधिक समय हम ब्लॉक की संख्या कम से कम हो (विखंडन को रोकने)

हम क्या करना चाहते हैं पहले से ही करने की कोशिश की:

1. std::vector<bool> + std::list<Block*>। प्रत्येक परिवर्तन पर: vector पर सही/गलत लिखें, फिर इसे लूप के लिए पार करें और list पुन: उत्पन्न करें। ब्लॉक की हर क्वेरी पर list लौटाता है। हम चाहते थे से धीमे।

2. std::list<Block*> अद्यतन सूची सीधे, इसलिए कोई ट्रैवर्सिंग नहीं। वापसी सूची। डीबग/परीक्षण करने के लिए बहुत कोड।

सवाल:

1. है कि डेटा संरचना कुछ सामान्य नाम है?
2. क्या पहले से ही ऐसे डेटा संरचनाएं लागू की गई हैं (डीबग और परीक्षण)?
3. यदि नहीं, तो आप इस तरह की डेटा संरचना के तेज़ और मजबूत कार्यान्वयन पर क्या सलाह दे सकते हैं?

क्षमा करें अगर मेरी व्याख्या बिल्कुल स्पष्ट नहीं है।

संपादित

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

एक और एप्लिकेशन एक कस्टम "ब्लॉक मेमोरी आवंटक" है। उस उद्देश्य के लिए, घुसपैठ लिंक्ड सूची के माध्यम से "अलेक्जेंड्रेस्कू ए - मॉडर्न सी ++ डिज़ाइन" पुस्तक में लागू समान डेटा संरचना। मैं बेहतर विकल्पों की तलाश में हूं।

Answer 1

आप संरचना जैसे पेड़, या तो एक साधारण लाल-काले पेड़ या बी + पेड़ की कोशिश कर सकते हैं।

Answer 2

आपका पहला समाधान (बूल की वेक्टर + ब्लॉक की सूची) एक अच्छी दिशा की तरह प्रतीत होता है, लेकिन ध्यान दें कि आपको पूरी तरह से स्क्रैच से पूरी तरह से पुन: उत्पन्न करने की आवश्यकता नहीं है (या पूरे वेक्टर पर जाएं) - आपको बस इसकी आवश्यकता है जब तक आपको पता न लगे कि नई बदली गई इंडेक्स को ठीक किया जाना चाहिए, और सूची में उचित ब्लॉक को विभाजित/विलय करें, तब तक सूची को पार करें।

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

Answer 3

जो मैं यहां देखता हूं वह एक साधारण है बाइनरी पेड़
आपके पास begin औरके साथ जोड़े (ब्लॉक) हैंसूचकांक, यानी, (a,b) जोड़े जहां a <= b। तो ब्लॉक के सेट को आसानी से ऑर्डर किया जा सकता है और खोज-बाइनरी-पेड़ में संग्रहीत किया जा सकता है।
किसी दिए गए नंबर से मेल खाने वाले ब्लॉक को खोजना आसान है (बस टिपिकल बाइनरी-पेड़-सर्च)। इसलिए जब आप सरणी से कोई संख्या हटाते हैं, तो आपको उस ब्लॉक को खोजना होगा जो संख्या से मेल खाता है और इसे दो नए ब्लॉक में विभाजित करता है। ध्यान दें कि सभी ब्लॉक पत्तियां हैं, आंतरिक नोड्स अंतराल होते हैं जिनमें दो बच्चे नोड्स होते हैं।
दूसरी तरफ सम्मिलन का अर्थ ब्लॉक को खोजना है, और अपने भाइयों का परीक्षण करना है कि भाइयों को गिरना है या नहीं। यह पेड़ के माध्यम से बार-बार किया जाना चाहिए।

Answer 4

आप ब्लॉक की एक सूची का उपयोग क्यों कर रहे हैं? क्या आपको स्थिर इटरेटर्स और स्थिर संदर्भों की आवश्यकता है? बढ़ावा :: स्थिर_वेक्टर मदद कर सकता है। यदि आपको स्थिर संदर्भों की आवश्यकता नहीं है, तो हो सकता है कि आप जो चाहते हैं वह एक रैपर कंटेनर लिखना है जिसमें एक std :: वेक्टर ब्लॉक और आकार ब्लॉक का एक द्वितीयक मेमोरी मानचित्र है। Capacity() जो इटरेटर इंडेक्स से एक मानचित्र है (जिसे रखा जाता है अंदर अवरोधक को ब्लॉक वेक्टर में वास्तविक ऑफसेट में लौटा दिया गया) और वर्तमान में अप्रयुक्त इटरेटर सूचकांक की एक सूची।

जब भी आप ब्लॉक से सदस्यों को मिटते हैं, तो आप ब्लॉक को दोबारा हटाते हैं और बढ़ाए गए कैश समेकन के लिए मानचित्र को घुमाते हैं, और जब आप डालना चाहते हैं, तो बस ब्लॉक पर push_back करें।

ब्लॉक पैकिंग के साथ, आपको हटाने की गति की लागत पर फिर से कैश समेकन मिलता है। और अपेक्षाकृत तेज़ डालने के समय बनाए रखें।

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