Zliczanie liczby wystąpień każdego elementu na liście

Question

Mam dane wejściowe strumieniowe, które mają powtarzające się wartości. Mogę użyć dowolnej struktury danych, ale muszę policzyć liczbę wystąpień każdego elementu. Załóżmy, że mam listę dostawców telefonii komórkowej tak:

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

muszę zbudować żadnej struktury danych korzystnie mapę ze szczegółami jak

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

Nie jestem pewien, czy jest to optymalne. Czy istnieje lepsze rozwiązanie niż to?
W rzeczywistości muszę jeszcze napisać powyższe jako kod. Lepszy kod też pomoże.

Answer 1

Tak, użyłbym Map<String, Integer>. Chciałbym zawinąć add w coś takiego:

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); 
} 

Albo bez rodzajowych:

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

Skąd pochodzą dane? Jeśli db - możesz to zrobić bardzo łatwo w zapytaniu na zapleczu w grupie przez.

Answer 3

Mapa wydaje się droga. Bezpośredni dostęp :)

Klucz: Element wartość: liczba ocurenrences lub lista z indeksami elementu na liście.

Answer 4

Poza rozwiązaniami, które zostały opublikowane, pierwszą rzeczą, która przychodzi mi do głowy, jest utworzenie tabeli "wartość kodu" i zakodowanie listy za pomocą kodów. Byłaby bardzo efektywna w przestrzeni kosmicznej.

Answer 5

Najbardziej naturalną strukturą jest torba typu Multiset.

Worek jest zasadniczo funkcją od Object do Count.

Kolekcje Google mają Multiset, ale można je łatwo zbudować za pomocą HashMap.

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

Answer 6

Ponieważ został wymieniony przez pytającego, że leki generyczne nie mogą być wykorzystane, jako platforma docelowa była Java 1.4, można użyć Apache Commons Collections które nie używa rodzajowych.

W książce answer by pjp podano, że można użyć torby.

Okazuje się, że zbiory Apache Commons mają Bag, które mają metodę getCount, która zwróci liczbę określonego obiektu, który został dodany do Bag.

Poniżej jest przykład, że add s niektóre Integer obiektów do HashBag i liczy ile z każdego obiektu Integer że Bag zawiera:

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))); 

Wyniki były:

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

(Powinienem dodać zastrzeżenie, że ten kod został faktycznie skompilowany i uruchomiony na Javie 6, ale uważam, że użyłem tylko funkcji, które były obecne w pre-Java 5 dni.)