Korzystanie SparseIntArray zamiast HashMap <Integer, Integer> z putSeriazable

Question

Gdy używam HashMap z kluczem i danych wartości całkowite w android dostaję komunikat w Eclipse:

Use new SparseIntArray(...) for better performance 

Teraz problemem jest to, że SparseIntArray() nie implementuje interfejsu Serizable i nie można go używać z .getSerializable() i .putSerializable() w onRestoreInstanceState().

1) Jak ważne jest używanie SparseIntArray() zamiast HashMap?

2) Czy powinienem przejść przez problem z serializacją SparseIntArray? (Moim pierwszym pomysłem jest stworzenie klasy opakowania obsługującej Serializable, czy jest to właściwa droga?)

Answer 1

1) Jak ważne jest używanie SparseIntArray() zamiast HashMap?

To zależy od tego, jak go używasz. Ale chyba że próbujesz reprezentować wiele i/lub duże "tablice" w ten sposób, różnica jest mało prawdopodobna.

Należy zauważyć, że Java SE nie ma żadnych rzadkich klas tablicowych i zazwyczaj nie stanowi problemu.

2) Czy powinienem zadać sobie trud robienia serii SparseIntArray? (Moim pierwszym pomysłem jest stworzenie klasy opakowania, która implementuje Serializable, czy jest to właściwa droga?)

Zobacz powyżej i poniżej. (Tak, to brzmi rozsądnie ... jeśli trzeba iść do tego niepokoić.)

---

SparseIntArray klasa (source code) wykorzystuje parę int tablic do reprezentowania klucze i wartości w mapowaniu i wykorzystuje wyszukiwanie binarne, aby wykonać wyszukiwanie. Klucze są przechowywane w porządku bez żadnych "dziur", a wyszukiwanie odbywa się za pomocą wyszukiwania binarnego. Oznacza to, że:

• Użycie pamięci dla SparseIntArray będzie grubsza czynnik 10 mniej niż dla równoważnego HashMap. Wynika to kombinacja rzeczy:

  • tablica tabeli mieszania posiada w przybliżeniu 1 referencyjnych na wejściu (w zależności od tego, jak pełna tabela jest ...),

  • klucze i wartości muszą być „zapakowane”, jak Integer obiektów w HashMap i

  • każdy wpis w HashMap wymaga „węzła” obiekt, który jest dość duży ciężar - 4 pola w standardowej implementacji.

  (Jeśli jednak stworzyć Integer obiektów we właściwy sposób, w „boks” overhead mogą być złagodzone przez skutkami Integer klasy instancji cache).

  Natomiast rzadki wersja wymaga 2 * capacity 4 bajtowe słowa.

• wyszukiwania (tj get) jest O(logN) porównaniu z O(1) dla HashMap.

• Losowe wstawianie to O(N) w porównaniu z O(1) dla HashMap. (Dzieje się tak dlatego, że wstawienie musi przesunąć się o połowę z istniejących pozycji, aby nowy wpis mógł zostać dodany we właściwej pozycji w tablicach).

• Kolejne wstawianie (tj. W porządku rosnącym) to O(1) .

"To, co najlepsze", zależy oczywiście od tego, z czym się optymalizujesz, od tego, jak korzystasz ze struktury danych i jak duży będzie to uzyskać.

Answer 2

Problem z używaniem HashMap<Integer, Integer> polega na tym, że każdy klucz i wartość muszą zostać zapakowane. Wpływ tego może wahać się od zera do bycia dużym obciążeniem systemu z ogromnych ilości generowania śmieci i/lub korzystania z pamięci (nie wspominając o niewielkiej karze za wydajność wartości boksu/rozpakowywania). (Te obawy przyczyniły się również do rozwoju wielu firm trzecich: collection frameworks for primitives.)

Jeśli uważasz, że korzyści z SparseIntArray są warte posiadania, to myślę, że twoje podejście do klasy opakowania jest uzasadnione. Alternatywą może być implementacja Parcelable, która może również służyć do zapisywania/przywracania stanu instancji.