Jak znaleźć i zwrócić zduplikowaną wartość w tablicy

arr to tablica ciągów:

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

Jaki byłby łatwy i elegancki sposób sprawdzenia, czy arrma duplikaty, a jeśli tak, zwróć jeden z nich (bez względu na który)?

Przykłady:

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

Wiem, że to niezbyt elegancka odpowiedź, ale uwielbiam ją. To piękny jeden kod liniowy. I działa doskonale, chyba że musisz przetwarzać ogromny zestaw danych.

Szukasz szybszego rozwiązania? Proszę bardzo!

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

Jest liniowy, O (n), ale teraz wymaga zarządzania wieloma wierszami kodu, wymaga przypadków testowych itp.

Jeśli potrzebujesz jeszcze szybszego rozwiązania, może zamiast tego wypróbuj C.

A oto sedno porównujące różne rozwiązania: https://gist.github.com/naveed-ahmad/8f0b926ffccf5fbd206a1cc58ce9743e

Możesz to zrobić na kilka sposobów, przy czym pierwsza opcja jest najszybsza:

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)

I opcja O (N ^ 2) (tj. Mniej wydajna):

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

Po prostu znajdź pierwszą instancję, w której indeks obiektu (licząc od lewej) nie jest równy indeksowi obiektu (licząc od prawej).

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

Jeśli nie ma duplikatów, wartość zwracana będzie równa zero.

Uważam, że jest to również najszybsze jak dotąd rozwiązanie opublikowane w wątku, ponieważ nie polega na tworzeniu dodatkowych obiektów #indexi #rindexjest zaimplementowane w C. Środowisko uruchomieniowe big-O to N ^ 2, a zatem wolniejsze niż Sergio's, ale czas ściany mógłby być znacznie szybszy ze względu na fakt, że „wolne” części działają w C.

detectznajduje tylko jeden duplikat. find_allznajdzie je wszystkie:

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

Oto dwa inne sposoby na znalezienie duplikatu.

Użyj zestawu

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" 

Użyj selectzamiast, findaby zwrócić tablicę wszystkich duplikatów.

Posługiwać się 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" 

Upuść, .firstaby zwrócić tablicę wszystkich duplikatów.

Obie metody zwracają się, niljeśli nie ma duplikatów.

I zaproponował, byArray#difference zostać dodany do rdzenia Ruby. Więcej informacji znajduje się w mojej odpowiedzi tutaj .

Reper

Porównajmy sugerowane metody. Najpierw potrzebujemy tablicy do testowania:

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

oraz metodę uruchamiania testów porównawczych dla różnych tablic testowych:

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

Nie załączyłem odpowiedzi @ JjP, ponieważ ma zostać zwrócony tylko jeden duplikat, a kiedy jego / jej odpowiedź jest tak zmodyfikowana, jest to taka sama, jak wcześniejsza odpowiedź @ Naveed. Nie zamieściłem również odpowiedzi @ Marin, która, mimo że opublikowana przed odpowiedzią @ Naveed, zwróciła wszystkie duplikaty, a nie tylko jeden (drobna uwaga, ale nie ma sensu oceniać obu, ponieważ są identyczne, gdy zwracają tylko jeden duplikat).

Zmodyfikowałem również inne odpowiedzi, które zwracały wszystkie duplikaty, aby zwracały tylko pierwszą znalezioną, ale to w zasadzie nie powinno mieć wpływu na wydajność, ponieważ obliczali wszystkie duplikaty przed wybraniem jednego.

Wyniki dla każdego testu porównawczego są wymienione od najszybszego do najwolniejszego:

Najpierw załóżmy, że tablica zawiera 100 elementów:

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

Rozważmy teraz tablicę zawierającą 10000 elementów:

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

Zauważ, że find_a_dup_using_difference(arr)byłoby to znacznie bardziej wydajne, gdyby Array#differencezostało zaimplementowane w C, co miałoby miejsce, gdyby zostało dodane do rdzenia Ruby.

Wniosek

Wiele odpowiedzi jest rozsądnych, ale użycie zestawu jest zdecydowanie najlepszym wyborem . Jest najszybszy w przypadkach średnio-twardych, łączony najszybciej w najtrudniejszych i tylko w przypadkach obliczeniowo błahych - gdy Twój wybór i tak nie ma znaczenia - można go pokonać.

Jedynym bardzo szczególnym przypadkiem, w którym możesz wybrać rozwiązanie Chrisa, jest to, że chcesz użyć metody do oddzielnego zduplikowania tysięcy małych tablic i spodziewasz się znaleźć duplikat zwykle mniej niż 10 elementów. Będzie to nieco szybsze ponieważ pozwala uniknąć małego dodatkowego obciążenia związanego z tworzeniem Zestawu.

