مجموعه (نوع داده انتزاعی)

در علوم رایانه، یک مجموعه یک نوع داده انتزاعی است که می تواند مقادیر یکتایی را بدون هیچ ترتیب خاصی ذخیره کند. در واقع این نوع داده، یک پیاده‌سازی برای مفهوم ریاضی مجموعه‌های متناهی به زبان رایانه است. بر خلاف سایر گردآوردها، به جای این که بخواهیم یک عنصر خاص از مجموعه را به دست آوریم، معمولاً، بررسی می‌کنیم که آیا یک مقدار دلخواه در مجموعه وجود دارد یا خیر.

برخی از داده‌ساختارهای موجود برای مجموعه، برای مجموعه‌های ایستا یا frozen طراحی شده‌اند که پس از ساخت، تغییر نمی‌کنند. مجموعه‌های ایستا فقط عملیات پرس‌وجو – مانند بررسی وجود یا عدم وجود مقدار داده شده در مجموعه یا برشمردن مقادیر موجود در مجموعه با ترتیب دلخواه – را روی عناصر خود مجاز می‌دانند. نوع دیگر، مجموعه‌های پویا یا mutable نامیده می شوند که امکان افزودن و حذف عناصر از مجموعه را هم دارند.

چندمجموعه یک نوع خاص از مجموعه است که در آن یک عنصر می‌تواند چندین بار ظاهر شود.

نظریه نوع

در نظریه‌ٔ نوع‌، مجموعه‌ها به طور کلی با تابع مشخصه‌ی خود مشخص می شوند. بنابراین، مجموعه‌ای از مقادیر از نوع ${\displaystyle A}$ می‌تواند با ${\displaystyle 2^{A}}$ یا ${\displaystyle {\mathcal {P}}(A)}$ نشان داده شود. (می‌توان زیرگروه‌ها و زیرمجموعه‌ها را با refinement types مدل سازی کرد و کلاس‌های هم‌ارزی می‌توان با Setoidها جایگزین کرد.) تابع مشخصه‌ی ${\displaystyle F}$ مربوط به مجموعه‌ی ${\displaystyle S}$ به این شکل تعریف می‌شود:

${\displaystyle F(x)={\begin{cases}1,&{\mbox{if }}x\in S\\0,&{\mbox{if }}x\not \in S\end{cases}}}$

به صورت نظری، می‌توان بسیاری از داده‌ساختارهای انتزاعی دیگر را به شکل مجموعه‌ای دارای عملیات‌های بیشتر و/یا مجموعه‌ای با اصول موضوعه‌ی اضافی اعمال شده بر عملیات‌های استاندارد، در نظر گرفت. مثلاً، می‌توان یک هرم انتزاعی را به شکل یک مجموعه با عملیات 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): خالی بودن مجموعه S را بررسی می‌کند.
• size(S) یا cardinality(S): تعداد عناصر موجود در S را برمی گرداند.
• iterate(S): تابعی را برمی‌گرداند که به ازای هر بار فراخوانی، طبق ترتیبی دلخواه و مشخص، مقدار بعدی از S را برمی گرداند.
• enumerate(S): لیستی را با عناصر S به ترتیبی دلخواه برمی‌گرداند.
• build(x1,x2,…،xn): یک ساختار مجموعه با مقادیر xn ،... ،x2 ،x1 ایجاد می‌کند.
• create_from(collection): یک ساختار مجموعه جدید ایجاد می کند که شامل تمام عناصر گردآورد داده شده یا تمام عناصر برگشتی توسط ایتریتور داده شده است.

مجموعه‌های پویا

ساختارهای مجموعه‌ی پویا، عملیات‌های زیر را نیز دارند:

• ()create: یک ساختار مجموعه‌ای جدید و ابتدائاً خالی ایجاد می‌کند.
  • create_with_capacity(n): یک ساختار مجموعه جدید و ابتدائاً خالی ایجاد می‌کند که حداکثر می‌تواند n عنصر را درون خود جا دهد.
