Jak liczyć identyczne elementy łańcuchowe w tablicy Ruby


91

Mam następujące Array = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]

Jak obliczyć liczbę dla każdego identycznego elementu ?

Where:
"Jason" = 2, "Judah" = 3, "Allison" = 1, "Teresa" = 1, "Michelle" = 1?

lub stwórz hash Gdzie:

Gdzie: hash = {"Jason" => 2, "Judah" => 3, "Allison" => 1, "Teresa" => 1, "Michelle" => 1}


2
Od wersji Ruby 2.7 możesz używać Enumerable#tally. Więcej informacji tutaj .
SRack

Odpowiedzi:


82
names = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]
counts = Hash.new(0)
names.each { |name| counts[name] += 1 }
# => {"Jason" => 2, "Teresa" => 1, ....

127
names.inject(Hash.new(0)) { |total, e| total[e] += 1 ;total}

daje Ci

{"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1} 

3
+1 Podobnie jak wybrana odpowiedź, ale ja wolę używać wtrysku i żadnej zmiennej „zewnętrznej”.

18
Jeśli używasz each_with_objectzamiast injectyou, nie musisz zwracać ( ;total) w bloku.
mfilej,

12
Dla potomnych to właśnie oznacza @mfilej:array.each_with_object(Hash.new(0)){|string, hash| hash[string] += 1}
Gon Zifroni

2
Z Ruby 2.7, można po prostu zrobić: names.tally.
Hallgeir Wilhelmsen

99

Ruby v2.7 + (najnowszy)

Począwszy od wersji 2.7.0 Ruby (wydanej w grudniu 2019 r.), Rdzeń języka zawiera teraz Enumerable#tally- nową metodę , zaprojektowaną specjalnie dla tego problemu:

names = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]

names.tally
#=> {"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1}

Ruby v2.4 + (obecnie obsługiwane, ale starsze)

Poniższy kod nie był możliwy w standardowym ruby, gdy po raz pierwszy zadano to pytanie (luty 2011), ponieważ używa:

Te nowoczesne dodatki do Rubiego umożliwiają następującą implementację:

names = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]

names.group_by(&:itself).transform_values(&:count)
#=> {"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1}

Ruby v2.2 + (przestarzały)

Jeśli używasz starszej wersji Ruby, bez dostępu do wyżej wymienionej Hash#transform_valuesmetody, możesz zamiast tego użyć Array#to_h, który został dodany do Ruby v2.1.0 (wydany w grudniu 2013):

names.group_by(&:itself).map { |k,v| [k, v.length] }.to_h
#=> {"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1}

W przypadku nawet starszych wersji Ruby ( <= 2.1) istnieje kilka sposobów rozwiązania tego problemu, ale (moim zdaniem) nie ma jednoznacznego, „najlepszego” sposobu. Zobacz inne odpowiedzi na ten post.


Miałem napisać: P. Czy jest zauważalna różnica między używaniem countzamiast size/ length?
lód ツ

1
@SagarPandya Nie, nie ma różnicy. W przeciwieństwie do Array#sizei Array#length, Array#count może przyjmować opcjonalny argument lub blok; ale jeśli jest używany z żadnym z nich, jego implementacja jest identyczna. Dokładniej, wszystkie trzy metody wywołują LONG2NUM(RARRAY_LEN(ary))pod maską: liczba / długość
Tom Lord

1
To taki fajny przykład idiomatycznego Rubiego. Świetna odpowiedź.
slhck

1
Dodatkowy kredyt! Sortuj według liczby.group_by(&:itself).transform_values(&:count).sort_by{|k, v| v}.reverse
Abram

2
@Abram, możesz sort_by{ |k, v| -v}, nie reversepotrzeba! ;-)
Sony Santos

26

Teraz używając Ruby 2.2.0 możesz wykorzystać tę itselfmetodę .

names = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]
counts = {}
names.group_by(&:itself).each { |k,v| counts[k] = v.length }
# counts > {"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1}

