नई पुस्तक-सॉर्टिंग एल्गोरिदम, लगभग परफेक्ट प्रदर्शन

 (quantamagazine.org)
2 पॉइंट द्वारा GN⁺ 2025-01-26 | 1 टिप्पणियां | WhatsApp पर शेयर करें

परिचय

  • नया एल्गोरिदम यह दिखाता है कि लाइब्रेरी सॉर्टिंग समस्या को कैसे हल किया जा सकता है।
  • यह समस्या केवल किताबों को क्रम में लगाने तक सीमित नहीं है, बल्कि hard drive और database में file arrangement पर भी लागू होती है।
  • नया approach बुकशेल्फ़ की पिछली सामग्री और randomness को मिलाकर सैद्धांतिक आदर्श के करीब परिणाम देता है।

सीमाएँ संकरी करना

  • अच्छी तरह सॉर्ट की गई बुकशेल्फ़ को मापने का एक सामान्य तरीका यह देखना है कि individual item को insert करने में कितना समय लगता है।
  • 1981 के एक paper ने यह सवाल उठाया था कि क्या ऐसा एल्गोरिदम बनाया जा सकता है जिसका average insertion time, n से बहुत कम हो।
  • 2004 के research में पाया गया कि लाइब्रेरी सॉर्टिंग समस्या की optimal lower bound, log n है।
  • यह भी दिखाया गया कि smooth या deterministic एल्गोरिदम के साथ average insertion time में (log n)² से बेहतर प्रदर्शन हासिल नहीं किया जा सकता।

रहस्यमय इतिहास

  • 2022 में, Bender और उनके साथियों ने random और non-smooth एल्गोरिदम आज़माया, जिससे average insertion time घटकर (log n)¹.⁵ हो गया।
  • यह एल्गोरिदम बुकशेल्फ़ के पुराने रिकॉर्ड पर निर्भर नहीं करता, जो security कारणों से उपयोगी हो सकता है।

अंतर कम करना

  • Bender और Kuszmaul ने upper bound को घटाकर (log n) × (log log n)³ कर दिया, जो सैद्धांतिक lower bound के बहुत करीब है।
  • यह एल्गोरिदम सीमित स्तर की history dependence का उपयोग करके भविष्य की घटनाओं की योजना बनाता है।
  • यह नतीजा पिछले research पर आधारित है, लेकिन randomness का उपयोग पूरी तरह अलग तरीके से करता है।

निष्कर्ष

  • यह research सैद्धांतिक दृष्टि से एक महत्वपूर्ण सुधार दिखाती है, और applications के लिहाज़ से भी बड़े सुधार की संभावना रखती है।
  • फिर भी log log n term अब भी पूरी तरह समाधान तक पहुँचने में बाधा है, और इसका हल upper bound को घटाना या lower bound को बढ़ाना हो सकता है।

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-01-26
Hacker News राय

  • यह दिलचस्प है कि performance सुधारने के लिए cryptographic techniques का इस्तेमाल किया जा सकता है। performance का मतलब सिर्फ अधिक instructions चलाना नहीं है, बल्कि यह चुनना है कि काम कम कैसे किया जाए। "history independence" नाम का security property यह दर्शाता है कि अतीत को ट्रैक करने का काम नहीं किया जाता

  • लेख में जिन मुख्य papers का ज़िक्र है, उन्हें ढूँढना मुश्किल है। अगर Quanta लेख के अंत में सभी references सूचीबद्ध करे, तो यह पाठकों के लिए मददगार होगा

  • database table में items को arbitrary तरीके से रखने की समस्या को हल करने के लिए जटिल algorithms मौजूद हैं। लेकिन इस समस्या का एक सरल समाधान fractional values का उपयोग करना और कभी-कभी list को फिर से व्यवस्थित करना है

  • याद है कि मैंने छात्रों को 'Library Sort' algorithm के आधार पर यह समस्या दी थी। मूल paper का शीर्षक 'Insertion Sort is O(n log n)' है

  • संदेह है कि क्या इसके सच में अभी उपयोग में मौजूद algorithms से तेज़ होने का कोई कारण है। B-tree node की array में memmove() का उपयोग ज़्यादा तेज़ हो सकता है। बड़े arrays के लिए B tree का उपयोग करना ज़्यादा आसान है

  • सोच रहा हूँ कि क्या problem statement fixed-length preallocated array मानकर चलती है

  • यह देखकर आश्चर्य हुआ कि British Library किताबों को कैसे संभालती है। जब कोई किताब पहुँचती है, तो electronic catalog बाकी काम संभाल लेता है, इसलिए किताबों को फिर से व्यवस्थित करने की ज़रूरत नहीं पड़ती

  • लेख के ऊपर वाला animation screensaver के रूप में बनाना चाहता हूँ

  • mobile users के लिए साफ़ links

  • upper bound को (log n) गुणा (log log n)^3 तक घटाना ही असली बात है। polynomial reference classes का उपयोग करने वाली big-O complexity में logs का infinitesimal values देना दिलचस्प है