在Ruby中反转一个字符串

Question

你如何在Ruby中反转字符串？我知道字符串#verse.我有兴趣了解如何用纯Ruby编写它,最好是一个就地解决方案.

Answer 1

已经存在一种称为"反向!"的现场反向方法:

$ a = "abc"
$ a.reverse!
$ puts a
cba

如果你想手动尝试这个(但它可能不是多字节安全的,例如UTF-8),它会慢一些:

class String
  def reverse_inplace!
    half_length = self.length / 2
    half_length.times {|i| self[i], self[-i-1] = self[-i-1], self[i] }
    self
  end
end

这将从开头的每个字节开始交换每个字节,直到两个索引在中心相交:

$ a = "abcd"
$ a.reverse_inplace!
$ puts a
dcba

Answer 2

只是为了讨论,有很多替代品,很高兴看到速度/效率是否存在重大差异.我稍微清理了代码,因为显示输出的代码反复反转输出.

# encoding: utf-8

require "benchmark"

reverse_proc = Proc.new { |reverse_me| reverse_me.chars.inject([]){|r,c| r.unshift c}.join }

class String
  def reverse # !> method redefined; discarding old reverse
    each_char.to_a.reverse.join
  end

  def reverse! # !> method redefined; discarding old reverse!
    replace reverse
  end

  def reverse_inplace!
    half_length = self.length / 2
    half_length.times {|i| self[i], self[-i-1] = self[-i-1], self[i] }
  end

end

def reverse(a)
  (0...(a.length/2)).each {|i| a[i], a[a.length-i-1]=a[a.length-i-1], a[i]}
  return a
end

def reverse_string(string) # method reverse_string with parameter 'string'
  loop = string.length       # int loop is equal to the string's length
  word = ''                  # this is what we will use to output the reversed word
  while loop > 0             # while loop is greater than 0, subtract loop by 1 and add the string's index of loop to 'word'
    loop -= 1                  # subtract 1 from loop
    word += string[loop]       # add the index with the int loop to word
  end                        # end while loop
  return word                # return the reversed word
end                        # end the method

lorum = <<EOT
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent quis magna eu
lacus pulvinar vestibulum ut ac ante. Lorem ipsum dolor sit amet, consectetur
adipiscing elit. Suspendisse et pretium orci. Phasellus congue iaculis
sollicitudin. Morbi in sapien mi, eget faucibus ipsum. Praesent pulvinar nibh
vitae sapien congue scelerisque. Aliquam sed aliquet velit. Praesent vulputate
facilisis dolor id ultricies. Phasellus ipsum justo, eleifend vel pretium nec,
pulvinar a justo. Phasellus erat velit, porta sit amet molestie non,
pellentesque a urna. Etiam at arcu lorem, non gravida leo. Suspendisse eu leo
nibh. Mauris ut diam eu lorem fringilla commodo. Aliquam at augue velit, id
viverra nunc.
EOT

结果如下:

RUBY_VERSION # => "1.9.2"

name = "Marc-André"; reverse_proc.call(name) # => "érdnA-craM"
name = "Marc-André"; name.reverse! # => "érdnA-craM"
name = "Marc-André"; name.chars.inject([]){|s, c| s.unshift(c)}.join # => "érdnA-craM"
name = "Marc-André"; name.reverse_inplace!; name # => "érdnA-craM"
name = "Marc-André"; reverse(name) # => "érdnA-craM"
name = "Marc-André"; reverse_string(name) # => "érdnA-craM"

n = 5_000
Benchmark.bm(7) do |x|
  x.report("1:") { n.times do; reverse_proc.call(lorum); end }
  x.report("2:") { n.times do; lorum.reverse!; end }
  x.report("3:") { n.times do; lorum.chars.inject([]){|s, c| s.unshift(c)}.join; end }
  x.report("4:") { n.times do; lorum.reverse_inplace!; end }
  x.report("5:") { n.times do; reverse(lorum); end }
  x.report("6:") { n.times do; reverse_string(lorum); end }
end

# >>              user     system      total        real
# >> 1:       4.540000   0.000000   4.540000 (  4.539138)
# >> 2:       2.080000   0.010000   2.090000 (  2.084456)
# >> 3:       4.530000   0.010000   4.540000 (  4.532124)
# >> 4:       7.010000   0.000000   7.010000 (  7.015833)
# >> 5:       5.660000   0.010000   5.670000 (  5.665812)
# >> 6:       3.990000   0.030000   4.020000 (  4.021468)

有趣的是,"C"版本("reverse_string()")是最快的纯Ruby版本.#2("反向!")是最快的,但它正在利用,[].reverse在C中.

• 由Marc-AndréLafortune编辑*

添加额外的测试用例(7):

def alt_reverse(string)
  word = ""
  chars = string.each_char.to_a
  chars.size.times{word << chars.pop}
  word
end

如果字符串是更长的(lorum *= 10, n/=10),我们可以看到差异变宽,因为一些函数在O(n ^ 2)中,而其他函数(我的:-)是O(n):

             user     system      total        real
1:      10.500000   0.030000  10.530000 ( 10.524751)
2:       0.960000   0.000000   0.960000 (  0.954972)
3:      10.630000   0.080000  10.710000 ( 10.721388)
4:       6.210000   0.060000   6.270000 (  6.277207)
5:       4.210000   0.070000   4.280000 (  4.268857)
6:      10.470000   3.540000  14.010000 ( 15.012420)
7:       1.600000   0.010000   1.610000 (  1.601219)

Answer 3

内置的Ruby等价物reverse可能如下所示:

# encoding: utf-8

class String
  def reverse
    each_char.to_a.reverse.join
  end

  def reverse!
    replace reverse
  end
end

str = "Marc-André"
str.reverse!
str # => "érdnA-craM"
str.reverse # => "Marc-André"

注意:这假设是Ruby 1.9,否则require "backports"设置$KCODE为UTF-8.

对于不涉及的解决方案reverse,可以做:

def alt_reverse(string)
  word = ""
  chars = string.each_char.to_a
  chars.size.times{word << chars.pop}
  word
end                        

注意:任何[]用于访问单个字母的解决方案都是有序的O(n^2); 要访问第1000个字母,Ruby必须逐个检查第一个999以检查多字节字符.因此,重要的是使用迭代器,如each_char解决方案O(n).

要避免的另一件事是建立增加长度的中间值; 使用+=而不是<<in alt_reverse也会使解决方案O(n^2)而不是O(n).

构建数组unshift也将构成解决方案O(n^2),因为它意味着每次执行一个索引时重新复制所有现有元素unshift.

Answer 4

这是使用inject和unshift执行此操作的一种方法:

"Hello world".chars.inject([]) { |s, c| s.unshift(c) }.join

Answer 5

str = "something"
reverse = ""
str.length.times do |i|
  reverse.insert(i, str[-1-i].chr)
end

Answer 6

"abcde".chars.reduce{|s,c| c + s }          # => "edcba"

Answer 7

使用

def reverse_string(string) # Method reverse_string with parameter 'string'.
  loop = string.length # int loop is equal to the string's length.
  word = '' # This is what we will use to output the reversed word.
  while loop > 0 # while loop is greater than 0, subtract loop by 1 and add the string's index of loop to 'word'.
    loop -= 1 # Subtract 1 from loop.
    word += string[loop] # Add the index with the int loop to word.
  end # End while loop.
  return word # Return the reversed word.
end # End the method.