3
Zgadzam się, ale nieco wolę nazwy.group_by (&: siebie) .map {| k, v | [k, v.count]}. to_h, abyś nigdy nie musiał deklarować obiektu skrótu
Andy Day

8
@andrewkday Idąc o krok dalej, Ruby v2.4 dodał metodę: Hash#transform_valuesktóra pozwala nam jeszcze bardziej uprościć Twój kod:names.group_by(&:itself).transform_values(&:count)
Tom Lord

Jest to również bardzo subtelna kwestia (która prawdopodobnie nie będzie już miała znaczenia dla przyszłych czytelników!), Ale zwróć uwagę, że Twój kod również wykorzystuje Array#to_h- co zostało dodane do Rubiego w wersji 2.1.0 (wydanej w grudniu 2013 - tj. Prawie 3 lata po pierwotnym pytaniu został zapytany!)
Tom Lord

17

Jest rzeczywiście struktura danych, która wykonuje to: MultiSet.

Niestety, nie ma MultiSetimplementacji w podstawowej bibliotece Ruby ani w standardowej bibliotece, ale jest kilka implementacji pływających po sieci.

To doskonały przykład tego, jak wybór struktury danych może uprościć algorytm. W rzeczywistości w tym konkretnym przykładzie algorytm całkowicie znika. To dosłownie tylko:

Multiset.new(*names)

I to wszystko. Przykład, używając https://GitHub.Com/Josh/Multimap/ :

require 'multiset'

names = %w[Jason Jason Teresa Judah Michelle Judah Judah Allison]

histogram = Multiset.new(*names)
# => #<Multiset: {"Jason", "Jason", "Teresa", "Judah", "Judah", "Judah", "Michelle", "Allison"}>

histogram.multiplicity('Judah')
# => 3

Przykład, używając http://maraigue.hhiro.net/multiset/index-en.php :

require 'multiset'

names = %w[Jason Jason Teresa Judah Michelle Judah Judah Allison]

histogram = Multiset[*names]
# => #<Multiset:#2 'Jason', #1 'Teresa', #3 'Judah', #1 'Michelle', #1 'Allison'>

Czy koncepcja MultiSet wywodzi się z matematyki czy innego języka programowania?
Andrew Grimm,

2
@Andrew Grimm: Zarówno słowo „multiset” (de Bruijn, lata 70.), jak i koncepcja (Dedekind 1888) wywodzą się z matematyki. Multisetrządzi się ścisłymi regułami matematycznymi i obsługuje typowe operacje na zbiorach (suma, przecięcie, dopełnienie, ...) w sposób, który jest w większości zgodny z aksjomatami, prawami i twierdzeniami "normalnej" matematycznej teorii mnogości, chociaż niektóre ważne prawa tak nie trzymaj się, gdy próbujesz uogólnić je na zestawy wielokrotne. Ale to przekracza moje rozumienie sprawy. Używam ich jako struktury danych programowania, a nie koncepcji matematycznej.
Jörg W Mittag

Aby nieco rozwinąć tę kwestię: „… w sposób, który jest w większości zgodny z aksjomatami…” : Zbiory „normalne” są zwykle formalnie definiowane przez zbiór aksjomatów (założeń) zwanych „teorią mnogości Zermelo-Frankela ”. Jednak jeden z tych aksjomatów: aksjomat rozszerzalności stwierdza, że ​​zbiór jest precyzyjnie definiowany przez jego elementy - np {A, A, B} = {A, B}. Jest to ewidentne naruszenie samej definicji multizestawów!
Tom Lord

... Jednak bez wchodzenia w zbyt wiele szczegółów (ponieważ jest to forum oprogramowania, a nie zaawansowana matematyka!), Jedno Można formalnie zdefiniować multi-zbiory w sposób matematyczny za pomocą aksjomatów dla zestawów Crisp, aksjomatów Peano i innych aksjomatów specyficznych dla MultiSet.
Tom Lord

13

Enumberable#each_with_object oszczędza przed zwróceniem końcowego skrótu.

names.each_with_object(Hash.new(0)) { |name, hash| hash[name] += 1 }

Zwroty:

