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

 (quantamagazine.org)
2 पॉइंट द्वारा GN⁺ 2025-01-26 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • लाइब्रेरी सॉर्टिंग समस्या सिर्फ़ किताबों की अलमारी व्यवस्थित करने तक सीमित नहीं है; यह हार्ड ड्राइव और डेटाबेस में क्रमिक स्टोरेज की लागत को भी प्रभावित करती है, और नया शोध औसत insertion time को सैद्धांतिक सीमा के बहुत करीब तक घटाता है
  • 1981 का एल्गोरिद्म deterministic और smooth था, और औसत insertion time ((log n)^2) की गारंटी देता था, लेकिन 40 से अधिक वर्षों तक इससे कम कोई upper bound नहीं आया
  • बाद के lower-bound शोध ने दिखाया कि सामान्य एल्गोरिद्म के लिए सबसे अच्छा परिणाम (log n) है, जबकि smooth एल्गोरिद्म और deterministic एल्गोरिद्म की सीमा ((log n)^2) है, इसलिए randomized और non-smooth दृष्टिकोण की ज़रूरत पड़ी
  • 2022 में Bender, Kuszmaul आदि ने history independent randomized एल्गोरिद्म के साथ upper bound को ((log n)^{1.5}) तक घटाया, और नवीनतम शोध ने सीमित past information का उपयोग करके ((log n)(log log n)^3) हासिल किया
  • बचा हुआ अंतर सिर्फ़ (log log n) पद का है, और यह प्रगति list labeling आधारित dynamic graph storage और processing जैसे अनुप्रयोगों को तेज़ बना सकती है

लाइब्रेरी सॉर्टिंग समस्या क्या पूछती है

  • लाइब्रेरी सॉर्टिंग समस्या यह है कि sorted order बनाए रखते हुए नया item जोड़ते समय आवश्यक movement time को न्यूनतम कैसे किया जाए
  • अगर किताबों को एक तरफ़ ठूंसकर रखा जाए, तो बीच में नई किताब डालने पर बहुत-सी किताबें फिर से खिसकानी पड़ सकती हैं
    • Isabel Allende की किताब जोड़ते समय पूरी शेल्फ़ खिसकानी पड़ सकती है
    • उसके बाद Douglas Adams की किताब जोड़ने पर वही काम फिर दोहराना पड़ सकता है
  • अगर खाली जगह को पूरी शेल्फ़ में सही तरह से फैलाया जाए, तो insertion cost कम की जा सकती है, लेकिन मुख्य सवाल यह है कि जगह कहाँ और कितनी छोड़ी जाए
  • अधिक औपचारिक रूप में इसे list labeling समस्या कहा जाता है, जिसे 1981 के पेपर में पेश किया गया था
  • इसका उपयोग किताबों की अलमारी से आगे बढ़कर हार्ड ड्राइव और डेटाबेस में फ़ाइलों और items की व्यवस्था तक जाता है
    • items की संख्या अरबों तक हो सकती है
    • अक्षम व्यवस्था लंबा wait time और बड़ी computational cost पैदा कर सकती है

upper bound और lower bound से प्रदर्शन को समझना

  • sorted arrangement का प्रदर्शन आमतौर पर इस आधार पर मापा जाता है कि एक नया item insert करने में कितना समय लगता है
  • जब items की संख्या (n) हो, और सभी किताबें खिसकानी पड़ें, तो insertion time (n) के अनुपात में होगा
    • इसे नया item जोड़ने में लग सकने वाले समय का upper bound माना जा सकता है
  • 1981 के पेपर ने पूछा था कि क्या औसत insertion time को (n) से बहुत कम किया जा सकता है, और उसने ((log n)^2) की गारंटी देने वाला एल्गोरिद्म दिया
    • यह randomness पर निर्भर न करने वाला deterministic एल्गोरिद्म था
    • इसमें smooth गुण था, यानी जिस interval में insertion या deletion हो रही हो, वहाँ items काफ़ी समान रूप से फैले रहें
  • शोधकर्ता upper bound और lower bound के बीच के अंतर को कम करते हैं, और जब दोनों मिल जाते हैं, तब एल्गोरिद्म को optimal माना जाता है

