Ruby - skrzyżowanie macierzy (z duplikatami)

Question

Mam array(1 and 2). Jak mogę uzyskać od nich array3?

array1 = [2,2,2,2,3,3,4,5,6,7,8,9] 

array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0] 

array3 = [2,2,2,3,4,8] 

array1 & array2 powraca [2,3,4,8], ale muszę się trzymać duplikatów.

Answer 1

(array1 & array2).flat_map { |n| [n]*[array1.count(n), array2.count(n)].min } 
    #=> [2,2,2,3,4,8] 

etapy:

a = array1 & array2 
    #=> [2, 3, 4, 8] 

Pierwszy element a (2) jest przekazywane do bloku i przypisany zmiennej blokowego:

n = 2 

i obliczenie bloku następuje:

[2]*[array1.count(2), array2.count(2)].min 
    #=> [2]*[4,3].min 
    #=> [2]*3 
    #=> [2,2,2] 

tak 2 jest zmapowany do [2,2,2]. Obliczenia są podobne dla pozostałych trzech elementów z a. Ponieważ używam flat_map, to zwraca [2,2,2,3,4,8].

Czy masz problemy z zapamiętaniem, jak różni się Enumerable#flat_map od Enumerable#map? Załóżmy, że użyłem map zamiast flat_map. Następnie

a.map { |n| [n]*[array1.count(n), array2.count(n)].min } 
    #=> [[2, 2, 2], [3], [4], [8]] 

flat_map robi nic więcej niż umieścić ikona przed każdym z tych tablic:

[*[2, 2, 2], *[3], *[4], *[8]] 
    #=> [2, 2, 2, 3, 4, 8] 

Jeżeli macierze array1 i array2 są duże i sprawność jest problemem, mogliśmy zrobić trochę o (N) pre-processing:

def cnt(arr) 
    arr.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 } 
end 

cnt1 = cnt(array1) 
    #=> {2=>4, 3=>2, 4=>1, 5=>1, 6=>1, 7=>1, 8=>1, 9=>1} 
cnt2 = cnt(array2) 
    #=> {2=>3, 3=>1, 4=>4, 8=>2, 0=>3} 

(array1 & array2).flat_map { |n| [n]*[cnt1[n], cnt2[n]].min } 
    #=> [2,2,2,3,4,8] 

Answer 2

array1 = [2,2,2,2,3,3,4,5,6,7,8,9] 
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0] 

a1, a2 = array1.dup, array2.dup # we’ll mutate them 

loop.with_object([]) do |_, memo| 
    break memo if a1.empty? || a2.empty? 
    e = a2.delete_at(a2.index(a1.shift)) rescue nil 
    memo << e if e 
end 
#⇒ [2,2,2,3,4,8] 

Answer 3

array1 = [2,2,2,2,3,3,4,5,6,7,8,9] 
    array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0] 

Uzyskanie częstotliwości każdego elementu macierzy próbek:

a1_freq=Hash.new(0); a2_freq=Hash.new(0); dup_items=[]; 
    array1.each {|a| a1_freq[a]+=1 } 
    array2.each {|b| a2_freq[b]+=1 } 

wreszcie porównanie elementy, jeśli są one obecne w drugiej tablicy, czy nie. Jeśli tak, należy przyjąć minimalną liczbę wspólnego elementu znajdującego się w obu tablicach próbek.

a1_freq.each {|k,v| a2_freq[k] ? dup_items+=[k]*[v,a2_freq[k]].min : nil} 
    #dup_items=> [2, 2, 2, 3, 4, 8] 

Answer 4

Jest nieco rozwlekły, ale zakładając, że masz na myśli, gdzie wartości są w tym samym miejscu:

def combine(array1, array2) 
    longer_array = array1.length > array2.length ? array1 : array2 

    intersection = [] 
    count = 0 
    longer_array.each do |item| 
     if array1 == longer_array 
      looped_array = array2 
     else 
      looped_array = array1 
     end 
     if item == looped_array[count] 
      intersection.push(item) 
     end 
     count +=1 
    end 
    print intersection 
end 


array_1 = [2,2,2,2,3,3,4,5,6,7,8,9] 
array_2 = [2,2,2,3,4,4,4,4,8,8,0,0,0] 


combine(array_1, array_2) 

Chciałem tylko zwrócić uwagę, że nie mam pojęcia, jak masz do tablicy 3 ponieważ położenie indeksu 3 we wszystkich trzech macierzach różnią:

array_1[3] = 2 

array_2[3] = 3 

array_3[3] = 3 

Answer 5

postaram się osiągnąć oczekiwany rezultat w ten sposób:

array1, array2 = [array1, array2].sort_by(&:size) 
arr_copy = array2.dup 

array1.each.with_object([]) do |el, arr| 
    index = arr_copy.find_index(el) 
    arr << arr_copy.slice!(index) if index 
end 
# => [2, 2, 2, 3, 4, 8] 

Answer 6

To jest zabawne; Rozwiązanie Cary'ego flat_map jest szczególnie sprytne.Oto alternatywa jedno-liner stosując regularne stare map z jakiejś pomocy od each_with_object:

