Wie kann ich diese Ruby-Methode umgestalten, um schneller zu laufen?

Question

Die folgende Methode nimmt ein Array a und gibt die doppelte Ganzzahl zurück, deren zweiter Indexwert der niedrigste ist. Das Array enthält nur Ganzzahlen zwischen 1 und a.length. Mit diesem Beispiel

firstDuplicate([1,2,3,2,4,5,1]) 

gibt die Methode 2 zurück.

def firstDuplicate(a) 
    num = 1 
    big_num_array = [] 
    a.length.times do 
     num_array = [] 
     if a.include?(num) 
      num_array.push(a.index(num)) 
      a[a.index(num)] = "x" 
      if a.include?(num) 
       num_array.unshift(a.index(num)) 
       num_array.push(num) 
      end 
      big_num_array.push(num_array) if num_array.length == 3 
     end   
     num += 1 
    end 
    if big_num_array.length > 0 
     big_num_array.sort![0][2] 
    else 
     -1 
    end 
end 

Der Code funktioniert, scheint aber länger als nötig und läuft nicht schnell genug. Ich suche nach Wegen, dies zu überdenken.

Answer 1

Sie die Einträge zählen konnte, wie Sie gehen und verwenden Enumerable#find Iterieren so schnell zu stoppen, wie Sie etwas wieder finden:

h = { } 
a.find do |e| 
    h[e] = h[e].to_i + 1 # The `to_i` converts `nil` to zero without a bunch of noise. 
    h[e] == 2 
end 

konnte Sie auch sagen:

h = Hash.new(0) # to auto-vivify with zeros 
a.find do |e| 
    h[e] += 1 
    h[e] == 2 
end 

oder Hash#fetch mit einem Standardwert verwenden:

h = { } 
a.find do |e| 
    h[e] = h.fetch(e, 0) + 1 
    h[e] == 2 
end 

find stoppt, sobald es ein Element findet, das diesen Block true macht, so sollte dies einigermaßen effizient sein.

Answer 2

Wenn Sie nach Superperformance suchen, ist Rubin wahrscheinlich nicht die beste Sprache der Wahl. Wenn Sie für eine Lesbarkeit suchen, hier gehen Sie:

[1,2,3,2,4,5,1]. 
    map.    # or each (less readable, probably faster) 
    with_index. 
    group_by(&:shift). # or group_by(&:first) 
    min_by { |v, a| a[1] && a[1].last || Float::INFINITY }. 
    first 
#⇒ 2 

Answer 3

Hier sind zwei Möglichkeiten, die einfach gemacht werden könnten.

Verwenden Sie einen Satz

require 'set' 

def first_dup(arr) 
    st = Set.new 
    arr.find { |e| st.add?(e).nil? } 
end 

first_dup [1,2,3,2,4,5,4,1,4] 
    #=> 2 
first_dup [1,2,3,4,5] 
    #=> nil 

Set#add? See.

Verwenden Array#difference

def first_dup(arr) 
    arr.difference(arr.uniq).first 
end 

first_dup [1,2,3,2,4,5,4,1,4] 
    #=> 2 
first_dup [1,2,3,4,5] 
    #=> nil 

I Array#difference ausreichend nützlich erwiesen haben, dass ich proposed it be added to the Ruby core (aber es nicht Traktion gewinnen zu sein scheint). Es ist wie folgt:

class Array 
    def difference(other) 
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 } 
    reject { |e| h[e] > 0 && h[e] -= 1 } 
    end 
end 

Wie bei der Verbindung erläutert, ist es von Array#- unterscheidet sich wie folgt:

a = [1,2,2,3,3,2,2] 
b = [2,2,3] 

a - b 
    #=> [1] 
a.difference(b) 
    #=> [1,3,2,2] 

Das heißt, difference "entfernt" one 2 in a für jede 2 in b (ähnlich für 3), die Reihenfolge von dem behaltend, was von a übrig ist. a ist jedoch nicht mutiert.

Die Schritte in dem oben für das vorliegende Problem angegebenen Beispiel sind wie folgt.

arr = [1,2,3,2,4,5,4,1,4] 
a = arr.uniq 
    #=> [1,2,3,4,5] 
b = arr.difference(a) 
    #=> [2, 4, 1, 4] 
b.first 
    #=> 2