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

فاجعه‌ای به نام پیچیدگی O(n^2)

زمانی که شما یک حلقه را داخل حلقه دیگری قرار می‌دهید تا داده‌های دو مجموعه را با هم مقایسه کنید، در واقع دارید از مرتبه زمانی Quadratic Time یا O(n^2) استفاده می‌کنید.

مثال عملی:

فرض کنید دو لیست دارید که هر کدام ۱۰۰۰۰ نام کاربری دارند و می‌خواهید نام‌های مشترک را پیدا کنید.

• در حالت حلقه تودرتو: برنامه شما باید 10,000 \times 10,000 مقایسه انجام دهد. یعنی ۱۰۰ میلیون عملیات!

• اگر این تعداد به ۱۰۰ هزار برسد، تعداد عملیات‌ها به ۱۰ میلیارد می‌رسد که می‌تواند سیستم را کاملاً فلج کند.

نجات‌دهنده‌ای به نام HashMap (دیکشنری)

دیکشنری‌ها یا نقشه‌های هش، داده‌ها را به صورت «کلید-مقدار» (Key-Value) ذخیره می‌کنند. جادوی اصلی آن‌ها در این است که زمان جستجو در آن‌ها تقریباً ثابت یا O(1) است. یعنی فرقی نمی‌کند دیکشنری شما ۱۰ عضو داشته باشد یا ۱۰ میلیون؛ پیدا کردن یک کلید خاص در آن با سرعتی باورنکردنی انجام می‌شود.

چرا دیکشنری سریع است؟

برخلاف لیست که برای پیدا کردن یک آیتم باید از ابتدا تا انتها را بگردد، دیکشنری از یک تابع هش (Hash Function) استفاده می‌کند که مستقیماً آدرس حافظه مربوط به آن کلید را پیدا می‌کند.

بازنویسی کد: از O(n^2) به O(n)

بیایید یک سناریوی واقعی را بررسی کنیم. فرض کنید لیستی از «سفارشات» و لیستی از «مشتریان» داریم و می‌خواهیم نام مشتری را به هر سفارش اضافه کنیم.

روش غلط (Nested Loops):

در این روش، برای هر سفارش، کل لیست مشتریان را یک بار از اول تا آخر می‌گردیم.

پایتون:

# پیچیدگی زمانی: O(n * m)
for order in orders:
    for customer in customers:
        if order['customer_id'] == customer['id']:
            order['customer_name'] = customer['name']

سی شارپ:

// تعریف کلاس‌ها
public class Order
{
    public int CustomerId { get; set; }
    public string CustomerName { get; set; }
}

public class Customer
{
    public int Id { get; set; }
    public string Name { get; set; }
}

// حلقه تودرتو
foreach (var order in orders)
{
    foreach (var customer in customers)
    {
        if (order.CustomerId == customer.Id)
        {
            order.CustomerName = customer.Name;
        }
    }
}

روش بهینه (Using Dictionaries):

ابتدا یک بار لیست مشتریان را به دیکشنری تبدیل می‌کنیم (زمان: O(m))، سپس در لیست سفارشات می‌چرخیم و مشتری را از دیکشنری فراخوانی می‌کنیم (زمان: O(n)).

پایتون:

# پیچیدگی زمانی: O(n + m)
customer_lookup = {c['id']: c['name'] for c in customers}

for order in orders:
    order['customer_name'] = customer_lookup.get(order['customer_id'])

سی شارپ:

// ایجاد دیکشنری برای جستجوی سریع
var customerLookup = customers.ToDictionary(c => c.Id, c => c.Name);

foreach (var order in orders)
{
    if (customerLookup.TryGetValue(order.CustomerId, out string customerName))
    {
        order.CustomerName = customerName;
    }
}

در این حالت، به جای ۱۰۰ میلیون عملیات (در مثال قبلی)، ما فقط ۲۰ هزار عملیات انجام می‌دهیم (۱۰۰۰۰ برای ساخت دیکشنری و ۱۰۰۰۰ برای جستجو). این یعنی ۵۰۰۰ برابر سرعت بیشتر!

مقایسه عملکرد در مقیاس بزرگ

در جدول زیر می‌توانید تفاوت فاحش این دو رویکرد را مشاهده کنید:

چه زمانی نباید از دیکشنری استفاده کرد؟ (Trade-offs)

با وجود تمام مزایا، استفاده از دیکشنری یک «معامله» است. شما سرعت می‌خرید، اما در مقابل حافظه (RAM) مصرف می‌کنید.

• مصرف حافظه: دیکشنری‌ها به دلیل ساختار هش، فضای بیشتری نسبت به لیست‌های ساده اشغال می‌کنند. اگر با محدودیت شدید رم (مثلاً در میکروکنترلرها) روبرو هستید، باید احتیاط کنید.

• کلیدهای تکراری: در دیکشنری، کلیدها باید منحصربه‌فرد باشند. اگر داده‌های شما کلید یکتا ندارند، باید به فکر ساختارهای پیچیده‌تر مثل defaultdict (در پایتون) باشید.

• داده‌های بسیار کوچک: اگر لیست شما فقط ۵ یا ۱۰ عضو دارد، هزینه‌ی ساختن یک دیکشنری ممکن است بیشتر از همان حلقه ساده باشد. اما در ۹۹٪ پروژه‌های مدرن، این موضوع اهمیتی ندارد.

نکات حرفه‌ای برای بهینه‌سازی بیشتر

۱. استفاده از Sets: اگر فقط می‌خواهید بدانید که آیا یک آیتم در مجموعه دیگر وجود دارد یا خیر (و نیازی به مقدار یا Value ندارید)، از Set استفاده کنید. Setها هم مانند دیکشنری‌ها بر پایه هش هستند و سرعت جستجوی O(1) دارند.

۲. پیش‌بینی کلیدها: اگر کلیدهای شما رشته‌های طولانی هستند، هش کردن آن‌ها زمان‌بر است. در صورت امکان از اعداد صحیح (Integer) به عنوان کلید استفاده کنید.

۳. Generator Expressions: در زبان‌هایی مثل پایتون، برای جلوگیری از اشغال ناگهانی حافظه هنگام پردازش لیست‌های حجیم، از Generatorها استفاده کنید.

نتیجه‌گیری

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

قانون طلایی: هرگاه دیدید دو حلقه را در هم فرو برده‌اید تا داده‌ای را پیدا کنید، مکث کنید و بپرسید: «آیا می‌توانم اینجا از یک دیکشنری استفاده کنم؟»