सेट (अमूर्त डेटा प्रकार): Difference between revisions
(Created page with "{{Short description|Abstract data type for storing unique values}} {{more citations needed|date=October 2011}} भारत कंप्यूटर विज्ञा...") |
No edit summary |
||
Line 1: | Line 1: | ||
{{Short description|Abstract data type for storing unique values}} | {{Short description|Abstract data type for storing unique values}} | ||
[[भारत]] [[कंप्यूटर विज्ञान]], उपसमुच्चय [[सार डेटा प्रकार]] है जो बिना किसी विशेष क्रम के अद्वितीय मूल्यों को संग्रहीत कर सकता है। यह परिमित समुच्चय की गणित अवधारणा का कंप्यूटर कार्यान्वयन है। अधिकांश अन्य [[संग्रह (सार डेटा प्रकार)]] प्रकारों के विपरीत, उपसमुच्चय से विशिष्ट तत्व को पुनः प्राप्त करने के अतिरिक्त, सामान्यतः उपसमुच्चय में सदस्यता के लिए मूल्य का परीक्षण किया जाता है। | |||
[[भारत]] [[कंप्यूटर विज्ञान]], | |||
कुछ | कुछ उपसमुच्चय डेटा संरचनाएं स्थिर या एकत्रित उपसमुच्चय के लिए चित्रित किए गए हैं जो उनके निर्माण के पश्चात परिवर्तित नहीं होते हैं। स्थिर उपसमुच्चय स्वयं तत्वों पर केवल क्वेरी संचालन की अनुमति देते हैं - जैसे कि यह देखना कि क्या दिया गया मान उपसमुच्चय में है, या कुछ मनमाना क्रम में मानों की गणना करना अन्य वेरिएंट, जिन्हें डायनेमिक या म्यूटेबल उपसमुच्चय कहा जाता है, उपसमुच्चय से तत्वों को सम्मिलित करने एवं विस्थापित करने की भी अनुमति देते हैं। | ||
[[ multiset |बहुसमुच्चय]] विशेष प्रकार का उपसमुच्चय है, जिसमें तत्व उपसमुच्चय में कई बार दिखाई दे सकता है। | |||
== [[प्रकार सिद्धांत]] == | == [[प्रकार सिद्धांत]] == | ||
प्रकार सिद्धांत में, | प्रकार सिद्धांत में, उपसमुच्चय सामान्यतः उनके संकेतक फ़ंक्शन (विशेषता समारोह) के साथ पहचाने जाते हैं: तदनुसार, प्रकार के मूल्यों का एक उपसमुच्चय <math>A</math> द्वारा दर्शाया जा सकता है <math>2^{A}</math> या <math>\mathcal{P}(A)</math>. (उपप्रकार एवं उपसमुच्चय को [[शोधन प्रकार]]ों द्वारा प्रतिरूपित किया जा सकता है, एवं भागफल उपसमुच्चय को उपसमुच्चयोइड्स द्वारा प्रतिस्थापित किया जा सकता है।) विशेषता कार्य <math>F</math> एक उपसमुच्चय का <math>S</math> परिभाषित किया जाता है: | ||
:<math>F(x) = \begin{cases} | :<math>F(x) = \begin{cases} | ||
1, & \mbox{if } x \in S \\ | 1, & \mbox{if } x \in S \\ | ||
Line 14: | Line 13: | ||
\end{cases} | \end{cases} | ||
</math> | </math> | ||
सिद्धांत रूप में, कई अन्य अमूर्त डेटा संरचनाओं को मानक संचालन पर लगाए गए अतिरिक्त संचालन | सिद्धांत रूप में, कई अन्य अमूर्त डेटा संरचनाओं को मानक संचालन पर लगाए गए अतिरिक्त संचालन एवं/या अतिरिक्त सिद्धांतों के साथ उपसमुच्चय संरचनाओं के रूप में देखा जा सकता है। उदाहरण के लिए, एक अमूर्त हीप डेटा संरचना को एक उपसमुच्चय संरचना के रूप में देखा जा सकता है <code>min(''S'')</code> ऑपरेशन जो सबसे छोटे मूल्य का तत्व लौटाता है। | ||
== संचालन == | == संचालन == | ||
=== कोर | === कोर उपसमुच्चय-सैद्धांतिक संचालन === | ||
कोई | कोई उपसमुच्चय के बीजगणित के संचालन को परिभाषित कर सकता है: | ||
* <code>union(''S'',''T'')</code>: समुच्चय S | * <code>union(''S'',''T'')</code>: समुच्चय S एवं T का [[संघ (सेट सिद्धांत)|संघ (उपसमुच्चय सिद्धांत)]] लौटाता है। | ||
* <code>intersection(''S'',''T'')</code>: समुच्चय S | * <code>intersection(''S'',''T'')</code>: समुच्चय S एवं T का प्रतिच्छेदन (उपसमुच्चय सिद्धांत) लौटाता है। | ||
* <code>difference(''S'',''T'')</code>: समुच्चय S | * <code>difference(''S'',''T'')</code>: समुच्चय S एवं T का [[अंतर (सेट सिद्धांत)|अंतर (उपसमुच्चय सिद्धांत)]] लौटाता है। | ||
* <code>subset(''S'',''T'')</code>: एक विधेय जो परीक्षण करता है कि क्या समुच्चय S, समुच्चय T का उपसमुच्चय है। | * <code>subset(''S'',''T'')</code>: एक विधेय जो परीक्षण करता है कि क्या समुच्चय S, समुच्चय T का उपसमुच्चय है। | ||
=== स्थैतिक | === स्थैतिक उपसमुच्चय === | ||
स्टैटिक | स्टैटिक उपसमुच्चय स्ट्रक्चर S द्वारा प्रदान किए जा सकने वाले विशिष्ट ऑपरेशन हैं: | ||
* <code>is_element_of(''x'',''S'')</code>: जाँचता है कि क्या मान x | * <code>is_element_of(''x'',''S'')</code>: जाँचता है कि क्या मान x उपसमुच्चय S में है। | ||
* <code>is_empty(''S'')</code>: जांचता है कि | * <code>is_empty(''S'')</code>: जांचता है कि उपसमुच्चय एस खाली है या नहीं। | ||
* <code>size(''S'')</code> या <code>[[cardinality]](''S'')</code>: एस में तत्वों की संख्या लौटाता है। | * <code>size(''S'')</code> या <code>[[cardinality]](''S'')</code>: एस में तत्वों की संख्या लौटाता है। | ||
* <code>[[iterator|iterate]](''S'')</code>: एक ऐसा फ़ंक्शन लौटाता है जो प्रत्येक कॉल पर S का एक | * <code>[[iterator|iterate]](''S'')</code>: एक ऐसा फ़ंक्शन लौटाता है जो प्रत्येक कॉल पर S का एक एवं मान देता है, कुछ मनमाना क्रम में। | ||
* <code>enumerate(''S'')</code>: कुछ मनमानी क्रम में एस के तत्वों वाली एक सूची देता है। | * <code>enumerate(''S'')</code>: कुछ मनमानी क्रम में एस के तत्वों वाली एक सूची देता है। | ||
* <code>build(''x''<sub>1</sub>,''x''<sub>2</sub>,…,''x''<sub>''n''</sub>,)</code>: मान x के साथ एक | * <code>build(''x''<sub>1</sub>,''x''<sub>2</sub>,…,''x''<sub>''n''</sub>,)</code>: मान x के साथ एक उपसमुच्चय संरचना बनाता है<sub>1</sub>,एक्स<sub>2</sub>,...,एक्स<sub>''n''</sub>. | ||
* <code>create_from(''collection'')</code>: दिए गए संग्रह के सभी तत्वों (सार डेटा प्रकार) या दिए गए पुनरावर्तक द्वारा लौटाए गए सभी तत्वों वाली एक नई | * <code>create_from(''collection'')</code>: दिए गए संग्रह के सभी तत्वों (सार डेटा प्रकार) या दिए गए पुनरावर्तक द्वारा लौटाए गए सभी तत्वों वाली एक नई उपसमुच्चय संरचना बनाता है। | ||
=== गतिशील | === गतिशील उपसमुच्चय === | ||
गतिशील | गतिशील उपसमुच्चय संरचनाएं सामान्यतः जोड़ती हैं: | ||
* <code>create()</code>: एक नया, प्रारंभ में खाली | * <code>create()</code>: एक नया, प्रारंभ में खाली उपसमुच्चय संरचना बनाता है। | ||
** <code>create_with_capacity(''n'')</code>: एक नई | ** <code>create_with_capacity(''n'')</code>: एक नई उपसमुच्चय संरचना बनाता है, प्रारंभ में खाली लेकिन n तत्वों तक धारण करने में सक्षम। | ||
* <code>add(''S'',''x'')</code>: तत्व x को S में जोड़ता है, यदि यह पहले से मौजूद नहीं है। | * <code>add(''S'',''x'')</code>: तत्व x को S में जोड़ता है, यदि यह पहले से मौजूद नहीं है। | ||
* <code>remove(''S'', ''x'')</code>: तत्व x को S से हटाता है, यदि यह मौजूद है। | * <code>remove(''S'', ''x'')</code>: तत्व x को S से हटाता है, यदि यह मौजूद है। | ||
* <code>capacity(''S'')</code>: S द्वारा धारण किए जा सकने वाले मानों की अधिकतम संख्या लौटाता है। | * <code>capacity(''S'')</code>: S द्वारा धारण किए जा सकने वाले मानों की अधिकतम संख्या लौटाता है। | ||
कुछ | कुछ उपसमुच्चय संरचनाएं इनमें से केवल कुछ परिचालनों की अनुमति दे सकती हैं। प्रत्येक ऑपरेशन की लागत कार्यान्वयन पर निर्भर करेगी, एवं संभवतः उपसमुच्चय में संग्रहीत विशेष मूल्यों पर भी, एवं जिस क्रम में उन्हें सम्मिलित किया गया है। | ||
=== अतिरिक्त संचालन === | === अतिरिक्त संचालन === | ||
ऐसे कई अन्य ऑपरेशन हैं जिन्हें (सिद्धांत रूप में) उपरोक्त के संदर्भ में परिभाषित किया जा सकता है, जैसे: | ऐसे कई अन्य ऑपरेशन हैं जिन्हें (सिद्धांत रूप में) उपरोक्त के संदर्भ में परिभाषित किया जा सकता है, जैसे: | ||
* <code>pop(''S'')</code>: एस का एक मनमाना तत्व लौटाता है, इसे एस से हटा देता है।<ref>Python: [https://docs.python.org/3/library/stdtypes.html#set.pop pop()]</ref> | * <code>pop(''S'')</code>: एस का एक मनमाना तत्व लौटाता है, इसे एस से हटा देता है।<ref>Python: [https://docs.python.org/3/library/stdtypes.html#set.pop pop()]</ref> | ||
* <code>pick(''S'')</code>: S का मनमाना तत्व लौटाता है।<ref>''Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings,'' ed. Kai v. Luck, Heinz Marburger, [https://books.google.com/books?id=ymhoQ3y0vccC&q=pick&pg=PA76 p. 76]</ref><ref>Python [http://bugs.python.org/issue7212 Issue7212]: Retrieve an arbitrary element from a set without removing it; see [http://bugs.python.org/issue7212#msg106593 msg106593] regarding standard name</ref><ref>Ruby [https://bugs.ruby-lang.org/issues/4553 Feature #4553]: Add Set#pick and Set#pop</ref> कार्यात्मक रूप से, उत्परिवर्ती <code>pop</code> चयनकर्ताओं की जोड़ी के रूप में व्याख्या की जा सकती है <code>(pick, rest),</code> कहाँ <code>rest</code> मनमाने तत्व को छोड़कर सभी तत्वों से युक्त | * <code>pick(''S'')</code>: S का मनमाना तत्व लौटाता है।<ref>''Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings,'' ed. Kai v. Luck, Heinz Marburger, [https://books.google.com/books?id=ymhoQ3y0vccC&q=pick&pg=PA76 p. 76]</ref><ref>Python [http://bugs.python.org/issue7212 Issue7212]: Retrieve an arbitrary element from a set without removing it; see [http://bugs.python.org/issue7212#msg106593 msg106593] regarding standard name</ref><ref>Ruby [https://bugs.ruby-lang.org/issues/4553 Feature #4553]: Add Set#pick and Set#pop</ref> कार्यात्मक रूप से, उत्परिवर्ती <code>pop</code> चयनकर्ताओं की जोड़ी के रूप में व्याख्या की जा सकती है <code>(pick, rest),</code> कहाँ <code>rest</code> मनमाने तत्व को छोड़कर सभी तत्वों से युक्त उपसमुच्चय लौटाता है।<ref>''Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning,'' Ute Schmid, Springer, Aug 21, 2003, [https://books.google.com/books?id=p-Fy25LE4lMC&q=pick&pg=PA240 p. 240]</ref> के रूप में समझा जा सकता है <code>iterate</code>.{{efn|For example, in Python <code>pick</code> can be implemented on a derived class of the built-in <code>set</code> as follows: | ||
<syntaxhighlight lang="python"> | <syntaxhighlight lang="python"> | ||
class Set(set): | class Set(set): | ||
def pick(self): | def pick(self): | ||
return next(iter(self))</syntaxhighlight>}} | return next(iter(self))</syntaxhighlight>}} | ||
* <code>[[Map (higher-order function)|map]](''F'',''S'')</code>: फ़ंक्शन F को S के प्रत्येक तत्व पर लागू करने के परिणामस्वरूप भिन्न मानों का | * <code>[[Map (higher-order function)|map]](''F'',''S'')</code>: फ़ंक्शन F को S के प्रत्येक तत्व पर लागू करने के परिणामस्वरूप भिन्न मानों का उपसमुच्चय लौटाता है। | ||
* <code>[[Filter (higher-order function)|filter]](''P'',''S'')</code>: एस के सभी तत्वों से युक्त | * <code>[[Filter (higher-order function)|filter]](''P'',''S'')</code>: एस के सभी तत्वों से युक्त सबउपसमुच्चय लौटाता है जो किसी दिए गए [[विधेय (गणितीय तर्क)]] पी को संतुष्ट करता है। | ||
* <code>[[Fold (higher-order function)|fold]](''A''<sub>0</sub>,''F'',''S'')</code>: मान A लौटाता है<sub>|''S''|</sub> आवेदन करने के | * <code>[[Fold (higher-order function)|fold]](''A''<sub>0</sub>,''F'',''S'')</code>: मान A लौटाता है<sub>|''S''|</sub> आवेदन करने के पश्चात <code>''A''<sub>i+1</sub> := ''F''(''A<sub>i</sub>'', ''e'')</code> एस के प्रत्येक तत्व ई के लिए, कुछ बाइनरी ऑपरेशन एफ के लिए। एफ को अच्छी तरह से परिभाषित करने के लिए सहयोगी एवं कम्यूटेटिव होना चाहिए। | ||
* <code>clear(''S'')</code>: एस के सभी तत्वों को हटा दें। | * <code>clear(''S'')</code>: एस के सभी तत्वों को हटा दें। | ||
* <code>equal(''S''<sub>1</sub>', ''S''<sub>2</sub>')</code>: जांचता है कि क्या दिए गए दो | * <code>equal(''S''<sub>1</sub>', ''S''<sub>2</sub>')</code>: जांचता है कि क्या दिए गए दो उपसमुच्चय समान हैं (अर्थात सभी एवं केवल समान तत्व शामिल हैं)। | ||
* <code>hash(''S'')</code>: स्थिर | * <code>hash(''S'')</code>: स्थिर उपसमुच्चय S के लिए एक [[हैश मान]] लौटाता है जैसे कि if <code>equal(''S''<sub>1</sub>, ''S''<sub>2</sub>)</code> तब <code>hash(''S<sub>1</sub>'') = hash(''S<sub>2</sub>'')</code> | ||
अन्य कार्यों को एक विशेष प्रकार के तत्वों वाले | अन्य कार्यों को एक विशेष प्रकार के तत्वों वाले उपसमुच्चय के लिए परिभाषित किया जा सकता है: | ||
* <code>sum(''S'')</code>: योग की कुछ परिभाषा के लिए S के सभी तत्वों का योग लौटाता है। उदाहरण के लिए, पूर्णांक या वास्तविक से अधिक, इसे इस रूप में परिभाषित किया जा सकता है <code>fold(0, add, ''S'')</code>. | * <code>sum(''S'')</code>: योग की कुछ परिभाषा के लिए S के सभी तत्वों का योग लौटाता है। उदाहरण के लिए, पूर्णांक या वास्तविक से अधिक, इसे इस रूप में परिभाषित किया जा सकता है <code>fold(0, add, ''S'')</code>. | ||
* <code>collapse(''S'')</code>: | * <code>collapse(''S'')</code>: उपसमुच्चय का एक उपसमुच्चय दिया गया है, संघ वापस करें।<ref>''Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10,'' ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, [https://books.google.com/books?id=LkvQYL23v1sC&q=collapse&pg=PA38 p. 38]</ref> उदाहरण के लिए, <code>collapse({{1}, {2, 3}}) == {1, 2, 3}</code>. प्रकार का माना जा सकता है <code>sum</code>. | ||
* <code>flatten(''S'')</code>: | * <code>flatten(''S'')</code>: उपसमुच्चय एवं परमाणु तत्वों (तत्व जो उपसमुच्चय नहीं हैं) से मिलकर एक उपसमुच्चय दिया गया है, एक उपसमुच्चय देता है जिसके तत्व मूल शीर्ष-स्तरीय उपसमुच्चय के परमाणु तत्व या उपसमुच्चय के तत्व होते हैं। दूसरे शब्दों में, नेस्टिंग के स्तर को हटा दें - जैसे <code>collapse,</code> लेकिन परमाणुओं की अनुमति दें। यह एक बार किया जा सकता है, या केवल परमाणु तत्वों का एक उपसमुच्चय प्राप्त करने के लिए पुनरावर्ती चपटा किया जा सकता है।<ref>Ruby: [http://www.ruby-doc.org/stdlib-2.1.2/libdoc/set/rdoc/Set.html#method-i-flatten flatten()]</ref> उदाहरण के लिए, <code>flatten({1, {2, 3}}) == {1, 2, 3}</code>. | ||
* <code>nearest(''S'',''x'')</code>: एस का तत्व लौटाता है जो एक्स के मूल्य में निकटतम है (कुछ [[मीट्रिक (गणित)]] द्वारा)। | * <code>nearest(''S'',''x'')</code>: एस का तत्व लौटाता है जो एक्स के मूल्य में निकटतम है (कुछ [[मीट्रिक (गणित)]] द्वारा)। | ||
* <code>min(''S'')</code>, <code>max(''S'')</code>: S का न्यूनतम/अधिकतम तत्व लौटाता है। | * <code>min(''S'')</code>, <code>max(''S'')</code>: S का न्यूनतम/अधिकतम तत्व लौटाता है। | ||
== कार्यान्वयन == | == कार्यान्वयन == | ||
विभिन्न [[डेटा संरचना]]ओं का उपयोग करके | विभिन्न [[डेटा संरचना]]ओं का उपयोग करके उपसमुच्चय को लागू किया जा सकता है, जो विभिन्न कार्यों के लिए अलग-अलग समय एवं स्थान का समझौता प्रदान करते हैं। कुछ कार्यान्वयन बहुत विशिष्ट संचालन की दक्षता में सुधार के लिए डिज़ाइन किए गए हैं, जैसे <code>nearest</code> या <code>union</code>. सामान्य उपयोग के रूप में वर्णित कार्यान्वयन आम तौर पर अनुकूलित करने का प्रयास करते हैं <code>element_of</code>, <code>add</code>, एवं <code>delete</code> संचालन। एक सरल कार्यान्वयन एक [[सूची (सार डेटा प्रकार)]] का उपयोग करना है, तत्वों के क्रम की अनदेखी करना एवं बार-बार मूल्यों से बचने के लिए ध्यान रखना। यह सरल लेकिन अक्षम है, क्योंकि उपसमुच्चय सदस्यता या तत्व विलोपन जैसे ऑपरेशन ओ (एन) हैं, क्योंकि उन्हें पूरी सूची को स्कैन करने की आवश्यकता होती है।{{efn|Element insertion can be done in ''O''(1) time by simply inserting at an end, but if one avoids duplicates this takes ''O''(''n'') time.}} उपसमुच्चय को अक्सर अधिक कुशल डेटा संरचनाओं का उपयोग करके कार्यान्वित किया जाता है, विशेष रूप से ट्री (डेटा संरचना), कोशिशों, या [[हैश टेबल]] के विभिन्न स्वाद। | ||
जैसा कि | जैसा कि उपसमुच्चय को एक प्रकार के मानचित्र (संकेतक फ़ंक्शन द्वारा) के रूप में व्याख्या किया जा सकता है, उपसमुच्चय सामान्यतः उसी तरह (आंशिक) मानचित्र (सहयोगी सरणियाँ) में लागू होते हैं - इस मामले में जिसमें प्रत्येक कुंजी-मूल्य जोड़ी का मान होता है [[इकाई प्रकार]] या एक प्रहरी मान (जैसे 1) - अर्थात्, क्रमबद्ध उपसमुच्चयों के लिए एक स्व-संतुलन बाइनरी खोज वृक्ष{{Definition needed|date=November 2020}} (जिसमें अधिकांश ऑपरेशनों के लिए O(log n) है), या अनसोल्ड उपसमुच्चय के लिए एक हैश टेबल (जिसमें O(1) औसत-केस है, लेकिन O(n) सबसे खराब-केस, अधिकांश ऑपरेशनों के लिए)। एक क्रमबद्ध रैखिक [[हैश तालिका]]<ref>{{Citation |title=Sorted Linear Hash Table |first1=Thomas |last1=Wang |url=http://www.concentric.net/~Ttwang/tech/sorthash.htm |year=1997 |url-status=dead |archive-url=https://web.archive.org/web/20060112115812/http://www.concentric.net/~Ttwang/tech/sorthash.htm |archive-date=2006-01-12 }}</ref> नियतात्मक रूप से आदेशित उपसमुच्चय प्रदान करने के लिए उपयोग किया जा सकता है। | ||
इसके अलावा, उन भाषाओं में जो नक्शों का समर्थन करती हैं लेकिन | इसके अलावा, उन भाषाओं में जो नक्शों का समर्थन करती हैं लेकिन उपसमुच्चय का नहीं, उपसमुच्चय को नक्शों के संदर्भ में लागू किया जा सकता है। उदाहरण के लिए, [[पर्ल]] में एक सामान्य [[प्रोग्रामिंग मुहावरा]] जो एक सरणी को एक हैश में परिवर्तित करता है जिसका मूल्य प्रहरी मान 1 है, एक उपसमुच्चय के रूप में उपयोग के लिए: | ||
<syntaxhighlight lang="perl"> | <syntaxhighlight lang="perl"> | ||
my %elements = map { $_ => 1 } @elements; | my %elements = map { $_ => 1 } @elements; | ||
</syntaxhighlight> | </syntaxhighlight> | ||
अन्य लोकप्रिय विधियों में [[सरणी डेटा संरचना]] शामिल है। विशेष रूप से पूर्णांक 1..n का एक | अन्य लोकप्रिय विधियों में [[सरणी डेटा संरचना]] शामिल है। विशेष रूप से पूर्णांक 1..n का एक सबउपसमुच्चय एन-बिट [[बिट सरणी]] के रूप में कुशलतापूर्वक कार्यान्वित किया जा सकता है, जो बहुत ही कुशल संघ एवं चौराहे के संचालन का भी समर्थन करता है। एक [[ ब्लूम नक्शा ]] एक बहुत ही कॉम्पैक्ट प्रतिनिधित्व का उपयोग करते हुए संभावित रूप से एक उपसमुच्चय को लागू करता है, लेकिन प्रश्नों पर झूठी सकारात्मकता की एक छोटी सी संभावना को जोखिम में डालता है। | ||
बूलियन | बूलियन उपसमुच्चय ऑपरेशंस को अधिक प्राथमिक ऑपरेशंस के संदर्भ में कार्यान्वित किया जा सकता है (<code>pop</code>, <code>clear</code>, एवं <code>add</code>), लेकिन विशेष एल्गोरिदम कम स्पर्शोन्मुख समय सीमा उत्पन्न कर सकते हैं। यदि उपसमुच्चय को सॉर्ट की गई सूचियों के रूप में कार्यान्वित किया जाता है, उदाहरण के लिए, भोली एल्गोरिथ्म के लिए <code>union(''S'',''T'')</code> S की लंबाई m गुणा T की लंबाई n के अनुपात में समय लगेगा; जबकि [[मर्ज एल्गोरिथम]] का एक संस्करण m+n के आनुपातिक समय में काम करेगा। इसके अलावा, विशेष उपसमुच्चय डेटा संरचनाएं हैं (जैसे कि [[ संघ-खोज एल्गोरिथ्म ]] | यूनियन-फाइंड डेटा स्ट्रक्चर) जो दूसरों की कीमत पर इनमें से एक या अधिक ऑपरेशन के लिए अनुकूलित हैं। | ||
== भाषा समर्थन == | == भाषा समर्थन == | ||
[[ पास्कल प्रोग्रामिंग भाषा ]] | [[ पास्कल प्रोग्रामिंग भाषा ]] उपसमुच्चय का समर्थन करने वाली शुरुआती भाषाओं में से एक थी; कई भाषाओं में अब यह शामिल है, चाहे मूल भाषा में हो या किसी [[मानक पुस्तकालय]] में। | ||
* [[C++]] में, [[मानक टेम्पलेट लाइब्रेरी]] (STL) प्रदान करती है <code>[[set (C++)|set]]</code> टेम्प्लेट क्लास, जिसे | * [[C++]] में, [[मानक टेम्पलेट लाइब्रेरी]] (STL) प्रदान करती है <code>[[set (C++)|set]]</code> टेम्प्लेट क्लास, जिसे सामान्यतः एक बाइनरी सर्च ट्री (जैसे लाल-काले पेड़) का उपयोग करके लागू किया जाता है; [[सिलिकॉन ग्राफिक्स इंटरनेशनल]] का एसटीएल भी प्रदान करता है <code>hash_set</code> टेम्प्लेट क्लास, जो हैश टेबल का उपयोग करके एक उपसमुच्चय को लागू करता है। [[C++11]] के लिए समर्थन है <code>[[unordered_set (C++)|unordered_set]]</code> टेम्प्लेट क्लास, जिसे हैश टेबल का उपयोग करके कार्यान्वित किया जाता है। उपसमुच्चय में, तत्व स्वयं कुंजी हैं, अनुक्रमित कंटेनरों के विपरीत, जहां तत्वों को उनकी (सापेक्ष या पूर्ण) स्थिति का उपयोग करके एक्सेस किया जाता है। उपसमुच्चय तत्वों में सख्त कमजोर क्रम होना चाहिए। | ||
* रस्ट (प्रोग्रामिंग भाषा) मानक पुस्तकालय सामान्य प्रदान करता है <code>[https://doc.rust-lang.org/std/collections/struct.HashSet.html HashSet]</code> | * रस्ट (प्रोग्रामिंग भाषा) मानक पुस्तकालय सामान्य प्रदान करता है <code>[https://doc.rust-lang.org/std/collections/struct.HashSet.html HashSet]</code> एवं <code>[https://doc.rust-lang.org/std/collections/struct.BTreeSet.html BTreeSet]</code> प्रकार। | ||
* [[जावा (प्रोग्रामिंग भाषा)]] प्रदान करता है {{Javadoc:SE|java/util|Set}} [[इंटरफ़ेस (कंप्यूटर विज्ञान)]] | * [[जावा (प्रोग्रामिंग भाषा)]] प्रदान करता है {{Javadoc:SE|java/util|Set}} [[इंटरफ़ेस (कंप्यूटर विज्ञान)]] उपसमुच्चय का समर्थन करने के लिए ( {{Javadoc:SE|java/util|HashSet}} वर्ग इसे हैश तालिका का उपयोग करके कार्यान्वित करता है), एवं {{Javadoc:SE|java/util|SortedSet}} सॉर्ट किए गए उपसमुच्चयों का समर्थन करने के लिए उप-इंटरफ़ेस ( {{Javadoc:SE|java/util|TreeSet}} वर्ग इसे बाइनरी सर्च ट्री का उपयोग करके कार्यान्वित करता है)। | ||
* ऐप्पल इंक की [[फाउंडेशन किट]] ([[कोको (एपीआई)]] का हिस्सा) [[ उद्देश्य सी ]] क्लास प्रदान करती है <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/ NSSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/ NSMutableSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSCountedSet_Class/ NSCountedSet]</code>, <code>[https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSOrderedSet_Class/Reference/Reference.html NSOrderedSet]</code>, | * ऐप्पल इंक की [[फाउंडेशन किट]] ([[कोको (एपीआई)]] का हिस्सा) [[ उद्देश्य सी ]] क्लास प्रदान करती है <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSSet_Class/ NSSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSMutableSet_Class/ NSMutableSet]</code>, <code>[https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSCountedSet_Class/ NSCountedSet]</code>, <code>[https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSOrderedSet_Class/Reference/Reference.html NSOrderedSet]</code>, एवं <code>[https://developer.apple.com/library/mac/#documentation/Foundation/Reference/NSMutableOrderedSet_Class/Reference/Reference.html NSMutableOrderedSet]</code>. [[CoreFoundation]] API इनके लिए [https://developer.apple.com/documentation/CoreFoundation/Reference/CFSetRef/ CFSet] एवं [https://developer.apple.com/documentation/CoreFoundation/Reference/CFMutableSetRef/ CFMutableSet] प्रकार प्रदान करता है। [[सी (प्रोग्रामिंग भाषा)]] में उपयोग करें। | ||
* [[पायथन (प्रोग्रामिंग भाषा)]] में अंतर्निहित है [https://docs.python.org/library/stdtypes.html#set-types-set-frozenset <code>set</code> | * [[पायथन (प्रोग्रामिंग भाषा)]] में अंतर्निहित है [https://docs.python.org/library/stdtypes.html#set-types-set-frozenset <code>set</code> एवं <code>frozenset</code> प्रकार] 2.4 के पश्चात से, एवं पायथन 3.0 एवं 2.7 के पश्चात से, कर्ली-ब्रैकेट सिंटैक्स का उपयोग करके गैर-खाली उपसमुच्चय शाब्दिक का समर्थन करता है, जैसे: <code>{x, y, z}</code>; खाली उपसमुच्चय का उपयोग करके बनाया जाना चाहिए <code>set()</code>, क्योंकि पायथन उपयोग करता है <code>{}</code> खाली शब्दकोश का प्रतिनिधित्व करने के लिए। | ||
* .NET फ्रेमवर्क जेनेरिक प्रदान करता है <code>[http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet]</code> | * .NET फ्रेमवर्क जेनेरिक प्रदान करता है <code>[http://msdn.microsoft.com/en-us/library/bb359438.aspx HashSet]</code> एवं <code>[http://msdn.microsoft.com/en-us/library/dd412070.aspx SortedSet]</code> कक्षाएं जो सामान्य को लागू करती हैं <code>[http://msdn.microsoft.com/en-us/library/dd412081.aspx ISet]</code> इंटरफेस। | ||
* स्मॉलटॉक की क्लास लाइब्रेरी में शामिल हैं <code>Set</code> | * स्मॉलटॉक की क्लास लाइब्रेरी में शामिल हैं <code>Set</code> एवं <code>IdentitySet</code>समावेशन परीक्षण के लिए क्रमशः समानता एवं पहचान का उपयोग करना। कई बोलियाँ संपीडित भंडारण के लिए भिन्नताएँ प्रदान करती हैं (<code>NumberSet</code>, <code>CharacterSet</code>), ऑर्डर करने के लिए (<code>OrderedSet</code>, <code>SortedSet</code>, आदि) या [[कमजोर संदर्भ]]ों के लिए (<code>WeakIdentitySet</code>). | ||
* [[रूबी (प्रोग्रामिंग भाषा)]] के मानक पुस्तकालय में शामिल है a <code>[http://ruby-doc.org/stdlib/libdoc/set/rdoc/index.html set]</code> मॉड्यूल जिसमें शामिल है <code>Set</code> | * [[रूबी (प्रोग्रामिंग भाषा)]] के मानक पुस्तकालय में शामिल है a <code>[http://ruby-doc.org/stdlib/libdoc/set/rdoc/index.html set]</code> मॉड्यूल जिसमें शामिल है <code>Set</code> एवं <code>SortedSet</code> कक्षाएं जो हैश टेबल का उपयोग करके उपसमुच्चय को लागू करती हैं, पश्चात वाले क्रमबद्ध क्रम में पुनरावृत्ति की अनुमति देते हैं। | ||
* [[OCaml]] की मानक लाइब्रेरी में a शामिल है <code>Set</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके एक कार्यात्मक | * [[OCaml]] की मानक लाइब्रेरी में a शामिल है <code>Set</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके एक कार्यात्मक उपसमुच्चय डेटा संरचना को लागू करता है। | ||
* [[हास्केल (प्रोग्रामिंग भाषा)]] का [[ग्लासगो हास्केल कंपाइलर]] कार्यान्वयन एक प्रदान करता है <code>[https://hackage.haskell.org/package/containers/docs/Data-Set.html Data.Set]</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके अपरिवर्तनीय | * [[हास्केल (प्रोग्रामिंग भाषा)]] का [[ग्लासगो हास्केल कंपाइलर]] कार्यान्वयन एक प्रदान करता है <code>[https://hackage.haskell.org/package/containers/docs/Data-Set.html Data.Set]</code> मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके अपरिवर्तनीय उपसमुच्चय को लागू करता है।<ref>Stephen Adams, [http://www.swiss.ai.mit.edu/~adams/BB "''Efficient sets: a balancing act''"], Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.</ref> | ||
* [[Tcl]] [[Tcllib]] पैकेज एक | * [[Tcl]] [[Tcllib]] पैकेज एक उपसमुच्चय मॉड्यूल प्रदान करता है जो TCL सूचियों के आधार पर एक उपसमुच्चय डेटा संरचना को लागू करता है। | ||
* [[ स्विफ्ट (प्रोग्रामिंग भाषा) ]] स्टैंडर्ड लाइब्रेरी में होता है a <code>Set</code> प्रकार, स्विफ्ट 1.2 के | * [[ स्विफ्ट (प्रोग्रामिंग भाषा) ]] स्टैंडर्ड लाइब्रेरी में होता है a <code>Set</code> प्रकार, स्विफ्ट 1.2 के पश्चात से। | ||
* [[जावास्क्रिप्ट]] पेश किया <code>[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set Set]</code> ईसीएमएस्क्रिप्ट 2015 के साथ एक मानक अंतर्निर्मित वस्तु के रूप में<ref>{{Cite web|url=http://www.ecma-international.org/ecma-262/6.0/#sec-set-objects|title=ECMAScript 2015 Language Specification – ECMA-262 6th Edition|website=www.ecma-international.org|language=en-GB|access-date=2017-07-11}}</ref> मानक। | * [[जावास्क्रिप्ट]] पेश किया <code>[https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set Set]</code> ईसीएमएस्क्रिप्ट 2015 के साथ एक मानक अंतर्निर्मित वस्तु के रूप में<ref>{{Cite web|url=http://www.ecma-international.org/ecma-262/6.0/#sec-set-objects|title=ECMAScript 2015 Language Specification – ECMA-262 6th Edition|website=www.ecma-international.org|language=en-GB|access-date=2017-07-11}}</ref> मानक। | ||
* [[Erlang (प्रोग्रामिंग भाषा)]] की मानक लाइब्रेरी में a <code>[http://erlang.org/doc/man/sets.html sets]</code> मापांक। | * [[Erlang (प्रोग्रामिंग भाषा)]] की मानक लाइब्रेरी में a <code>[http://erlang.org/doc/man/sets.html sets]</code> मापांक। | ||
* [[क्लोजर]] में हैशेड | * [[क्लोजर]] में हैशेड उपसमुच्चय के लिए शाब्दिक सिंटैक्स है, एवं सॉर्ट किए गए उपसमुच्चय को भी लागू करता है। | ||
* [[LabVIEW]] के पास संस्करण 2019 से | * [[LabVIEW]] के पास संस्करण 2019 से उपसमुच्चय के लिए मूल समर्थन है। | ||
* [[एडा (प्रोग्रामिंग भाषा)]] प्रदान करता है <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-8.html Ada.Containers.Hashed_Sets]</code> | * [[एडा (प्रोग्रामिंग भाषा)]] प्रदान करता है <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-8.html Ada.Containers.Hashed_Sets]</code> एवं <code>[http://www.ada-auth.org/standards/12rm/html/RM-A-18-9.html Ada.Containers.Ordered_Sets]</code> संकुल। | ||
जैसा कि पिछले खंड में उल्लेख किया गया है, उन भाषाओं में जो सीधे | जैसा कि पिछले खंड में उल्लेख किया गया है, उन भाषाओं में जो सीधे उपसमुच्चय का समर्थन नहीं करते हैं, लेकिन साहचर्य सरणियों का समर्थन करते हैं, तत्वों को कुंजियों के रूप में उपयोग करके, एवं मूल्यों के रूप में एक डमी मान का उपयोग करके उपसमुच्चय को साहचर्य सरणियों का उपयोग करके अनुकरण किया जा सकता है, जिन्हें अनदेखा किया जाता है। | ||
== | == मल्टीउपसमुच्चय == | ||
{{Main|Multiset}} | {{Main|Multiset}} | ||
एक | एक उपसमुच्चय की धारणा का एक सामान्यीकरण एक मल्टीउपसमुच्चय या बैग का है, जो एक उपसमुच्चय के समान है लेकिन बार-बार (बराबर) मान (डुप्लिकेट) की अनुमति देता है। इसका उपयोग दो अलग-अलग अर्थों में किया जाता है: या तो समान मानों को ''समान'' माना जाता है एवं उन्हें केवल गिना जाता है, या समान मानों को ''समतुल्य'' माना जाता है एवं अलग-अलग वस्तुओं के रूप में संग्रहीत किया जाता है। उदाहरण के लिए, लोगों की एक सूची (नाम से) एवं उम्र (वर्षों में) दी गई है, कोई भी उम्र के एक मल्टीउपसमुच्चय का निर्माण कर सकता है, जो कि किसी दिए गए उम्र के लोगों की संख्या की गणना करता है। वैकल्पिक रूप से, कोई लोगों का एक मल्टीउपसमुच्चय बना सकता है, जहां दो लोगों को समान माना जाता है यदि उनकी आयु समान है (लेकिन अलग-अलग लोग हो सकते हैं एवं अलग-अलग नाम हो सकते हैं), इस मामले में प्रत्येक जोड़ी (नाम, आयु) को संग्रहित किया जाना चाहिए, एवं चयन करना एक दी गई आयु पर एक दी गई आयु के सभी लोगों को देता है। | ||
औपचारिक रूप से, कंप्यूटर विज्ञान में वस्तुओं के लिए कुछ [[तुल्यता संबंध]] के तहत समान माना जाना संभव है लेकिन फिर भी एक अन्य संबंध के तहत अलग है। कुछ प्रकार के | औपचारिक रूप से, कंप्यूटर विज्ञान में वस्तुओं के लिए कुछ [[तुल्यता संबंध]] के तहत समान माना जाना संभव है लेकिन फिर भी एक अन्य संबंध के तहत अलग है। कुछ प्रकार के मल्टीउपसमुच्चय कार्यान्वयन अलग-अलग समान वस्तुओं को डेटा संरचना में अलग-अलग वस्तुओं के रूप में संग्रहीत करेंगे; जबकि अन्य इसे एक संस्करण (पहले वाले का सामना करना पड़ा) में संक्षिप्त कर देंगे एवं तत्व की बहुलता की एक सकारात्मक पूर्णांक गणना रखेंगे। | ||
उपसमुच्चय के साथ, मल्टीउपसमुच्चय स्वाभाविक रूप से हैश टेबल या पेड़ों का उपयोग करके कार्यान्वित किया जा सकता है, जो विभिन्न प्रदर्शन विशेषताओं को उत्पन्न करता है। | |||
टाइप टी पर सभी बैग का | टाइप टी पर सभी बैग का उपसमुच्चय एक्सप्रेशन बैग टी द्वारा दिया गया है। यदि मल्टीउपसमुच्चय द्वारा कोई समान वस्तुओं को समान मानता है एवं उन्हें आसानी से गिनता है, तो एक मल्टीउपसमुच्चय को इनपुट डोमेन से गैर-नकारात्मक पूर्णांक (प्राकृतिक) के फ़ंक्शन के रूप में व्याख्या किया जा सकता है संख्या), इसके सूचक समारोह के साथ एक उपसमुच्चय की पहचान को सामान्यीकृत करना। कुछ मामलों में इस गिनती के अर्थ में एक मल्टीउपसमुच्चय को नकारात्मक मूल्यों की अनुमति देने के लिए सामान्यीकृत किया जा सकता है, जैसा कि पायथन में है। | ||
* C++ की स्टैंडर्ड टेम्प्लेट लाइब्रेरी सॉर्ट किए गए | * C++ की स्टैंडर्ड टेम्प्लेट लाइब्रेरी सॉर्ट किए गए एवं अनसोर्टेड मल्टीउपसमुच्चय दोनों को लागू करती है। यह प्रदान करता है <code>[[Multiset (C++)|multiset]]</code> क्रमबद्ध मल्टीउपसमुच्चय के लिए क्लास, एक प्रकार के [[सहयोगी कंटेनर (सी ++)]] के रूप में, जो स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करके इस मल्टीउपसमुच्चय को लागू करता है। यह प्रदान करता है <code>unordered_multiset</code> [[अनियंत्रित सहयोगी कंटेनर (सी ++)]]C++) के एक प्रकार के रूप में अनसोर्टेड मल्टीउपसमुच्चय के लिए क्लास, जो हैश टेबल का उपयोग करके इस मल्टीउपसमुच्चय को लागू करता है। अनसोर्टेड मल्टीउपसमुच्चय C++11 के अनुसार मानक है; पहले SGI का STL प्रदान करता है <code>hash_multiset</code> क्लास, जिसे कॉपी किया गया एवं अंततः मानकीकृत किया गया। | ||
* जावा (प्रोग्रामिंग भाषा) के लिए, तृतीय-पक्ष पुस्तकालय | * जावा (प्रोग्रामिंग भाषा) के लिए, तृतीय-पक्ष पुस्तकालय मल्टीउपसमुच्चय कार्यक्षमता प्रदान करते हैं: | ||
** [[अपाचे कॉमन्स]] कलेक्शंस प्रदान करता है <code>[https://web.archive.org/web/20150109083430/https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Bag.html Bag]</code> | ** [[अपाचे कॉमन्स]] कलेक्शंस प्रदान करता है <code>[https://web.archive.org/web/20150109083430/https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Bag.html Bag]</code> एवं <code>SortedBag</code> इंटरफेस, जैसे कक्षाओं को लागू करने के साथ <code>HashBag</code> एवं <code>TreeBag</code>. | ||
** Google अमरूद प्रदान करता है <code>[https://google.github.io/guava/releases/20.0/api/docs/com/google/common/collect/Multiset.html Multiset]</code> इंटरफ़ेस, जैसे कक्षाओं को लागू करने के साथ <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/HashMultiset.html HashMultiset]</code> | ** Google अमरूद प्रदान करता है <code>[https://google.github.io/guava/releases/20.0/api/docs/com/google/common/collect/Multiset.html Multiset]</code> इंटरफ़ेस, जैसे कक्षाओं को लागू करने के साथ <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/HashMultiset.html HashMultiset]</code> एवं <code>[https://guava.dev/releases/20.0/api/docs/com/google/common/collect/TreeMultiset.html TreeMultiset]</code>. | ||
* सेब प्रदान करता है <code>[https://developer.apple.com/documentation/foundation/nscountedset NSCountedSet]</code> कोको (एपीआई) के हिस्से के रूप में क्लास, | * सेब प्रदान करता है <code>[https://developer.apple.com/documentation/foundation/nscountedset NSCountedSet]</code> कोको (एपीआई) के हिस्से के रूप में क्लास, एवं <code>[https://developer.apple.com/documentation/corefoundation/cfbag-s1l CFBag]</code> एवं <code>[https://developer.apple.com/documentation/corefoundation/cfmutablebag-rqn CFMutableBag]</code> CoreFoundation के हिस्से के रूप में प्रकार। | ||
* पायथन (प्रोग्रामिंग भाषा)|पायथन के मानक पुस्तकालय में शामिल हैं <code>[https://docs.python.org/library/collections.html#collections.Counter collections.Counter]</code>, जो एक | * पायथन (प्रोग्रामिंग भाषा)|पायथन के मानक पुस्तकालय में शामिल हैं <code>[https://docs.python.org/library/collections.html#collections.Counter collections.Counter]</code>, जो एक मल्टीउपसमुच्चय के समान है। | ||
* स्मॉलटाक में शामिल हैं <code>Bag</code> वर्ग, जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है। | * स्मॉलटाक में शामिल हैं <code>Bag</code> वर्ग, जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है। | ||
जहां एक | जहां एक मल्टीउपसमुच्चय डेटा संरचना उपलब्ध नहीं है, एक नियमित उपसमुच्चय का उपयोग करने के लिए एक वर्कअराउंड है, लेकिन अलग-अलग वस्तुओं पर हमेशा समान नहीं होने के लिए समानता की भविष्यवाणी को ओवरराइड करता है (हालांकि, यह अभी भी उसी की कई घटनाओं को स्टोर करने में सक्षम नहीं होगा ऑब्जेक्ट) या उनके पूर्णांक गुणकों के मानों को मैप करने के लिए एक साहचर्य सरणी का उपयोग करें (यह समान तत्वों के बीच अंतर करने में सक्षम नहीं होगा)। | ||
बैग पर विशिष्ट संचालन: | बैग पर विशिष्ट संचालन: | ||
Line 129: | Line 128: | ||
* <code>union(''B''<sub>1</sub>, ''B''<sub>2</sub>)</code>: एक बैग देता है जिसमें केवल वे मान होते हैं जो बैग बी में होते हैं<sub>1</sub> या बैग बी<sub>2</sub>, सिवाय इसके कि परिणामस्वरूप बैग में मूल्य x की संख्या बराबर होती है (बी<sub>1</sub> # एक्स) + (बी<sub>2</sub> # एक्स); कभी-कभी बी के रूप में दर्शाया जाता है<sub>1</sub> ⊎ बी<sub>2</sub>. | * <code>union(''B''<sub>1</sub>, ''B''<sub>2</sub>)</code>: एक बैग देता है जिसमें केवल वे मान होते हैं जो बैग बी में होते हैं<sub>1</sub> या बैग बी<sub>2</sub>, सिवाय इसके कि परिणामस्वरूप बैग में मूल्य x की संख्या बराबर होती है (बी<sub>1</sub> # एक्स) + (बी<sub>2</sub> # एक्स); कभी-कभी बी के रूप में दर्शाया जाता है<sub>1</sub> ⊎ बी<sub>2</sub>. | ||
=== SQL === में | === SQL === में मल्टीउपसमुच्चय | ||
[[संबंधपरक डेटाबेस प्रबंधन प्रणाली]] में, एक तालिका एक (गणितीय) | [[संबंधपरक डेटाबेस प्रबंधन प्रणाली]] में, एक तालिका एक (गणितीय) उपसमुच्चय या एक मल्टीउपसमुच्चय हो सकती है, जो कुछ स्तंभों पर एकता की कमी की उपस्थिति पर निर्भर करता है (जो इसे एक [[उम्मीदवार कुंजी]] में बदल देता है)। | ||
[[एसक्यूएल]] एक रिलेशनल टेबल से पंक्तियों के चयन की अनुमति देता है: यह ऑपरेशन सामान्य रूप से एक | [[एसक्यूएल]] एक रिलेशनल टेबल से पंक्तियों के चयन की अनुमति देता है: यह ऑपरेशन सामान्य रूप से एक मल्टीउपसमुच्चय उत्पन्न करेगा, जब तक कि कीवर्ड <code>DISTINCT</code> पंक्तियों को सभी अलग-अलग होने के लिए मजबूर करने के लिए प्रयोग किया जाता है, या चयन में प्राथमिक (या उम्मीदवार) कुंजी शामिल होती है। | ||
एसक्यूएल # मानकीकरण इतिहास में <code>MULTISET</code> उप-क्वेरी को संग्रह अभिव्यक्ति में बदलने के लिए कीवर्ड का उपयोग किया जा सकता है: | एसक्यूएल # मानकीकरण इतिहास में <code>MULTISET</code> उप-क्वेरी को संग्रह अभिव्यक्ति में बदलने के लिए कीवर्ड का उपयोग किया जा सकता है: | ||
Line 144: | Line 143: | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[ब्लूम फिल्टर]] | * [[ब्लूम फिल्टर]] | ||
* [[विसंधित सेट (डेटा संरचना)]] | * [[विसंधित सेट (डेटा संरचना)|विसंधित उपसमुच्चय (डेटा संरचना)]] | ||
* [[सेट (गणित)]] | * [[सेट (गणित)|उपसमुच्चय (गणित)]] | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== |
Revision as of 13:17, 18 May 2023
भारत कंप्यूटर विज्ञान, उपसमुच्चय सार डेटा प्रकार है जो बिना किसी विशेष क्रम के अद्वितीय मूल्यों को संग्रहीत कर सकता है। यह परिमित समुच्चय की गणित अवधारणा का कंप्यूटर कार्यान्वयन है। अधिकांश अन्य संग्रह (सार डेटा प्रकार) प्रकारों के विपरीत, उपसमुच्चय से विशिष्ट तत्व को पुनः प्राप्त करने के अतिरिक्त, सामान्यतः उपसमुच्चय में सदस्यता के लिए मूल्य का परीक्षण किया जाता है।
कुछ उपसमुच्चय डेटा संरचनाएं स्थिर या एकत्रित उपसमुच्चय के लिए चित्रित किए गए हैं जो उनके निर्माण के पश्चात परिवर्तित नहीं होते हैं। स्थिर उपसमुच्चय स्वयं तत्वों पर केवल क्वेरी संचालन की अनुमति देते हैं - जैसे कि यह देखना कि क्या दिया गया मान उपसमुच्चय में है, या कुछ मनमाना क्रम में मानों की गणना करना अन्य वेरिएंट, जिन्हें डायनेमिक या म्यूटेबल उपसमुच्चय कहा जाता है, उपसमुच्चय से तत्वों को सम्मिलित करने एवं विस्थापित करने की भी अनुमति देते हैं।
बहुसमुच्चय विशेष प्रकार का उपसमुच्चय है, जिसमें तत्व उपसमुच्चय में कई बार दिखाई दे सकता है।
प्रकार सिद्धांत
प्रकार सिद्धांत में, उपसमुच्चय सामान्यतः उनके संकेतक फ़ंक्शन (विशेषता समारोह) के साथ पहचाने जाते हैं: तदनुसार, प्रकार के मूल्यों का एक उपसमुच्चय द्वारा दर्शाया जा सकता है या . (उपप्रकार एवं उपसमुच्चय को शोधन प्रकारों द्वारा प्रतिरूपित किया जा सकता है, एवं भागफल उपसमुच्चय को उपसमुच्चयोइड्स द्वारा प्रतिस्थापित किया जा सकता है।) विशेषता कार्य एक उपसमुच्चय का परिभाषित किया जाता है:
सिद्धांत रूप में, कई अन्य अमूर्त डेटा संरचनाओं को मानक संचालन पर लगाए गए अतिरिक्त संचालन एवं/या अतिरिक्त सिद्धांतों के साथ उपसमुच्चय संरचनाओं के रूप में देखा जा सकता है। उदाहरण के लिए, एक अमूर्त हीप डेटा संरचना को एक उपसमुच्चय संरचना के रूप में देखा जा सकता है min(S)
ऑपरेशन जो सबसे छोटे मूल्य का तत्व लौटाता है।
संचालन
कोर उपसमुच्चय-सैद्धांतिक संचालन
कोई उपसमुच्चय के बीजगणित के संचालन को परिभाषित कर सकता है:
union(S,T)
: समुच्चय S एवं T का संघ (उपसमुच्चय सिद्धांत) लौटाता है।intersection(S,T)
: समुच्चय S एवं T का प्रतिच्छेदन (उपसमुच्चय सिद्धांत) लौटाता है।difference(S,T)
: समुच्चय S एवं T का अंतर (उपसमुच्चय सिद्धांत) लौटाता है।subset(S,T)
: एक विधेय जो परीक्षण करता है कि क्या समुच्चय S, समुच्चय T का उपसमुच्चय है।
स्थैतिक उपसमुच्चय
स्टैटिक उपसमुच्चय स्ट्रक्चर S द्वारा प्रदान किए जा सकने वाले विशिष्ट ऑपरेशन हैं:
is_element_of(x,S)
: जाँचता है कि क्या मान x उपसमुच्चय S में है।is_empty(S)
: जांचता है कि उपसमुच्चय एस खाली है या नहीं।size(S)
याcardinality(S)
: एस में तत्वों की संख्या लौटाता है।iterate(S)
: एक ऐसा फ़ंक्शन लौटाता है जो प्रत्येक कॉल पर S का एक एवं मान देता है, कुछ मनमाना क्रम में।enumerate(S)
: कुछ मनमानी क्रम में एस के तत्वों वाली एक सूची देता है।build(x1,x2,…,xn,)
: मान x के साथ एक उपसमुच्चय संरचना बनाता है1,एक्स2,...,एक्सn.create_from(collection)
: दिए गए संग्रह के सभी तत्वों (सार डेटा प्रकार) या दिए गए पुनरावर्तक द्वारा लौटाए गए सभी तत्वों वाली एक नई उपसमुच्चय संरचना बनाता है।
गतिशील उपसमुच्चय
गतिशील उपसमुच्चय संरचनाएं सामान्यतः जोड़ती हैं:
create()
: एक नया, प्रारंभ में खाली उपसमुच्चय संरचना बनाता है।create_with_capacity(n)
: एक नई उपसमुच्चय संरचना बनाता है, प्रारंभ में खाली लेकिन n तत्वों तक धारण करने में सक्षम।
add(S,x)
: तत्व x को S में जोड़ता है, यदि यह पहले से मौजूद नहीं है।remove(S, x)
: तत्व x को S से हटाता है, यदि यह मौजूद है।capacity(S)
: S द्वारा धारण किए जा सकने वाले मानों की अधिकतम संख्या लौटाता है।
कुछ उपसमुच्चय संरचनाएं इनमें से केवल कुछ परिचालनों की अनुमति दे सकती हैं। प्रत्येक ऑपरेशन की लागत कार्यान्वयन पर निर्भर करेगी, एवं संभवतः उपसमुच्चय में संग्रहीत विशेष मूल्यों पर भी, एवं जिस क्रम में उन्हें सम्मिलित किया गया है।
अतिरिक्त संचालन
ऐसे कई अन्य ऑपरेशन हैं जिन्हें (सिद्धांत रूप में) उपरोक्त के संदर्भ में परिभाषित किया जा सकता है, जैसे:
pop(S)
: एस का एक मनमाना तत्व लौटाता है, इसे एस से हटा देता है।[1]pick(S)
: S का मनमाना तत्व लौटाता है।[2][3][4] कार्यात्मक रूप से, उत्परिवर्तीpop
चयनकर्ताओं की जोड़ी के रूप में व्याख्या की जा सकती है(pick, rest),
कहाँrest
मनमाने तत्व को छोड़कर सभी तत्वों से युक्त उपसमुच्चय लौटाता है।[5] के रूप में समझा जा सकता हैiterate
.[lower-alpha 1]map(F,S)
: फ़ंक्शन F को S के प्रत्येक तत्व पर लागू करने के परिणामस्वरूप भिन्न मानों का उपसमुच्चय लौटाता है।filter(P,S)
: एस के सभी तत्वों से युक्त सबउपसमुच्चय लौटाता है जो किसी दिए गए विधेय (गणितीय तर्क) पी को संतुष्ट करता है।fold(A0,F,S)
: मान A लौटाता है|S| आवेदन करने के पश्चातAi+1 := F(Ai, e)
एस के प्रत्येक तत्व ई के लिए, कुछ बाइनरी ऑपरेशन एफ के लिए। एफ को अच्छी तरह से परिभाषित करने के लिए सहयोगी एवं कम्यूटेटिव होना चाहिए।clear(S)
: एस के सभी तत्वों को हटा दें।equal(S1', S2')
: जांचता है कि क्या दिए गए दो उपसमुच्चय समान हैं (अर्थात सभी एवं केवल समान तत्व शामिल हैं)।hash(S)
: स्थिर उपसमुच्चय S के लिए एक हैश मान लौटाता है जैसे कि ifequal(S1, S2)
तबhash(S1) = hash(S2)
अन्य कार्यों को एक विशेष प्रकार के तत्वों वाले उपसमुच्चय के लिए परिभाषित किया जा सकता है:
sum(S)
: योग की कुछ परिभाषा के लिए S के सभी तत्वों का योग लौटाता है। उदाहरण के लिए, पूर्णांक या वास्तविक से अधिक, इसे इस रूप में परिभाषित किया जा सकता हैfold(0, add, S)
.collapse(S)
: उपसमुच्चय का एक उपसमुच्चय दिया गया है, संघ वापस करें।[6] उदाहरण के लिए,collapse({{1}, {2, 3}}) == {1, 2, 3}
. प्रकार का माना जा सकता हैsum
.flatten(S)
: उपसमुच्चय एवं परमाणु तत्वों (तत्व जो उपसमुच्चय नहीं हैं) से मिलकर एक उपसमुच्चय दिया गया है, एक उपसमुच्चय देता है जिसके तत्व मूल शीर्ष-स्तरीय उपसमुच्चय के परमाणु तत्व या उपसमुच्चय के तत्व होते हैं। दूसरे शब्दों में, नेस्टिंग के स्तर को हटा दें - जैसेcollapse,
लेकिन परमाणुओं की अनुमति दें। यह एक बार किया जा सकता है, या केवल परमाणु तत्वों का एक उपसमुच्चय प्राप्त करने के लिए पुनरावर्ती चपटा किया जा सकता है।[7] उदाहरण के लिए,flatten({1, {2, 3}}) == {1, 2, 3}
.nearest(S,x)
: एस का तत्व लौटाता है जो एक्स के मूल्य में निकटतम है (कुछ मीट्रिक (गणित) द्वारा)।min(S)
,max(S)
: S का न्यूनतम/अधिकतम तत्व लौटाता है।
कार्यान्वयन
विभिन्न डेटा संरचनाओं का उपयोग करके उपसमुच्चय को लागू किया जा सकता है, जो विभिन्न कार्यों के लिए अलग-अलग समय एवं स्थान का समझौता प्रदान करते हैं। कुछ कार्यान्वयन बहुत विशिष्ट संचालन की दक्षता में सुधार के लिए डिज़ाइन किए गए हैं, जैसे nearest
या union
. सामान्य उपयोग के रूप में वर्णित कार्यान्वयन आम तौर पर अनुकूलित करने का प्रयास करते हैं element_of
, add
, एवं delete
संचालन। एक सरल कार्यान्वयन एक सूची (सार डेटा प्रकार) का उपयोग करना है, तत्वों के क्रम की अनदेखी करना एवं बार-बार मूल्यों से बचने के लिए ध्यान रखना। यह सरल लेकिन अक्षम है, क्योंकि उपसमुच्चय सदस्यता या तत्व विलोपन जैसे ऑपरेशन ओ (एन) हैं, क्योंकि उन्हें पूरी सूची को स्कैन करने की आवश्यकता होती है।[lower-alpha 2] उपसमुच्चय को अक्सर अधिक कुशल डेटा संरचनाओं का उपयोग करके कार्यान्वित किया जाता है, विशेष रूप से ट्री (डेटा संरचना), कोशिशों, या हैश टेबल के विभिन्न स्वाद।
जैसा कि उपसमुच्चय को एक प्रकार के मानचित्र (संकेतक फ़ंक्शन द्वारा) के रूप में व्याख्या किया जा सकता है, उपसमुच्चय सामान्यतः उसी तरह (आंशिक) मानचित्र (सहयोगी सरणियाँ) में लागू होते हैं - इस मामले में जिसमें प्रत्येक कुंजी-मूल्य जोड़ी का मान होता है इकाई प्रकार या एक प्रहरी मान (जैसे 1) - अर्थात्, क्रमबद्ध उपसमुच्चयों के लिए एक स्व-संतुलन बाइनरी खोज वृक्ष[definition needed] (जिसमें अधिकांश ऑपरेशनों के लिए O(log n) है), या अनसोल्ड उपसमुच्चय के लिए एक हैश टेबल (जिसमें O(1) औसत-केस है, लेकिन O(n) सबसे खराब-केस, अधिकांश ऑपरेशनों के लिए)। एक क्रमबद्ध रैखिक हैश तालिका[8] नियतात्मक रूप से आदेशित उपसमुच्चय प्रदान करने के लिए उपयोग किया जा सकता है।
इसके अलावा, उन भाषाओं में जो नक्शों का समर्थन करती हैं लेकिन उपसमुच्चय का नहीं, उपसमुच्चय को नक्शों के संदर्भ में लागू किया जा सकता है। उदाहरण के लिए, पर्ल में एक सामान्य प्रोग्रामिंग मुहावरा जो एक सरणी को एक हैश में परिवर्तित करता है जिसका मूल्य प्रहरी मान 1 है, एक उपसमुच्चय के रूप में उपयोग के लिए:
my %elements = map { $_ => 1 } @elements;
अन्य लोकप्रिय विधियों में सरणी डेटा संरचना शामिल है। विशेष रूप से पूर्णांक 1..n का एक सबउपसमुच्चय एन-बिट बिट सरणी के रूप में कुशलतापूर्वक कार्यान्वित किया जा सकता है, जो बहुत ही कुशल संघ एवं चौराहे के संचालन का भी समर्थन करता है। एक ब्लूम नक्शा एक बहुत ही कॉम्पैक्ट प्रतिनिधित्व का उपयोग करते हुए संभावित रूप से एक उपसमुच्चय को लागू करता है, लेकिन प्रश्नों पर झूठी सकारात्मकता की एक छोटी सी संभावना को जोखिम में डालता है।
बूलियन उपसमुच्चय ऑपरेशंस को अधिक प्राथमिक ऑपरेशंस के संदर्भ में कार्यान्वित किया जा सकता है (pop
, clear
, एवं add
), लेकिन विशेष एल्गोरिदम कम स्पर्शोन्मुख समय सीमा उत्पन्न कर सकते हैं। यदि उपसमुच्चय को सॉर्ट की गई सूचियों के रूप में कार्यान्वित किया जाता है, उदाहरण के लिए, भोली एल्गोरिथ्म के लिए union(S,T)
S की लंबाई m गुणा T की लंबाई n के अनुपात में समय लगेगा; जबकि मर्ज एल्गोरिथम का एक संस्करण m+n के आनुपातिक समय में काम करेगा। इसके अलावा, विशेष उपसमुच्चय डेटा संरचनाएं हैं (जैसे कि संघ-खोज एल्गोरिथ्म | यूनियन-फाइंड डेटा स्ट्रक्चर) जो दूसरों की कीमत पर इनमें से एक या अधिक ऑपरेशन के लिए अनुकूलित हैं।
भाषा समर्थन
पास्कल प्रोग्रामिंग भाषा उपसमुच्चय का समर्थन करने वाली शुरुआती भाषाओं में से एक थी; कई भाषाओं में अब यह शामिल है, चाहे मूल भाषा में हो या किसी मानक पुस्तकालय में।
- C++ में, मानक टेम्पलेट लाइब्रेरी (STL) प्रदान करती है
set
टेम्प्लेट क्लास, जिसे सामान्यतः एक बाइनरी सर्च ट्री (जैसे लाल-काले पेड़) का उपयोग करके लागू किया जाता है; सिलिकॉन ग्राफिक्स इंटरनेशनल का एसटीएल भी प्रदान करता हैhash_set
टेम्प्लेट क्लास, जो हैश टेबल का उपयोग करके एक उपसमुच्चय को लागू करता है। C++11 के लिए समर्थन हैunordered_set
टेम्प्लेट क्लास, जिसे हैश टेबल का उपयोग करके कार्यान्वित किया जाता है। उपसमुच्चय में, तत्व स्वयं कुंजी हैं, अनुक्रमित कंटेनरों के विपरीत, जहां तत्वों को उनकी (सापेक्ष या पूर्ण) स्थिति का उपयोग करके एक्सेस किया जाता है। उपसमुच्चय तत्वों में सख्त कमजोर क्रम होना चाहिए। - रस्ट (प्रोग्रामिंग भाषा) मानक पुस्तकालय सामान्य प्रदान करता है
HashSet
एवंBTreeSet
प्रकार। - जावा (प्रोग्रामिंग भाषा) प्रदान करता है
Set
इंटरफ़ेस (कंप्यूटर विज्ञान) उपसमुच्चय का समर्थन करने के लिए (HashSet
वर्ग इसे हैश तालिका का उपयोग करके कार्यान्वित करता है), एवंSortedSet
सॉर्ट किए गए उपसमुच्चयों का समर्थन करने के लिए उप-इंटरफ़ेस (TreeSet
वर्ग इसे बाइनरी सर्च ट्री का उपयोग करके कार्यान्वित करता है)। - ऐप्पल इंक की फाउंडेशन किट (कोको (एपीआई) का हिस्सा) उद्देश्य सी क्लास प्रदान करती है
NSSet
,NSMutableSet
,NSCountedSet
,NSOrderedSet
, एवंNSMutableOrderedSet
. CoreFoundation API इनके लिए CFSet एवं CFMutableSet प्रकार प्रदान करता है। सी (प्रोग्रामिंग भाषा) में उपयोग करें। - पायथन (प्रोग्रामिंग भाषा) में अंतर्निहित है
set
एवंfrozenset
प्रकार 2.4 के पश्चात से, एवं पायथन 3.0 एवं 2.7 के पश्चात से, कर्ली-ब्रैकेट सिंटैक्स का उपयोग करके गैर-खाली उपसमुच्चय शाब्दिक का समर्थन करता है, जैसे:{x, y, z}
; खाली उपसमुच्चय का उपयोग करके बनाया जाना चाहिएset()
, क्योंकि पायथन उपयोग करता है{}
खाली शब्दकोश का प्रतिनिधित्व करने के लिए। - .NET फ्रेमवर्क जेनेरिक प्रदान करता है
HashSet
एवंSortedSet
कक्षाएं जो सामान्य को लागू करती हैंISet
इंटरफेस। - स्मॉलटॉक की क्लास लाइब्रेरी में शामिल हैं
Set
एवंIdentitySet
समावेशन परीक्षण के लिए क्रमशः समानता एवं पहचान का उपयोग करना। कई बोलियाँ संपीडित भंडारण के लिए भिन्नताएँ प्रदान करती हैं (NumberSet
,CharacterSet
), ऑर्डर करने के लिए (OrderedSet
,SortedSet
, आदि) या कमजोर संदर्भों के लिए (WeakIdentitySet
). - रूबी (प्रोग्रामिंग भाषा) के मानक पुस्तकालय में शामिल है a
set
मॉड्यूल जिसमें शामिल हैSet
एवंSortedSet
कक्षाएं जो हैश टेबल का उपयोग करके उपसमुच्चय को लागू करती हैं, पश्चात वाले क्रमबद्ध क्रम में पुनरावृत्ति की अनुमति देते हैं। - OCaml की मानक लाइब्रेरी में a शामिल है
Set
मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके एक कार्यात्मक उपसमुच्चय डेटा संरचना को लागू करता है। - हास्केल (प्रोग्रामिंग भाषा) का ग्लासगो हास्केल कंपाइलर कार्यान्वयन एक प्रदान करता है
Data.Set
मॉड्यूल, जो बाइनरी सर्च ट्री का उपयोग करके अपरिवर्तनीय उपसमुच्चय को लागू करता है।[9] - Tcl Tcllib पैकेज एक उपसमुच्चय मॉड्यूल प्रदान करता है जो TCL सूचियों के आधार पर एक उपसमुच्चय डेटा संरचना को लागू करता है।
- स्विफ्ट (प्रोग्रामिंग भाषा) स्टैंडर्ड लाइब्रेरी में होता है a
Set
प्रकार, स्विफ्ट 1.2 के पश्चात से। - जावास्क्रिप्ट पेश किया
Set
ईसीएमएस्क्रिप्ट 2015 के साथ एक मानक अंतर्निर्मित वस्तु के रूप में[10] मानक। - Erlang (प्रोग्रामिंग भाषा) की मानक लाइब्रेरी में a
sets
मापांक। - क्लोजर में हैशेड उपसमुच्चय के लिए शाब्दिक सिंटैक्स है, एवं सॉर्ट किए गए उपसमुच्चय को भी लागू करता है।
- LabVIEW के पास संस्करण 2019 से उपसमुच्चय के लिए मूल समर्थन है।
- एडा (प्रोग्रामिंग भाषा) प्रदान करता है
Ada.Containers.Hashed_Sets
एवंAda.Containers.Ordered_Sets
संकुल।
जैसा कि पिछले खंड में उल्लेख किया गया है, उन भाषाओं में जो सीधे उपसमुच्चय का समर्थन नहीं करते हैं, लेकिन साहचर्य सरणियों का समर्थन करते हैं, तत्वों को कुंजियों के रूप में उपयोग करके, एवं मूल्यों के रूप में एक डमी मान का उपयोग करके उपसमुच्चय को साहचर्य सरणियों का उपयोग करके अनुकरण किया जा सकता है, जिन्हें अनदेखा किया जाता है।
मल्टीउपसमुच्चय
एक उपसमुच्चय की धारणा का एक सामान्यीकरण एक मल्टीउपसमुच्चय या बैग का है, जो एक उपसमुच्चय के समान है लेकिन बार-बार (बराबर) मान (डुप्लिकेट) की अनुमति देता है। इसका उपयोग दो अलग-अलग अर्थों में किया जाता है: या तो समान मानों को समान माना जाता है एवं उन्हें केवल गिना जाता है, या समान मानों को समतुल्य माना जाता है एवं अलग-अलग वस्तुओं के रूप में संग्रहीत किया जाता है। उदाहरण के लिए, लोगों की एक सूची (नाम से) एवं उम्र (वर्षों में) दी गई है, कोई भी उम्र के एक मल्टीउपसमुच्चय का निर्माण कर सकता है, जो कि किसी दिए गए उम्र के लोगों की संख्या की गणना करता है। वैकल्पिक रूप से, कोई लोगों का एक मल्टीउपसमुच्चय बना सकता है, जहां दो लोगों को समान माना जाता है यदि उनकी आयु समान है (लेकिन अलग-अलग लोग हो सकते हैं एवं अलग-अलग नाम हो सकते हैं), इस मामले में प्रत्येक जोड़ी (नाम, आयु) को संग्रहित किया जाना चाहिए, एवं चयन करना एक दी गई आयु पर एक दी गई आयु के सभी लोगों को देता है।
औपचारिक रूप से, कंप्यूटर विज्ञान में वस्तुओं के लिए कुछ तुल्यता संबंध के तहत समान माना जाना संभव है लेकिन फिर भी एक अन्य संबंध के तहत अलग है। कुछ प्रकार के मल्टीउपसमुच्चय कार्यान्वयन अलग-अलग समान वस्तुओं को डेटा संरचना में अलग-अलग वस्तुओं के रूप में संग्रहीत करेंगे; जबकि अन्य इसे एक संस्करण (पहले वाले का सामना करना पड़ा) में संक्षिप्त कर देंगे एवं तत्व की बहुलता की एक सकारात्मक पूर्णांक गणना रखेंगे।
उपसमुच्चय के साथ, मल्टीउपसमुच्चय स्वाभाविक रूप से हैश टेबल या पेड़ों का उपयोग करके कार्यान्वित किया जा सकता है, जो विभिन्न प्रदर्शन विशेषताओं को उत्पन्न करता है।
टाइप टी पर सभी बैग का उपसमुच्चय एक्सप्रेशन बैग टी द्वारा दिया गया है। यदि मल्टीउपसमुच्चय द्वारा कोई समान वस्तुओं को समान मानता है एवं उन्हें आसानी से गिनता है, तो एक मल्टीउपसमुच्चय को इनपुट डोमेन से गैर-नकारात्मक पूर्णांक (प्राकृतिक) के फ़ंक्शन के रूप में व्याख्या किया जा सकता है संख्या), इसके सूचक समारोह के साथ एक उपसमुच्चय की पहचान को सामान्यीकृत करना। कुछ मामलों में इस गिनती के अर्थ में एक मल्टीउपसमुच्चय को नकारात्मक मूल्यों की अनुमति देने के लिए सामान्यीकृत किया जा सकता है, जैसा कि पायथन में है।
- C++ की स्टैंडर्ड टेम्प्लेट लाइब्रेरी सॉर्ट किए गए एवं अनसोर्टेड मल्टीउपसमुच्चय दोनों को लागू करती है। यह प्रदान करता है
multiset
क्रमबद्ध मल्टीउपसमुच्चय के लिए क्लास, एक प्रकार के सहयोगी कंटेनर (सी ++) के रूप में, जो स्व-संतुलन बाइनरी सर्च ट्री का उपयोग करके इस मल्टीउपसमुच्चय को लागू करता है। यह प्रदान करता हैunordered_multiset
अनियंत्रित सहयोगी कंटेनर (सी ++)C++) के एक प्रकार के रूप में अनसोर्टेड मल्टीउपसमुच्चय के लिए क्लास, जो हैश टेबल का उपयोग करके इस मल्टीउपसमुच्चय को लागू करता है। अनसोर्टेड मल्टीउपसमुच्चय C++11 के अनुसार मानक है; पहले SGI का STL प्रदान करता हैhash_multiset
क्लास, जिसे कॉपी किया गया एवं अंततः मानकीकृत किया गया। - जावा (प्रोग्रामिंग भाषा) के लिए, तृतीय-पक्ष पुस्तकालय मल्टीउपसमुच्चय कार्यक्षमता प्रदान करते हैं:
- अपाचे कॉमन्स कलेक्शंस प्रदान करता है
Bag
एवंSortedBag
इंटरफेस, जैसे कक्षाओं को लागू करने के साथHashBag
एवंTreeBag
. - Google अमरूद प्रदान करता है
Multiset
इंटरफ़ेस, जैसे कक्षाओं को लागू करने के साथHashMultiset
एवंTreeMultiset
.
- अपाचे कॉमन्स कलेक्शंस प्रदान करता है
- सेब प्रदान करता है
NSCountedSet
कोको (एपीआई) के हिस्से के रूप में क्लास, एवंCFBag
एवंCFMutableBag
CoreFoundation के हिस्से के रूप में प्रकार। - पायथन (प्रोग्रामिंग भाषा)|पायथन के मानक पुस्तकालय में शामिल हैं
collections.Counter
, जो एक मल्टीउपसमुच्चय के समान है। - स्मॉलटाक में शामिल हैं
Bag
वर्ग, जिसे समावेशन परीक्षण के लिए विधेय के रूप में या तो पहचान या समानता का उपयोग करने के लिए तत्काल किया जा सकता है।
जहां एक मल्टीउपसमुच्चय डेटा संरचना उपलब्ध नहीं है, एक नियमित उपसमुच्चय का उपयोग करने के लिए एक वर्कअराउंड है, लेकिन अलग-अलग वस्तुओं पर हमेशा समान नहीं होने के लिए समानता की भविष्यवाणी को ओवरराइड करता है (हालांकि, यह अभी भी उसी की कई घटनाओं को स्टोर करने में सक्षम नहीं होगा ऑब्जेक्ट) या उनके पूर्णांक गुणकों के मानों को मैप करने के लिए एक साहचर्य सरणी का उपयोग करें (यह समान तत्वों के बीच अंतर करने में सक्षम नहीं होगा)।
बैग पर विशिष्ट संचालन:
contains(B, x)
: जांचता है कि बैग बी में तत्व एक्स मौजूद है (कम से कम एक बार)।is_sub_bag(B1, B2)
: जांचता है कि बैग बी में प्रत्येक तत्व है या नहीं1 बी में होता है1 बैग बी में होने की तुलना में अधिक बार नहीं2; कभी-कभी बी के रूप में दर्शाया जाता है1 ⊑ बी2.count(B, x)
: तत्व x के बैग B में होने की संख्या लौटाता है; कभी-कभी बी # एक्स के रूप में दर्शाया जाता है।scaled_by(B, n)
: एक प्राकृतिक संख्या n दिया गया है, एक बैग लौटाता है जिसमें बैग बी के समान तत्व होते हैं, सिवाय इसके कि प्रत्येक तत्व जो बी में एम बार होता है परिणामी बैग में एन * एम बार होता है; कभी-कभी n ⊗ B के रूप में निरूपित किया जाता है।union(B1, B2)
: एक बैग देता है जिसमें केवल वे मान होते हैं जो बैग बी में होते हैं1 या बैग बी2, सिवाय इसके कि परिणामस्वरूप बैग में मूल्य x की संख्या बराबर होती है (बी1 # एक्स) + (बी2 # एक्स); कभी-कभी बी के रूप में दर्शाया जाता है1 ⊎ बी2.
=== SQL === में मल्टीउपसमुच्चय संबंधपरक डेटाबेस प्रबंधन प्रणाली में, एक तालिका एक (गणितीय) उपसमुच्चय या एक मल्टीउपसमुच्चय हो सकती है, जो कुछ स्तंभों पर एकता की कमी की उपस्थिति पर निर्भर करता है (जो इसे एक उम्मीदवार कुंजी में बदल देता है)।
एसक्यूएल एक रिलेशनल टेबल से पंक्तियों के चयन की अनुमति देता है: यह ऑपरेशन सामान्य रूप से एक मल्टीउपसमुच्चय उत्पन्न करेगा, जब तक कि कीवर्ड DISTINCT
पंक्तियों को सभी अलग-अलग होने के लिए मजबूर करने के लिए प्रयोग किया जाता है, या चयन में प्राथमिक (या उम्मीदवार) कुंजी शामिल होती है।
एसक्यूएल # मानकीकरण इतिहास में MULTISET
उप-क्वेरी को संग्रह अभिव्यक्ति में बदलने के लिए कीवर्ड का उपयोग किया जा सकता है:
SELECT expression1, expression2... FROM table_name...
एक सामान्य चयन है जिसका उपयोग किसी अन्य सामान्य क्वेरी की सबक्वेरी अभिव्यक्ति के रूप में किया जा सकता है, जबकि
MULTISET(SELECT expression1, expression2... FROM table_name...)
सबक्वायरी को एक संग्रह अभिव्यक्ति में बदल देता है जिसका उपयोग किसी अन्य क्वेरी में या उचित संग्रह प्रकार के कॉलम में असाइनमेंट में किया जा सकता है।
यह भी देखें
टिप्पणियाँ
संदर्भ
- ↑ Python: pop()
- ↑ Management and Processing of Complex Data Structures: Third Workshop on Information Systems and Artificial Intelligence, Hamburg, Germany, February 28 - March 2, 1994. Proceedings, ed. Kai v. Luck, Heinz Marburger, p. 76
- ↑ Python Issue7212: Retrieve an arbitrary element from a set without removing it; see msg106593 regarding standard name
- ↑ Ruby Feature #4553: Add Set#pick and Set#pop
- ↑ Inductive Synthesis of Functional Programs: Universal Planning, Folding of Finite Programs, and Schema Abstraction by Analogical Reasoning, Ute Schmid, Springer, Aug 21, 2003, p. 240
- ↑ Recent Trends in Data Type Specification: 10th Workshop on Specification of Abstract Data Types Joint with the 5th COMPASS Workshop, S. Margherita, Italy, May 30 - June 3, 1994. Selected Papers, Volume 10, ed. Egidio Astesiano, Gianna Reggio, Andrzej Tarlecki, p. 38
- ↑ Ruby: flatten()
- ↑ Wang, Thomas (1997), Sorted Linear Hash Table, archived from the original on 2006-01-12
- ↑ Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.
- ↑ "ECMAScript 2015 Language Specification – ECMA-262 6th Edition". www.ecma-international.org (in British English). Retrieved 2017-07-11.