如何優化代碼去除不需要的字符

Question

此代碼是針對用戶計算機出現問題的問題而設計的，每次他/她點擊退格按鈕時都會顯示'<'符號。創建的程序應該修復此問題並輸出預期的字符串，因爲'<'代表退格。輸入字符串最長可達10^6個字符，並且只能包含小寫字母和'<'。

我的代碼似乎正確執行，但是，當我提交它時，網站說它超過了測試5/25的時間限制。給出的時間是1秒。另外，如果只有'<'符號，它不應該產生輸出。

例如，

"hellooo<< my name is matthe<<" 

將輸出

"hello my name is matt" 

和

"ssadfas<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<" 

將輸出什麼，等等

下面是代碼：

input = gets.chomp 
while input[/[[:lower:]]</] 
    input.gsub!(/[[:lower:]]</, "") 
end 
input.gsub!(/</, "") 
puts"#{input}" 

在上述餘留在while循環，如果存在其中小寫字母是在一個「<」前任何實例的代碼。在任何一個小寫字母后面跟着'<'，它都會被替換爲無。一旦while循環退出，如果有任何「<」符號，它們將被替換爲無。然後顯示最後一個字符串。

我創建了一個測試，我認爲這是對我的代碼，最糟糕的情況：

input = ("a" + "<" + "a")*10000000 

#input = gets.chomp 
while input[/[[:lower:]]</] 
    input.gsub!(/[[:lower:]]</, "") 
end 
input.gsub!(/</, "") 
puts"#{input}" 

我所做的創建的字符串和while循環的執行之間，然後程序停止運行它完全以如果花費時間超過一秒鐘，就能夠吸引眼球。它似乎需要比1秒更長的時間。

如何修改爲更快或有更好的方法來做到這一點？

Answer 1

def backspace(str) 
    bs_count = 0 
    str.reverse.each_char.with_object([]) do |s, arr| 
    if s == '<' 
     bs_count += 1 
    else 
     bs_count.zero? ? arr.unshift(s) : bs_count -= 1 
    end 
    end.join 
end 

backspace "Now is the<< tim<e fo<<<r every<<<one to chill ou<<<<t" 
    #=> "Now is t tier evone to chilt" 

Answer 2

您的方法很好，但如果您修改正則表達式，您的表現會更好。

Cary，我希望你不介意我也在基準測試中採用你的優秀解決方案？

MRI ruby​​ 2.3.0p0（2015-12-25 revision 53290）[x64-mingw32] 我在樣本字符串上使用了.dup，以確保沒有任何方法更改輸入樣本。

require 'benchmark' 
input = "" 
10_000_000.times{input << ['a','<'].sample} 

def original_method inp 
    while inp[/[[:lower:]]</] 
    inp.gsub!(/[[:lower:]]</, "") 
    end 
    inp.gsub(/</, "") 
end 

def better_method inp 
    tuple = /[^<]</ 
    while inp[tuple] 
    inp.gsub!(inp[tuple], "") 
    end 
    inp.gsub(/</, "") 
end 

def backspace str 
    bs_count = 0 
    str.reverse.each_char.with_object([]) do |s, arr| 
    if s == '<' 
     bs_count += 1 
    else 
     bs_count.zero? ? arr.unshift(s) : bs_count -= 1 
    end 
    end.join 
end 

puts original_method(input.dup).length 
puts better_method(input.dup).length 
puts backspace(input.dup).length 

Benchmark.bm do |x| 
    x.report("original_method") { original_method(input.dup) } 
    x.report("backspace  ") { backspace(input.dup) } 
    x.report("better_method ") { better_method(input.dup) } 
end 

給

3640 
3640 
3640 
     user  system  total  real 
original_method 3.494000 0.016000 3.510000 ( 3.510709) 
backspace  1.872000 0.000000 1.872000 ( 1.862550) 
better_method 1.155000 0.031000 1.186000 ( 1.187495)