ruby - 我该如何改进这种 super 简单的排序方法？ - 初级 ruby

Question

我正在从 Chris Pine 的“学习编程”一书中学习 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

代码有效，但我想看看是否有任何经验丰富的 ruby​​-ists 可以提供一些关于如何提高效率的意见。

谢谢!

Answer 1

当您开始了解优化时，首先要了解的是，最明显的修复通常是效率最低的。例如，您可以在这里花费大量时间来调整其中一些比较，或者切换到一种略有不同的方法来评估同一事物，并获得 5-10% 的性能提升。

您也可以使用完全不同的算法并获得 5 到 10 倍的增长。冒泡排序，也就是你所拥有的，几乎是有史以来性能最差的排序算法。这是一种你应该学习的技术，如果只是为了了解它很糟糕，你应该立即转向其他方法，比如 Quicksort。如果您系统地解决问题，这并不难实现。

换句话说，在你开始调整小事情之前，退后一步问问自己“我处理这个问题的方式是否正确？”当您遇到性能问题时，请始终考虑其他角度。

话虽如此，以下是让您的代码更像 Ruby 的方法:

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)

所以这个算法比内置方法慢 642 倍。我相信您可以使用更好的算法更接近。