पहले के lower-bound नतीजों से बनी सीमाएँ

  • 2004 के शोध ने दिखाया कि लाइब्रेरी सॉर्टिंग समस्या के सबसे सामान्य संस्करण में कोई भी एल्गोरिद्म (log n) से बेहतर नहीं हो सकता; यही ultimate lower bound है
  • 1990 में यह स्थापित हुआ कि smooth एल्गोरिद्म के लिए lower bound ((log n)^2) है
  • 2012 में यह नतीजा भी आया कि randomness का उपयोग न करने वाले deterministic एल्गोरिद्म का भी वही lower bound ((log n)^2) है
  • इन नतीजों का मतलब था कि केवल smooth या deterministic एल्गोरिद्म के सहारे 1981 के ((log n)^2) upper bound को बेहतर बनाना मुश्किल है
  • Michael Bender ने निष्कर्ष निकाला कि बेहतर परिणाम के लिए randomized और non-smooth एल्गोरिद्म चाहिए
    • non-smooth तरीका सहज रूप से जोखिमभरा लगा, क्योंकि इसमें items को समान रूप से नहीं फैलाया जाता
    • randomness मदद क्यों करेगी, यह भी साफ़ नहीं था

2022: history independent तरीके से upper bound घटा

  • Bender, William Kuszmaul और अन्य 6 शोधकर्ताओं ने 2022 में history independent, non-smooth, randomized एल्गोरिद्म बनाया
  • history independent एल्गोरिद्म शेल्फ़ की पुरानी स्थिति को उजागर नहीं करता
    • Kuszmaul ने उदाहरण दिया कि अगर शेल्फ़ से कोई किताब हटाई गई हो, तो कोई दूसरा व्यक्ति यह जान न सके कि वह पहले वहाँ थी
    • ऐसी विशेषता privacy या security कारणों से उपयोगी हो सकती है
  • इस एल्गोरिद्म ने 1981 के upper bound को पहली बार घटाकर औसत insertion time ((log n)^{1.5}) कर दिया
  • Kuszmaul को यह बात अप्रत्याशित लगी कि आमतौर पर privacy के लिए इस्तेमाल होने वाला tool एल्गोरिद्म को तेज़ भी बना सकता है
  • Georgia Institute of Technology की Helen Xu ने कहा कि security के अलावा history independence का उपयोग करने का विचार दूसरी समस्याओं को भी प्रभावित कर सकता है

नवीनतम शोध: सीमित past information और randomness का संयोजन

  • Bender, Kuszmaul आदि ने नवीनतम पेपर में upper bound को फिर घटाकर ((log n)(log log n)^3) कर दिया
  • यह मान ((log n)^{1.000…1}) के बराबर है, यानी ultimate lower bound (log n) के बहुत करीब
  • नया तरीका भी non-smooth और randomized है, लेकिन इस बार इसमें सीमित history dependence का उपयोग किया गया है
  • एल्गोरिद्म अतीत के कुछ रुझानों को देखकर भविष्य के insertions की तैयारी करता है
    • अगर Nabokov, Neruda और Ng जैसे N से शुरू होने वाले surname वाले लेखकों की किताबें बहुत आई हों, तो N वाले हिस्से में थोड़ा अधिक खाली स्थान रखा जाता है
    • लेकिन अगर बहुत ज़्यादा जगह reserve कर दी जाए, तो A से शुरू होने वाले surname वाले लेखकों की किताबें अधिक आने पर समस्या हो सकती है
  • Bender के अनुसार, यह तरीका इसलिए उपयोगी बना क्योंकि एल्गोरिद्म निर्णय लेते समय यह भी रणनीतिक रूप से randomize करता है कि अतीत का कितना हिस्सा देखा जाए
  • Seth Pettie ने कहा कि यह शोध 2022 के पेपर से बिल्कुल अलग तरीके से randomness का उपयोग करता है

