Conteggio del numero di occorrenze di ciascun elemento in un elenco

Question

Ho un ingresso streaming che ha valori ripetuti. Posso usare qualsiasi struttura dati, ma devo contare il numero di occorrenze di ogni elemento. Supponiamo che io sono un elenco di fornitori di telefonia mobile come il seguente:

 
Apple 
Nokia 
Samsung 
Apple 
LG 
Nokia 
HTC 
Android 
Apple 
Nokia 
Nokia 
Apple 
Samsung 

devo costruire qualsiasi struttura di dati di preferenza una mappa con dettagli come

 
Apple,4 
Nokia,4 
Samsung,2 
LG,1 
Android,1 

Non sono sicuro se questo è ottimale. C'è una soluzione migliore di questa?
In effetti devo ancora scrivere quanto sopra come codice. Quindi anche un codice migliore ti aiuterà.

Answer 1

Sì, vorrei usare uno Map<String, Integer>. Vorrei avvolgere il add in qualcosa di simile:

private static void incrementValue(Map<String, Integer> counters, String toAdd) { 
    Integer currValue = counters.get(toAdd); 
    if (currValue == null) 
     counters.put(toAdd, 1); 
    else 
     counters.put(toAdd, currValue+1); 
} 

O senza farmaci generici:

private static void incrementValue(Map counters, String toAdd) { 
    Integer currValue = (Integer) counters.get(toAdd); 
    if (currValue == null) 
     counters.put(toAdd, 1); 
    else 
     counters.put(toAdd, currValue+1); 
} 

Answer 2

Da dove provengono i dati? Se un db - puoi farlo molto facilmente nella query sul backend con group by.

Answer 3

Una mappa sembra la strada da percorrere. Accesso diretto :)

Chiave: Elemento valore: numero di occorrenze o un elenco con gli indici dell'elemento nell'elenco.

Answer 4

Oltre alle soluzioni che sono state pubblicate, la prima cosa che mi viene in mente è di creare una tabella "codice-valore" e codificare l'elenco utilizzando i codici. Sarebbe molto efficiente nello spazio.

Answer 5

La struttura più naturale per questo è un Bag aka un Multiset.

Una busta è essenzialmente una funzione da Oggetto a Conteggio.

Le raccolte Google hanno un Multiset, tuttavia è possibile creare facilmente le proprie utilizzando una HashMap.

http://google-collections.googlecode.com/svn/trunk/javadoc/index.html?com/google/common/collect/Multiset.html

Answer 6

Da quando è stato menzionato da l'interrogante che i generici non possono essere usati, come piattaforma di destinazione era Java 1.4, si potrebbe utilizzare la Apache Commons Collections che non utilizza farmaci generici.

Il answer by pjp indica che è possibile utilizzare una borsa.

Risulta, gli Apache Commons Collections ha una Bag che ha un metodo getCount che riporterà il conteggio di un determinato oggetto che è stato aggiunto al Bag.

Il seguente è un esempio che add s alcuni Integer oggetti a un HashBag e conta il numero di ogni oggetto Integer che il Bag contiene:

Bag b = new HashBag(); 

b.add(Integer.valueOf(1)); 
b.add(Integer.valueOf(2)); 
b.add(Integer.valueOf(2)); 
b.add(Integer.valueOf(3)); 

System.out.println("Count for 1: " + b.getCount(Integer.valueOf(1))); 
System.out.println("Count for 2: " + b.getCount(Integer.valueOf(2))); 
System.out.println("Count for 3: " + b.getCount(Integer.valueOf(3))); 

I risultati sono stati:

 
Count for 1: 1 
Count for 2: 2 
Count for 3: 1 

(Dovrei aggiungere una dichiarazione di non responsabilità che questo codice è stato effettivamente compilato ed eseguito su Java 6, ma credo di aver usato solo le funzionalità che erano presenti dai 5 giorni precedenti alla Java.)