مجموعه (نوع داده انتزاعی)
در علوم رایانه، یک مجموعه یک نوع داده انتزاعی است که می تواند مقادیر یکتایی را بدون هیچ ترتیب خاصی ذخیره کند. در واقع این نوع داده، یک پیادهسازی برای مفهوم ریاضی مجموعههای متناهی به زبان رایانه است. بر خلاف سایر گردآوردها، به جای این که بخواهیم یک عنصر خاص از مجموعه را به دست آوریم، معمولاً، بررسی میکنیم که آیا یک مقدار دلخواه در مجموعه وجود دارد یا خیر.
برخی از دادهساختارهای موجود برای مجموعه، برای مجموعههای ایستا یا frozen طراحی شدهاند که پس از ساخت، تغییر نمیکنند. مجموعههای ایستا فقط عملیات پرسوجو – مانند بررسی وجود یا عدم وجود مقدار داده شده در مجموعه یا برشمردن مقادیر موجود در مجموعه با ترتیب دلخواه – را روی عناصر خود مجاز میدانند. نوع دیگر، مجموعههای پویا یا mutable نامیده می شوند که امکان افزودن و حذف عناصر از مجموعه را هم دارند.
چندمجموعه یک نوع خاص از مجموعه است که در آن یک عنصر میتواند چندین بار ظاهر شود.
نظریه نوع
در نظریهٔ نوع، مجموعهها به طور کلی با تابع مشخصهی خود مشخص می شوند. بنابراین، مجموعهای از مقادیر از نوع
به صورت نظری، میتوان بسیاری از دادهساختارهای انتزاعی دیگر را به شکل مجموعهای دارای عملیاتهای بیشتر و/یا مجموعهای با اصول موضوعهی اضافی اعمال شده بر عملیاتهای استاندارد، در نظر گرفت. مثلاً، میتوان یک هرم انتزاعی را به شکل یک مجموعه با عملیات 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 همچنین STLhash_set
ارائه می دهد که مجموعه ای را با استفاده از جدول هش پیاده سازی می کند. C ++ 11unordered_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 SGIhash_multiset
که کپی و در نهایت استاندارد شده ارائه می دهد. - برای جاوا ، کتابخانه های شخص ثالث قابلیت چند مجموعه ای را ارائه می دهند:
- مجموعه های Apache Commons
Bag
وSortedBag
را با کلاس های اجرایی مانندHashBag
وTreeBag
فراهم می کند. - Google Guava با کلاسهای پیاده سازی مانند
HashMultiset
وTreeMultiset
Multiset
را فراهم می کند.
- مجموعه های Apache Commons
- اپل فراهم می کند
NSCountedSet
کلاس به عنوان بخشی از کاکائو وCFBag
وCFMutableBag
انواع به عنوان بخشی از CoreFoundation . - کتابخانه استاندارد پایتون
collections.
Counter
، که شبیه به چند مجموعه است. - Smalltalk شامل
Bag
، که می تواند نمونه ای از آن باشد که از هویت یا برابری به عنوان محمول برای آزمون ورود استفاده کند.
در مواردی که ساختار داده ای چند مجموعه ای در دسترس نباشد ، استفاده از یک مجموعه منظم برای رفع اشکال است ، اما عدد مساوی موارد آن را نادیده بگیرید تا همیشه "مساوی" بر روی اشیا objects مجزا برگردد (با این حال ، چنین مواردی هنوز قادر به ذخیره چندین مورد نیستند از همان شی object استفاده کنید) یا از یک آرایه انجمنی استفاده کنید که مقادیر را بر ضرب های عدد صحیح آنها ترسیم کند (این به هیچ وجه نمیتواند بین عناصر مساوی تفاوت قائل شود).
عملیات معمول روی کیسه ها:
contains( B, x )
: بررسی می کند که آیا عنصر x (حداقل یک بار) در کیسه B وجود داردis_sub_bag( B 1, B 2 )
: بررسی می کند که آیا هر عنصر در کیسه B 1 در B 1 رخ می دهد بیش از آنچه در کیسه B 2 وجود دارد . گاهی اوقات به عنوان B 1 ⊑ B 2 نشان داده می شود.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 1 یا کیسه B 2 وجود دارد ، با این تفاوت که تعداد دفعاتی که مقدار x در کیسه حاصله اتفاق می افتد برابر است با ( B 1 # x) + ( B 2 # x) ؛ گاهی اوقات به عنوان B 1 ⊎ B 2 نشان داده می شود.
جستارهای وابسته
- ↑ 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 (به انگلیسی). Retrieved 2017-07-11.
یادداشتها
منابع
مشارکتکنندگان ویکیپدیا. «Set (abstract data type)». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲۲ مه ۲۰۲۱.