बचा हुआ अंतर और संभावित अनुप्रयोग

  • अब बचा हुआ अंतर छोटा-सा (log log n) पद है
  • Bender का कहना है कि अभी यह स्पष्ट नहीं है कि upper bound को और घटाना चाहिए या lower bound को ऊपर ले जाना चाहिए
  • Pettie का मानना है कि जब अंतर इतना कम हो, और एक सीमा स्वाभाविक लगे जबकि दूसरी कुछ अस्वाभाविक, तो आमतौर पर स्वाभाविक सीमा ही सही उत्तर निकलती है
    • उनके अनुसार आगे का सुधार शायद upper bound को (log n) तक घटाने की दिशा में होगा
    • हालांकि उन्होंने यह भी जोड़ा कि “दुनिया अजीब आश्चर्यों से भरी हुई है”
  • University of Chicago के Brian Wheatman ने कहा कि ये पेपर सिद्धांत के स्तर पर काफ़ी बड़ा सुधार हैं, और अनुप्रयोगों में भी बड़े सुधार की संभावना है
  • Helen Xu ने कहा कि वह हाल में list labeling आधारित data structures से dynamic graph को store और process करने में रुचि ले रही थीं, और यह प्रगति उन्हें लगभग निश्चित रूप से तेज़ बनाएगी

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

