हैकेल

Question

में तेजी से सॉर्टिंग पूर्णांक है क्या हैकेल पुस्तकालयों में कोई फ़ंक्शन है जो ओ (एन) समय में पूर्णांक टाइप करता है ?? [रखकर हे (एन) मैं तेजी से तुलना प्रकार और पूर्णांकों के लिए विशिष्ट से मतलब]

मूल रूप से मुझे लगता है कि निम्नलिखित कोड प्रकार के साथ बहुत समय लेता है (छँटाई के बिना सूची संक्षेप की तुलना में):

import System.Random 
import Control.DeepSeq 
import Data.List (sort) 

genlist gen = id $!! sort $!! take (2^22) ((randoms gen)::[Int]) 

main = do 
    gen <- newStdGen 
    putStrLn $ show $ sum $ genlist gen 

किसी सूची को सारांशित करने के लिए गहरे सेक की आवश्यकता नहीं है, लेकिन मैं जो करने की कोशिश कर रहा हूं, लेकिन उपर्युक्त कोड उन पॉइंटर्स के लिए पर्याप्त है जो मैं चाहता हूं।

समय: 6 सेकंड (बिना सॉर्ट); लगभग 35 सेकंड (क्रमशः)

मेमोरी: लगभग 80 एमबी (बिना सॉर्ट); 310 के बारे में एमबी (प्रकार) के साथ

नोट 1: स्मृति यहाँ हाथ में काम मैं स्मृति त्रुटियों से बाहर हो रही है (स्मृति के उपयोग 3GB हो जाता है के लिए के रूप में मेरे लिए समय की तुलना में एक बड़ा मुद्दा है रन के 30 मिनट के बाद -टाइम)

मुझे लगता है कि तेजी से एल्गोरिदम bettor मेमोरी प्रिंट भी प्रदान करेगा, इसलिए ओ (एन) समय की तलाश है।

नोट 2: मैं Int64 के लिए तेज़ एल्गोरिदम की तलाश में हूं, हालांकि अन्य विशिष्ट प्रकारों के लिए तेज़ एल्गोरिदम भी सहायक होंगे।

---

समाधान उपयोग किया: अनबॉक्स्ड वैक्टर साथ IntroSort मेरे कार्य के लिए काफी अच्छा था:

import qualified Data.Vector.Unboxed as V 
import qualified Data.Vector.Algorithms.Intro as I 

sort :: [Int] -> [Int] 
sort = V.toList . V.modify I.sort . V.fromList 

Answer 1

एक सरणी का उपयोग कर संख्याओं को सॉर्ट करने का विचार स्मृति उपयोग को कम करने के लिए सही है।

हालांकि, सीमाओं के रूप में अधिकतम और न्यूनतम सूची का उपयोग करने से स्मृति उपयोग या यहां तक ​​कि रनटाइम विफलता हो सकती है जब maximum xs - minimum xs > (maxBound :: Int)।

तो मैं एक अनबॉक्स किए गए म्यूटेबल सरणी में सूची सामग्री लिखने का सुझाव देता हूं, जो उस जगह को सॉर्ट करता है (उदा। क्विकॉर्ट के साथ), और फिर उस से एक सूची बना रहा है।

import System.Random 
import Control.DeepSeq 
import Data.Array.Base (unsafeRead, unsafeWrite) 
import Data.Array.ST 
import Control.Monad.ST 

myqsort :: STUArray s Int Int -> Int -> Int -> ST s() 
myqsort a lo hi 
    | lo < hi = do 
     let lscan p h i 
       | i < h = do 
        v <- unsafeRead a i 
        if p < v then return i else lscan p h (i+1) 
       | otherwise = return i 
      rscan p l i 
       | l < i = do 
        v <- unsafeRead a i 
        if v < p then return i else rscan p l (i-1) 
       | otherwise = return i 
      swap i j = do 
       v <- unsafeRead a i 
       unsafeRead a j >>= unsafeWrite a i 
       unsafeWrite a j v 
      sloop p l h 
       | l < h = do 
        l1 <- lscan p h l 
        h1 <- rscan p l1 h 
        if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1 
       | otherwise = return l 
     piv <- unsafeRead a hi 
     i <- sloop piv lo hi 
     swap i hi 
     myqsort a lo (i-1) 
     myqsort a (i+1) hi 
    | otherwise = return() 


