このスーパーシンプルなソート方法をどのように改善できますか？ - Beginning Ruby

Question

私はChris Pineの "Learn To Program"の本からRubyを学んでいます。ループや再帰のいずれかのアルファベット順にソートされた単語をソートするメソッドを書くように求められました。私はまずループを試みました。

def sort words 
    i = 0 
    checked = 0 
    while true 
     if (i+1 < words.length) 
      if (words[i]>words[i+1]) 
       temp = words[i] 
       words[i] = words[i+1] 
       words[i+1] = temp 
      else 
       checked+=1 
      end 
      i+=1 
     elsif (checked == words.length-1) 
      break 
     else 
      i =0 
      checked =0 
     end 
    end 
    return words 
end 

コードは動作しますが、私はどんなベテランルビーISTSは、それをより効率的にする方法についていくつかの入力を提供することができるかどうかを確認したかったです。

ありがとうございました！

Answer 1

あなたは最適化を理解し始めているときに学ぶべき最初の事は最も明白な修正は、多くの場合、少なくとも生産的であるということです。たとえば、これらの比較の一部を調整したり、同じことを評価したり、5〜10％のパフォーマンスを向上させるためのやり方を変えるなど、多くの時間を費やすことができます。

また、完全に異なるアルゴリズムを使用して、5倍から10倍の増加を得ることもできます。ここにあるバブルソートは、これまでに作成されたソートアルゴリズムの中で最も悪いものです。これはひどいことを理解するためだけに学ぶべきテクニックであり、すぐに問題に体系的にアプローチする場合は実現しにくいQuicksortのような他の方法に移行する必要があります。

つまり、小さなことを微調整し始める前に、私はこの問題に正しい方法でアプローチしていますか？パフォーマンスに問題があるときは、常に他の角度を考慮してください。言われていること

は、ここにあなたのコードをよりルビーのようにする方法は次のとおりです。

def sort(words) 
    # Make a copy so the original isn't mangled 
    words = words.dup 

    # Iterate over ranges: 
    # (n..m) goes from N to M inclusive 
    # (n...m) goes from N up to but not including M 
    (0...words.length-1).each do |i| 
    (0...words.length-1-i).each do |j| 
     # Examine the pair of words at this offset using an array slice 
     a, b = words[j, 2] 

     # If A is ahead of B then... 
     if (a > b) 
     # ...swap these elements. 
     words[j, 2] = [ b, a ] 
     end 
    end 
    end 

    words 
end 

# Quick test function that uses randomized data 
p sort(%w[ a c d f b e ].shuffle) 

あなたはいつも試してみて、何とか自分の進捗状況を測定する必要があり、開発者としての向上のために。 Rubocopのようなツールは、非効率的なコーディング方法の特定に役立ちます。テスト駆動開発は、プログラミングの初期段階で欠陥を特定し、変更が回帰を引き起こさないようにするのに役立ちます。ベンチマークツールは、コードのパフォーマンスをよりよく理解するのに役立ちます。例えば

：

require 'benchmark' 

CHARS = ('a'..'z').to_a 

def random_data 
    Array.new(1000) { CHARS.sample } 
end 

count = 100 

Benchmark.bm do |bm| 
    bm.report('my sort:') do 
    count.times do 
     sort(random_data) 
    end 
    end 

    bm.report('built-in sort:') do 
    count.times do 
     random_data.sort 
    end 
    end 
end 

#      user  system  total  real 
# my sort:  19.220000 0.060000 19.280000 (19.358073) 
# built-in sort: 0.030000 0.000000 0.030000 ( 0.025662) 

ので、このアルゴリズムは、組み込みの方法より642x遅いです。私はあなたがより良いアルゴリズムにもっと近づくことができると確信しています。

Answer 2

まず、ホイールを改造する必要はありません。つまり、次の例を参照してください。

> ['a', 'abc', 'bac', 'cad'].sort 
# => ["a", "abc", "bac", "cad"] 

Rubyには膨大なライブラリセットがあります。一般的なものはRubyによって非常に効率的にサポートされています。言語機能を効率的に使用するには、十分な知識が必要です。

Rubyのコアライブラリを使い、何か特別なものを実現するために機能を組み合わせることをお勧めします。

このルビーKoans http://rubykoans.com/

RubyKoansに試してみてはRuby言語の上に支配を達成するのが最も効率的です。ここで

---

あなたは賢明な問題ドメインとユースケースのサイズに基づくアルゴリズムの間で選択する必要があり、このサイトではタイプによってhttps://www.sitepoint.com/sorting-algorithms-ruby/

をアルゴリズムの例を並べ替えのリストです。