=> {"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1}

Zgadzam się, each_with_objectwariant jest dla mnie bardziej czytelny niżinject
Lev Lukomsky

9

Ruby 2.7+

W Enumerable#tallytym właśnie celu wprowadza się Ruby 2.7 . Jest dobre podsumowanie tutaj .

W tym przypadku:

array.tally
# => { "Jason" => 2, "Judah" => 3, "Allison" => 1, "Teresa" => 1, "Michelle" => 1 }

Dokumentacja dotycząca udostępnianych funkcji jest tutaj .

Mam nadzieję, że to komuś pomoże!


Fantastyczna wiadomość!
tadman

6

To działa.

arr = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]
result = {}
arr.uniq.each{|element| result[element] = arr.count(element)}

2
+1 Dla innego podejścia - chociaż ma to gorszą teoretyczną złożoność - O(n^2)(co będzie miało znaczenie dla niektórych wartości n) i wykonuje dodatkową pracę (na przykład musi liczyć się dla „Judy” 3x) !. Sugerowałbym również eachzamiast map(wynik mapy jest odrzucany)

Dziękuję za to! Zmieniłem mapę na każdą z nich, a także ujednoliciłem tablicę przed przejściem przez nią. Może teraz problem złożoności został rozwiązany?
Shreyas,

6

Poniżej przedstawiono nieco bardziej funkcjonalny styl programowania:

array_with_lower_case_a = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]
hash_grouped_by_name = array_with_lower_case_a.group_by {|name| name}
hash_grouped_by_name.map{|name, names| [name, names.length]}
=> [["Jason", 2], ["Teresa", 1], ["Judah", 3], ["Michelle", 1], ["Allison", 1]]

Jedną z zalet group_byjest to, że można go użyć do grupowania równoważnych, ale nie dokładnie identycznych elementów:

another_array_with_lower_case_a = ["Jason", "jason", "Teresa", "Judah", "Michelle", "Judah Ben-Hur", "JUDAH", "Allison"]
hash_grouped_by_first_name = another_array_with_lower_case_a.group_by {|name| name.split(" ").first.capitalize}
hash_grouped_by_first_name.map{|first_name, names| [first_name, names.length]}
=> [["Jason", 2], ["Teresa", 1], ["Judah", 3], ["Michelle", 1], ["Allison", 1]]

Czy słyszałem programowanie funkcjonalne? +1 :-) To zdecydowanie najlepszy sposób, chociaż można argumentować, że nie jest efektywny pod względem pamięci. Zwróć również uwagę, że Facets ma częstotliwość Enumerable #.
tokland

5
a = [1, 2, 3, 2, 5, 6, 7, 5, 5]
a.each_with_object(Hash.new(0)) { |o, h| h[o] += 1 }

# => {1=>1, 2=>2, 3=>1, 5=>3, 6=>1, 7=>1}

Kredyt Frank Wambutt


3
names = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]
Hash[names.group_by{|i| i }.map{|k,v| [k,v.size]}]
# => {"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1}

2

Wiele świetnych realizacji tutaj.

Ale jako początkujący uznałbym to za najłatwiejsze do odczytania i wdrożenia

names = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]

name_frequency_hash = {}

names.each do |name|
  count = names.count(name)
  name_frequency_hash[name] = count  
end
#=> {"Jason"=>2, "Teresa"=>1, "Judah"=>3, "Michelle"=>1, "Allison"=>1}

Kroki, które podjęliśmy:

  • stworzyliśmy hash
  • przeszliśmy przez namestablicę
  • policzyliśmy, ile razy każda nazwa pojawiła się w namestablicy
  • utworzyliśmy klucz przy użyciu namei wartość przy użyciucount

Może być nieco bardziej rozwlekły (i jeśli chodzi o wydajność, będziesz wykonywać niepotrzebną pracę z nadpisywaniem klawiszy), ale moim zdaniem łatwiejszy do odczytania i zrozumienia dla tego, co chcesz osiągnąć


2
Nie widzę, żeby było to łatwiejsze do odczytania niż zaakceptowana odpowiedź i jest to wyraźnie gorszy projekt (wykonujący dużo niepotrzebnej pracy).
Tom Lord

