Comment trouver et retourner une valeur répétée dans le tableau

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'aime. Ceci est un beau code avec une ligne. Et fonctionne bien, sauf si vous avez besoin de gérer un énorme ensemble de données.

Vous cherchez une solution plus rapide? Vous voilà!

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

Il est linéaire O/n/, Mais maintenant il a besoin de gérer plusieurs lines-of-code, Besoin de cas de test, etc.

Si vous avez besoin de solution encore plus rapide, vous pouvez essayer C au lieu de cela.

Mais l'essence de la comparaison de diverses solutions:
https://gist.github.com/naveed ... 9743e

Vous pouvez le faire de plusieurs manières et la première option sera 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 option O/N^2/ /c'est-à-dire moins efficace/:

ary.select{ |e| ary.count/e/ > 1 }.uniq

Il suffit de trouver la première instance où l'indice d'objet /Compter à gauche/ pas égal à l'index de l'objet /Considérant juste/.

arr.detect {|e| arr.rindex/e/ != arr.index/e/ }

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

Je crois que c'est la solution la plus rapide publiée dans le flux jusqu'à présent, car elle ne dépend pas de la création d'objets supplémentaires, mais

#index

et

#rindex

mis en œuvre dans C. Délai de mise en œuvre big-O se réconcilier N^2 Et, par conséquent, plus lent que Sergio, mais le temps du mur peut être beaucoup plus rapide en raison du fait que des pièces "slow" Travailler dans C.

detect

Il n'y a qu'un seul duplicata.

find_all

va tous les trouver tous:

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

a.find_all { |e| a.count/e/ > 1 }

Voici deux autres façons de trouver un duplicata.

Utiliser l'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"

Utilisation

select

au lieu

find

, Pour retourner le 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"

Jeter

.first

, Pour retourner le tableau de tous les doublons.

Les deux méthodes sont retournées

nil

, S'il n'y a pas de doublons.

je
https://bugs.ruby-lang.org/issues/11815
Être ajouté à K. Ruby noyau. Pour plus d'informations, voir ma réponse.
https://coderoad.ru/24987054/
.

Indicateur

Comparons les méthodes proposé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 la méthode d'exécution des indicateurs de contrôle pour diverses matrices 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 @JjP's, Parce qu'un seul duplicata devrait être retourné et quand il/Sa réponse sera changée pour le faire, ce sera la même chose que la réponse précédente. @Naveed's. Je n'ai pas non plus l'inclusion de la réponse @Marin's, qui, étant envoyé à la réponse @Naveed's, retourné tous les doublons, et pas seulement un /un léger point, mais cela n'a aucun sens d'évaluer les deux, car ils sont identiques lorsqu'un seul duplicata est renvoyé/.

J'ai également modifié d'autres réponses qui ont renvoyé tous les doublons pour ne renvoyer que le premier trouvé, mais il n'aurait pas dû être considérablement affecté par la performance, car ils ont calculé tous les doublons avant de choisir l'un d'entre eux.

Les résultats pour chaque référence sont énumérés du plus rapide au plus lent:

Principalement supposer que le tableau contient 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

Maintenant considérons un tableau de 10 000 É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

find_a_dup_using_difference/arr/

Ce serait beaucoup plus efficace si

Array#difference

A été implémenté B. C, Que se passerait-il s'il a été ajouté au noyau Ruby.

Production

Beaucoup de réponses sont raisonnables, mais

L'utilisation d'un ensemble est le meilleur choix évident

. Il fonctionne plus rapidement dans les cas intermédiaires, cela fonctionne plus rapidement dans les cas les plus difficiles et les plus difficiles à caractère informatique - lorsque votre choix n'aura pas d'importance - Il peut être vaincu.

Le seul cas très spécial dans lequel vous pourriez choisir la décision de Chris, c'est si vous souhaitez utiliser cette méthode pour éliminer séparé des doublons de milliers de petites tableaux et s'attendre à trouver un duplicata, en règle générale, moins 10 Éléments. Ce sera un peu plus rapide, car il évitera de petits coûts supplémentaires supplémentaires pour créer un ensemble.

Hélas, la plupart des réponses

O/n^2/

.

Voici la solution

O/n/

,

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é?

Courir B.

O/n/

et se casse sur le premier match

Utilise la mémoire

O/n/