1 टिप्पणियां

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

  • मुझे भी यह देखकर हैरानी हुई कि “privacy protection में इस्तेमाल होने वाला tool दूसरे फायदे भी दे सकता है”
    गहराई से देखें तो performance का बड़ा हिस्सा सचमुच “प्रति घंटे ज़्यादा instructions execute करने” का मामला नहीं, बल्कि कम काम करने का तरीका चुनने जैसा है
    यहां security property history independence का मतलब यह भी है कि “history track करने का काम करने की ज़रूरत भी नहीं है, और सचमुच किया भी नहीं जा सकता”, इसलिए cryptography को constraint की तरह इस्तेमाल करके गैरज़रूरी काम रोकने वाला एक दिलचस्प performance approach लगता है

    • यह व्याख्या सही नहीं लगती। अगर algorithm की slow-ness को computation time से मापा जाए तो यह सही होगा, लेकिन यहां वास्तविक metric उन किताबों की संख्या है जिन्हें स्थानांतरित करना पड़ता है
      मेरी समझ में model ऐसा है जिसमें computation time अनंत तक इस्तेमाल किया जा सकता है
    • अच्छी insight है। मैं सोचता आया हूं कि अच्छे algorithm/data structure design का मूल datasets में मौजूद सारी जानकारी का इस्तेमाल करना है
      उदाहरण के लिए, अगर पता हो कि list sorted है तो binary search इस्तेमाल कर सकते हैं। लेकिन शायद कितनी जानकारी छोड़नी है यह चुनना भी मूल बात हो सकती है। हालांकि ऐसे मामले कम दिखते हैं, और कोई सरल उदाहरण तुरंत याद नहीं आता
    • अंत में यह समस्या ऐसी लगती है कि algorithm “ज़्यादा मेहनत” नहीं बल्कि “ज़्यादा smart” तरीके से काम करे, इसके लिए problem context में से क्या selective रूप से छिपाया जा सकता है और छिपाया जाना चाहिए, यह ढूंढना है। अजीब है
    • असल में बेहतर algorithm history dependency का इस्तेमाल करता है। इसलिए मुझे लगता है कि article में यह हिस्सा कुछ हद तक भ्रम पैदा करता है

  • क्या मैं ही अकेला हूं जिसने article में बताए गए मुख्य papers, यानी original problem और लगभग optimal algorithm papers [1], [2] को खोजने की कोशिश की?
    दोनों शायद article के काफी अंदर link किए गए हैं, लेकिन अगर Quanta article के अंत में सभी references को अनिवार्य रूप से इकट्ठा रखे तो readers के लिए बहुत मददगार होगा
    [1] Nearly Optimal List Labeling:
    https://arxiv.org/abs/2405.00807
    [2] A sparse table implementation of priority queues:
    https://link.springer.com/chapter/10.1007/3-540-10843-2_34

    • दोनों papers article में बहुत साफ़ तौर पर link किए गए हैं, और पढ़े बिना सिर्फ़ skim करने पर भी जल्दी मिल सकते थे
      “This problem was introduced in a 1981 paper” में “1981 paper” https://link.springer.com/chapter/10.1007/3-540-10843-2_34 से जुड़ता है, और अगले paragraph में “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers” में “a study” https://arxiv.org/abs/2405.00807 से जुड़ता है
      दोनों introduction के तीसरे और चौथे paragraphs में हैं, details·history·context में जाने से पहले। अगर इसे “article के काफी अंदर” कहा जाए, तो काफी अंदर की परिभाषा काफ़ी अलग ही होगी

  • पिछले हफ्ते मैं ठीक यही problem देख रहा था। database table के items को arbitrary positions पर रखना था, लेकिन संभव हो तो बाकी list को छुए बिना
    जैसे user item 5 के बाद नया element जोड़ता है तो वह element 6 बन जाए, लेकिन जो item पहले 5 के बाद था उसे update न करना पड़े। इस problem को manage करने और theoretical limits को minimize करने वाले बहुत sophisticated algorithms वाकई मौजूद हैं
    हालांकि इस specific version में fractional indexes का इस्तेमाल करना और कभी-कभी list को rearrange करने की cost चुकाना सबसे सरल solution जैसा लगा

    • Wikipedia के exponential labels section में यह algorithm है: https://en.m.wikipedia.org/wiki/List-labeling_problem
      मूल रूप से अगर label space items की संख्या की तुलना में बड़ा हो तो यह अच्छा काम करता है। वरना ज़्यादा sophisticated method चाहिए। उदाहरण के लिए अगर labels में सिर्फ़ 4 bytes हों और items 1 अरब हों, तो समस्या होगी
    • मुझे यह problem interview question के रूप में हूबहू मिली थी
      जहां तक याद है, वास्तविक solution elements के बीच gap छोड़ने का था। जैसे 0, 1, 2 की जगह 0, 100, 200 रखना और ज़रूरत पड़ने पर फिर से indexing करना। यह पर्याप्त रूप से अच्छा काम करेगा लगता है
      मेरे मन में जो आया था वह, जैसा कहा गया, fractional indexing था; लेकिन decimals handle करना झंझट है, इसलिए उसे vector के रूप में represent किया जा सकता है, और इसे lexicographically sorted number string के रूप में दिखा सकते हैं
      1 और 2 के बीच insert हुआ element index 11 बनेगा। 11~19 के बीच कुछ भी हो सकता है। 1 और 11 के बीच हो तो 101, 11 और 2 के बीच हो तो 12, ऐसी बात है। लेकिन ये indexes numbers नहीं, बल्कि lexicographically compare होने वाली strings हैं
      कमियां भी ज़रूर होंगी। उदाहरण के लिए ऐसे indexes को sort करने में memory बहुत ज़्यादा लगेगी। strings numbers से कहीं बड़ी होती हैं। यह इतना clever लगता है कि unexpected downside न हो, ऐसा मुश्किल है
    • पुराने BASIC programs के line numbers जैसा है
    • सैद्धांतिक रूप से fractions को list labels की तरह इस्तेमाल करने के लिए fractions store करने में अनंत memory चाहिए
      असल में वह limit बहुत सीमित होती है, लेकिन अगर आप collection को केवल order labels नहीं दे रहे बल्कि इन labels को सीधे array indexes की तरह इस्तेमाल करके elements store करना चाहें, तो फर्क सचमुच समस्या बन जाता है। वही library sorting problem को ज़्यादा शाब्दिक रूप से model करने वाला रूप है
    • क्या वह hash table chaining नहीं है?

  • याद है कि कुछ साल पहले मैंने students को Library Sort algorithm पर आधारित problem present की थी
    original paper का title अभी भी साफ़ याद है: “Insertion Sort is O(n log n)”

  • मुझे यह जानने की उत्सुकता है कि क्या यह algorithm असल field में अभी इस्तेमाल होने वाले तरीकों से सचमुच तेज़ होने की कोई वजह रखता है
    मैंने यह problem ज़्यादातर B-tree node के array में देखी है, और वहाँ मुझे शक है कि यह सीधे memmove() इस्तेमाल करने से तेज़ होगा; और अगर array सच में बहुत बड़ा हो, तो शायद B-tree इस्तेमाल करना ही आसान होगा
    ऐसे में यह algorithm asymptotically तो तेज़ है, लेकिन paradoxically उन algorithms की category में आ जाता है जो real-world में इस्तेमाल होने वाले algorithms से धीमे होते हैं. इसका उदाहरण fast matrix multiplication algorithms हैं, जो अच्छे implementation वाले textbook O(n^3) algorithm (GEMM) से धीमे होते हैं

    • ऐसे algorithms को कभी-कभी Galactic Algorithms कहा जाता है: https://en.wikipedia.org/wiki/Galactic_algorithm
      page का पहला example usefulness को अच्छी तरह समझाने वाला quote रखता है
      “galactic algorithm के example के तौर पर, दो numbers को multiply करने का ज्ञात सबसे तेज़ तरीका 1729-dimensional Fourier transform पर आधारित है. इसमें सिर्फ O(n log n) bit operations चाहिए, लेकिन Big-O notation में छिपा constant इतना बड़ा है कि practically इसका इस्तेमाल नहीं होता. फिर भी यह दिखाता है कि ऐसे algorithms उपयोगी क्यों हो सकते हैं. authors कहते हैं, ‘हम उम्मीद करते हैं कि आगे के improvements से यह अरबों या खरबों digits वाले numbers के साथ भी practical हो जाएगा’”

  • upper bound को (log n) × (log log n)^3 तक घटाता है — जो (log n)^(1.000...1) के बराबर है वाली बात सही है
    polynomial आधार वाले परिवारों में Big-O complexity को देखने की अच्छी बातों में से एक यह है कि logarithm infinitesimal value देता है. “infinitesimals असल में exist नहीं करते” कहने वालों के लिए यह करारा जवाब है

    • रुको, क्या? इसे सीखने के लिए कोई reference material है क्या?

  • यह जानकर हैरानी हुई कि British Library लाखों books और हर हफ्ते आने वाली ढेरों नई books को कैसे manage करती है
    इस साल सबसे पहले आई book shelf की 2025.0000001 position पर रखी गई, और अगली book उसके ठीक बगल में 2025.0000002 पर रखी गई. बाकी काम electronic catalogue संभालता है
    books को फिर से shuffle करने की जरूरत नहीं पड़ती, लेकिन shelves के बीच घूमकर book ढूंढने के तरीके के लिए यह solution fit नहीं बैठता

    • इससे Amazon का वह तरीका याद आता है जिसमें वह चीज़ों को store की तरह similar items के साथ नहीं रखता. vacuum cleaner model के बगल में kitchen dinner set हो सकता है
      बल्कि वह जानबूझकर similarity से बचता है ताकि picker कोई मिलता-जुलता लेकिन गलत item न उठा ले
      घर पर भी मैं अक्सर भूल जाता हूँ कि कभी-कभार इस्तेमाल होने वाली चीज़ें कहाँ रखी हैं. जैसे x-acto blade refills किस closet के किस storage bin में रखे हैं. similar चीज़ों को साथ रखने की कोशिश में एक storage bin भर जाता है और दूसरा आधा खाली रह जाता है
      कभी-कभी सोचता हूँ कि अगर अपनी सारी belongings को spreadsheet में track करूँ और लिखूँ कि कौन-सी चीज़ किस storage bin में है, तो चीज़ें गुम नहीं होंगी और storage space भी maximum efficiency से use होगा. लेकिन नई चीज़ रखते समय update करना मैं पक्का भूल जाऊँगा, और यह तरीका इंसानों से ज़्यादा robots के लायक, अजीब तरह से non-human लगता है

  • article के top पर जो animation है, उससे screensaver बनाने का मन हो गया

  • मैं core constraint समझने की कोशिश कर रहा हूँ. क्या problem definition fixed-length preallocated array assume करती है?

    • नहीं, यह array को बिल्कुल assume नहीं करती. यह एक data structure है जो total order वाला set maintain करता है, और operations तीन हैं:
      insert(X), delete(X), label(X)
      label उस element X का label निकालता है जिसे पहले insert किया गया था और अभी delete नहीं किया गया है. label 0 से n-1 तक का number है, और n currently stored elements की संख्या है