Как я могу сделать это решение головоломки Ruby быстрее? - PullRequest
Новая
       15

Как я могу сделать это решение головоломки Ruby быстрее?

0 голосов
/ 20 декабря 2011

Одна из причин, по которым я ненавижу сайты-головоломки, заключается в том, что они сообщают вам, когда вы терпите неудачу, но вы не можете узнать, как улучшить. Обычно я не люблю публиковать подобные вопросы, но я потратил столько времени, пытаясь выяснить, почему это не удается, я ДОЛЖЕН ЗНАТЬ ответ!

Вот мой код: 

ARGF.each do |line|
  if ARGF.lineno > 1
    string_a = line.strip
    string_b = line.strip
    sum = string_a.size
    (0...string_a.size).each do |i|
      string_b[0] = '' 
      (0...string_b.size).each do |j|
        break if string_a[j] != string_b[j]
        sum = sum + 1 
      end 
    end
    puts sum
  end
end

Вот проблема (если вам интересно): http://pastie.org/3044657

Он проходит большинство тестов, но затем завершается неудачей по причинам оптимизации. Я хотел бы знать, как оптимизировать это. Я не знаю, как "определить и научиться", как оптимизировать.

PS. Это самая головоломка начального уровня, поэтому я очень сомневаюсь, что это причинит кому-то боль, пройдя через это.

1 Ответ

1 голос
/ 20 декабря 2011

Ваш алгоритм O (n²).Вы можете сделать с этим немного, просто оптимизировав код.

Некоторые идеи немного улучшить производительность для данного алгоритма:

  • Разделить строку в массив.
  • Как только вы нашли j с string_a[j] != string_b[j], увеличивайте sum на j вместо подсчета каждой равной пары.

Этот код примерно в два раза быстреекак вы на моей машине для моих тестовых случаев: 

ary = line.strip.chars.to_a
n = ary.count
sum = (1...n).inject(n) do | sum, i |
  sum + (n-i).times { | j | break j if ary[j] != ary[j + i] }
end
...