جدول البحث

في عملية بحث بسيطة باستخدام دالة التجزئة ، تُستخدم قيمة البيانات الأولية غير الموقعة مباشرةً كمؤشر لجدول أحادي البعد لاستخراج النتيجة. بالنسبة للنطاقات الصغيرة، قد تكون هذه الطريقة من بين أسرع عمليات البحث، حتى أنها تتجاوز سرعة البحث الثنائي بدون أي تفرعات وتُنفذ في وقت ثابت . ^{[ 7 ]}

دالة ` count_ones` تأخذ عددًا صحيحًا غير مُوقّع ` x` كمدخل ، وتُعيد النتيجة .​​​​​​​​​​​​​​​​​​​​​​

دالة `count_ones` تأخذ مُدخلًا من نوع `int` وتُمرر إليه قيمة الإدخال `input_value` . تُعرّف الدالة `union` على النحو التالي: `four_bytes` ، حيث `int` عدد صحيح كبير ، و`char` عدد بايتات من أربعة . ثم تُعيّن قيمة `operand` إلى قيمة الإدخال `input_value` . const int bits_set [ 256 ] = { 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 1 , 2 , 2 , 3 , 2 , 3 , 3 , 4 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 2 , 3 , 3 , 4 , 3 , 4 , 4 , 5 , 3 , } ٤ ، ٤ ، ٥ ، ٤ ، ٥ ، ٥ ، ٦ ، ١ ، ٢ ، ٢ ، ٣ ، ٢ ، ٣ ، ٣ ، ٤ ، ٢ ، ٣ ، ٣ ، ٤ ، ٣ ، ٤ ، ٤ ، ٥ ، ٢ ، ٣ ، ٣ ، ٤ ، ٣ ، ٤ ، ٤ ، ٥ ، ٣، 4 ، 4 ، 5 ، 4 ، 5 ، 5 ، 6 ، 2 ، 3 ، 3 ، 4 ، 3 ، 4 ، 4 ، 5 ، 3 ، 4 ، 4 ، 5 ، 4 ، 5 ، 5 ، 6 ، 4 ، 5 ، 5 ، 6 ، 5 ، 6 ، 6 ، 7 ، 1 ، 2 ، 2 ، 3 ، 2 ، 3 ، 3 ، 4 ، 2 ، 3 ، 3 ، 4 ، 3 ، 4 ، 4 ، 5 ، 2 ، 3 ، 3 ، 4 ، 3 ، 4 ،​​​​​​​​​​​​​​​​٤ ، ٥ ، ٣ ، ٤ ، ٤ ، ٥ ، ٤ ، ٥ ، ٥ ، ٦ ، ٢ ، ٣ ، ٣ ، ٤ ، ٣ ، ٤ ، ٤ ، ٥ ، ٣ ، ٤ ، ٤ ، ٥ ، ٤ ، ٥ ، ٥ ، ٦ ، ٣ ، ٤ ، ٤ ، ٥ ، ٤ ، ٥ ، ٥ ، ٦ ، ٤ ، ٥ ، ٥ ، ٦ ، ٥ ، ٦ ، ٦ ، ٧ ، ٢ ، ٣ ، ٣ ، ٤, 3 , 4 , 4 , 5 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 3 , 4 , 4 , 5 , 4 , 5 , 5 , 6 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 4 , 5 , 5 , 6 , 5 , 6 , 6 , 7 , 5 , 6 , 6 , 7 , 6 , 7 , 7 , 8 } ; return ( bits_set [ operand . each_byte [ 0 ]] + bits_set [ operand . each_byte [ 1 ]] + bits_set [ operand . each_byte [ 2 ]] + bits_set [ operand . each_byte [ 3 ]]); }}

تُعدّ جداول البحث (LUTs) تقنية ممتازة لتحسين تقييم الدوال التي تتطلب حسابًا مكلفًا وتخزينًا مؤقتًا غير مكلف. ... بالنسبة لطلبات البيانات التي تقع بين عينات الجدول، يمكن لخوارزمية الاستيفاء توليد تقريبات معقولة عن طريق حساب متوسط ​​العينات القريبة. ^{[ 9 ]}