Niestety większość odpowiedzi tak O(n^2).

Oto O(n)rozwiązanie,

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

Jaka jest złożoność tego?

• Wbiega O(n)i przerywa w pierwszym meczu
• Wykorzystuje O(n)pamięć, ale tylko minimalną ilość

Teraz, w zależności od tego, jak częste są duplikaty w twojej tablicy, te środowiska wykonawcze mogą stać się jeszcze lepsze. Na przykład, jeśli tablica rozmiarów O(n)została pobrana z populacji k << nróżnych elementów O(k), staje się to tylko złożoność zarówno dla środowiska wykonawczego, jak i przestrzeni , jednak jest bardziej prawdopodobne, że oryginalny plakat sprawdza poprawność danych wejściowych i chce się upewnić, że nie ma duplikatów. W takim przypadku zarówno czas wykonywania, jak i złożoność pamięci, O(n)ponieważ oczekujemy, że elementy nie będą miały powtórzeń dla większości danych wejściowych.

Ruby obiektów Array mają wielki metody select.

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

Tutaj interesuje Cię pierwsza forma. Pozwala wybrać obiekty, które przejdą test.

Ruby obiektów Array mieć inną metodę count.

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

W tym przypadku interesują Cię duplikaty (obiekty, które pojawiają się w tablicy więcej niż raz). Odpowiednim testem jest a.count(obj) > 1.

Jeśli a = ["A", "B", "C", "B", "A"]tak

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

Oświadczasz, że chcesz tylko jednego przedmiotu. Więc wybierz jedną.

find_all () zwraca element arrayzawierający wszystkie elementy, enumktórych blocknie jest false.

Aby zdobyć duplicateelementy

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

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

Lub zduplikowane uniqelementy

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

Coś takiego zadziała

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 }

To znaczy, umieść wszystkie wartości w hashu, gdzie klucz jest elementem tablicy, a wartość jest liczbą wystąpień. Następnie zaznacz wszystkie elementy, które występują więcej niż raz. Łatwo.

Wiem, że ten wątek dotyczy konkretnie Rubiego, ale wylądowałem tutaj, szukając, jak to zrobić w kontekście Ruby on Rails z ActiveRecord i pomyślałem, że podzielę się również moim rozwiązaniem.

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

Powyższe zwraca tablicę wszystkich adresów e-mail, które są zduplikowane w tabeli bazy danych tego przykładu (która w Railsach byłaby „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

To jest O(n)procedura.

Alternatywnie możesz wykonać jedną z następujących linii. Również O (n), ale tylko jedna iteracja

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]

Oto moje podejście do dużego zestawu danych - takich jak starsza tabela dBase do znajdowania zduplikowanych części

# 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 jest twoim przyjacielem!

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}

Ten kod zwróci listę zduplikowanych wartości. Klucze z krzyżykiem są używane jako skuteczny sposób sprawdzania, które wartości zostały już wyświetlone. Na podstawie tego, czy wartość została zauważona, oryginalna tablica aryjest dzielona na 2 tablice: pierwsza zawiera unikalne wartości, a druga zawiera duplikaty.

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

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

=> ["hello"]

Możesz go dodatkowo skrócić - aczkolwiek kosztem nieco bardziej złożonej składni - do tej postaci:

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

Wyniki

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

Jeśli porównujesz dwie różne tablice (zamiast jednej ze sobą), bardzo szybkim sposobem jest użycie operatora przecięcia &dostarczonego przez klasę Array Rubiego .

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

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

Musiałem dowiedzieć się, ile było duplikatów i czym one były, więc napisałem funkcję bazującą na tym, co napisał wcześniej Naveed:

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. Utwórzmy metodę powielania, która pobierze tablicę elementów jako dane wejściowe
2. W treści metody stwórzmy 2 nowe obiekty tablicowe, jeden jest widoczny, a drugi jest zduplikowany
3. na koniec pozwala iterować przez każdy obiekt w podanej tablicy i dla każdej iteracji pozwala znaleźć obiekt, który istniał w widzianej tablicy.
4. jeśli obiekt istniał w tablicy seen_array, jest traktowany jako obiekt zduplikowany i umieszczany w tablicy duplication_array
5. jeśli obiekt nie istnieje w widzianym, to jest traktowany jako unikatowy obiekt i wepchnij ten obiekt do widzianej tablicy

pokażmy w implementacji kodu

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

Teraz wywołaj metodę powielania i zwróć wynik -

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

Zauważ, że powyższe jest destrukcyjne