performance - কেন হাসেল কুইকোর্টের পরিবর্তে মার্জোর্ট ব্যবহার করে?




sorting haskell (4)

উইকিবুকের হাস্কেল- এ নিম্নলিখিত দাবি রয়েছে :

ডেটা.লাইস্ট তালিকাগুলি বাছাইয়ের জন্য একটি বাছাই ফাংশন সরবরাহ করে। এটি কুইকোর্ট ব্যবহার করে না; বরং এটি একত্রীকরণ নামে পরিচিত একটি অ্যালগরিদমের কার্যকর প্রয়োগ ব্যবহার করে।

হাস্কেলের কুইকোর্টের ওপরে সংযুক্তি ব্যবহারের অন্তর্নিহিত কারণ কী? কুইকোর্টের সাধারণত ব্যবহারিক পারফরম্যান্স থাকে তবে এ ক্ষেত্রে নাও হতে পারে। আমি সংগ্রহ করেছি যে কুইকোর্টের অন্তর্নিহিত সুবিধাগুলি হাস্কেল তালিকাগুলির সাথে করা (কঠিন) অসম্ভব?

সফ্টওয়্যারেনজেনারিং.এসই সম্পর্কিত একটি প্রশ্ন ছিল, তবে কেন মার্জোর্ট ব্যবহার করা হয় সে সম্পর্কে এটি আসলে ছিল না।

প্রোফাইলিংয়ের জন্য আমি দু'ধরনের প্রয়োগ করেছি। Mergesort উন্নত ছিল (2 ^ 20 উপাদানের তালিকার চেয়ে দ্বিগুণ দ্রুত), তবে আমি নিশ্চিত নই যে আমার quicksort বাস্তবায়ন অনুকূল ছিল।

সম্পাদনা করুন: এখানে আমার একত্রীকরণ এবং কুইকোর্টের বাস্তবায়ন রয়েছে:

mergesort :: Ord a => [a] -> [a]
mergesort [] = []
mergesort [x] = [x]
mergesort l = merge (mergesort left) (mergesort right)
    where size = div (length l) 2
          (left, right) = splitAt size l

merge :: Ord a => [a] -> [a] -> [a]
merge ls [] = ls
merge [] vs = vs
merge first@(l:ls) second@(v:vs)
    | l < v = l : merge ls second
    | otherwise = v : merge first vs

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort [x] = [x]
quicksort l = quicksort less ++ pivot:(quicksort greater)
    where pivotIndex = div (length l) 2
          pivot = l !! pivotIndex
          [less, greater] = foldl addElem [[], []] $ enumerate l
          addElem [less, greater] (index, elem)
            | index == pivotIndex = [less, greater]
            | elem < pivot = [elem:less, greater]
            | otherwise = [less, elem:greater]

enumerate :: [a] -> [(Int, a)]
enumerate = zip [0..]

সম্পাদনা 2 3: আমাকে Data.List সাজানো বনাম আমার বাস্তবায়নের জন্য সময় সরবরাহ করতে বলা হয়েছিল। @ উইল নেসের পরামর্শ অনুসারে, আমি প্রতিটি -O2 সরবরাহ করা -O2 পরিবর্তিত করে -O2 পতাকাটি দিয়ে এই -O2 সংকলন করেছি এবং এটি +RTS -s দিয়ে সম্পাদন করেছি। বাছাই করা তালিকাটি হ'ল 2 ^ 20 টি উপাদান সহ সস্তার তৈরি সিউডোর্যান্ডম [Int] তালিকা। ফলাফলগুলি নিম্নরূপ ছিল:

  • Data.List.sort : 0.171 এস
  • mergesort : 1.092 সেকেন্ড (। 6x। Data.List.sort তুলনায় ধীর)
  • কুইকোর্ট: 1.152 সেকেন্ড (। 7x Data.List.sort চেয়ে ধীর)

