क्रमबद्ध तेजी से रैकेट में हैश तालिका

Question

का उपयोग कर तो मैं इस

(define A (list 'a 'c 'd 'e 'f 'e 'a)) 

जैसे तत्वों का एक उदाहरण सूची है अब मैं इस नमूना

(define (scan lst) 
    (foldl (lambda (element a-hash) (hash-update a-hash element add1 0)) 
      (hash) 
      lst)) 

परिणाम इस तरह से किया जाना चाहिए से एक रैंकिंग बनाना चाहते :

> #(('a . 2) ('f . 1) ('e . 2) ....) 

क्योंकि स्कैन फ़ंक्शन एक हैश तालिका बना देगा जिसमें अद्वितीय कुंजी और पुनरावृत्ति की संख्या होगी वह कुंजी (यदि यह एक अनइंडेक्ड कुंजी पकड़ लेती है तो यह 0 से गिनती, उस नई कुंजी के लिए एक नई जगह तैयार करेगी)।

(define (rank A) 
    (define ranking (scan A))   
    (sort ranking > #:key cdr))) 

तो परिणाम इस प्रकार दिखाई देगा:

तो मुझे लगता है कि हैश तालिका सॉर्ट करने के लिए है क्योंकि यह अवर्गीकृत है चाहें

# (('एक 2) (।' ई। 2) ('च। 1) ...)

अब मैं हैश तालिका में काट-छांट और n की दहलीज पर नीचे फेंक करना चाहते हैं = 1 (उर्फ केवल साथ तत्वों ले 2 से अधिक पुनरावृत्ति)।

(define (truncate lst n) 
    (define l (length lst)) 
    (define how-many-to-take 
     (for/list 
      ([i l] 
       #:when (> (cdr (list-ref lst i)) 
          n)) 
       i)) 
    (take lst (length how-many-to-take))) 

तो परिणाम इस प्रकार दिखाई देंगे:

(। ('। एक 2) (' ई 2))

हालांकि, बड़े पैमाने पर, इस प्रक्रिया बहुत कुशल नहीं है, यह बहुत लंबा लगता है। क्या आपके पास प्रदर्शन में सुधार करने के लिए कोई सुझाव होगा?

आपको बहुत बहुत धन्यवाद,

भाग 2:

(automaton x 
    (vector (state y (vector a b c)) 
      (state y (vector a b c)) ...)) 

तब मैं बेतरतीब ढंग से उन्हें 1000 की आबादी उत्पन्न:

मैं इस डेटा संरचना है। फिर मैं ऊपर दिए गए कार्यों का उपयोग करके उन्हें स्कैन और रैंक करता हूं। अगर मैं उन्हें बस स्कैन करता हूं, तो इसमें काफी समय लगता है। अगर मैं उन्हें

(list x y a b c y a b c...) 

जैसी सूची में उन्हें फ़्लैट करने का प्रयास करता है तो इसमें और भी समय लगेगा। यहाँ समतल समारोह है:

(define (flatten-au au) 
    (match-define (automaton x states) au) 
    (define l (vector-length states)) 
    (define body 
    (for/list ([i (in-range l)]) 
     (match-define (state y z) (vector-ref states i)) 
     (list y (vector->list z)))) 
    (flatten (list x body))) 

स्कैन समारोह कुछ अलग दिखाई देगा:

(define (scan population) 
    (foldl (lambda (auto a-hash) (hash-update a-hash (flatten-automaton auto) add1 0)) 
      (hash) 
      population)) 

Answer 1

हां, मेरा मानना ​​है कि मैं इस समस्या को देखते हैं। आपके एल्गोरिदम में ओ (एन^2) ("एन-स्क्वायर") चलने का समय है। ऐसा इसलिए है क्योंकि आप प्रत्येक सूची के लिए सूची के लिए पर गिन रहे हैं, list-ref प्रदर्शन करते हैं, जो सूचकांक के आकार के लिए आनुपातिक समय लेता है।

यह ठीक करने के लिए बहुत आसान है।

असल में, इसे सॉर्ट करने या इसे सूची में बदलने के लिए वास्तव में कोई कारण नहीं है यदि आप यही चाहते हैं; बस हैश तालिका को सीधे फ़िल्टर करें। इस तरह ...

#lang racket 

(define A (build-list 1000000 (λ (idx) (random 50)))) 

(define (scan lst) 
    (foldl (lambda (element a-hash) (hash-update a-hash element add1 0)) 
      (hash) 
      lst)) 

(define ht (scan A)) 

(define only-repeated 
    (time 
    (for/hash ([(k v) (in-hash ht)] 
       #:when (< 1 v)) 
    (values k v)))) 

मैं time करने के लिए कॉल जोड़ा देखने के लिए कितना समय लगता है। मेरे कंप्यूटर पर एक मिलियन आकार की सूची के लिए यह 1 मिलीसेकंड का मापा समय लेता है।

असीमोटिक जटिलता महत्वपूर्ण है!