في تطبيقات تحليل البيانات، مثل معالجة الصور ، يمكن استخدام جدول بحث (LUT) لتحويل بيانات الإدخال إلى تنسيق إخراج أكثر ملاءمة. على سبيل المثال، يمكن تحويل صورة رمادية لكوكب زحل إلى صورة ملونة لإبراز الاختلافات في حلقاته.

في معالجة الصور، تُعرف جداول البحث عادةً باسم LUT (أو 3DLUT)، وتُعطي قيمة إخراج لكل قيمة من نطاق قيم الفهرس. يُستخدم أحد جداول البحث الشائعة، والذي يُسمى خريطة الألوان أو لوحة الألوان ، لتحديد الألوان وقيم الشدة التي ستُعرض بها صورة معينة. في التصوير المقطعي المحوسب ، يُشير مصطلح "التحديد المكاني" إلى مفهوم ذي صلة لتحديد كيفية عرض شدة الإشعاع المقاس.

من الأمثلة الكلاسيكية على تقليل وقت الحساب باستخدام جداول البحث، الحصول على نتيجة عملية حسابية مثلثية ، مثل جيب قيمة معينة. ^{[ 10 ]} قد يؤدي حساب الدوال المثلثية إلى إبطاء تطبيق حاسوبي بشكل ملحوظ. يمكن للتطبيق نفسه أن ينهي عمله بشكل أسرع بكثير إذا قام مسبقًا بحساب جيب عدد من القيم، على سبيل المثال لكل عدد صحيح من الدرجات (يمكن تعريف الجدول كمتغيرات ثابتة في وقت الترجمة، مما يقلل من تكاليف وقت التشغيل المتكررة). عندما يحتاج البرنامج إلى جيب قيمة ما، يمكنه استخدام جدول البحث لاسترجاع أقرب قيمة جيب من عنوان ذاكرة، وقد يقوم أيضًا بالاستيفاء للوصول إلى جيب القيمة المطلوبة، بدلًا من الحساب باستخدام صيغة رياضية. وبالتالي، يمكن استخدام جداول البحث بواسطة المعالجات المساعدة الرياضية في أنظمة الحاسوب. كان خطأ في جدول البحث مسؤولًا عن خطأ قسمة الأعداد العشرية الشهير في شركة إنتل .

يمكن تمثيل الدوال التي تستخدم متغيرًا واحدًا (مثل الجيب وجيب التمام) باستخدام مصفوفة بسيطة. أما الدوال التي تستخدم متغيرين أو أكثر، فتتطلب تقنيات فهرسة متعددة الأبعاد. في هذه الحالة، يمكن استخدام مصفوفة ثنائية الأبعاد من نوع power[x][y] بدلاً من دالة لحساب x و ^y لنطاق محدود من قيم x و y. ويمكن تمثيل الدوال التي لها أكثر من نتيجة واحدة باستخدام جداول بحث عبارة عن مصفوفات من هياكل البيانات.

كما ذُكر، توجد حلول وسيطة تستخدم الجداول مع قدر ضئيل من العمليات الحسابية، وغالبًا ما تستخدم الاستيفاء . يمكن للحساب المسبق مع الاستيفاء أن يُحسّن دقة القيم الواقعة بين قيمتين محسوبتين مسبقًا. تتطلب هذه التقنية وقتًا أطول قليلًا، لكنها تُحسّن الدقة بشكل كبير في التطبيقات التي تتطلب ذلك. اعتمادًا على القيم المحسوبة مسبقًا، يمكن أيضًا استخدام الحساب المسبق مع الاستيفاء لتقليص حجم جدول البحث مع الحفاظ على الدقة.

على الرغم من فعالية استخدام جداول البحث في كثير من الأحيان، إلا أنه قد يؤدي إلى تكلفة باهظة إذا كانت العملية الحسابية التي يحل محلها جدول البحث بسيطة نسبيًا. إذ يمكن أن يؤدي وقت استرجاع البيانات من الذاكرة وتعقيد متطلباتها إلى زيادة وقت تشغيل التطبيق وتعقيد النظام مقارنةً بما يتطلبه حساب الصيغ مباشرةً. كما قد يُشكل احتمال تلوث ذاكرة التخزين المؤقت مشكلةً أيضًا، حيث أن الوصول إلى الجداول الكبيرة سيؤدي حتمًا إلى عدم العثور على البيانات في ذاكرة التخزين المؤقت . وتزداد هذه الظاهرة حدةً مع تفوق سرعة المعالجات على سرعة الذاكرة. وتظهر مشكلة مماثلة في إعادة التجسيد ، وهي إحدى تقنيات تحسين المُصرّف . في بعض بيئات البرمجة، مثل لغة جافا ، قد تكون عمليات البحث في الجداول أكثر تكلفةً نظرًا لضرورة التحقق من الحدود، والذي يتضمن مقارنةً وتفرعًا إضافيين لكل عملية بحث.

