ruby - 如何有效地确定字符串中每个 100 个字符 block 中特定字符的百分比？

Question

我正在尝试计算任意长度的任意给定字符串的每 100 个 block 子字符串中特定字符的百分比。我有一个工作版本如下所示，但给定的字符串可能很长 - 数以万计到数百万个字符。

该字符串将由不超过 8 个不同的字符组成:A、B、C、D、E、F、G 和 H。

我需要扫描每 100 个字符 block 并确定给定字符在该 block 中的百分比。如果百分比大于确定的量，则记录 block 索引。我发现很难解释什么是“100 个字符 block ”。我不需要将字符串分成 100 个字符 block ，我需要从每个字符开始读取接下来的 99 个字符，然后对每个字符重复直到结束。比如，阅读 [0..99]、[1..100]、[2..101]、[3..102]、[4..103] 等等。

我目前正在暴力破解计算，但速度相当慢。有没有一种聪明的方法可以提高效率？

def calculate_percentage_errors full_string, searched_character, percentage_limit 
# full_string:        ABCDGFGEDCBADDEGDCGGBCDEEFGAAAC.......
# searched_character: A
# percentage_limit:   0.5

n = 0 
error_index = []
while n < (full_string.length - 99) do
  #grab the string 1..100, 2..101 .... 
  sub_string =  full_string[n..(n+99)] 

  # determine the number of characters in the string
  character_count = (100 - sub_string.gsub(searched_character, '').length)

  if (character_count/100.0) > percentage_limit
    # record the index if percentage exceeds limit
    error_index << [(n+1),(n+100)]
  end

  n += 1
end

return error_index
end

Answer 1

使用前一个 block 的计数。它最多更改为 2。让我举个例子。如果您在 block 2..101 中有 5 次 A 并且您想要计算 3..102 的计数，您可以简单地检查位置 2 是否有 A，以及位置 102 是否有 A。如果您在 102 上有一个 A，但在 2 上没有，例如，计数将为 6。你需要再看三个案例。我相信使用它会快得多。

下面是一些示例代码:

def calculate_percentage_errors full_string, searched_character, percentage_limit                                                                                         
  count = full_string[0..99].count(searched_character)                                                                                                                    
  error_index = []                                                                                                                                                        
  error_index << full_string[0..99] if count / 100.0 > percentage_limit                                                                                                   

  1.upto(full_string.length - 100).each do |index|                                                                                                                        
    count -= 1 if searched_character == full_string[index - 1]                                                                                                            
    count += 1 if searched_character == full_string[index + 99]                                                                                                           

    error_index << full_string[index, index + 99] if count / 100.0 > percentage_limit                                                                                     
  end                                                                                                                                                                     

  error_index                                                                                                                                                             
end