이 Ruby 퍼즐 솔루션을 더 빠르게 만들 수 있습니까?

Question

내가 퍼즐 사이트를 싫어하는 한 가지 이유는 실패했을 때 알려주지 만 개선 방법을 배울 수 없기 때문입니다. 나는 일반적으로 이런 종류의 질문을 게시하는 것을 좋아하지 않지만, 왜 이것이 실패해야 하는지를 알아 내려고 너무 많은 시간을 낭비했습니다. 대답을 꼭 알아야합니다! (당신의 호기심 경우)

여기

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

그것은 대부분의 테스트를 통과하지만 때문에 최적화 이유로 이후 실패

여기 내 코드입니다. 나는 이것을 최적화하는 방법을 알고 싶다. 나는 "식별하고 학습하는"방법을 최적화하는 방법을 알지 못합니다.

추신. 이것은 가장 엔트리 레벨 퍼즐이므로 나는 이것을 통해 걷는 것으로 누군가를 해치고 있다고 의심한다.

Answer 1

귀하의 알고리즘은 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