@Tom Lord - zgadzam się z tobą co do wydajności (wspomniałem nawet o tym w mojej odpowiedzi) - ale jako początkujący, próbujący zrozumieć rzeczywisty kod i wymagane kroki, uważam, że pomaga to być bardziej rozwlekłym, a następnie można refaktoryzować, aby poprawić wydajność i uczynienie kodu bardziej deklaratywnym
Sami Birnbaum

1
Zgadzam się trochę z @SamiBirnbaum. Jest to jedyny, który prawie nie używa specjalnej wiedzy o rubinach Hash.new(0). Najbliższy pseudokodowi. Może to być dobre dla czytelności, ale wykonywanie niepotrzebnej pracy może zaszkodzić czytelnikom, którzy to zauważą, ponieważ w bardziej złożonych przypadkach spędzą trochę czasu na myśleniu, że oszaleli, próbując dowiedzieć się, dlaczego to się stało.
Adamantish

1

To bardziej komentarz niż odpowiedź, ale komentarz nie byłby sprawiedliwy. Jeśli to zrobisz Array = foo, zawiesisz co najmniej jedną implementację IRB:

C:\Documents and Settings\a.grimm>irb
irb(main):001:0> Array = nil
(irb):1: warning: already initialized constant Array
=> nil
C:/Ruby19/lib/ruby/site_ruby/1.9.1/rbreadline.rb:3177:in `rl_redisplay': undefined method `new' for nil:NilClass (NoMethodError)
        from C:/Ruby19/lib/ruby/site_ruby/1.9.1/rbreadline.rb:3873:in `readline_internal_setup'
        from C:/Ruby19/lib/ruby/site_ruby/1.9.1/rbreadline.rb:4704:in `readline_internal'
        from C:/Ruby19/lib/ruby/site_ruby/1.9.1/rbreadline.rb:4727:in `readline'
        from C:/Ruby19/lib/ruby/site_ruby/1.9.1/readline.rb:40:in `readline'
        from C:/Ruby19/lib/ruby/1.9.1/irb/input-method.rb:115:in `gets'
        from C:/Ruby19/lib/ruby/1.9.1/irb.rb:139:in `block (2 levels) in eval_input'
        from C:/Ruby19/lib/ruby/1.9.1/irb.rb:271:in `signal_status'
        from C:/Ruby19/lib/ruby/1.9.1/irb.rb:138:in `block in eval_input'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:189:in `call'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:189:in `buf_input'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:103:in `getc'
        from C:/Ruby19/lib/ruby/1.9.1/irb/slex.rb:205:in `match_io'
        from C:/Ruby19/lib/ruby/1.9.1/irb/slex.rb:75:in `match'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:287:in `token'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:263:in `lex'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:234:in `block (2 levels) in each_top_level_statement'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:230:in `loop'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:230:in `block in each_top_level_statement'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:229:in `catch'
        from C:/Ruby19/lib/ruby/1.9.1/irb/ruby-lex.rb:229:in `each_top_level_statement'
        from C:/Ruby19/lib/ruby/1.9.1/irb.rb:153:in `eval_input'
        from C:/Ruby19/lib/ruby/1.9.1/irb.rb:70:in `block in start'
        from C:/Ruby19/lib/ruby/1.9.1/irb.rb:69:in `catch'
        from C:/Ruby19/lib/ruby/1.9.1/irb.rb:69:in `start'
        from C:/Ruby19/bin/irb:12:in `<main>'

C:\Documents and Settings\a.grimm>

To dlatego, że Arrayto klasa.


1
arr = ["Jason", "Jason", "Teresa", "Judah", "Michelle", "Judah", "Judah", "Allison"]

arr.uniq.inject({}) {|a, e| a.merge({e => arr.count(e)})}

Upłynął czas 0,028 milisekund

co ciekawe, implementacja stupidgeeka została przetestowana pod kątem:

Upłynął czas 0,041 milisekundy

i zwycięska odpowiedź:

Upłynął czas 0,011 milisekund

:)

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.