So finden Sie einen doppelten Wert im Array und geben ihn zurück

arr ist ein Array von Zeichenfolgen:

["hello", "world", "stack", "overflow", "hello", "again"]

Was wäre eine einfache und elegante Möglichkeit, um zu überprüfen, ob arrDuplikate vorhanden sind, und wenn ja, eines davon zurückzugeben (egal welches)?

Beispiele:

["A", "B", "C", "B", "A"]    # => "A" or "B"
["A", "B", "C"]              # => nil

a = ["A", "B", "C", "B", "A"]
a.detect{ |e| a.count(e) > 1 }

Ich weiß, dass dies keine sehr elegante Antwort ist, aber ich liebe es. Es ist wunderschön einzeiliger Code. Und funktioniert einwandfrei, es sei denn, Sie müssen große Datenmengen verarbeiten.

Suchen Sie nach einer schnelleren Lösung? Bitte schön!

def find_one_using_hash_map(array)
  map = {}
  dup = nil
  array.each do |v|
    map[v] = (map[v] || 0 ) + 1

    if map[v] > 1
      dup = v
      break
    end
  end

  return dup
end

Es ist linear, O (n), muss aber jetzt mehrere Codezeilen verwalten, benötigt Testfälle usw.

Wenn Sie eine noch schnellere Lösung benötigen, versuchen Sie es stattdessen mit C.

Und hier ist der Kern, der verschiedene Lösungen vergleicht: https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

Sie können dies auf verschiedene Arten tun, wobei die erste Option die schnellste ist:

ary = ["A", "B", "C", "B", "A"]

ary.group_by{ |e| e }.select { |k, v| v.size > 1 }.map(&:first)

ary.sort.chunk{ |e| e }.select { |e, chunk| chunk.size > 1 }.map(&:first)

Und eine O (N ^ 2) -Option (dh weniger effizient):

ary.select{ |e| ary.count(e) > 1 }.uniq

Suchen Sie einfach die erste Instanz, in der der Index des Objekts (von links gezählt) nicht dem Index des Objekts entspricht (von rechts zählen).

arr.detect {|e| arr.rindex(e) != arr.index(e) }

Wenn keine Duplikate vorhanden sind, ist der Rückgabewert Null.

Ich glaube, dies ist auch die schnellste Lösung, die bisher im Thread veröffentlicht wurde, da sie nicht auf der Erstellung zusätzlicher Objekte beruht #indexund #rindexin C implementiert ist. Die Big-O-Laufzeit ist N ^ 2 und daher langsamer als Sergios, aber die Wandzeit könnte viel schneller sein, da die "langsamen" Teile in C laufen.

detectfindet nur ein Duplikat. find_allwird sie alle finden:

a = ["A", "B", "C", "B", "A"]
a.find_all { |e| a.count(e) > 1 }

Hier sind zwei weitere Möglichkeiten, ein Duplikat zu finden.

Verwenden Sie ein Set

require 'set'

def find_a_dup_using_set(arr)
  s = Set.new
  arr.find { |e| !s.add?(e) }
end

find_a_dup_using_set arr
  #=> "hello" 

Verwenden Sie selectanstelle von find, um ein Array aller Duplikate zurückzugeben.

Verwenden Array#difference

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

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

find_a_dup_using_difference arr
  #=> "hello" 

Löschen .first, um ein Array aller Duplikate zurückzugeben.

Beide Methoden werden zurückgegeben, nilwenn keine Duplikate vorhanden sind.

Ich schlug vor,Array#difference das dem Ruby-Kern hinzuzufügen. Weitere Informationen finden Sie in meiner Antwort hier .

Benchmark

Vergleichen wir die vorgeschlagenen Methoden. Zunächst benötigen wir ein Array zum Testen:

CAPS = ('AAA'..'ZZZ').to_a.first(10_000)
def test_array(nelements, ndups)
  arr = CAPS[0, nelements-ndups]
  arr = arr.concat(arr[0,ndups]).shuffle
end

und eine Methode zum Ausführen der Benchmarks für verschiedene Testarrays:

require 'fruity'

