Faragiri

همهٔ زبان‌ها

آموزش دیکشنری و مجموعهساختمان داده

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

۴بخش
۳دقیقه خواندن
۴عمق

دو شعبه، یک انبار

ناحیه‌ای که هر چهار عملگر درباره‌اش می‌پرسند

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

  • کدهای شعبه انقلاب
  • کدهای شعبه صادقیه
دفتر یدکی و خودکار آبی
  • کدهای شعبه انقلابکاغذ کاهی و پاک‌کن فقط اینجا هستند
  • کدهای شعبه صادقیهچسب ماتیکی فقط اینجاست

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

دو شعبه یک لوازم‌التحریری، انقلاب و صادقیه، هرکدام فهرستی از کد کالاهایشان دارند. چهار پرسشی که معمولا با حلقه نوشته می‌شوند، هرکدام یک نویسه‌اند:

  • enghelab & sadeghieh کدهایی که هر دو شعبه دارند
  • enghelab | sadeghieh فهرست کل، بدون تکرار
  • enghelab - sadeghieh کدهایی که فقط انقلاب دارد
  • enghelab ^ sadeghieh کدهایی که دقیقا یکی از دو شعبه دارد

سومی همان چیزی است که برای پر کردن انبار شعبه دوم لازم دارید و چهارمی همان چیزی که در یک مغایرت‌گیری دنبالش می‌گردید. هر چهار عملگر یک مجموعه تازه برمی‌گردانند و هیچ‌کدام به ترتیب کاری ندارند، چون مجموعه ترتیب ندارد.

عضویت، و عددی که تصمیم را عوض می‌کند

پرسش «این کد هست یا نه» روی یک فهرست یعنی خواندن قلم به قلم تا پیدا شدن. روی یک مجموعه یعنی یک بار درهم‌سازی و یک بار نگاه کردن. روی یک میلیون قلم، اندازه‌گیری‌شده روی یک مک‌بوک با تراشه M1 Max و پایتون 3.14 در تاریخ ۲۰۲۶-۰۹-۰۳: روی فهرست ۸٫۹ میلی‌ثانیه، روی مجموعه ۳۹٫۵ نانوثانیه. این همان تفاوتی است که یک گزارش را از سه دقیقه به یک ثانیه می‌آورد و کل تغییرش یک تبدیل در ابتدای کار است.

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

دیکشنری همان مجموعه است، با یک مقدار روی هر کلید

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

دو روش که جای نصف کدهای شمارش را می‌گیرند: d.setdefault(kod, []).append(radif) که گروه‌بندی را بدون بررسی وجود کلید انجام می‌دهد، و collections.Counter که شمردن تکرارها و گرفتن پرتکرارترین‌ها را در یک سطر می‌دهد. مجموعه به هیچ‌کدام از این دو جواب نمی‌دهد، چون اصلا تعداد را نگه نمی‌دارد.

جایی که کار گیر می‌کند، مغایرت‌گیری دو فایل است

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

ابزار، و سالی که این حرف درست است

در سال ۲۰۲۶ collections.Counter و collections.defaultdict هر دو در کتابخانه استاندارد و رایگان‌اند و جای الگوی «اگر کلید نبود بسازش» را گرفته‌اند، که هم طولانی‌تر است و هم جایی که فراموش شود یک KeyError می‌دهد. برای دیدن اینکه یک مجموعه واقعا چقدر حافظه گرفته sys.getsizeof کافی است و به شبکه نیازی ندارد. هیچ‌کدام از این‌ها بسته بیرونی لازم ندارند، که وقتی نصب کردن یک وابستگی خودش یک ماجراست، خودش یک دلیل انتخاب است.

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

کنار این

بالای این