Wiem, może tytuł jest trochę mylący. Jednak moje rzeczywiste pytanie jest podstawowe, że myślę. Pracuję nad nową implementacją LRU, ponieważ używam tabeli indeksu, która mapuje nazwę pakietu przychodzącego do indeksu, gdzie zawartość pakietu zapisana w CS. Jak pokazano poniżej każdego przychodzącego sklepu pakietów w CS i może być adresowany przez tabelę indeksu. Wpisz opis obrazu tutaj

Załóżmy teraz, że nowa pakiet dotarła, jak wiemy, dotycząca Lru, jego indeks musi ustawić na początek CS (zero) i musi uaktualnić inne indeksy, muszą być zwiększane w wyniku. Wprowadź opis obrazu tutaj Jednym oczywistym rozwiązaniem jest pętla wszystkich wpisów w tabeli indeksu i zwiększa je. Czy istnieje jakieś rozwiązanie lub struktura, która jest używana do takiego problemu?

2
Ali Rasaii 5 grudzień 2019, 18:41

1 odpowiedź

Najlepsza odpowiedź

Nie widzę, jak utworzysz kolejność swojej pamięci podręcznej w opisie. Ale aby odpowiedzieć na twoje pytanie, możliwe jest zmniejszenie metody sklepu LRU do O (1) złożoności czasu.

Klasyczny sposób na to, aby mieć te dwie struktury danych:

  • podwójnie powiązana lista : Aby zamówić w pamięci podręcznej. Każdy węzeł przechowuje element danych (odgrywa rolę sklepu treści).

  • Hashmap kojarzy każdy klucz do wskaźnika do węzła na liście połączonych. (Odgrywa rolę tabeli indeksu)

Więc podczas uzyskania dostępu do już przechowywanych danych w pamięci podręcznej, musi być na górze listy, więc usuwanie odpowiedniego węzła z listy połączonej (w czasie O (1), ponieważ masz dostęp do swoich poprzednich i następnych węzłów) i Przechowuj go na głowie.

W przypadku nowych danych jest prostsze, przechowuje go tylko na głowie listy i przechowywać (klucz, wartość) w Hashmapie.

3
Ayoub Omari 6 grudzień 2019, 08:18