def benchmark(nelements, ndups)
  arr = test_array nelements, ndups
  puts "\n#{ndups} duplicates\n"    
  compare(
    Naveed:    -> {arr.detect{|e| arr.count(e) > 1}},
    Sergio:    -> {(arr.inject(Hash.new(0)) {|h,e| h[e] += 1; h}.find {|k,v| v > 1} ||
                     [nil]).first },
    Ryan:      -> {(arr.group_by{|e| e}.find {|k,v| v.size > 1} ||
                     [nil]).first},
    Chris:     -> {arr.detect {|e| arr.rindex(e) != arr.index(e)} },
    Cary_set:  -> {find_a_dup_using_set(arr)},
    Cary_diff: -> {find_a_dup_using_difference(arr)}
  )
end

Ich habe die Antwort von @ JjP nicht aufgenommen, da nur ein Duplikat zurückgegeben werden soll. Wenn seine Antwort geändert wird, entspricht dies der früheren Antwort von @ Naveed. Ich habe auch nicht die Antwort von @ Marin aufgenommen, die, obwohl sie vor der Antwort von @ Naveed veröffentlicht wurde, alle Duplikate und nicht nur eines zurückgegeben hat (ein kleiner Punkt, aber es macht keinen Sinn, beide zu bewerten, da sie identisch sind, wenn nur ein Duplikat zurückgegeben wird).

Ich habe auch andere Antworten geändert, bei denen alle Duplikate zurückgegeben wurden, um nur die zuerst gefundenen zurückzugeben. Dies sollte jedoch im Wesentlichen keine Auswirkungen auf die Leistung haben, da alle Duplikate vor der Auswahl eines Duplikats berechnet wurden.

Die Ergebnisse für jeden Benchmark sind vom schnellsten zum langsamsten aufgeführt:

Angenommen, das Array enthält 100 Elemente:

benchmark(100, 0)
0 duplicates
Running each test 64 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is similar to Ryan
Ryan is similar to Sergio
Sergio is faster than Chris by 4x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 1)
1 duplicates
Running each test 128 times. Test will take about 2 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Ryan by 2x ± 1.0
Ryan is similar to Sergio
Sergio is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(100, 10)
10 duplicates
Running each test 1024 times. Test will take about 3 seconds.
Chris is faster than Naveed by 2x ± 1.0
Naveed is faster than Cary_diff by 2x ± 1.0 (results differ: AAC vs AAF)
Cary_diff is similar to Cary_set
Cary_set is faster than Sergio by 3x ± 1.0 (results differ: AAF vs AAC)
Sergio is similar to Ryan

Betrachten Sie nun ein Array mit 10.000 Elementen:

benchmark(10000, 0)
0 duplicates
Running each test once. Test will take about 4 minutes.
Ryan is similar to Sergio
Sergio is similar to Cary_set
Cary_set is similar to Cary_diff
Cary_diff is faster than Chris by 400x ± 100.0
Chris is faster than Naveed by 3x ± 0.1

benchmark(10000, 1)
1 duplicates
Running each test once. Test will take about 1 second.
Cary_set is similar to Cary_diff
Cary_diff is similar to Sergio
Sergio is similar to Ryan
Ryan is faster than Chris by 2x ± 1.0
Chris is faster than Naveed by 2x ± 1.0

benchmark(10000, 10)
10 duplicates
Running each test once. Test will take about 11 seconds.
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 3x ± 1.0 (results differ: AAE vs AAA)
Sergio is similar to Ryan
Ryan is faster than Chris by 20x ± 10.0
Chris is faster than Naveed by 3x ± 1.0

benchmark(10000, 100)
100 duplicates
Cary_set is similar to Cary_diff
Cary_diff is faster than Sergio by 11x ± 10.0 (results differ: ADG vs ACL)
Sergio is similar to Ryan
Ryan is similar to Chris
Chris is faster than Naveed by 3x ± 1.0

Beachten Sie, dass find_a_dup_using_difference(arr)dies viel effizienter wäre, wenn Array#differencees in C implementiert würde, was der Fall wäre, wenn es dem Ruby-Kern hinzugefügt würde.

Fazit

Viele der Antworten sind vernünftig, aber die Verwendung eines Sets ist die eindeutig beste Wahl . Es ist am schnellsten in mittelschweren Fällen, am schnellsten in den schwierigsten Fällen und nur in rechnerisch trivialen Fällen - wenn Ihre Wahl sowieso keine Rolle spielt - kann es geschlagen werden.

Der ganz besondere Fall, in dem Sie sich für die Lösung von Chris entscheiden könnten, wäre, wenn Sie die Methode verwenden möchten, um Tausende kleiner Arrays separat zu de-duplizieren und ein Duplikat zu finden, das normalerweise weniger als 10 Elemente enthält. Dies ist etwas schneller Dies vermeidet den geringen zusätzlichen Aufwand beim Erstellen des Sets.