• add(S,x): عنصر x را به مجموعه‌ی S اضافه می‌کند، اگر قبلاً وجود نداشته باشد.
• remove(S,x): عنصر x را از S – در صورت وجود – حذف می‌کند.
• capacity(S): حداکثر تعداد عناصری را که S می‌تواند درون خود نگه دارد، برمی‌گرداند.

برخی از ساختارهای تنظیم شده ممکن است فقط برخی از این عملیات را مجاز باشند. هزینه هر عملیات به اجرا بستگی دارد و احتمالاً به مقادیر خاص ذخیره شده در مجموعه و ترتیب درج آنها نیز بستگی دارد.

عملیات اضافی

بسیاری از عملیات دیگر وجود دارد که (در اصل) می تواند با توجه به موارد فوق تعریف شود ، مانند:

• pop(S): گرداند یک عنصر دلخواه از S، حذف آن از S. ^[۱]
• pick(S): عنصر دلخواه S را برمی گرداند. ^{[۲] [۳] [۴]} عملکردی ، pop جهش دهنده می تواند به عنوان جفت انتخابگرها (pick, rest), تفسیر شود ، جایی که rest مجموعه ای متشکل از همه عناصر به جز عنصر دلخواه را برمی گرداند. ^[۵] iterate قابل تفسیر است. ^[الف]
• map(F,S): مجموعه مقادیر متمایز حاصل از اعمال تابع F به هر عنصر S را برمی گرداند.
• filter(P,S): زیرمجموعه ای را که حاوی تمام عناصر S است که یک گزاره P مشخص را برآورده می کند ، برمی گرداند.
• fold(A0,F,S): مقدار A _{| را برمی گرداند S |} پس از استفاده از A i+1:= F ( A i, e ) برای هر عنصر الکترونیکی از S، برای برخی از عمل دوتایی F. F باید انجمنی و مبادلهای برای این که به خوبی تعریف شده است.
• clear(S): حذف تمام عناصر S.
• equal(S1',S2'): بررسی می کند که آیا دو مجموعه داده شده برابر هستند (یعنی شامل همه و فقط عناصر یکسان هستند).
• hash(S): یک مقدار هش برای مجموعه ثابت S به دست می آورد به طوری که اگر equal(S1,S2) سپس hash(S1) = hash(S2)

سایر عملیات را می توان برای مجموعه هایی با عناصر نوع خاصی تعریف کرد:

• sum(S): جمع تمام عناصر S را برای برخی تعریفهای "sum" برمی گرداند. به عنوان مثال ، در مورد عدد صحیح یا واقعی ، ممکن است به صورت fold(0,add,S) .
• collapse(S): با توجه به مجموعه ای از مجموعه ها ، اتحادیه را برگردانید. ^[۶] به عنوان مثال ، collapse({{1}, {2, 3}}) == {1, 2, 3} . ممکن است نوعی sum نظر گرفته شود.
• flatten(S): با توجه به مجموعه ای متشکل از مجموعه ها و عناصر اتمی (عناصری که مجموعه نیستند) ، مجموعه ای را برمی گرداند که عناصر آن عناصر اتمی مجموعه سطح بالای اصلی یا عناصر مجموعه های موجود در آن است. به عبارت دیگر ، سطحی از لانه سازی را حذف کنید - مانند collapse, اما اجازه دهید اتم ها وجود داشته باشد. برای دستیابی به مجموعه ای از عناصر اتمی می توان این کار را یک بار انجام داد ، یا به طور متناوب صاف کرد. ^[۷] به عنوان مثال ، flatten({1, {2, 3}}) == {1, 2, 3} .
• nearest(S,x): عنصر S را که از نظر ارزش نزدیک به x است (توسط برخی از معیارها ) نزدیک می کند.
• min(S) ، max(S): حداقل / حداکثر عنصر S را برمی گرداند.

پیاده سازی ها

