JDK एल्गोरिदम और डेटा संरचनाएं

[ अंग्रेजी संस्करण ]
समय-समय पर जाँच करना कि क्या jdk में एक या दूसरे मानक एल्गोरिथ्म का कार्यान्वयन है, विचार एक समान समीक्षा करने के लिए आया था। ब्याज के अलावा कई ज्ञात डेटा संरचनाओं की उपस्थिति / अनुपस्थिति के कारण थे।
समीक्षा का प्रारूप - केवल महत्वपूर्ण गुण और संरचना और एल्गोरिदम की संरचना में jdk, विवरण और विवरण - स्रोतों में खोजने के लिए javadoc या आसान में लिखे गए हैं।
मैं रचनात्मक आलोचना और सामूहिक मन की उम्मीद करता हूं अगर मैं कुछ याद करता हूं।
पर्याप्त परिचय, तो चलिए नजर डालते हैं कि वर्तमान jdk 7 में क्या शामिल है और क्यों।

संरचना

अनेकता

Jdk का एक पुराना स्टैक ( Stack ) है, जो जावा की रिहाई के बाद से अस्तित्व में है और अब इसकी अनुशंसा नहीं की जाती है, यह जटिल और अजीब है: यह वेक्टर से विरासत में मिला है, जिसका अर्थ है कि यह एक गतिशील विस्तार योग्य सरणी और सिंक्रनाइज़ पर बनाया गया है।
सामान्य स्टैक के लिए यह सब क्यों है और यह एक इंटरफ़ेस क्यों नहीं है? यह पूरी तरह से स्पष्ट नहीं है (एक से अधिक बार चर्चा की गई: 1 , 2 ), लेकिन यह एक डिज़ाइन त्रुटि की तरह दिखता है, जो वेक्टर के समान है।
इसके अलावा, javadoc खुद Deque का उपयोग करने की सलाह देता है।

Deque एक दो-तरफा कतार (OIF (1) के लिए LIFO + FIFO) का इंटरफ़ेस (एपीआई) है, जिसमें स्टैक ऑपरेशन (पुश, पॉप, आइस खाली, आकार) शामिल हैं। Jdk में बहुत पहले से उपलब्ध नहीं (1.6+)।
बेशक, यह आसान होगा यदि ये स्टैक ऑपरेशन स्टैक इंटरफ़ेस में थे, और डीके उदाहरण के लिए इसे प्राप्त करेंगे, लेकिन चूंकि स्टैक पहले से मौजूद था, और बैकवर्ड संगतता "जावा के लिए हमारी हर चीज" है, इसलिए मुझे एक सामान्य डिजाइन का त्याग करना पड़ा।
Deque के कार्यान्वयन ArrayDeque और LinkedList हैं , जो संयोजन में, सामान्य कतार को भी लागू करते हैं, इसलिए हम बाद में विचार करेंगे।

कतारों

अगले क्रम में हम कतार को देखते हैं। यहां सब कुछ ठीक है, डिजाइन सभ्य है।
कतार - FIFO कतार इंटरफ़ेस (एपीआई), शुरुआत में जोड़ें, ओ (1) में अंत से हटाएं।

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

अगला, प्राथमिकता 1.5 juek के साथ जोड़ा गया था, जो वास्तव में कतार अनुबंध का उल्लंघन करता है तत्वों को अंत से नहीं लिया जाता है (शुरुआत में या तो नहीं डाला जाता है) लेकिन उनकी प्राथमिकताओं के अनुसार।
यह एक विस्तार योग्य बाइनरी हीप के आधार पर बनाया गया है, शीर्ष पर - न्यूनतम तत्व (इसके तुलनित्र के अनुसार), जब भरा जाता है, तो यह आकार में डेढ़ गुना बढ़ जाता है। तदनुसार, जोड़ना / निकालना हे (लॉग एन) है, न्यूनतम (सिर) का एक संदर्भ ओ (1) है।

शेष प्रकार की कतारें मल्टीथ्रेडेड हैं, जैसे कि ब्लॉकिंग क्यू, ट्रांसक्यूक्यू, कॉनक्यूरल लिंक क्यू और कॉन्ट्रेक्टलिंकडेक।

BlockingQueue कार्यान्वयन (ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue) उनके मूल के सिंक्रनाइज़ किए गए संस्करण हैं, अर्थात्। लगभग हर ऑपरेशन को सिंक्रोनाइज़ (अवरुद्ध) किया जाता है। इसमें DelayQueue भी शामिल है - सिंक्रनाइज़, आंतरिक रूप से प्रायोरिटी क्यू का उपयोग करता है।

