क्या कोई जावा पुस्तकालय एक यादृच्छिक पहुंच कतार कार्यान्वयन प्रदान करता है?

Question

मैं जावा में ईवेंट की स्ट्रीम पर एक स्लाइडिंग विंडो को कार्यान्वित कर रहा हूं। तो मैं एक डेटा संरचना जो मेरा पीछा करने की अनुमति देता हैं:

1. जब नए ईवेंट के होने पर डेटा संरचना के अंत में जोड़ने;

2. पुराने ईवेंट संसाधित होने पर डेटा संरचना की शुरुआत से हटा दें;

3. डेटा संरचना के तत्वों के लिए मानक यादृच्छिक पहुंच (size(), get(i)) प्राप्त करें; सामान्य रूप से, सामान्य List "पढ़ा" संचालन;

4. उपरोक्त सभी कार्यों के लिए कुशल है;

5. असंबद्ध है।

कोई अन्य एक्सेस आवश्यक नहीं है। और कोई थ्रेड सुरक्षा की आवश्यकता नहीं है।

मैं वर्तमान में चीजों को चलाने और चलाने के लिए ArrayList के साथ ऐसा कर रहा हूं। लेकिन मुझे कुछ और कुशल चाहिए; remove(0) विधि (2. ऊपर) ArrayList के साथ अक्षम है।

संख्या 1. और 2. मानक Queue -स्टाइल संचालन हैं। हालांकि, JDK (जैसे ArrayDeque के रूप में) में Queue के कार्यान्वयन अगर वहाँ किसी भी पुस्तकालयों इस प्रकार का कार्यान्वयन है जो कर रहे हैं, और कर रहे हैं 3.

तो में get(i) के लिए अनुमति नहीं देते, मैं सोच रहा हूँ वाणिज्यिक उपयोग के लिए उपयुक्त है।

यदि नहीं, तो मुझे लगता है कि मैं अपने खुद के लेखन का सहारा होगा ...

Answer 1

केवल पुस्तकालय मैं उस के बारे में सोच सकते हैं लागू करेगा इस तरह के एक इंटरफेस एक LinkedList होगा, लेकिन स्पष्ट रूप से मुझे यकीन है कि क्या नहीं कर रहा हूँ प्रदर्शन विशेषताओं हैं।

Answer 2

Circular Buffer के लिए एक कार्य की तरह लगता है - जब तक कि कतार में निश्चित क्षमता हो तो ठीक है। हालांकि मुझे किसी मानक कार्यान्वयन की जानकारी नहीं है। लेकिन यहां a nice recipe to roll your own है।

Answer 3

यदि आपके पास पर्याप्त पर्याप्त सरणी है तो आप एक मूल सरणी के साथ एक कतार लागू कर सकते हैं, और सूची के शीर्ष के रूप में केवल एक इंडेक्स का उपयोग कर सकते हैं, और मॉड ऑपरेटर का उपयोग करें ताकि यदि आवश्यक हो तो आप चारों ओर लपेट सकें।

तो, मूल रूप से आपके पास एक गोलाकार सरणी है जो सम्मिलित करने और कार्यों को हटाने का समर्थन करती है।

अद्यतन:

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

Answer 4

इस कतार में आने वाली घटनाएं कितनी तेजी से आ रही हैं?

एक तरफ, आपके पास "पर्याप्त रूप से बड़ा" परिपत्र बफर हो सकता है।

हालांकि यह तकनीकी रूप से "बाध्य" है, आप इसे आवश्यकतानुसार इसे बढ़ाकर "असंबद्ध" बना सकते हैं।

उसी टोकन से, आप "शांत" होने पर समग्र क्षमता के संदर्भ में इसे "संक्षिप्त" कर सकते हैं।

लेकिन, कई अनुप्रयोगों के लिए 100, 1000, या यहां तक ​​कि 10000 आइटम क्षमता परिपत्र बफर प्रभावी रूप से असंबद्ध है।

Answer 5

बस इसे अपने आप को घुमाने के विकल्प के रूप में बाहर फेंक दें, इसलिए कृपया नमक के अनाज के साथ लें: कितनी बार आपको यादृच्छिक पहुंच get(i) की आवश्यकता होती है और इसके द्वारा आपको किस प्रदर्शन की आवश्यकता होती है (और आपकी कतार का आकार कितना बड़ा है आमतौर पर होगा), जब आप किसी तत्व को एक्सेस करने की आवश्यकता होती है तो आप हमेशा ArrayDeque.toArray()[i] का उपयोग कर सकते हैं। toArray() कवर के तहत System.arraycopy() का उपयोग करता है जो छोटे कतार आकार और कभी-कभी उपयोग के लिए बहुत तेज़ होना चाहिए। यह समझने में सहायता करेगा कि आपको कतार में यादृच्छिक पहुंच की आवश्यकता क्यों है और इसकी कितनी बार आवश्यकता है - संभवतः इसके बिना आपके एल्गोरिदम को लागू करने का एक अलग तरीका है।

Answer 6

एक द्विपदीय ढेर में ओ (1) अमूर्त डालने और ओ (लॉग एन) amortized मिट मिनट हो सकता है; मेरा मानना ​​है कि इसमें ओ (लॉग ** 2 एन) एमोरेटेड यादृच्छिक पहुंच भी हो सकती है। कतार-पुश कुंजी को चाबियों के रूप में लगातार पूर्णांक के साथ ढेर में डाल देगा।

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

Answer 7

यदि यह वास्तव में असंबद्ध होना चाहिए, तो ConcurrentSkipListMap की तरह कुछ उपयोगी हो सकता है, यदि आप मानचित्र में कुंजी के रूप में उपयोग करने के लिए प्रत्येक ईवेंट में वृद्धिशील अनुक्रम निर्दिष्ट करते हैं। यह प्रदूषण/LastEntry जैसे तरीके प्रदान करता है। यदि आप इसकी असंबद्ध प्रकृति का त्याग कर सकते हैं, तो एक अंगूठी बफर शायद आपको चाहिए।

Answer 8

मैं इस समस्या को मिला है और ArrayDeque के स्रोत कोड को कॉपी करने और की तरह कुछ जोड़कर इसे सुलझाने की कोशिश की:

E get(index){ return elements[(head + index) % size];}