, Mais seulement le volume minimum

Maintenant, en fonction de la fréquence des duplicats dans votre tableau, ces environnements d'exécution peuvent être encore meilleurs. par exemple , Si la taille de la taille

O/n/

a été choisi parmi l'agrégat

k << n

différents éléments, puis la complexité à la fois pour le temps d'exécution et l'espace devient

O/k/

, Cependant, il est plus probable que l'affiche source vérifie les données d'entrée et veut s'assurer qu'il n'y a pas de doublons. Dans ce cas, le temps d'exécution et la complexité de la mémoire

O/n/

, Comme nous nous attendons à ce que des articles ne disposent pas de répétitions pour la plupart des données d'entrée.

Ruby Les objets de la matrice ont une excellente méthode,

select

.

select {|item| block } → new_ary

select → an_enumerator

Le premier formulaire est ce qui vous intéresse ici. Il vous permet de choisir des objets qui passent le test.

Ruby Les objets de la matrice ont une autre méthode,

count

.

count → int

count/obj/ → int

count { |item| block } → int

Dans ce cas, vous êtes intéressé par des duplicats /Objets qui apparaissent dans le tableau plus d'une fois/. Test correspondant

a.count/obj/ > 1

.

Si un

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

, cette

a.select{|item| a.count/item/ > 1}.uniq

=> ["A", "B"]

Vous déclarez que vous n'avez besoin que de

une

un objet. Alors choisissez-en un.

http://apidock.com/ruby/Enumerable/find_all
Retour

array

, Contenant tous les éléments

enum

, Pour qui

block

n'est pas

false

.

Obtenir

duplicate

Élément

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

>> arr.find_all { |x| arr.count/x/ > 1 }



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

Ou dupliquer

uniq

Élément

>> arr.find_all { |x| arr.count/x/ > 1 }.uniq

=> ["A", "B"]

Quelque chose comme ça va travailler

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 }

C'est-à-dire placer toutes les valeurs dans hash, où la clé est un élément de tableau et la valeur du nombre d'occurrences. Ensuite, sélectionnez tous les éléments rencontrés plus d'une fois. Facilement.

Je sais que ce sujet concerne spécifiquement Ruby, Mais j'ai atterri ici, cherche comment le faire dans son contexte Ruby sur Rails de ActiveRecord, Et pensais que je partagerais aussi ma décision.

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 la matrice de toutes les adresses email, qui sont dupliqués dans la table de base de données de cet exemple /qui B. Rails sera "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 procédure

O/n/

.

Sinon, vous pouvez faire l'une des lignes suivantes. Également 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 regard sur le grand ensemble de données - Par exemple, une table obsolète dBase rechercher 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-ce ton 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 retournera une liste de valeurs dupliquées. Hash Les clés sont utilisées comme moyen efficace de vérifier quelles valeurs ont déjà été observées. Selon si la valeur a été remarquée, le tableau d'origine

ary

brisé 2 Array: La première contient des valeurs uniques et les secondes duplicats.

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 couper encore plus - Bien que le prix soit une syntaxe un peu plus complexe - à ce formulaire:

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 /et pas un contre lui-même/, Très rapide moyen d'utiliser l'opérateur intersect

&

, À condition de
https://ruby-doc.org/core-2.4. ... -i-26
Ruby .

# Given

a = ['a', 'b', 'c', 'd']

b = ['e', 'f', 'c', 'd']



# Then this...

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

Je devais savoir combien de doublons étaient et ce qu'ils ont été imaginés, j'ai donc écrit un bâtiment fonctionnel de ce que Navid a publié précédemment:

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

Créons une méthode de duplication qui accepte une gamme d'éléments en tant que données d'entrée

Dans le corps de la méthode crée 2 nouveaux objets du tableau, dont l'un est visible et l'autre est dupliqué

Enfin, exécutons chaque objet dans cette matrice et pour chaque itération, nous constaterons que l'objet existait dans un tableau visible.

Si l'objet existait dans seen_array, Ensuite, il est considéré comme un objet en double et placé dans duplication_array

Si l'objet n'existe pas en vue, il est considéré comme un objet unique, puis cliquez sur ce que l'objet dans seen_array

Démontrons-le dans la mise en œuvre 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 renvoyé. -

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

Veuillez noter que ce qui précède est destructeur