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

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

مثال ها

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

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

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

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

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

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

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

یک مساله ی گسسته که در بسیاری از کامپیوتر ها با هزینه ی زیادی قابل حل است، شمارش تعداد بیت های برابر 1 در یک عدد باینری است، که گاهی به آن تابع جمعیت گویند. برای مثال، عدد دسیمال 37 به شکل باینری برابر 00100101 است، بنابراین دارای سه بیت برابر 1 است.

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

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

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

/* 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] برای جایگزینی یک تابع محاسبه xy برای یک محدوده از مقادیر   x و y استفاده شود.

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

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

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

پانویس

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

  1. McNamee, Paul (August 21, 1998). "Automated Memoization in C++". Archived from the original on 2019-04-16.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.