هناك قيدان أساسيان على إمكانية إنشاء جدول بحث لعملية مطلوبة. الأول هو مقدار الذاكرة المتاحة: لا يمكن إنشاء جدول بحث أكبر من المساحة المتاحة له، مع أنه من الممكن إنشاء جداول بحث على القرص، ولكن على حساب وقت البحث. أما الثاني فهو الوقت اللازم لحساب قيم الجدول في البداية؛ مع أن هذا عادةً ما يُجرى مرة واحدة فقط، إلا أنه إذا استغرق وقتًا طويلاً جدًا، فقد يجعل استخدام جدول البحث حلاً غير مناسب. وكما ذُكر سابقًا، يمكن تعريف الجداول بشكل ثابت في كثير من الحالات.

معظم أجهزة الكمبيوتر لا تُجري سوى العمليات الحسابية الأساسية، ولا تستطيع حساب جيب قيمة معينة مباشرةً. بدلاً من ذلك، تستخدم خوارزمية CORDIC أو صيغة معقدة مثل متسلسلة تايلور التالية لحساب قيمة الجيب بدقة عالية: ^{[ 11 ] : 5}

${\displaystyle \operatorname {sin} (x)\approx x-{\frac {x^{3}}{6}}+{\frac {x^{5}}{120}}-{\frac {x^{7}}{5040}}}$(عندما تكون قيمة x قريبة من الصفر)

مع ذلك، قد تكون هذه العملية مكلفة حسابيًا، خاصةً على المعالجات البطيئة، وهناك العديد من التطبيقات، لا سيما في رسومات الحاسوب التقليدية ، التي تتطلب حساب آلاف قيم الجيب كل ثانية. يتمثل الحل الشائع في حساب جيب العديد من القيم الموزعة بالتساوي في البداية، ثم لإيجاد جيب x، نختار جيب القيمة الأقرب إلى x من خلال عملية فهرسة المصفوفة. ستكون هذه القيمة قريبة من القيمة الصحيحة لأن الجيب دالة متصلة ذات معدل تغير محدود. ^{[ 11 ] : 6} على سبيل المثال: ^{[ 12 ] : 545-548}

مصفوفة حقيقية sine_table [ -1000 .. 1000 ] لكل x من -1000 إلى 1000 sine_table [ x ] = sine ( pi * x / 1000 )​​دالة lookup_sine ( x ) تُرجع جدول_الجيب [ تقريب ( 1000 * x / π )]

لسوء الحظ، يتطلب الجدول مساحة تخزين كبيرة: فإذا استخدمنا أرقام الفاصلة العائمة ذات الدقة المزدوجة وفقًا لمعيار IEEE، فسنحتاج إلى أكثر من 16000 بايت. يمكننا استخدام عدد أقل من العينات، لكن دقة النتائج ستتراجع بشكل ملحوظ. أحد الحلول الجيدة هو الاستيفاء الخطي ، الذي يرسم خطًا بين النقطتين في الجدول على جانبي القيمة، ويحدد موقع الإجابة على هذا الخط. لا يزال هذا الحل سريعًا في الحساب، وأكثر دقة بكثير للدوال السلسة مثل دالة الجيب. إليك مثال على استخدام الاستيفاء الخطي:

دالة lookup_sine ( x ) x1 = floor ( x * 1000 / pi ) y1 = sine_table [ x1 ] y2 = sine_table [ x1 + 1 ] return y1 + ( y2 - y1 ) * ( x * 1000 / pi - x1 )

يُتيح الاستيفاء الخطي الحصول على دالة مُستوفاة متصلة، ولكنها لا تمتلك، بشكل عام، مشتقات متصلة . وللحصول على استيفاء أكثر سلاسة لبيانات البحث في الجداول، بحيث تكون متصلة ولها مشتقة أولى متصلة ، يُنصح باستخدام دالة هيرميت التكعيبية .