مجموعه ها را می توان با استفاده از ساختارهای مختلف داده اجرا کرد ، که مبادلات زمانی و مکانی متفاوتی را برای انجام عملیات مختلف فراهم می کند. برخی از پیاده سازی ها برای بهبود کارایی عملیات بسیار تخصصی مانند nearest یا union . پیاده سازی هایی که به عنوان "استفاده عمومی" توصیف می شوند ، معمولاً تلاش می کنند تا element_of ، add و delete عملیات را بهینه کنند. یک پیاده سازی ساده استفاده از یک لیست ، نادیده گرفتن ترتیب عناصر و مراقبت برای جلوگیری از تکرار مقادیر است. این ساده اما ناکارآمد است ، زیرا عملیاتی مانند عضویت در مجموعه یا حذف عنصر O ( n ) هستند ، زیرا به اسکن کل لیست نیاز دارند. ^[ب] مجموعه ها اغلب با استفاده از ساختار داده های کارآمد تر ، به ویژه طعم های مختلف درختان ، جدول ها یا جداول هش ، پیاده سازی می شوند.

از آنجا که مجموعه ها می توانند به عنوان نوعی نقشه تفسیر شوند (توسط تابع نشانگر) ، مجموعه ها معمولاً به همان روشی که نقشه های (جزئی) ( آرایه های انجمنی ) اجرا می کنند - در این حالت که مقدار هر جفت کلید-مقدار دارای نوع واحد یا مقدار نگهبان (مانند 1) - یعنی یک درخت جستجوی دودویی خود متعادل برای مجموعه های مرتب شده  (که برای بیشتر عملیات O (log n) دارد) ، یا یک جدول هش برای مجموعه های مرتب نشده (که دارای O (1) متوسط ، اما O (n) بدترین حالت ، برای اکثر عملیات). یک جدول هش خطی مرتب شده ^[۸] ممکن است برای تهیه مجموعه های مرتب شده قطعی استفاده شود.

بعلاوه ، در زبانهایی که از نقشه پشتیبانی می کنند اما مجموعه نیستند ، می توان مجموعه ها را از نظر نقشه پیاده سازی کرد. به عنوان مثال ، اصطلاح رایج برنامه نویسی در Perl که آرایه ای را به هش تبدیل می کند که مقادیر آن مقدار نگهبان 1 است ، برای استفاده به عنوان یک مجموعه ، این است:

my %elements = map { $_ => 1 } @elements;

از دیگر روشهای معروف می توان به آرایه ها اشاره کرد . به طور خاص می توان زیرمجموعه ای از عددهای صحیح 1 .. n را به عنوان یک آرایه بیتی n- bit به طور کارآمد پیاده سازی کرد ، که همچنین از عملکردهای بسیار کارآمد اتحاد و تقاطع پشتیبانی می کند. نقشه بلوم با استفاده از یک نمایش بسیار فشرده اما با احتمال کمی احتمال مثبت کاذب در نمایش داده ها ، یک مجموعه را به صورت احتمالاتی پیاده سازی می کند.

عملیات مجموعه بولی را می توان از نظر عملیات ابتدایی تر ( pop ، clear add و افزودن) پیاده سازی کرد ، اما الگوریتم های تخصصی ممکن است محدوده های زمانی مجانبی کمتری داشته باشند. اگر مجموعه ها به عنوان لیست مرتب شده اجرا شوند ، به عنوان مثال الگوریتم ساده لوح برای union( S, T ) متناسب با طول m S برابر طول n از T طول می کشد. در حالی که یک نوع الگوریتم ادغام لیست کار را در زمان متناسب با m + n انجام می دهد . علاوه بر این ، ساختارهای داده ای مجموعه ای تخصصی (مانند ساختار داده اتحادیه-پیدا کردن ) وجود دارد که برای یک یا چند مورد از این عملیات و با هزینه دیگران بهینه شده اند.

پشتیبانی از زبان