जबकि SynchronousQueue, TransferQueue (LinkedTransferQueue), ConcurrentLinkedQueue, ConcurrentLinkedDeque अलग-अलग दृष्टिकोण पर आधारित हैं: वे कैस निर्देश का उपयोग करके लिंक किए गए सूचियों में गैर-अवरुद्ध कतार एल्गोरिदम का उपयोग करते हैं जो एक मल्टीप्रोसेसर वातावरण में अच्छी तरह से समानांतर होते हैं। एक विस्तृत विवरण स्रोत में है।
इस वर्ग के एल्गोरिदम काफी व्यापक और नई सामग्री हैं, अभी तक पूरी तरह से मानकीकृत और संरचित नहीं हैं, इसलिए, यह इस समीक्षा के दायरे से परे है और एक अलग लेख के लिए विषय नहीं है।

प्राथमिकता कतार (ढेर)

जैसा कि पहले ही उल्लेख किया गया है, 1.5 से शुरू होना एक सार्वभौमिक प्राथमिकता है, इसके अलावा jdk में ढेर का एक और कार्यान्वयन है। यह अच्छा पुराना टाइमर है, टास्कक्यू के एक आंतरिक क्लासिक (शीर्ष पर - एक न्यूनतम प्रतीक्षा समय के साथ एक कार्य)। स्वाभाविक रूप से, यह एक बंद कार्यान्वयन है और टाइमर के अलावा, इसका उपयोग नहीं किया जा सकता है।

सूचियों

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

और दूसरा पहले से ही उल्लेखित लिंक्डलिस्ट है, जो एक दोहरी रूप से जुड़ी अनुक्रमिक एक्सेस सूची है, आकार केवल मुफ्त jvm मेमोरी द्वारा सीमित है। यद्यपि यादृच्छिक अभिगम विधि (सूचकांक द्वारा) भी मौजूद हैं - जैसा कि पहले ही उल्लेख किया गया है, वे ओ (एन) में यहां निष्पादित होते हैं।

किसी कारण से, जावा संग्रह में कोई सरल एकल-लिंक की गई सूची नहीं है, हालांकि यह संभवतः (2 बार कम लिंक ओवरहेड), साथ ही साथ एक साधारण स्टैक नहीं होगा।

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

चरित्र टेबल

एक बाइनरी ट्री और हैश टेबल द्वारा प्रस्तुत किया गया।

एक पेड़ एक रेडमैप -ट्री ट्री (ट्रीसेट) है, जो क्रमबद्ध रूप से (सॉर्टेडसेट, क्रमशः) एक क्लासिक लाल-काले पेड़ पर आधारित है, अर्थात। ओ (लॉग एन) के लिए संतुलित और बुनियादी संचालन की गारंटी, आकार में असीमित।
Jdk में अन्य प्रकार के पेड़ नहीं हैं।

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

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

Multithreaded संस्करण: ConcurrentHashMap, SyncMap आवरण, हैशटेबल और ConcurrentSkipListMap। एक रैपर स्वाभाविक रूप से एक नियमित हाशप का अवरुद्ध संस्करण है, एक हैशटेबल एक ही है, समवर्ती हाशप एक लॉक-स्ट्रिपिंग संस्करण है जो आपको महत्वपूर्ण अनुभागों को काटने की अनुमति देता है (यह JCiP में इसके बारे में पढ़ने के लिए बेहतर है, यहां एक अंश है )।
ConcurrentSkipListMap हैश तालिका के लिए अनुकूलित समान नाम के एल्गोरिथ्म का एक गैर-अवरोधक संस्करण है (अधिक विवरण के लिए स्रोत देखें)।

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

गिनता

ग्राफ़ संरचनाओं और एल्गोरिदम को jdk में दर्शाया नहीं गया है। इसलिए, इस मामले में, यह केवल तीसरे पक्ष के पुस्तकालयों का उपयोग करने के लिए रहता है

पंक्तियां

मानक कार्यान्वयन यूनिकोड वर्णों की एक सरणी पर आधारित है। यह याद रखने योग्य है कि संस्करण 1.7_17 से शुरू होकर, सबस्ट्रिंग प्रदर्शन अब O (n) है, क्योंकि सबस्ट्रिंग की प्रतिलिपि बनाई गई है।

