جدول مراجعه و جستجو

جدول مراجعه و جستجو در علوم کامپیوتر آرایه ای است که به‌جای محاسبات زمان اجرا، از یک عملیات اندکس گذاری آرایه ای ساده استفاده می‌کند. در نتیجه، صرفه جویی در زمان پردازش می‌تواند چشمگیر باشد، زیرا استخراج یک مقدار از حافظه، معمولاً سریع تر از انجام یک محاسبهٔ هزینه بر یا عملیات ورودی/خروجی است. این جدول را می‌توان از پیش محاسبه و در حافظهٔ استاتیک برنامه ذخیره کرد یا بعنوان بخشی از فاز شروع یک برنامه محاسبه شود (به انگلیسی: memoization) یا حتی در سخت‌افزار پلتفرم‌های با کاربرد اختصاصی ذخیره شود. این نوع جداول همچنین کاربرد وسیعی برای تعیین اعتبار مقادیر ورودی بوسیلهٔ مقایسهٔ آن‌ها با لیستی از موارد معتبر (یا غیر معتبر) در یک آرایه، و در برخی زبان‌های برنامه‌نویسی، ممکن است در برگیرندهٔ توابع اشاره گر برای پردازش ورودی سازگار، باشد. آرایه‌های درگاهی قابل برنامه‌ریزی توسط کاربر (به انگلیسی: FPGA) نیز استفادهٔ زیادی از این نوع جداول قابل پیکربندی، پیاده‌سازی شده به طریق سخت‌افزاری، برای کاربرد سخت‌افزاری قابل برنامه‌ریزی می‌کنند.

مثال‌ها

مراجعه و جستجوی ساده در یک آرایهٔ ارتباطی، یا یک لیست پیوندی (لیست نامرتب)

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

جستجوی دودویی در یک آرایه یا یک آرایهٔ ارتباطی (لیست مرتب)

جستجوی دودویی یک مثال از الگوریتم تقسیم و غلبه است که در آن در هر مرحله، نیمی از آرایه که امکان یافتن معادل عنصر مورد نظر در آن وجود دارد، مشخص می‌شود و نیمهٔ دیگر کنار گذاشته می‌شود و این کار تا زمانیکه به موفقیت یا شکست ختم شود، ادامه می‌یابد. البته این روش فقط در صورتی امکان‌پذیر است که لیست مرتب شده باشد. با این وجود، کارایی بالایی حتی در لیست‌های طولانی دارد.

تابع درهم سازی ناچیز

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

شمارش بیت‌ها در توالی بایت‌ها

یک مسألهٔ گسسته که در بسیاری از کامپیوترها با هزینهٔ زیادی قابل حل است، شمارش تعداد بیت‌های برابر ۱ در یک عدد باینری است، که گاهی به آن تابع جمعیت گویند. برای مثال، عدد دسیمال ۳۷ به شکل باینری برابر ۰۰۱۰۰۱۰۱ است، بنابراین دارای سه بیت برابر ۱ است.

در ادامه یک مثال ساده در زبان C برای شمارش تعداد بیت‌های ۱ در یک int نشان داده شده‌است:

int count_ones(unsigned int x)
{
    int result = 0;
    while (x != 0)
    {
        x = x & (x - 1);
        result++;
    }
    return result;
}

این الگوریتم به ظاهر ساده می‌تواند، به‌طور بالقوه حتی در معماری‌های مدرن، صدها چرخه بگیرد، چون انشعابات بسیاری در حلقه ایجاد می‌کند، و انشعاب باعث کندی می‌شود. این مشکل را می‌توان با استفاده از روش باز کردن حلقه و برخی از بهینه‌سازی‌های کامپایلر کمتر کرد. با این حال، یک راه حل الگوریتمی ساده و خیلی سریعتر با استفاده از جدول مراجعه و تابع درهم سازی ناچیز وجود دارد.
کافی است که یک جدول وضعیت به نام bits_set با ۲۵۶ ورودی درست کنیم که دارای تعداد ست بیت یک در هر مقدار بایت ممکن است (مثلا: 0x00 = 0, 0x01 = 1, 0x02 = ۱, و …). سپس از این جدول برای پیدا کردن تعداد ۱ها در هر بایت اینتیجر با استفاده از جدول مراجعهٔ تابع درهم سازی ناچیز برای هر بایت استفاده می‌کنیم و آن‌ها را با هم جمع می‌کنیم. در اینجا، نیاز به انشعاب نداریم و فقط نیاز به چهار بار دسترسی اندکسی به حافظه است، در نتیجه در مقایسه با کد اول بسیار سریع تر است.