عند استخدام الاستيفاء، يمكن تقليل حجم جدول البحث باستخدام أخذ عينات غير منتظمة ، ما يعني أنه عندما تكون الدالة قريبة من الخط المستقيم، نستخدم عددًا قليلًا من نقاط العينة، بينما عندما تتغير قيمتها بسرعة، نستخدم عددًا أكبر من نقاط العينة للحفاظ على التقريب قريبًا من المنحنى الحقيقي. لمزيد من المعلومات، انظر الاستيفاء .

تعمل ذاكرات التخزين المؤقتة (بما في ذلك ذاكرات التخزين المؤقتة للقرص للملفات، أو ذاكرات التخزين المؤقتة للمعالج للتعليمات البرمجية أو البيانات) كجدول بحث. يُبنى هذا الجدول باستخدام ذاكرة فائقة السرعة بدلاً من تخزينه على ذاكرة خارجية أبطأ، ويحتفظ بجزأين من البيانات لنطاق فرعي من البتات التي تُكوّن عنوان ذاكرة خارجية (أو قرص) (وخاصةً البتات الأدنى لأي عنوان خارجي ممكن):

• يحتوي جزء واحد (العلامة) على قيمة البتات المتبقية من العنوان؛ إذا تطابقت هذه البتات مع تلك الموجودة في عنوان الذاكرة المراد قراءته أو كتابته، فإن الجزء الآخر يحتوي على القيمة المخزنة مؤقتًا لهذا العنوان.
• أما الجزء الآخر فيحتفظ بالبيانات المرتبطة بذلك العنوان.

يتم إجراء بحث سريع واحد لقراءة الوسم في جدول البحث عند الفهرس المحدد بواسطة البتات الأدنى من عنوان التخزين الخارجي المطلوب، ولتحديد ما إذا كان عنوان الذاكرة موجودًا في ذاكرة التخزين المؤقت. عند العثور على عنوان موجود، لا يلزم الوصول إلى الذاكرة الخارجية (باستثناء عمليات الكتابة، حيث قد يلزم تحديث القيمة المخزنة مؤقتًا بشكل غير متزامن إلى الذاكرة الأبطأ بعد فترة من الزمن، أو إذا كان يجب استبدال الموضع في ذاكرة التخزين المؤقت لتخزين عنوان آخر).

في الدوائر المنطقية الرقمية ، يمكن تنفيذ جدول البحث باستخدام مُضاعِف إشارات ، حيث تُشغَّل خطوط الاختيار فيه بإشارة العنوان، وتكون مدخلاته هي قيم العناصر الموجودة في المصفوفة. يمكن أن تكون هذه القيم ثابتة، كما هو الحال في الدوائر المتكاملة الخاصة بالتطبيقات (ASIC) التي يكون غرضها محددًا لوظيفة معينة، أو يمكن توفيرها بواسطة دوائر D التي تسمح بقيم قابلة للتهيئة (مثل ذاكرة القراءة فقط ROM ، أو ذاكرة القراءة فقط القابلة للمسح والبرمجة EPROM ، أو ذاكرة القراءة فقط القابلة للمسح والبرمجة كهربائيًا EEPROM ، أو ذاكرة الوصول العشوائي RAM ).

يمكن لجدول بحث (LUT) ذي n بت أن يُشفّر أي دالة منطقية ذات n مدخلات عن طريق تخزين جدول الحقيقة الخاص بالدالة في جدول البحث. تُعد هذه طريقة فعّالة لتشفير الدوال المنطقية ، وتُعتبر جداول البحث ذات 4-6 بتات من المدخلات في الواقع المكون الرئيسي لمصفوفات البوابات المنطقية القابلة للبرمجة الميدانية (FPGAs) الحديثة التي توفر إمكانيات إعادة تكوين منطق الأجهزة.

في أنظمة جمع البيانات والتحكم بها ، تُستخدم جداول البحث بشكل شائع لإجراء العمليات التالية في:

• تطبيق بيانات المعايرة ، وذلك لإجراء تصحيحات على القياسات غير المعايرة أو قيم نقاط الضبط ؛ و
• إجراء تحويل وحدات القياس ؛ و
• إجراء عمليات حسابية عامة يحددها المستخدم.

في بعض الأنظمة، يمكن أيضًا تعريف كثيرات الحدود بدلاً من جداول البحث لهذه الحسابات.