यह दिलचस्प है कि एक विकल्प के लिए खोज करने के लिए, सबसे खराब स्थिति में ओ (एन * एम) देने वाला सरल खोज एल्गोरिदम का उपयोग किया जाता है, न कि एक परिमित राज्य मशीन (नूथ-मॉरिस-प्रैट और अन्य) पर निर्मित कुछ कुशल एल्गोरिदम ।
कई कारण हैं: सबसे पहले, UTF वर्णों (~ 65K) में वर्णमाला भी बड़ी है, जिसका अर्थ है कि राज्य मशीन को संग्रहीत करने के लिए बहुत अधिक ओवरहेड है, जबकि खोज एल्गोरिथ्म में जगह है (कोई अतिरिक्त मेमोरी का उपयोग नहीं किया जाता है)।
और दूसरी बात, औसत लाइनों पर प्रदर्शन - इसमें, जाहिरा तौर पर, खोज अन्य एल्गोरिदम से बहुत कम नहीं होती है।

छँटाई के साथ एक ही बात। गिनती (एलएसडी, एमएसडी, आदि) द्वारा लाइनों की कुशल छंटाई की जाती है , लेकिन jdk वस्तुओं के लिए मानक का उपयोग करता है, ओ (एम * एन * लॉग एन) देते हुए यदि अधिकांश लाइनें बहुत अलग नहीं हैं (एम औसत लाइन लंबाई है)।
कारण समान है: गिनती सॉर्टिंग यूटीएफ वर्णमाला के आकार के सहायक सरणियों का उपयोग करते हैं, जो उन्हें औसत सांख्यिकीय इनपुट डेटा पर अक्षम बनाता है।

एल्गोरिदम

छंटाई

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

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

ऑब्जेक्ट संस्करण का उपयोग स्ट्रिंग्स को सॉर्ट करने के लिए भी किया जाता है, इसके कारणों का उल्लेख ऊपर किया गया है।

खोज

पारंपरिक बाइनरी खोज प्राइमिटिव्स और ऑब्जेक्ट्स के सभी सरणियों के साथ-साथ यादृच्छिक अभिगम का समर्थन करने वाली सूचियों के लिए मौजूद है।

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

नियमित अभिव्यक्ति

पारंपरिक कार्यान्वयन एक गैर-नियतात्मक परिमित राज्य मशीन ( एनएफए ) और बैकट्रैकिंग पर आधारित है । यानी अध: पतन मूल्यों पर सबसे खराब स्थिति में घातीय जटिलता ओ (एम ^ एन), उदाहरण:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".matches("(a|aa)*b") 

तथाकथित "ऑर्डर किए गए विकल्प" (क्रमिक विकल्प?) - यह तब होता है जब सबसे विशिष्ट (लंबे), उदाहरण के बजाय कई से पहला मैच खोजने के तुरंत बाद खोज बंद हो जाती है।

हैश फंक्शंस, चेकसम

Jdk में हैशकोड गणना के लिए छह पूर्णांक एल्गोरिदम हैं, पार्क-मिलर_रैंडम_number_generator डिफ़ॉल्ट रूप से उपयोग किया जाता है, हैबर पर एक हालिया लेख ।

मानक उद्योग-मानक हैशिंग एल्गोरिदम (SHA- *, MD5 और विविधताएं) भी हैं - MessageDigest

चेकसमों की गणना करने के लिए, एडलर -32 ( जेवाडॉक ) और सीआरसी 32 ( जेवाडॉक ) एल्गोरिदम के कार्यान्वयन अभी भी हैं

दबाव

Jdk में मानक डिफ्लेट कम्प्रेशन अल्गोरिथम ( डीफ्लैटर ) का कार्यान्वयन है और इसके आधार पर जिप / gzip भी है। यह सब java.util.zip पैकेज में

निष्कर्ष

जैसा कि आप देख सकते हैं, जावा में शास्त्रीय डेटा संरचनाएं पूरी तरह से प्रतिनिधित्व करती हैं, लेकिन एक ही समय में, लगभग हर एक के लिए थ्रेड सुरक्षित संस्करणों के लिए कई विकल्प हैं।
क्या गायब है यह एक खुला प्रश्न है। उदाहरण के लिए, कोई यह तर्क दे सकता है कि क्या jdk में कुछ Union-Find की जरूरत है, लेकिन सामाजिक नेटवर्क के युग में ग्राफ संरचनाओं और एल्गोरिदम की कमी ऐसी भाषा में है जो सबसे सार्वभौमिक होने का दावा करती है - बग और साइकिल आश्चर्यजनक हैं।