في ورقة عام 1985 ، أكد عالم الكمبيوتر أندرو ياو ، الذي سيستمر في الفوز بجائزة Am Turing ، أنه من بين طاولات التجزئة التي تحتوي على مجموعة محددة من الخصائص ، فإن أفضل طريقة للعثور على عنصر فردي أو بقعة فارغة هي فقط المرور من خلال المواقع المحتملة بشكل عشوائي – وهو نهج يُعرف باسم التحقيق الموحد. وذكر أيضًا أنه في أسوأ سيناريو ، حيث تبحث عن آخر بقعة مفتوحة ، لا يمكنك أبدًا أن تفعل أفضل من x. لمدة 40 عامًا ، افترض معظم علماء الكمبيوتر أن تخمين Yao كان صحيحًا.
لم يتم الاحتفاظ بالكرابفين بالحكمة التقليدية لسبب بسيط هو أنه لم يكن على دراية به. قال: “لقد فعلت هذا دون أن أعرف عن تخمين Yao”. أدت استكشافاته مع مؤشرات صغيرة إلى نوع جديد من طاولة التجزئة – واحد لم يعتمد على التحقيق الموحد. وللوحد التجزئة الجديد ، يتناسب الوقت اللازم للاستعلامات والإدراج الأسوأ مع (LOGH x)2– أسرع من x. هذه النتيجة تتناقض بشكل مباشر مع تخمين ياو. ساعد Farach-Colton و Kuszmaul Krapivin في إظهار ذلك (سجل x)2 هو المركز الأمثل الذي لا يهزم للفئة الشهيرة من جداول التجزئة التي كتبتها Yao.
وقال جاي بليلوش من كارنيجي ميلون: “هذه النتيجة جميلة من حيث أنها تتناول ويحل هذه المشكلة الكلاسيكية”.
وقال Sepehr Assadi من جامعة واترلو: “لا يقتصر الأمر على دحضهم (تخمين ياو) ، فقد وجدوا أيضًا أفضل إجابة ممكنة على سؤاله”. “كان بإمكاننا أن نذهب إلى 40 عامًا أخرى قبل أن نعرف الإجابة الصحيحة.”
بالإضافة إلى دحض تخمين Yao ، تحتوي الورقة الجديدة أيضًا على ما يعتبره الكثيرون نتيجة أكثر إثارة للدهشة. يتعلق الأمر بالوضع المرتبط ، وإن كان مختلفًا قليلاً ،: في عام 1985 ، لم ينظر Yao إلى أسوأ أوقات الحالات للاستعلامات ، ولكن أيضًا في متوسط الوقت الذي يستغرقه جميع الاستعلامات الممكنة. لقد أثبت أن جداول التجزئة ذات خصائص معينة – بما في ذلك تلك التي تم تصنيفها “الجشع” ، مما يعني أنه يجب وضع عناصر جديدة في المكان الأول المتاح – لن يحقق وقتًا متوسطًا أفضل من السجل x.
أراد Farach-Colton و Krapivin و Kuszmaul معرفة ما إذا كان هذا الحد نفسه ينطبق أيضًا على طاولات التجزئة غير الخضراء. لقد أظهروا أنه لم يفعل ذلك من خلال توفير مثال مضاد ، طاولة تجزئة غير غريدي مع متوسط وقت استعلام أفضل بكثير من السجل x. في الواقع ، لا يعتمد على x على الإطلاق. قال فاراش كولتون: “ستحصل على رقم ، وهو أمر ثابت ولا يعتمد على مدى امتلاء جدول التجزئة”. كانت حقيقة أنه يمكنك تحقيق وقت استفسار ثابت ، بغض النظر عن امتلاء جدول التجزئة ، غير متوقع تمامًا – حتى للمؤلفين أنفسهم.
وقال كونواي إن نتائج الفريق قد لا تؤدي إلى أي طلبات فورية ، لكن هذا ليس كل ما يهم. “من المهم فهم هذه الأنواع من هياكل البيانات بشكل أفضل. أنت لا تعرف متى ستؤدي نتيجة مثل هذه إلى إلغاء قفل شيء يتيح لك القيام بعمل أفضل في الممارسة “.
القصة الأصلية أعيد طبعه بإذن من مجلة Quanta ، منشور مستقل تحريري لـ مؤسسة سيمونز تتمثل مهمتها في تعزيز الفهم العام للعلوم من خلال تغطية التطورات البحثية والاتجاهات في الرياضيات والعلوم المادية والحياة.
