Обратная строка в Ruby

Question

Как вы переворачиваете строку в Ruby? Я знаю о строке # обратный. Мне интересно понять, как написать это на чистом 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.

• Редактирование: Марк-Лафортун *

Добавление дополнительного контрольного примера (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

Рубиновый эквивалент встроенного 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).

Другая вещь, которую следует избегать, - это создание промежуточных значений возрастающей длины;использование += вместо << в 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.

Answer 8

Решение описано ниже. Нет необходимости выходить за пределы половины размера массива:

class ReverseString

  def initialize(array)
    @array = array
    @size  = @array.size
  end

  def process
    (0...@size/2).to_a.each_with_index do |e,i|
      @array[i], @array[@size-i-1] = @array[@size-i-1], @array[i]
    end
    @array
  end

end


require 'minitest/autorun'

class ReverseStringTest < Minitest::Unit::TestCase
  def test_process
    assert_equal "9876543210", ReverseString.new("0123456789").process
  end
end

Answer 9

Трудно читаемый однострочный текст

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

Answer 10

Подумайте о том, как Rubinius реализует метод - они реализуют большую часть базовой библиотеки в самом Ruby, и я не удивлюсь, если в Ruby реализованы String#reverse и String#reverse!.