基因組範圍查詢的Ruby實現

-2

我參加了一個演示測試，並得到了結果分值62.我想我的代碼還不夠高效，實現了最高分100。因此，如何在一個子有效地找到最低的字符代碼？例如，字符串是s="ACGTTAGTAC"。找出有效子串s[p,q]中的最小字符是什麼 - 有相同的s但是不同的[p,q]有許多重複的查詢。實際上，這個問題被稱爲Range Minimum Query（RMQ），並且有多個算法可以解決這個問題。但是我很難理解並將它們應用於這個特定的實例。任何人都可以建議如何修復代碼？基因組範圍查詢的Ruby實現

# s is a string, p and q are arrays of integers with p[i] <= q[i] 
def solution (s, p, q) 
    len = s.length 
    a = Array.new(len,0) 
    for k in 0..len-1 
    case s[k] 
    when 'A' 
     a[k] = 1 
    when 'C' 
     a[k] = 2 
    when 'G' 
     a[k] = 3 
    when 'T' 
     a[k] = 4 
    end 
    end 
    s = [] 
    m = p.size 
    for i in 0..m-1 
    s << a[p[i]..q[i]].min 
    end 
    s 
end

由於版權問題，完整的問題不會複製到這裏。你可以從這個鏈接https://codility.com/demo/results/demoHSB3XQ-R24/閱讀完整的詳細信息。

來源

2013-11-21 canoe

Codility分析顯示您沒有達到預期的時間目標，甚至可以解釋哪些測試輸入會導致問題。就目前而言，這個問題是「請在此測試中調試我的代碼以獲得更高的分數」。建議：對這個腳本輸入一個失敗的結果，嘗試並改進性能，然後詢問 - 例如「如何有效地在子串中找到最低字符代碼？」。答案很可能涉及到在所有的1，2，3，4在*之前運行查詢，而你的解決方案是正確的，但是蠻力並且不能很好地擴展。 –

我重新編輯了您的問題以強調您擁有的縮放問題。您有兩個維度的輸入，N（字符串的長度）和M（查詢的數量）。你的解決方案對於大型N來說是相當有效的 - 當M是固定的時候，它就是'O（N）'，大約可以得到。然而，你的'O（N）'成本被分成兩部分，你重複其中一次'M'次，給你'O（N * M）'，當應該可以實現'O（N + M）'構建一個有效的查詢結構。基本上，雖然它減慢了單個查詢，但您需要考慮構建's'的*索引* –

感謝您的編輯。我不知道如何建立一個字符串的索引。 – canoe

你的問題與縮放的解決方案，是因爲你反覆掃描輸入的每個查詢，生成子陣列和直接尋找最低值。當你有很多查詢要處理時，這是低效的。例如，如果任何子字符串包含「A」，而包含該子字符串的字符串也包含「A」，但您的解決方案會拋棄先前的知識並重新計算。最終結果是，您的解決方案不僅可以根據輸入字符串的大小進行縮放，還可以將查詢數量乘以該值。如果s長，[p,q]也會導致性能下降。

您可以提高你的代碼通過預處理s換算成被設計成最有效地回答查詢索引結構。發現正確的結構使用是編碼問題挑戰的重要組成部分。獲得純粹的「正確輸出」代碼只有一半，所以62/100的評分標準似乎是有效的。

下面是一個索引結構，其能夠有效地從一個固定的字符串找到在給定的索引範圍內的最小文字。

開始由字符串分析成兩部分指數

s = "AGTCTTCGATGAAGCACATG" 
len = s.length 

# Index to answer "what count of each character type comes next in s" 
# E.g. next_char_instance["A"][7] returns the instance number of "A" that is 
# at or after position 7 (== 1) 
next_char_instance = Hash[ "A" => Array.new(len), "C" => Array.new(len), 
    "G" => Array.new(len), "T" => Array.new(len) ] 

# Index to answer "where does count value n of this character appear in s" 
# E.g. pos_of_char_instance["A"][1] returns the index position of 
# the second "A" (== 8) 
pos_of_char_instance = Hash[ "A" => Array.new, "C" => Array.new, 
    "G" => Array.new, "T" => Array.new ] 

# Basic building block during iteration 
next_instance_ids = Hash[ "A" => 0, "C" => 0, "G" => 0, "T" => 0 ] 

# Build the two indexes - O(N) 
(0...len).each do |i| 
    next_instance_ids.each do | letter, next_instance_id | 
    next_char_instance[letter][i] = next_instance_id 
    end 
    this_letter = s[i] 
    pos_of_char_instance[ this_letter ] << i 
    next_instance_ids[ this_letter ] += 1 
end

所以這是O(N)因爲你已經迭代串一次，所有的其他效果（有效）不變;好吧，創建陣列也是O(N)，但可能快10倍，如果你發現自己想到O(1.4 * N)，那麼沒有恐慌，你考慮純粹的縮放問題時扔掉常數1.4。

現在你有了這個索引，可以依次詢問「這個位置或之後的下一個A（或C或G）在哪裏」真正有效，你可以用它來快速找到裏面最小的字符一個特定的範圍。事實上，因爲它會被固定費用查詢和一些比較，這將是O(1)對於每個查詢，因此O(M)整體：

# Example queries 
p = [ 0, 3, 2, 7 ]  
q = [ 6, 4, 2, 9 ]  

# Search for each query - O(M) 
p.zip(q).map do | a, b | 
    # We need to find lowest character possible that fits into the range 
    "ACGT".chars.find do | letter | 
    next_instance_id = next_char_instance[ letter ][ a ] 
    pos_next_instance = pos_of_char_instance[ letter ][ next_instance_id ] 
    true if pos_next_instance && pos_next_instance <= b 
    end 
end 
# => ["A", "C", "T", "A"] is output for example data

我已經離開這個映射到信件，希望你可以看到，輸出1,2,3,4是微不足道的。事實上，編碼和使用基因組風格的字母在謎題中是紅色的，它們對解決方案沒有真正的影響（除了生成只有4個字母的結構更容易編碼爲固定值）。

上面的解決方案可能是很多。你應該注意到它依賴於允許的字母數量是固定的，並且不能用作在單個條目是整數或浮點數的範圍內找到最小值的答案。

來源

2013-11-22 14:20:11

基因組範圍查詢的Ruby實現

回答

相關問題