অপরিহার্য ভাষায় কুইকসোর্ট একটি অ্যারে রূপান্তরিত করে জায়গায় জায়গায় সঞ্চালিত হয়। আপনি আপনার কোডের নমুনায় প্রদর্শিত হিসাবে, আপনি পরিবর্তে একক-লিঙ্কযুক্ত তালিকা তৈরি করে হাস্কেলের মতো খাঁটি কার্যকরী ভাষায় কুইকসোর্টকে খাপ খাইয়ে নিতে পারেন, তবে এটি ততটা দ্রুত নয়।

অন্যদিকে, Mergesort একটি স্থানের অ্যালগরিদম নয়: একটি সরল অপরিহার্য বাস্তবায়ন মার্জড ডেটাটিকে একটি আলাদা বরাদ্দে অনুলিপি করে। এটি হাস্কেলের পক্ষে আরও ভাল ফিট, যা প্রকৃতির সাথে অবশ্যই ডেটা অনুলিপি করতে হবে।

আসুন কিছুটা পিছনে ফিরে আসুন: কুইকোর্টের অভিনয়ের প্রান্তটি "লোর" - আজকাল আমরা যেগুলি ব্যবহার করি তার চেয়ে মেশিনে অনেক দশক আগে নির্মিত খ্যাতি। এমনকি যদি আপনি একই ভাষা ব্যবহার করেন তবে এই ধরণের oreতিহ্যগুলি সময়ে সময়ে পুনরায় পুনর্বিবেচনা করা প্রয়োজন, কারণ স্থলভাগের তথ্যগুলি পরিবর্তন করতে পারে। আমি এই বিষয়টিতে যে সর্বশেষ বেঞ্চমার্কিং পত্রটি পড়েছিলাম তার উপরে কুইকসোর্ট এখনও শীর্ষে ছিল, তবে মার্জেসোর্টের উপরে এটির নেতৃত্ব স্লিম ছিল এমনকি সি / সি ++ তেও।

মার্জরোর্টের অন্যান্য সুবিধাগুলি রয়েছে: কুইকসোর্টের ও (এন ^ 2) সবচেয়ে খারাপ পরিস্থিতি এড়াতে এটি টুইট করার দরকার নেই এবং এটি স্বাভাবিকভাবেই স্থিতিশীল। সুতরাং, যদি আপনি অন্যান্য কারণগুলির কারণে সংকীর্ণ পারফরম্যান্সের পার্থক্যটি হারাতে থাকেন তবে Mergesort একটি স্পষ্ট পছন্দ choice


আমি নিশ্চিত নই, তবে কোডটি দেখে আমার মনে হয় না যে Data.List.sort আমরা জানি এটি মার্জরোর্ট। এটি কেবল একটি sequences দিয়ে sequences শুরু করে একটি সুন্দর ত্রিভুজাকার পারস্পরিক পুনরাবৃত্ত ফ্যাশনে ascending এবং descending ফাংশনগুলির সাথে ইতিমধ্যে আরোহণের বা ক্রমবর্ধমান sequences তালিকার প্রয়োজনীয় sequences ফলাফলের জন্য। তবেই এটি মার্জ শুরু হয়।

কোডিংয়ে এটি কবিতার বহিঃপ্রকাশ। কুইকসোর্টের বিপরীতে, এর সবচেয়ে খারাপ ক্ষেত্রে (মোট র্যান্ডম ইনপুট) ও (নলগন) সময়ের জটিলতা রয়েছে এবং সর্বোত্তম কেস (ইতিমধ্যে সাজানো বা উতরাই সাজানো) হ'ল (এন)।

আমি মনে করি না অন্য কোনও বাছাই করা অ্যালগরিদম এটি পরাজিত করতে পারে।