یکی از اولین زبانهایی که از مجموعه پشتیبانی می کند ، زبان پاسکال بود. اکنون بسیاری از زبانها آن را شامل می شوند ، چه در زبان اصلی و چه در یک کتابخانه استاندارد .

• در C ++ ، کتابخانه استاندارد الگو (STL) set می کند ، که معمولاً با استفاده از یک درخت جستجوی باینری (به عنوان مثال درخت قرمز-سیاه ) پیاده سازی می شود. SGI همچنین STL hash_set ارائه می دهد که مجموعه ای را با استفاده از جدول هش پیاده سازی می کند. C ++ 11 unordered_set پشتیبانی می کند که با استفاده از جدول هش پیاده سازی می شود. در مجموعه ها ، عناصر خود کلید هستند ، بر خلاف کانتینرهای توالی دار ، جایی که عناصر با استفاده از موقعیت (نسبی یا مطلق) خود قابل دسترسی هستند. عناصر تنظیم شده باید نظم دقیق ضعیفی داشته باشند.
• جاوا ارائه می دهد Set رابط به مجموعه پشتیبانی (با HashSet کلاس های پیاده سازی آن را با استفاده از یک جدول هش)، و SortedSet زیر رابط کاربری را پشتیبانی مجموعه طبقه بندی شده‌اند (با TreeSet کلاس های پیاده سازی آن با استفاده از یک درخت جستجوی دودویی).
• اپل را چارچوب بنیاد (بخشی از کاکائو ) فراهم می کند Objective-C با کلاس NSSet ، NSMutableSet ، NSCountedSet ، NSOrderedSet و NSMutableOrderedSet . CoreFoundation رابط های برنامه کاربردی ارائه CFSet و CFMutableSet برای استفاده در انواع C .
• پایتون ساخته شده است در set و frozenset انواع از 2.4، و از پایتون 3.0 و 2.7، با پشتیبانی از لیترال مجموعه غیر خالی با استفاده از نحو فرفری براکت، به عنوان مثال: {x, y, z} ؛ مجموعه های خالی باید با استفاده از set() ، زیرا Python از {} برای نمایش فرهنگ لغت خالی استفاده می کند.
• . دات نت فریم ورک generic (جنسی) فراهم می کند HashSet و SortedSet کلاس هایی است که اجرای عمومی ISet رابط.
• کتابخانه کلاس Smalltalk Set و IdentitySet ، به ترتیب با استفاده از برابری و هویت برای آزمون ورود به سیستم. گویش های ارائه تغییرات برای ذخیره سازی فشرده ( NumberSet ، CharacterSet )، برای سفارش ( OrderedSet ، SortedSet ، و غیره) و یا برای مراجع ضعیف ( WeakIdentitySet ).
• کتابخانه استاندارد Ruby set که شامل Set و SortedSet که مجموعه ها را با استفاده از جداول هش پیاده سازی می کند ، دسته دوم امکان تکرار به ترتیب مرتب شده را دارد.
• کتابخانه استاندارد OCaml Set ، که با استفاده از درختان جستجوی باینری ، یک ساختار داده عملکردی مجموعه را پیاده سازی می کند.
• اجرای GHC از Haskell Data. فراهم می کند. Set که مجموعه های تغییرناپذیر را با استفاده از درختان جستجوی دودویی پیاده سازی می کند. ^[۹]
• بسته Tcl Tcllib یک ماژول مجموعه را فراهم می کند که یک ساختار داده مجموعه را بر اساس لیست های TCL پیاده سازی می کند.
• سویفت کتابخانه استاندارد شامل Set نوع، از سویفت 1.2.
• جاوا اسکریپت Set به عنوان یک شی داخلی داخلی با استاندارد ECMAScript 2015 ^[۱۰] .
• کتابخانه استاندارد Erlang دارای یک ماژول sets
• Clojure برای مجموعه های hashed نحو واقعی دارد و همچنین مجموعه های مرتب شده را پیاده سازی می کند.
• LabVIEW از نسخه 2019 از مجموعه پشتیبانی محلی دارد.