Leider sind die meisten Antworten O(n^2).

Hier ist eine O(n)Lösung,

a = %w{the quick brown fox jumps over the lazy dog}
h = Hash.new(0)
a.find { |each| (h[each] += 1) == 2 } # => 'the"

Was ist die Komplexität davon?

• Läuft ein O(n)und bricht beim ersten Spiel ab
• Verwendet O(n)Speicher, aber nur die minimale Menge

Abhängig davon, wie häufig Duplikate in Ihrem Array vorhanden sind, werden diese Laufzeiten möglicherweise sogar noch besser. Wenn das Größenarray beispielsweise O(n)aus einer Population k << nverschiedener Elemente abgetastet wurde, wird nur die Komplexität sowohl für die Laufzeit als auch für den Speicherplatz. O(k)Es ist jedoch wahrscheinlicher, dass das Originalposter die Eingabe validiert und sicherstellen möchte, dass keine Duplikate vorhanden sind. In diesem Fall sind sowohl die Laufzeit als auch die Speicherkomplexität zu O(n)erwarten, da die Elemente für die meisten Eingaben keine Wiederholungen aufweisen.

Ruby Array-Objekte haben eine großartige Methode select.

select {|item| block } → new_ary
select → an_enumerator

Die erste Form interessiert Sie hier. Hier können Sie Objekte auswählen, die einen Test bestehen.

Ruby Array-Objekte haben eine andere Methode count.

count → int
count(obj) → int
count { |item| block } → int

In diesem Fall interessieren Sie sich für Duplikate (Objekte, die mehr als einmal im Array vorkommen). Der entsprechende Test ist a.count(obj) > 1.

Wenn ja a = ["A", "B", "C", "B", "A"], dann

a.select{|item| a.count(item) > 1}.uniq
=> ["A", "B"]

Sie geben an, dass Sie nur ein Objekt möchten . Wählen Sie also eine aus.

find_all () gibt ein zurück, arraydas alle Elemente enthält, enumfür die dies blocknicht der Fall ist false.

Um duplicateElemente

>> arr = ["A", "B", "C", "B", "A"]
>> arr.find_all { |x| arr.count(x) > 1 }

=> ["A", "B", "B", "A"]

Oder doppelte uniqElemente

>> arr.find_all { |x| arr.count(x) > 1 }.uniq
=> ["A", "B"] 

So etwas wird funktionieren

arr = ["A", "B", "C", "B", "A"]
arr.inject(Hash.new(0)) { |h,e| h[e] += 1; h }.
    select { |k,v| v > 1 }.
    collect { |x| x.first }

Das heißt, setzen Sie alle Werte in einen Hash, wobei key das Element des Arrays und value die Anzahl der Vorkommen ist. Wählen Sie dann alle Elemente aus, die mehrmals vorkommen. Einfach.

Ich weiß, dass es in diesem Thread speziell um Ruby geht, aber ich bin hier gelandet und habe nach einer Möglichkeit gesucht, dies im Kontext von Ruby on Rails mit ActiveRecord zu tun, und dachte, ich würde auch meine Lösung teilen.

class ActiveRecordClass < ActiveRecord::Base
  #has two columns, a primary key (id) and an email_address (string)
end

ActiveRecordClass.group(:email_address).having("count(*) > 1").count.keys

Das Obige gibt ein Array aller E-Mail-Adressen zurück, die in der Datenbanktabelle dieses Beispiels dupliziert sind (in Rails wäre dies "active_record_classes").

a = ["A", "B", "C", "B", "A"]
a.each_with_object(Hash.new(0)) {|i,hash| hash[i] += 1}.select{|_, count| count > 1}.keys

Dies ist eine O(n)Prozedur.

Alternativ können Sie eine der folgenden Zeilen ausführen. Auch O (n) aber nur eine Iteration

a.each_with_object(Hash.new(0).merge dup: []){|x,h| h[:dup] << x if (h[x] += 1) == 2}[:dup]

a.inject(Hash.new(0).merge dup: []){|h,x| h[:dup] << x if (h[x] += 1) == 2;h}[:dup]

Hier ist meine Sicht auf einen großen Datensatz - wie eine ältere dBase-Tabelle, um doppelte Teile zu finden

# Assuming ps is an array of 20000 part numbers & we want to find duplicates
# actually had to it recently.
# having a result hash with part number and number of times part is 
# duplicated is much more convenient in the real world application
# Takes about 6  seconds to run on my data set
# - not too bad for an export script handling 20000 parts