array1.each_with_object(array2.dup).map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact 
#=> [2,2,2,3,4,8] 

Wiele złożoności tutaj polega inline gimnastyka wykorzystywane w celu zapewnienia map wystarczających informacji, aby wykonać zadanie:

# 
# we want to duplicate array2 since we'll be 
# mutating it to track duplicates  
#      \  array1  array2 
#      \  value  copy 
#       \   \ /
array1.each_with_object(array2.dup).map{|v,t| ... } 
#   |      /  
# Enumerator for array1 Iterate over    
# with a copy of array2 Enumerator with map 

Możemy użyć each_with_object, aby dostarczyć moduł wyliczający dla tablicy 1, który również daje naszemu łańcuchowi metod dostęp do kopii tablicy2. Mapę można następnie przetestować na module wyliczającym each_with_object (który odwołuje się do array1), ładując każdą wartość do zmiennej lokalnej v i naszej kopii array2 do zmiennej lokalnej t. Stamtąd:

#    map the value IF... 
#    /it exists in  and we were able to 
#   /our array2 copy remove it from our copy 
#   /  |    | 
map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact 
# | \   \        | 
# array1 \  \       dump nils 
# value array2 \ 
#   copy  load index position into temporary variable l 

Mamy iteracyjne nad każdej wartości tablica1 i sprawdzić, czy wartość istnieje w tablica2 (przez t). Jeśli istnieje, usuniemy pierwsze wystąpienie wartości z naszej kopii array2 i map wartość naszej wynikowej tablicy.

Uwaga: kontrola t.index(v) przed t.slice!(t.index(v)) jest używana jako zabezpieczenie przed zwarciem w przypadku, gdy wartość nie istnieje w ramach t, naszej kopii tablicy2. Korzystamy również z inkrementacji polegającej na przypisywaniu wartości indeksu do lokalnej zmiennej l tutaj: (l = t.index v), abyśmy mogli odnieść się do l w kolejnej kontroli boolowskiej: t.slice!(l).

Wreszcie, ponieważ ta metodologia będzie mapować wartości zerowe, gdy wartość tablicy1 nie istnieje w tablicy2, my compact wynik, aby usunąć nils.

---

Dla ciekawskich, oto kilka testów porównawczych prezentowanych rozwiązań. Po pierwsze, tutaj są szybkości wykonywania operacji taktowany 100.000 razy na tablicach przykładowych:

Cary:  1.050000 0.010000 1.060000 ( 1.061217) 
Cary+:  1.580000 0.010000 1.590000 ( 1.603645) 
Cam:   0.550000 0.010000 0.560000 ( 0.552062) 
Mudasobwa: 2.540000 0.050000 2.590000 ( 2.610395) 
Sergii:  0.660000 0.000000 0.660000 ( 0.665408) 
Sahil:  1.750000 0.010000 1.760000 ( 1.769624) 
#Tommy:  0.290000 0.000000 0.290000 ( 0.290114) 

Jeśli rozszerzymy tablice testowe trzymać 10000 liczb całkowitych z wysokim stopniem skrzyżowaniu ...

array1 = array2 = [] 
10000.times{ array1 << rand(10) } 
10000.times{ array2 << rand(10) } 

i pętla 100 razy, proste rozwiązanie pętli (Sahil) zaczyna się rozróżniać. Rozwiązanie Cary trzyma też się dobrze, zwłaszcza z wyprzedzającym:

    user  system  total  real 
Cary:  1.590000 0.020000 1.610000 ( 1.615798) 
Cary+:  0.870000 0.010000 0.880000 ( 0.879331) 
Cam:   6.680000 0.090000 6.770000 ( 6.838829) 
Mudasobwa: 6.740000 0.080000 6.820000 ( 6.898394) 
Sergii:  6.760000 0.100000 6.860000 ( 6.962025) 
Sahil:  0.740000 0.030000 0.770000 ( 0.785975) 
#Tommy:  0.430000 0.010000 0.440000 ( 0.446482) 

Na tablicach 1/10th wielkości z 1000 liczb całkowitych i niskim stopniu skrzyżowaniu jednak ...

array1 = array2 = [] 
1000.times{ array1 << rand(10000) } 
1000.times{ array2 << rand(10000) } 

kiedy pętla 10 razy, rozwiązanie flat_map zostaje spłaszczona ... z wyjątkiem jeśli używamy przerób (Cary +):

    user  system  total  real 
Cary:  135.400000 0.700000 136.100000 (137.123393) 
Cary+:  0.270000 0.010000 0.280000 ( 0.268255) 
Cam:   0.670000 0.000000 0.670000 ( 0.676438) 
Mudasobwa: 0.670000 0.010000 0.680000 ( 0.684088) 
Sergii:  0.660000 0.010000 0.670000 ( 0.673881) 
Sahil:  1.970000 2.130000 4.100000 ( 4.121759) 
#Tommy:  0.050000 0.000000 0.050000 ( 0.045970) 

Oto istota z benchmarków: https://gist.github.com/camerican/139463b4bd9e0fd89424377931042ce4