همانطور که در بخش قبلی اشاره شد ، در زبانهایی که به طور مستقیم از مجموعه پشتیبانی نمی‌کنند اما از آرایه های انجمنی پشتیبانی می کنند ، می توان مجموعه ها را با استفاده از آرایه های تداعی ، با استفاده از عناصر به عنوان کلید و با استفاده از یک مقدار ساختگی به عنوان مقادیر ، که از آنها چشم پوشی می شود ، تقلید کرد.

چند مجموعه

چندمجوعه یا خورجین یک تعمیم مفهوم مجموعه است. تفاوت آن با مجموعه این است که اجازه می دهد تا مقادیر مساوی و تکراری داشته باشیم. این است که در دو معنای متمایز استفاده می شود: ارزش هم برابر هستند یکسان در نظر گرفته، و به سادگی شمارش، و یا مقادیر برابر باشند معادل در نظر گرفته، و به عنوان کالای مجزا ذخیره می شود. به عنوان مثال ، با توجه به لیستی از افراد (با نام) و سن (در سال) ، می توان چندین گروه از سنین را ایجاد کرد که به سادگی تعداد افراد در یک سن مشخص را محاسبه می کند. متناوباً ، می توان افراد زیادی را ساخت ، جایی که دو نفر در صورتی که سن آنها یکسان باشد معادل در نظر گرفته می شوند (اما ممکن است افراد مختلف باشند و نام های مختلفی داشته باشند) ، در این صورت هر جفت (نام ، سن) باید ذخیره شود و انتخاب در یک سن معین به همه افراد در یک سن داده می شود.

به طور رسمی ، این امکان وجود دارد که اشیا in در علوم کامپیوتر تحت برخی معادلات هم ارزی "برابر" قلمداد شوند اما در رابطه دیگری هنوز مشخص باشند. برخی از انواع پیاده سازی چند مجموعه ، اشیا equal مساوی مجزا را به عنوان موارد جداگانه در ساختار داده ذخیره می کنند. در حالی که دیگران آن را به یک نسخه تقسیم می کنند (نسخه اول با آن مواجه می شوند) و تعداد عددی مثبت را از کثرت عنصر حفظ می کنند.

همانند مجموعه ها ، چند مجموعه به طور طبیعی می توانند با استفاده از جدول هش یا درختان ، که دارای عملکردهای مختلف هستند ، اجرا شوند.

مجموعه همه کیسه ها در بالای نوع T با عبارت T ارائه می شود. اگر توسط چند مجموعه یکی موارد مساوی را یکسان در نظر گرفته و به سادگی آنها را بشمارد ، پس می توان چند مجموعه را به عنوان تابعی از دامنه ورودی به اعداد صحیح غیر منفی تفسیر کرد ( طبیعی اعداد ) ، شناسایی یک مجموعه با عملکرد نشانگر آن را تعمیم می دهد. در بعضی موارد ، یک مجموعه چندگانه به این معنی شمارش ممکن است تعمیم داده شود تا مقادیر منفی مانند پایتون مجاز باشد.

• کتابخانه الگوی استاندارد C ++ چندین مجموعه مرتب شده و مرتب نشده را پیاده سازی می کند. این فراهم می کند multiset کلاس برای MultiSet به مرتب شده اند، به عنوان یک نوع ظرف انجمنی ، که پیاده سازی این MultiSet به استفاده از یک درخت جستجوی دودویی خود متوازن . unordered_multiset برای چند مجموعه مرتب نشده ، به عنوان نوعی کانتینر انجمنی غیر مرتب ، فراهم می کند که این چند مجموعه را با استفاده از جدول هش پیاده سازی می کند. چند مجموعه مرتب نشده از C ++ 11 استاندارد است. قبلاً STL SGI hash_multiset که کپی و در نهایت استاندارد شده ارائه می دهد.
• برای جاوا ، کتابخانه های شخص ثالث قابلیت چند مجموعه ای را ارائه می دهند:
  • مجموعه های Apache Commons Bag و SortedBag را با کلاس های اجرایی مانند HashBag و TreeBag فراهم می کند.
  • Google Guava با کلاسهای پیاده سازی مانند HashMultiset و TreeMultiset Multiset را فراهم می کند.