h = {};

# or for readability

h = {} # result hash
ps.select{ |e| 
  ct = ps.count(e) 
  h[e] = ct if ct > 1
}; nil # so that the huge result of select doesn't print in the console

r = [1, 2, 3, 5, 1, 2, 3, 1, 2, 1]

r.group_by(&:itself).map { |k, v| v.size > 1 ? [k] + [v.size] : nil }.compact.sort_by(&:last).map(&:first)

each_with_object ist dein Freund!

input = [:bla,:blubb,:bleh,:bla,:bleh,:bla,:blubb,:brrr]

# to get the counts of the elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}
=> {:bla=>3, :blubb=>2, :bleh=>2, :brrr=>1}

# to get only the counts of the non-unique elements in the array:
> input.each_with_object({}){|x,h| h[x] ||= 0; h[x] += 1}.reject{|k,v| v < 2}
=> {:bla=>3, :blubb=>2, :bleh=>2}

Dieser Code gibt eine Liste doppelter Werte zurück. Hash-Schlüssel werden verwendet, um effizient zu überprüfen, welche Werte bereits gesehen wurden. Basierend darauf, ob ein Wert gesehen wurde, wird das ursprüngliche Array aryin zwei Arrays aufgeteilt: das erste enthält eindeutige Werte und das zweite enthält Duplikate.

ary = ["hello", "world", "stack", "overflow", "hello", "again"]

hash={}
arr.partition { |v| hash.has_key?(v) ? false : hash[v]=0 }.last.uniq

=> ["hello"]

Sie können es weiter verkürzen - wenn auch auf Kosten einer etwas komplexeren Syntax - auf diese Form:

hash={}
arr.partition { |v| !hash.has_key?(v) && hash[v]=0 }.last.uniq

a = ["A", "B", "C", "B", "A"]
b = a.select {|e| a.count(e) > 1}.uniq
c = a - b
d = b + c

Ergebnisse

 d
=> ["A", "B", "C"]

Wenn Sie zwei verschiedene Arrays vergleichen (anstatt eines mit sich selbst), können Sie sehr schnell den &von der Ruby-Array-Klasse bereitgestellten Schnittoperator verwenden .

# Given
a = ['a', 'b', 'c', 'd']
b = ['e', 'f', 'c', 'd']

# Then this...
a & b # => ['c', 'd']

Ich musste herausfinden, wie viele Duplikate es gab und was sie waren, also schrieb ich eine Funktion, die auf dem aufbaute, was Naveed zuvor gepostet hatte:

def print_duplicates(array)
  puts "Array count: #{array.count}"
  map = {}
  total_dups = 0
  array.each do |v|
    map[v] = (map[v] || 0 ) + 1
  end

  map.each do |k, v|
    if v != 1
      puts "#{k} appears #{v} times"
      total_dups += 1
    end
  end
  puts "Total items that are duplicated: #{total_dups}"
end

1. Lassen Sie uns eine Duplizierungsmethode erstellen, die ein Array von Elementen als Eingabe verwendet
2. Erstellen Sie im Methodenkörper zwei neue Array-Objekte, von denen eines angezeigt und eines doppelt vorhanden ist
3. Lassen Sie uns schließlich jedes Objekt in einem bestimmten Array durchlaufen und bei jeder Iteration feststellen, dass das Objekt in einem sichtbaren Array vorhanden ist.
4. Wenn ein Objekt im Seen_array vorhanden war, wird es als doppeltes Objekt betrachtet und dieses Objekt in das Duplizierungsarray verschoben
5. Wenn das Objekt im Gesehenen nicht vorhanden ist, wird es als eindeutiges Objekt betrachtet und das Objekt in "Seen_Array" verschoben

Lassen Sie uns in der Code-Implementierung demonstrieren

def duplication given_array
  seen_objects = []
  duplication_objects = []

  given_array.each do |element|
    duplication_objects << element if seen_objects.include?(element)
    seen_objects << element
  end

  duplication_objects
end

Rufen Sie nun die Duplizierungsmethode auf und geben Sie das Ergebnis zurück -

dup_elements = duplication [1,2,3,4,4,5,6,6]
puts dup_elements.inspect

[1,2,3].uniq!.nil? => true [1,2,3,3].uniq!.nil? => false

Beachten Sie, dass das oben Genannte destruktiv ist