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

۰۱ دومی نسخه سریع‌تر اولی نیست، پرسش دیگری است

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

بهایش را حافظه می‌دهد. مجموعه جدولش را عمداً بیشتر از نیمه خالی نگه می‌دارد، چون جدول پر تصادف می‌کند و جدولِ تصادف‌کرده راه می‌رود، و راه رفتن یعنی دوباره همان فهرست. از همین معامله است که مجموعه تکراری‌ها را می‌اندازد و ترتیب را نگه نمی‌دارد؛ دیکشنری همان جدول است با یک مقدار چسبیده به هر کلید، و ترتیب درج را نگه می‌دارد، که قولی است که پایتون در سال ۲۰۱۷ داد و نگه داشت.

دو حقیقت کوچک مستقیم از همین چیدمان درمی‌آیند. تاپل می‌تواند کلید دیکشنری باشد و فهرست نمی‌تواند، چون هش کردن چیزی که عوض می‌شود آن را زیر نشانی‌ای بایگانی می‌کند که بعداً از آن جابه‌جا می‌شود. و dict.get(kelid, pishfarz) به‌جای KeyError مقدار پیش‌فرض را برمی‌گرداند، که سه سطر مراقبت را یک سطر می‌کند. برادر بزرگ‌ترش هم همین‌جاست: defaultdict(list) سطر اول هر کلید را بدون شرط اضافه می‌کند، پس گروه‌بندی سفارش‌ها بر اساس داروخانه، از چهار سطر به یکی می‌رسد.

۰۲ پنج شکل، و پرسشی که هرکدام ارزان جواب می‌دهد

فهرست یک ردیف خانه پشت سر هم است، پس رسیدن به جای مشخص مجانی است و گشتن نیست. list.insert(0, x) همه عضوها را جابه‌جا می‌کند و deque.appendleft نمی‌کند، چون دومی از دو سر باز است و اولی فقط از یک سر. این تفاوت، مرز میان مرتب، اندیس‌دار، و بهایی که اندیس دارد و آخرین ورودی اولین خروجی، اولین ورودی اولین خروجی، و جای هرکدام است.

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

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

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

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

ماژول timeit این نوع بحث را با یک سطر تمام می‌کند و از پایتون 2.3 در کتابخانه استاندارد است. دو دستور، و جواب:

• python3 -m timeit -s "s=set(range(60000))" "59999 in s" که می‌دهد best of 5: 19.9 nsec per loop
• python3 -m timeit -s "L=list(range(60000))" "59999 in L" که می‌دهد best of 5: 531 usec per loop

جای ساعت گرفتن دستی دور کد را گرفته، که اولین اجرا را گزارش می‌کند و اولین اجرا شامل بالا آمدن خود مفسر است. ماژول collections دومین چیزی است که باید باز شود، آن هم در کتابخانه استاندارد و بدون نیاز به شبکه، که در ایران خودش یک ویژگی است چون هیچ‌کدام از این دو نصب نمی‌خواهند. deque و Counter و defaultdict سه‌تایی هستند که هفته اول خرج خودشان را درمی‌آورند، و هرکدام جای نسخه دست‌نویسی را گرفتند که هم کندتر بود و هم یک ایراد داشت.

۰۴ جایی که این درس گیر می‌کند: هیچ‌کس چیزی را اندازه نمی‌گیرد

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

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

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

این صفحه نگفت که چرا ۱۷ ثانیه و ۰٫۰۲۸ ثانیه و ۰٫۰۰۵ ثانیه سه خانواده‌اند و نه سه عدد؛ آن شمارشی است که پیش از هر اندازه‌گیری جواب را پیش‌بینی می‌کند و در الگوریتم‌ها است. همین انتخاب وقتی داده باید بعد از خاموش و روشن شدن هم بماند، موضوعی دیگر با همان استخوان‌بندی است و زیر پایگاه داده می‌نشیند، که خودش مثل همین صفحه زیر ایده‌هایی که با عوض شدن زبان از بین نمی‌روند ایستاده است.