優化此紅寶石循環結構

Question

已知事實列表，請測試事實is_real?，然後僅返回如果speaker屬性也不指明alternative_facts，則返回passing_facts。

passing_facts, alternative_facts = [] 
@facts.each do |fact| 
    if fact.is_real? 
    passing_facts << fact 
    else 
    alternative_facts << fact 
    end 
end 

alternative_facts.each do |bad_fact| 
    passing_facts = passing_facts.reject {|good_fact| good_fact.speaker == bad_fact.speaker } 
end 

return passing_facts 

如何重新安排循環/測試，以便數據不必多次訪問。

定數據集有更多passing_facts比alternative_facts

Answer 1

您的第8行可以用Enumerable#partition替換。

該代碼在@facts上迭代一次，一次在alternative_facts之上，一次在passing_facts之上。它採用Set更快的查找：

require 'set' 

passing_facts, alternative_facts = @facts.partition(&:real?) 

bad_speakers = Set.new(alternative_facts.map(&:speakers)) 

passing_facts.reject! do |fact| 
    bad_speakers.include? fact.speaker 
end 

return passing_facts 

平均複雜性應該是O(n)，相比O(n**2)爲您的代碼和O(n*log(n))對對方的回答。

Answer 2

取決於如果算上排序爲循環，這可能就足夠了。

由於散列訪問很便宜，我們可以說它是O(1)，排序是O(n*log(n))。以下實施將具有O(n + n*log(n))，這與O(n*log(n))相同。這比你的例子中的O(n + n^2)〜O(n^2)小。

這也意味着訪問數據的次數少於您的示例中的次數。

sorted_facts = @facts.sort_by(:real?).reverse! 
author_invalidity = {} 

sorted_facts.select do |fact| 
    author_invalidity[fact.speaker] ||= !fact.real? 
    fact.real? && !author_invalidity[fact.speaker] 
end 

這個想法的快速解釋。

我們嘗試構建一個作者有效性的散列圖，以從您的示例中刪除嵌套循環。通過真實性分類事實，以便錯誤的事實先出現，我們可以保證，當我們迭代第一個真實事實時，我們在散列映射中擁有所有無效的作者。然後通過檢查散列和事實我們可以在同一次迭代中構建一個有效事實列表，我們構建散列。

請注意，author_invalidity和雙!是混淆，但要求使用||=。如果將存儲author_validity（例如author_validity[fact.speaker] ||= fact.real?），那麼在處理第一個有效作者之後，支票總是返回true。因此，邏輯必須是負面的。如其他答案中所述，可以使用Hash而不是。那麼邏輯將是積極的。

希望這能讓你在正確的方向思考。

Answer 3

我建議你按如下方式寫。

class Fact 
    def initialize (fact) 
    @fact = fact 
    end 
    def fact 
    @fact[:fact] 
    end 
    def is_real? 
    @fact[:real] 
    end 
    def speaker 
    @fact[:speaker] 
    end 
end 

創建一些實例。

facts = [["grass is green", true, "Bob"], ["bears are orange", false, "Sue"], 
     ["cats say 'woof'", false, "Bob"], ["dogs are delightful", true, "Hal"]]. 
      map { |f,t,s| Fact.new(fact: f, real: t, speaker: s) } 
    #=> [#<Fact:0x007fd363e4bcc0 @fact= 
    #  {:fact=>"grass is green", :real=>true, :speaker=>"Bob"}>, 
    # #<Fact:0x007fd363e4bc20 @fact= 
    #  {:fact=>"bears are orange", :real=>false, :speaker=>"Sue"}>, 
    # #<Fact:0x007fd363e4bb80 @fact= 
    #  {:fact=>"cats say 'woof'", :real=>false, :speaker=>"Bob"}>, 
    # #<Fact:0x007fd363e4bae0 @fact= 
    #  {:fact=>"dogs are delightful", :real=>true, :speaker=>"Sue"}> 
    # ] 

分區facts到passing_facts和alternative_facts。

passing_facts, alternative_facts = facts.partition(&:is_real?) 
    #=> [[#<Fact:0x007fd363e4bcc0 @fact= 
    #  {:fact=>"grass is green", :real=>true, :speaker=>"Bob"}>, 
    #  #<Fact:0x007fd363e4bae0 @fact= 
    #  {:fact=>"dogs are delightful", :real=>true, :speaker=>"Hal"}> 
    # ], 
    # [#<Fact:0x007fd363e4bc20 @fact= 
    #  {:fact=>"bears are orange", :real=>false, :speaker=>"Sue"}>, 
    #  #<Fact:0x007fd363e4bb80 @fact= 
    #  {:fact=>"cats say 'woof'", :real=>false, :speaker=>"Bob"}> 
    # ] 
    # ] 
passing_facts 
    #=> [#<Fact:0x007fd363e4bcc0 @fact= 
    #  {:fact=>"grass is green", :real=>true, :speaker=>"Bob"}>, 
    # #<Fact:0x007fd363e4bae0 @fact= 
    #  {:fact=>"dogs are delightful", :real=>true, :speaker=>"Hal"}> 
    # ] 
alternative_facts 
    # [#<Fact:0x007fd363e4bc20 @fact= 
    #  {:fact=>"bears are orange", :real=>false, :speaker=>"Sue"}>, 
    # #<Fact:0x007fd363e4bb80 @fact= 
    #  {:fact=>"cats say 'woof'", :real=>false, :speaker=>"Bob"}> 
    # ] 

編制發言人名單alternative_facts。

alternative_speakers = alternative_facts.map { |f| f.speaker } 
    #=> ["Sue", "Bob"] 

拒絕的passing_facts的量，鍵:speaker的值的alternative_speakers成員的元素，然後映射那些剩餘的事實的名稱。

passing_facts.reject { |f| alternative_speakers.include?(f.speaker) }. 
       map { |f| f.fact } 
    #=> ["dogs are delightful"] 

注

passing_facts.reject { |f| alternative_speakers.include?(f.speaker) } 
    #=> [#<Fact:0x007fd364a38e70 @fact= 
    #  {:fact=>"dogs are delightful", :real=>true, :speaker=>"Hal"}> 
    # ] 

如果有大量的「事實」的，效率可通過加入require 'set'和粘性.to_set到計算facts表達的端部改善。