موضوع مقاله: مجموعه (نوع داده انتزاعی) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مجموعه (نوع داده انتزاعی) | مقدمه: در علوم رایانه، یک مجموعه یک نوع داده انتزاعی است که می تواند مقادیر یکتایی را بدون هیچ ترتیب خاصی ذخیره کند. | ## بخش 1: مجموعه (نوع داده انتزاعی) | در واقع این نوع داده، یک پیاده‌سازی برای مفهوم ریاضی مجموعه‌های متناهی به زبان رایانه است. بر خلاف سایر گردآوردها، به جای این که بخواهیم یک عنصر خاص از مجموعه را به دست آوریم، معمولاً، بررسی می‌کنیم که آیا یک مقدار دلخواه در مجموعه وجود دارد یا خیر. برخی از داده‌ساختارهای موجود برای مجموعه، برای مجموعه‌های ایستا یا frozen طراحی شده‌اند که پس از ساخت، تغییر نمی‌کنند. مجموعه‌های ایستا فقط عملیات پرس‌وجو – مانند بررسی وجود یا عدم وجود مقدار داده شده در مجموعه یا برشمردن مقادیر موجود در مجموعه با ترتیب دلخواه – را روی عناصر خود مجاز می‌دانند. نوع دیگر، مجموعه‌های پویا یا mutable نامیده می شوند که امکان افزودن و حذف عناصر از مجموعه را هم دارند. چندمجموعه یک نوع خاص از مجموعه است که در آن یک عنصر می‌تواند چندین بار ظاهر شود. نظریه نوع در نظریه‌ٔ نوع‌، مجموعه‌ها به طور کلی با تابع مشخصه‌ی خود مشخص می شوند. (می‌توان زیرگروه‌ها و زیرمجموعه‌ها را با refinement types مدل سازی کرد و کلاس‌های هم‌ارزی می‌توان با Setoidها جایگزین کرد.) تابع مشخصه‌ی مربوط به مجموعه‌ی به این شکل تعریف می‌شود: به صورت نظری، می‌توان بسیاری از داده‌ساختارهای انتزاعی دیگر را به شکل مجموعه‌ای دارای عملیات‌های بیشتر و/یا مجموعه‌ای با اصول موضوعه‌ی اضافی اعمال شده بر عملیات‌های استاندارد، در نظر گرفت. مثلاً، می‌توان یک هرم انتزاعی را به شکل یک مجموعه با عملیات min(S) که عنصر با کوچک‌ترین مقدار را برمی‌گرداند، تعریف کرد. عملیات‌ها عملیات‌های اصلی مربوط به نظریه‌ی مجموعه‌ها می‌توان عملیات‌های جبر مجموعه‌ها را تعریف کرد: union(S,T): اجتماع مجموعه‌های S و T را برمی‌گرداند. iterate(S): تابعی را برمی‌گرداند که به ازای هر بار فراخوانی، طبق ترتیبی دلخواه و مشخص، مقدار بعدی از S را برمی گرداند. مجموعه‌های پویا ساختارهای مجموعه‌ی پویا، عملیات‌های زیر را نیز دارند: create: یک ساختار مجموعه‌ای جدید و ابتدائاً خالی ایجاد می‌کند. هزینه هر عملیات به اجرا بستگی دارد و احتمالاً به مقادیر خاص ذخیره شده در مجموعه و ترتیب درج آنها نیز بستگی دارد. عملیات اضافی بسیاری از عملیات دیگر وجود دارد که (در اصل) می تواند با توجه به موارد فوق تعریف شود ، مانند: pop(S): گرداند یک عنصر دلخواه از S، حذف آن از S. equal(S1',S2'): بررسی می کند که آیا دو مجموعه داده شده برابر هستند (یعنی شامل همه و فقط عناصر یکسان هستند). flatten(S): با توجه به مجموعه ای متشکل از مجموعه ها و عناصر اتمی (عناصری که مجموعه نیستند) ، مجموعه ای را برمی گرداند که عناصر آن عناصر اتمی مجموعه سطح بالای اصلی یا عناصر مجموعه های موجود در آن است. به عبارت دیگر ، سطحی از لانه سازی را حذف کنید - مانند collapse, اما اجازه دهید اتم ها وجود داشته باشد. | ## بخش 2: مجموعه (نوع داده انتزاعی) | برای دستیابی به مجموعه ای از عناصر اتمی می توان این کار را یک بار انجام داد ، یا به طور متناوب صاف کرد. پیاده سازی ها مجموعه ها را می توان با استفاده از ساختارهای مختلف داده اجرا کرد ، که مبادلات زمانی و مکانی متفاوتی را برای انجام عملیات مختلف فراهم می کند. یک پیاده سازی ساده استفاده از یک لیست ، نادیده گرفتن ترتیب عناصر و مراقبت برای جلوگیری از تکرار مقادیر است. این ساده اما ناکارآمد است ، زیرا عملیاتی مانند عضویت در مجموعه یا حذف عنصر O ( n ) هستند ، زیرا به اسکن کل لیست نیاز دارند. مجموعه ها اغلب با استفاده از ساختار داده های کارآمد تر ، به ویژه طعم های مختلف درختان ، جدول ها یا جداول هش ، پیاده سازی می شوند. از آنجا که مجموعه ها می توانند به عنوان نوعی نقشه تفسیر شوند (توسط تابع نشانگر) ، مجموعه ها معمولاً به همان روشی که نقشه های (جزئی) ( آرایه های انجمنی ) اجرا می کنند - در این حالت که مقدار هر جفت کلید-مقدار دارای نوع واحد یا مقدار نگهبان (مانند 1) - یعنی یک درخت جستجوی دودویی خود متعادل برای مجموعه های مرتب شده (که برای بیشتر عملیات O (log n) دارد) ، یا یک جدول هش برای مجموعه های مرتب نشده (که دارای O (1) متوسط ، اما O (n) بدترین حالت ، برای اکثر عملیات). یک جدول هش خطی مرتب شده ممکن است برای تهیه مجموعه های مرتب شده قطعی استفاده شود. بعلاوه ، در زبانهایی که از نقشه پشتیبانی می کنند اما مجموعه نیستند ، می توان مجموعه ها را از نظر نقشه پیاده سازی کرد. n را به عنوان یک آرایه بیتی n- bit به طور کارآمد پیاده سازی کرد ، که همچنین از عملکردهای بسیار کارآمد اتحاد و تقاطع پشتیبانی می کند. نقشه بلوم با استفاده از یک نمایش بسیار فشرده اما با احتمال کمی احتمال مثبت کاذب در نمایش داده ها ، یک مجموعه را به صورت احتمالاتی پیاده سازی می کند. عملیات مجموعه بولی را می توان از نظر عملیات ابتدایی تر ( pop ، clear add و افزودن) پیاده سازی کرد ، اما الگوریتم های تخصصی ممکن است محدوده های زمانی مجانبی کمتری داشته باشند. اگر مجموعه ها به عنوان لیست مرتب شده اجرا شوند ، به عنوان مثال الگوریتم ساده لوح برای union( S, T ) متناسب با طول m S برابر طول n از T طول می کشد. در حالی که یک نوع الگوریتم ادغام لیست کار را در زمان متناسب با m + n انجام می دهد . علاوه بر این ، ساختارهای داده ای مجموعه ای تخصصی (مانند ساختار داده اتحادیه-پیدا کردن ) وجود دارد که برای یک یا چند مورد از این عملیات و با هزینه دیگران بهینه شده اند. پشتیبانی از زبان یکی از اولین زبانهایی که از مجموعه پشتیبانی می کند ، زبان پاسکال بود. اکنون بسیاری از زبانها آن را شامل می شوند ، چه در زبان اصلی و چه در یک کتابخانه استاندارد . در C ++ ، کتابخانه استاندارد الگو (STL) set می کند ، که معمولاً با استفاده از یک درخت جستجوی باینری (به عنوان مثال درخت قرمز-سیاه ) پیاده سازی می شود. | ## بخش 3: مجموعه (نوع داده انتزاعی) | در مجموعه ها ، عناصر خود کلید هستند ، بر خلاف کانتینرهای توالی دار ، جایی که عناصر با استفاده از موقعیت (نسبی یا مطلق) خود قابل دسترسی هستند. کتابخانه استاندارد OCaml Set ، که با استفاده از درختان جستجوی باینری ، یک ساختار داده عملکردی مجموعه را پیاده سازی می کند. Set که مجموعه های تغییرناپذیر را با استفاده از درختان جستجوی دودویی پیاده سازی می کند. همانطور که در بخش قبلی اشاره شد ، در زبانهایی که به طور مستقیم از مجموعه پشتیبانی نمی‌کنند اما از آرایه های انجمنی پشتیبانی می کنند ، می توان مجموعه ها را با استفاده از آرایه های تداعی ، با استفاده از عناصر به عنوان کلید و با استفاده از یک مقدار ساختگی به عنوان مقادیر ، که از آنها چشم پوشی می شود ، تقلید کرد. تفاوت آن با مجموعه این است که اجازه می دهد تا مقادیر مساوی و تکراری داشته باشیم. این است که در دو معنای متمایز استفاده می شود: ارزش هم برابر هستند یکسان در نظر گرفته، و به سادگی شمارش، و یا مقادیر برابر باشند معادل در نظر گرفته، و به عنوان کالای مجزا ذخیره می شود. به عنوان مثال ، با توجه به لیستی از افراد (با نام) و سن (در سال) ، می توان چندین گروه از سنین را ایجاد کرد که به سادگی تعداد افراد در یک سن مشخص را محاسبه می کند. متناوباً ، می توان افراد زیادی را ساخت ، جایی که دو نفر در صورتی که سن آنها یکسان باشد معادل در نظر گرفته می شوند (اما ممکن است افراد مختلف باشند و نام های مختلفی داشته باشند) ، در این صورت هر جفت (نام ، سن) باید ذخیره شود و انتخاب در یک سن معین به همه افراد در یک سن داده می شود. به طور رسمی ، این امکان وجود دارد که اشیا in در علوم کامپیوتر تحت برخی معادلات هم ارزی "برابر" قلمداد شوند اما در رابطه دیگری هنوز مشخص باشند. برخی از انواع پیاده سازی چند مجموعه ، اشیا equal مساوی مجزا را به عنوان موارد جداگانه در ساختار داده ذخیره می کنند. در حالی که دیگران آن را به یک نسخه تقسیم می کنند (نسخه اول با آن مواجه می شوند) و تعداد عددی مثبت را از کثرت عنصر حفظ می کنند. همانند مجموعه ها ، چند مجموعه به طور طبیعی می توانند با استفاده از جدول هش یا درختان ، که دارای عملکردهای مختلف هستند ، اجرا شوند. اگر توسط چند مجموعه یکی موارد مساوی را یکسان در نظر گرفته و به سادگی آنها را بشمارد ، پس می توان چند مجموعه را به عنوان تابعی از دامنه ورودی به اعداد صحیح غیر منفی تفسیر کرد ( طبیعی اعداد ) ، شناسایی یک مجموعه با عملکرد نشانگر آن را تعمیم می دهد. در بعضی موارد ، یک مجموعه چندگانه به این معنی شمارش ممکن است تعمیم داده شود تا مقادیر منفی مانند پایتون مجاز باشد. کتابخانه الگوی استاندارد C ++ چندین مجموعه مرتب شده و مرتب نشده را پیاده سازی می کند. در مواردی که ساختار داده ای چند مجموعه ای در دسترس نباشد ، استفاده از یک مجموعه منظم برای رفع اشکال است ، اما عدد مساوی موارد آن را نادیده بگیرید تا همیشه "مساوی" بر روی اشیا objects مجزا برگردد (با این حال ، چنین مواردی هنوز قادر به ذخیره چندین مورد نیستند از همان شی object استفاده کنید) یا از یک آرایه انجمنی استفاده کنید که مقادیر را بر ضرب های عدد صحیح آنها ترسیم کند (این به هیچ وجه نمی‌تواند بین عناصر مساوی تفاوت قائل شود). 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 نشان داده می شود.