• اپل فراهم می کند NSCountedSet کلاس به عنوان بخشی از کاکائو و CFBag و CFMutableBag انواع به عنوان بخشی از CoreFoundation .
• کتابخانه استاندارد پایتون collections. Counter ، که شبیه به چند مجموعه است.
• Smalltalk شامل Bag ، که می تواند نمونه ای از آن باشد که از هویت یا برابری به عنوان محمول برای آزمون ورود استفاده کند.

در مواردی که ساختار داده ای چند مجموعه ای در دسترس نباشد ، استفاده از یک مجموعه منظم برای رفع اشکال است ، اما عدد مساوی موارد آن را نادیده بگیرید تا همیشه "مساوی" بر روی اشیا objects مجزا برگردد (با این حال ، چنین مواردی هنوز قادر به ذخیره چندین مورد نیستند از همان شی object استفاده کنید) یا از یک آرایه انجمنی استفاده کنید که مقادیر را بر ضرب های عدد صحیح آنها ترسیم کند (این به هیچ وجه نمی‌تواند بین عناصر مساوی تفاوت قائل شود).

عملیات معمول روی کیسه ها:

• contains( B, x ) : بررسی می کند که آیا عنصر x (حداقل یک بار) در کیسه B وجود دارد
• is_sub_bag( B 1, B 2 ) : بررسی می کند که آیا هر عنصر در کیسه B ₁ در B ₁ رخ می دهد بیش از آنچه در کیسه B _{2 وجود دارد} . گاهی اوقات به عنوان B ₁ ⊑ B ₂ نشان داده می شود.
• count( B, x ) : تعداد دفعاتی که عنصر x در کیسه B رخ می دهد را برمی گرداند. گاهی اوقات به عنوان B # x نشان داده می شود.
• scaled_by( B, n ) : به یک عدد طبیعی n داده می شود ، کیسه ای برگردانده می شود که شامل همان عناصر کیسه B است ، با این تفاوت که هر عنصری که m بار در B اتفاق می افتد n * m بار در کیسه حاصل می شود گاهی اوقات به عنوان n ⊗ B نشان داده می شود.
• union( B 1, B 2 ) : کیسه ای را شامل می کند که فقط شامل مقادیری باشد که در کیسه B ₁ یا کیسه B _{2 وجود دارد} ، با این تفاوت که تعداد دفعاتی که مقدار x در کیسه حاصله اتفاق می افتد برابر است با ( B ₁ # x) + ( B ₂ # x) ؛ گاهی اوقات به عنوان B ₁ ⊎ B ₂ نشان داده می شود.

جستارهای وابسته

• فیلتر بلوم
• مجموعه جدا
• مجموعه (ریاضیات)  

1. Python: pop()
2. 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
3. Python Issue7212: Retrieve an arbitrary element from a set without removing it; see msg106593 regarding standard name
4. Ruby Feature #4553: Add Set#pick and Set#pop
5. 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
6. 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
7. Ruby: flatten()
8. Wang, Thomas (1997), Sorted Linear Hash Table, archived from the original on 2006-01-12
9. Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993. Retrieved on 2015-03-11.
10. "ECMAScript 2015 Language Specification – ECMA-262 6th Edition". www.ecma-international.org (به انگلیسی). Retrieved 2017-07-11.

یادداشت‌ها

1. For example, in Python pick can be implemented on a derived class of the built-in set as follows:

   class Set(set):
     def pick(self):
       return next(iter(self))
   

2. 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.

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Set (abstract data type)». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۲ مه ۲۰۲۱.