genlist gen = runST $ do 
    arr <- newListArray (0,2^22-1) $ take (2^22) (randoms gen) 
    myqsort arr 0 (2^22-1) 
    let collect acc 0 = do 
      v <- unsafeRead arr 0 
      return (v:acc) 
     collect acc i = do 
      v <- unsafeRead arr i 
      collect (v:acc) (i-1) 
    collect [] (2^22-1) 

main = do 
    gen <- newStdGen 
    putStrLn $ show $ sum $ genlist gen 

उचित रूप से तेज़ है और कम स्मृति का उपयोग करता है। यह अभी भी सूची के लिए बहुत सारी मेमोरी का उपयोग करता है, 2 Int एस 32 एमबी स्टोरेज कच्चा (64-बिट Int एस के साथ) लेता है, आईआईआरसी की प्रति उपरोक्त पांच शब्द प्रति शब्द, जो ~ 200 एमबी तक जोड़ता है, लेकिन कम मूल के आधे से अधिक।

Answer 2

यह रिचर्ड बर्ड की किताब से लिया जाता है, कार्यात्मक एल्गोरिथ्म डिजाइन के मोती, (हालांकि मैं संपादित करने के लिए किया था यह थोड़ा सा है, क्योंकि पुस्तक में कोड बिल्कुल लिखे गए संकलित नहीं थे)।

import Data.Array(Array,accumArray,assocs) 

sort :: [Int] -> [Int] 
sort xs = concat [replicate k x | (x,k) <- assocs count] 
     where count :: Array Int Int 
       count = accumArray (+) 0 range (zip xs (repeat 1)) 
       range = (0, maximum xs) 

यह एक सरणी पूर्णांकों जहां मूल्यों समय की संख्या प्रत्येक पूर्णांक सूची में होता हैं द्वारा अनुक्रमित बनाकर काम करता है। फिर यह इंडेक्स की एक सूची बनाता है, जो उन्हें गणना के अनुसार मूल सूची में समान संख्या में दोहराता है।

आपको ध्यान रखना चाहिए कि सूची में अधिकतम मूल्य के साथ यह रैखिक है, सूची की लंबाई नहीं, इसलिए [ 2^x | x <- [0..n] ] जैसी सूची को रैखिक रूप से क्रमबद्ध नहीं किया जाएगा।

Answer 3

मैं इस के लिए सूचियों के बजाय वैक्टर उपयोग करने पर विचार होता है, जबकि एक अनबॉक्स्ड वेक्टर अनिवार्य रूप से सिर्फ बाइट्स की एक सन्निहित ब्लॉक के रूप में सूचियों प्रति-तत्व भूमि के ऊपर का एक बहुत कुछ है। vector-algorithms पैकेज में विभिन्न सॉर्टिंग एल्गोरिदम शामिल हैं जिनका आप उपयोग कर सकते हैं, जिसमें radix sort भी शामिल है, जो मुझे उम्मीद है कि आपके मामले में अच्छा प्रदर्शन करना चाहिए।

यहाँ एक सरल उदाहरण है, हालांकि यह एक अच्छा विचार वेक्टर के रूप में परिणाम रखने के लिए हो सकता है, तो आप उस पर आगे की प्रक्रिया कर रही पर योजना है।

import qualified Data.Vector.Unboxed as V 
import qualified Data.Vector.Algorithms.Radix as R 

sort :: [Int] -> [Int] 
sort = V.toList . V.modify R.sort . V.fromList 

इसके अलावा, मुझे लगता है कि अपने उदाहरण का प्रयोग समय का एक महत्वपूर्ण भाग यादृच्छिक संख्या जनरेटर से आ रही है, के रूप में मानक एक बिल्कुल इसके प्रदर्शन के लिए जाना जाता है। आपको यह सुनिश्चित करना चाहिए कि आप केवल सॉर्टिंग भाग का समय दे रहे हैं, और यदि आपको अपने प्रोग्राम में बहुत से यादृच्छिक संख्या की आवश्यकता है, तो हैकेज पर तेज़ जेनरेटर उपलब्ध हैं।