একক লিঙ্কযুক্ত তালিকায়, একত্রিতকরণ স্থানে করা যেতে পারে। আরও কী, দ্বিতীয় সাবলিস্টের সূচনা পেতে নিখুঁত বাস্তবায়নগুলি অর্ধেকেরও বেশি তালিকাকে স্ক্যান করে, তবে দ্বিতীয় সাবলিস্টের শুরুটি প্রথম সাবলিস্টটি বাছাইয়ের পার্শ্ব প্রতিক্রিয়া হিসাবে দেখা দেয় এবং অতিরিক্ত স্ক্যানিংয়ের প্রয়োজন হয় না। কুইকোর্টের একত্রীকরণটি একীভূত হওয়ার বিষয়টি হ'ল ক্যাশে সংহতি। কুইকসোর্ট স্মৃতিতে একে অপরের কাছাকাছি উপাদানগুলির সাথে কাজ করে। এর মধ্যে ইন্ডিয়ারেশনের কোনও উপাদান প্রবেশ করার সাথে সাথে আপনি যখন ডেটা পরিবর্তে পয়েন্টার অ্যারে বাছাই করছেন, তখন সেই সুবিধাটি কম হয়ে যায়।

মার্জেসোর্টের নিকৃষ্টতম আচরণের জন্য কঠোর গ্যারান্টি রয়েছে এবং এটির সাথে স্থিতিশীল বাছাই করা সহজ।


হাস্কেলতে কেন কুইকসোর্ট ব্যবহার করা হয় না সে সম্পর্কে অনেক যুক্তি প্রশংসনীয় বলে মনে হয়। যাইহোক, কমপক্ষে কুইকসোর্টটি এলোমেলো ক্ষেত্রে ম্যাসেজর্টের চেয়ে ধীর নয়। রিচার্ড বার্ডের বইটিতে দেওয়া বাস্তবায়নের ভিত্তিতে, হাস্কেলের মধ্যে কার্যকরীভাবে চিন্তাভাবনা করে আমি একটি 3-উপায় কুইকোর্ট:

tqsort [] = []
tqsort (x:xs) = sortp xs [] [x] [] 
  where
    sortp [] us ws vs     = tqsort us ++ ws ++ tqsort vs
    sortp (y:ys) us ws vs =
      case compare y x of 
        LT -> sortp ys (y:us) ws vs 
        GT -> sortp ys us ws (y:vs)
        _  -> sortp ys us (y:ws) vs

আমি কয়েকটি কেস বেঞ্চমার্ক করেছি, উদাহরণস্বরূপ, আকারের তালিকা 10 ^ 4 এর মধ্যে 0 থেকে 10 Int 3 বা 10 ^ 4 এর মধ্যে রয়েছে এবং আরও অনেক কিছু। ফলাফলটি 3-ওয়ে কুইকসোর্ট বা এমনকি বার্ডের সংস্করণটি জিএইচসির মার্জেসোর্টের চেয়ে আরও ভাল, ডেস্কের ধরণের উপর নির্ভর করে (অনেকগুলি পুনরাবৃত্তি? খুব বিরল?) গিগের মার্জেসোর্টের চেয়ে 1.x ~ 3.x এর মতো দ্রুত। নিম্নলিখিত পরিসংখ্যান criterion দ্বারা উত্পাদিত:

benchmarking Data.List.sort/Diverse/10^5
time                 223.0 ms   (217.0 ms .. 228.8 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 226.4 ms   (224.5 ms .. 228.3 ms)
std dev              2.591 ms   (1.824 ms .. 3.354 ms)
variance introduced by outliers: 14% (moderately inflated)

benchmarking 3-way Quicksort/Diverse/10^5
time                 91.45 ms   (86.13 ms .. 98.14 ms)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 96.65 ms   (94.48 ms .. 98.91 ms)
std dev              3.665 ms   (2.775 ms .. 4.554 ms)

যাইহোক, হাস্কেল 98 বর্ণিত আরেকটি প্রয়োজন রয়েছে: এটি স্থিতিশীল হওয়া দরকার Data.List.partition ব্যবহার করে টিপিক্যাল Data.List.partition বাস্তবায়ন স্থিতিশীল , তবে Data.List.partition তা নয়।

পরের সংযোজন : মন্তব্যে উল্লিখিত একটি স্থিতিশীল tqsort এখানে tqsort হিসাবে tqsort দ্রুত বলে মনে হয়।







haskell