/* Pseudocode of the lookup table 'uint32_t bits_set[256]' */
/*                    0b00, 0b01, 0b10, 0b11, 0b100, 0b101, ... */
int bits_set[256] = {    0,    1,    1,    2,     1,     2, // 200+ more entries

/* (this code assumes that 'int' is an unsigned 32-bits wide integer) */
int count_ones(unsigned int x)
{
    return bits_set[x       & 255]
        + bits_set[(x >>  8) & 255]
        + bits_set[(x >> 16) & 255]
        + bits_set[(x >> 24) & 255];
}

کد بالا را می‌توان به راحتی بهبود بخشید (با اجتناب از ANDing و شیفت)، با تغییر فرم x بعنوان یک آرایهٔ کاراکتری چهار بایتی و ترجیحاً کد گذاری در یک خط به شکل یک عبارت منفرد به جای یک تابع. توجه کنید که حتی این الگوریتم ساده می‌تواند بسیار کند عمل کند، زیرا کد اولیه ممکن است از کش پردازنده‌های مدرن سریع تر اجرا شود و جدول‌های مراجعهٔ بزرگ بخوبی در کش جای نمی‌گیرند و می‌تواند باعث دسترسی کندتر به حافظه شود (علاوه بر این در مثال بالا، برای انجام چهار مراجعهٔ مورد نیاز، نیازمند محاسبهٔ آدرس‌ها در داخل یک جدول هستیم).

جدول مراجعه در پردازش تصاویر

در موارد آنالیز داده، نظیر پردازش تصویر، جدول مراجعه برای تبدیل دادهٔ ورودی به یک فرمت خروجی مطلوب تر استفاده می‌شود. برای مثال، برای جلوهٔ بیشتر تفاوت در حلقه ی‌های سیارهٔ زحل، تصویر طیف خاکستری از سیارهٔ زحل به تصویر رنگی تبدیل می‌شود. یک مثال کلاسیک برای کاهش محاسبات زمان اجرا با استفاده از جدول مراجعه، بدست آوردن نتیجهٔ یک محاسبهٔ مثلثاتی مثل مقدار سینوس است. محاسبهٔ توابع مثلثاتی می‌تواند به‌طور چشمگیری یک نرم‌افزار محاسباتی را کند کند. اگر همین نرم‌افزار، سینوس تعدادی از مقادیر، مثلاً تمام مقادیر کامل درجه‌ها را از پیش محاسبه کند، خیلی سریع تر اجرا و تمام می‌شود (جدول مورد نظر را می‌توان به شکل متغیرهای استاتیک در زمان اجرا تعریف کرد و بدین صورت، هزینهٔ زمان اجرای مکرر را کاهش داد). زمانیکه یک برنامه نیاز به سینوس یک مقدار داشته باشد، می‌تواند به جدول مراجعه کند تا نزدیک‌ترین مقدار سینوس را از یک آدرس حافظه استخراج کند و همچنین ممکن است مقدار سینوس مورد نظر را از بین دو مقدار جدول دریافت کند. در این حالت نیازی به محاسبه از طریق فرمول ریاضی نیست؛ بنابراین جدولهای مراجعه توسط پردازنده‌های جانبی مخصوص ریاضیات، در سیستم‌های کامپیوتری استفاده می‌شود. یک خطا در جدول مراجعه، عامل ایجاد باگ مشهور تقسیم ممیز شناور بود. توابع دارای یک متغیر (نظیر سینوس و کسینوس) ممکن است توسط یک آرایه پیاده‌سازی شوند. توابع حاوی دو یا بیش از دو متغیر نیازمند تکنیک‌های اندکس سازی آرایه ای چند بعدی هستند؛ بنابراین در مورد دوم ممکن است از یک آرایه دو بعدی مثلاً power[x][y] برای جایگزینی یک تابع محاسبه x^y برای یک محدوده از مقادیر x و y استفاده شود.

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

در توموگرافی محاسبه شده یا همان سی تی اسکن، اصطلاح پنجره به مفهومی مرتبط گفته می‌شود که مشخص می‌کند چطور شدت تشعشع اندازه‌گیری شده نمایش داده شود. اگرچه استفاده از جدول مراجعه معمولاً مؤثر است اما با این وجود ممکن است منجر به عواقب ناگواری شود، مخصوصاً اگر محاسبه ای که جدول مراجعه برای ما انجام می‌دهد نسبتاً ساده باشد. زمان استخراج از حافظه و پیچیدگی نیازمندی‌های حافظه می‌تواند زمان عملیات نرم‌افزار و پیچیدگی سیستم را در مقایسه با زمان مورد نیاز برای محاسبه مستقیم از طریق فرمول افزایش دهد. همچنین احتمال آلوده شدن کش نیز ممکن است مشکل ساز شود. دسترسی به جدول برای جدول‌های بزرگ قطعاً منجر به خطا (miss) در کش می‌شود. این پدیده به‌طور فزاینده‌ای مشکل ساز شده‌است، زیرا پردازنده‌ها از حافظه سبقت گرفته‌اند. یک مشکل مشابه در مورد محاسبهٔ مجدد (rematerialization) نیز رخ می‌دهد که یک بهینه‌سازی کامپایلر است. در برخی محیط‌ها نظیر زبان برنامه‌نویسی جاوا، جدولهای مراجعه می‌توانند حتی هزینهٔ بیشتری داشته باشند که دلیل آن چک کردن اجباری محدوده است که باعث مقایسه و انشعاب اضافه برای هر مراجعه می‌شود.

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

پانویس

مشارکت‌کنندگان ویکی‌پدیا. «Lookup table». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳۰ دسامبر ۲۰۲۰.