Performatic struktura bez powielania danych

Question

Powiedz, mam następujących klas:

public class Tagged { 

    private List<String> tags; 
} 

public class ContainerOfTagged { 

    private List<Tagged> tagged; 
} 

Przy takiej strukturze, ilekroć muszę znaleźć Tagged z określonym znacznikiem, muszę iteracyjne nad wszystkie oznaczone w ContainerOfTagged i iterowanie po wszystkich znacznikach każdego z nich: Tagged. To może wpłynąć na wydajność w zależności od wielkości list.

Prostym rozwiązaniem byłaby zmiana klasy ContainerOfTagged Aby użyć Map, tagi mapowania w listach od Tagged:

public class ContainerOfTagged { 

    private Map<String, List<Tagged>> tagMapping; 
} 

Teraz wszystko co musisz zrobić, to zapewnić tag, a Map zwróci wszystkie Tagged ze wspomnianym tagiem. Jednak w ten sposób powoduje duplikowanie danych, ponieważ te same znaczniki istnieją w klasach Tagged i ContainerOfTagged.

Czy istnieje sposób rozwiązania tego problemu za pomocą rozwiązania performatycznego, które nie powiela danych?

Answer 1

Tak naprawdę nie można uniknąć "duplikowania" znaczników, ale pamiętaj, że tak naprawdę ich nie duplikujesz, ponieważ listy i mapy przechowują tylko odniesienia do łańcucha znaczników, a nie wartości (jednak odniesienia prawdopodobnie będą brane pod uwagę dość dużo miejsca w sobie).

Problemem jest to, że potrzebne są dwa indeksy:

1. Trzeba znaleźć listę tagów, biorąc pod uwagę oznakowanego obiektu.
2. Musisz znaleźć obiekt Tagged, biorąc pod uwagę tag.

Idealnie byłoby, gdyby Twoje rozwiązanie wyglądało tak. Możesz rozwiązać swoje obawy dotyczące problemów niezsynchronizowanych dzięki zastosowaniu jednej metody zarządzania tagami.

Należy pamiętać, że w Tagged należy użyć zestawu zamiast listy, aby uniknąć powielania znaczników.

Jeśli wykorzystanie pamięci jest poważnym problemem, możesz spróbować jakiejś kompresji referencyjnej. Korzystając z tej techniki, możesz przechowywać tagi w tablicy, a następnie odwoływać się do nich według indeksu. Jeśli miałeś mało, możesz użyć bajtu lub krótkiego zamiast odniesienia, ale kod byłby dużo bardziej nieprzystępny i nie polecałbym go.

EDIT:

W moim pierwszym poście, zaproponowałem, że Tagged powinien być interfejs o nazwie Tagable. To jest czystsze, ale wydłuża czas rozwiązania, więc powróciłem do klasy. Mimo to możesz rozważyć posiadanie interfejsu Tagable i zaimplementować go w klasie Tagged.

public interface Tagable { 
    Set<String> getTags; 
    tag(String tag); 
}