Comment trouver et renvoyer une valeur en double dans un tableau

arr est un tableau de chaînes:

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

Quel serait un moyen simple et élégant de vérifier s'il y arra des doublons, et si oui, d'en renvoyer un (peu importe lequel)?

Exemples:

["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 }

Je sais que ce n'est pas une réponse très élégante, mais je l'adore. C'est beau un code de ligne. Et fonctionne parfaitement bien, sauf si vous devez traiter un énorme ensemble de données.

Vous recherchez une solution plus rapide? Voici!

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

C'est linéaire, O (n), mais doit maintenant gérer plusieurs lignes de code, nécessite des cas de test, etc.

Si vous avez besoin d'une solution encore plus rapide, essayez peut-être C à la place.

Et voici l'essentiel de la comparaison de différentes solutions: https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

Vous pouvez le faire de plusieurs manières, la première étant la plus rapide:

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)

Et une option O (N ^ 2) (c'est-à-dire moins efficace):

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

Trouvez simplement la première instance où l'index de l'objet (en partant de la gauche) n'est pas égal à l'index de l'objet (en partant de la droite).

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

S'il n'y a pas de doublons, la valeur de retour sera nulle.

Je crois que c'est la solution la plus rapide publiée dans le fil jusqu'à présent, car elle ne repose pas sur la création d'objets supplémentaires #indexet #rindexest implémentée en C.Le runtime big-O est N ^ 2 et donc plus lent que Sergio, mais le temps du mur pourrait être beaucoup plus rapide en raison du fait que les parties "lentes" tournent en C.

detectne trouve qu'un seul doublon. find_allles trouvera tous:

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

Voici deux autres façons de trouver un doublon.

Utilisez un ensemble

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" 

Utilisez selectà la place de findpour renvoyer un tableau de tous les doublons.

Utilisation 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" 

Drop .firstpour renvoyer un tableau de tous les doublons.

Les deux méthodes retournent nils'il n'y a pas de doublons.

J'ai proposé que celaArray#difference soit ajouté au noyau Ruby. Plus d'informations sont dans ma réponse ici .

Référence

Comparons les méthodes suggérées. Tout d'abord, nous avons besoin d'un tableau pour tester:

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

et une méthode pour exécuter les benchmarks pour différents tableaux de test:

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

Je n'ai pas inclus la réponse de @ JjP car un seul duplicata doit être retourné, et lorsque sa réponse est modifiée pour cela, c'est la même chose que la réponse précédente de @ Naveed. Je n'ai pas non plus inclus la réponse de @ Marin, qui, bien que publiée avant la réponse de @ Naveed, a renvoyé tous les doublons plutôt qu'un seul (un point mineur mais il est inutile d'évaluer les deux, car ils sont identiques lorsqu'ils ne renvoient qu'un seul double).

J'ai également modifié d'autres réponses qui renvoyaient tous les doublons pour ne renvoyer que la première trouvée, mais cela ne devrait essentiellement avoir aucun effet sur les performances, car ils ont calculé tous les doublons avant d'en sélectionner un.

Les résultats de chaque benchmark sont répertoriés du plus rapide au plus lent:

Supposons d'abord que le tableau contienne 100 éléments:

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

Considérons maintenant un tableau avec 10000 éléments:

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

Notez que ce find_a_dup_using_difference(arr)serait beaucoup plus efficace s'il Array#differenceétait implémenté en C, ce qui serait le cas s'il était ajouté au noyau Ruby.

Conclusion

Beaucoup de réponses sont raisonnables, mais l' utilisation d'un ensemble est clairement le meilleur choix . Il est le plus rapide dans les cas moyennement durs, le joint le plus rapide dans les cas les plus difficiles et seulement dans les cas informatiques triviaux - lorsque votre choix n'a pas d'importance de toute façon - il peut être battu.

Le cas très particulier dans lequel vous pourriez choisir la solution de Chris serait si vous souhaitez utiliser la méthode pour dédupliquer séparément des milliers de petits tableaux et vous attendez à trouver un doublon généralement moins de 10 éléments. Ce sera un peu plus rapide car cela évite la petite surcharge supplémentaire liée à la création de l'ensemble.

Hélas, la plupart des réponses le sont O(n^2).

Voici une O(n)solution,

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

Quelle est la complexité de cela?

• Rentre O(n)et se brise lors du premier match
• Utilise la O(n)mémoire, mais seulement la quantité minimale

Maintenant, en fonction de la fréquence des doublons dans votre tableau, ces environnements d'exécution pourraient en fait devenir encore meilleurs. Par exemple, si le tableau de taille O(n)a été échantillonné à partir d'une population d' k << néléments différents, seule la complexité pour le temps d'exécution et l'espace devient O(k), cependant il est plus probable que l'affiche d'origine valide l'entrée et veuille s'assurer qu'il n'y a pas de doublons. Dans ce cas, à la fois la complexité de l'exécution et de la mémoire, O(n)car nous nous attendons à ce que les éléments n'aient pas de répétitions pour la majorité des entrées.

Objets Ruby Array ont une bonne méthode, select.

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

La première forme est ce qui vous intéresse ici. Il vous permet de sélectionner des objets qui passent un test.

Objets Ruby Array ont une autre méthode, count.

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

Dans ce cas, vous êtes intéressé par les doublons (objets qui apparaissent plus d'une fois dans le tableau). Le test approprié est a.count(obj) > 1.

Si a = ["A", "B", "C", "B", "A"], alors

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

Vous déclarez que vous ne voulez qu'un seul objet. Alors choisissez-en un.

find_all () retourne un arraycontenant tous les éléments de enumpour lesquels blockn'est pas false.

Pour obtenir des duplicateéléments

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

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

Ou des uniqéléments en double

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

Quelque chose comme ça fonctionnera

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 }

Autrement dit, placez toutes les valeurs dans un hachage où key est l'élément du tableau et valeur est le nombre d'occurrences. Sélectionnez ensuite tous les éléments qui se produisent plus d'une fois. Facile.

Je sais que ce fil concerne spécifiquement Ruby, mais j'ai atterri ici pour savoir comment le faire dans le contexte de Ruby on Rails avec ActiveRecord et j'ai pensé que je partagerais également ma solution.

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

Ce qui précède renvoie un tableau de toutes les adresses e-mail qui sont dupliquées dans la table de base de données de cet exemple (qui dans Rails serait "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

Ceci est une O(n)procédure.

Vous pouvez également utiliser l'une des lignes suivantes. Aussi O (n) mais une seule itération

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]

Voici mon point de vue sur un grand ensemble de données - comme une table dBase héritée pour trouver des pièces en double

# 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 est votre ami!

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}

Ce code renverra la liste des valeurs dupliquées. Les clés de hachage sont utilisées comme un moyen efficace de vérifier quelles valeurs ont déjà été vues. Selon que la valeur a été vue, le tableau d'origine aryest partitionné en 2 tableaux: le premier contenant des valeurs uniques et le second contenant des doublons.

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

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

=> ["hello"]

Vous pouvez le raccourcir davantage - mais au prix d'une syntaxe légèrement plus complexe - à cette forme:

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

Résultats

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

Si vous comparez deux tableaux différents (au lieu d'un par rapport à lui-même), un moyen très rapide consiste à utiliser l'opérateur d'intersection &fourni par la classe Ruby's Array .

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

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

J'avais besoin de savoir combien il y avait de doublons et ce qu'ils étaient, alors j'ai écrit une fonction basée sur ce que Naveed avait publié plus tôt:

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. Créons une méthode de duplication qui prend un tableau d'éléments en entrée
2. Dans le corps de la méthode, créons 2 nouveaux objets de tableau, l'un est vu et l'autre est dupliqué
3. enfin permet de parcourir chaque objet dans un tableau donné et pour chaque itération, trouvons que l'objet existait dans le tableau vu.
4. si l'objet existait dans le saw_array, alors il est considéré comme un objet dupliqué et pousse cet objet dans duplication_array
5. si l'objet n'existait pas dans le vu, alors il est considéré comme un objet unique et pousse cet objet dans vu_array

démontrons dans l'implémentation du code

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

Appelez maintenant la méthode de duplication et affichez le résultat de retour -

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

Notez que ce qui précède est destructeur