Jakiej struktury danych należy użyć dla tej strategii buforowania?

11

Pracuję nad aplikacją .NET 4.0, która wykonuje dość drogie obliczenia dla dwóch podwójnych zwracających podwójne. Obliczenia wykonuje się dla każdego z kilku tysięcy pozycji . Obliczenia te są wykonywane w Taskwątku puli wątków.

Niektóre wstępne testy wykazały, że te same obliczenia są wykonywane w kółko, więc chciałbym buforować n wyników. Gdy bufor jest pełny, chciałbym wyrzucić najsłabiej często ostatnio używanego elementu. ( Edycja: zdałem sobie sprawę, że najmniej często nie ma sensu, ponieważ gdy pamięć podręczna jest pełna i zastąpiłbym wynik nowo obliczonym, ten byłby najmniej używany i natychmiast zastępowany następnym razem, gdy obliczany jest nowy wynik i dodane do pamięci podręcznej)

Aby to zaimplementować, zastanawiałem się nad użyciem Dictionary<Input, double>(gdzie Inputbyłaby mini-klasa przechowująca dwie podwójne wartości wejściowe) do przechowywania danych wejściowych i wyników w pamięci podręcznej. Musiałbym jednak również śledzić, kiedy wynik został wykorzystany ostatnim razem. W tym celu myślę, że potrzebowałbym drugiej kolekcji przechowującej informacje potrzebne do usunięcia wyniku ze słownika, gdy pamięć podręczna się zapełnia. Obawiam się, że ciągłe sortowanie tej listy wpłynęłoby negatywnie na wydajność.

Czy istnieje lepszy (tj. Bardziej wydajny) sposób, aby to zrobić, a może nawet wspólna struktura danych, której nie jestem świadomy? Jakie rzeczy powinienem profilować / mierzyć, aby określić optymalność mojego rozwiązania?

PersonalNexus
źródło

Odpowiedzi:

12

Jeśli chcesz użyć pamięci podręcznej eksmisji LRU (eksmisja „Najmniej ostatnio używane”), prawdopodobnie dobrą kombinacją struktur danych do użycia jest:

  • Okrągła lista połączona (jako kolejka priorytetowa)
  • Słownik

Dlatego:

  • Lista połączona ma czas wstawiania i usuwania O (1)
  • Węzły listy można ponownie wykorzystać, gdy lista jest pełna i nie trzeba wykonywać żadnych dodatkowych alokacji.

Oto jak powinien działać podstawowy algorytm:

Struktury danych

LinkedList<Node<KeyValuePair<Input,Double>>> list; Dictionary<Input,Node<KeyValuePair<Input,Double>>> dict;

  1. Wejście zostało odebrane
  2. Jeśli słownik zawiera klucz
    • zwróć wartość przechowywaną w węźle i przenieś węzeł na początek listy
  3. Jeśli słownik nie zawiera klucza
    • obliczyć wartość
    • zapisz wartość w ostatnim węźle listy
    • jeśli ostatni nie ma wartości, usuń poprzedni klucz ze słownika
    • przenieś ostatni węzeł do pierwszej pozycji.
    • zapisz w słowniku parę wartości klucza (wejściowy, węzeł).

Niektóre zalety tego podejścia to: odczytywanie i ustawianie wartości słownikowej zbliżonej do O (1), wstawianie i usuwanie węzła na połączonej liście to O (1), co oznacza, że ​​algorytm zbliża się do O (1) w celu odczytu i zapisu wartości do pamięci podręcznej i unika alokacji pamięci i blokuje operacje kopiowania pamięci, dzięki czemu jest stabilna z punktu widzenia pamięci.

Pop Catalin
źródło
Dobre punkty, jak dotąd najlepszy pomysł, IMHO. Zaimplementowałem pamięć podręczną na podstawie tego dzisiaj i będę musiał profilować i zobaczyć, jak jutro będzie działać.
PersonalNexus
3

Wydaje się, że to jeden wysiłek, aby przejść do pojedynczego obliczenia, biorąc pod uwagę moc przetwarzania, jaką masz do dyspozycji na przeciętnym komputerze. Ponadto nadal będziesz musiał ponieść koszty pierwszego wezwania do obliczeń dla każdej unikalnej pary wartości, więc 100 000 par unikalnych wartości nadal będzie Cię kosztować Czas n * 100 000 co najmniej. Weź pod uwagę, że dostęp do wartości w słowniku będzie prawdopodobnie wolniejszy w miarę powiększania się słownika. Czy możesz zagwarantować, że szybkość dostępu do słownika zrekompensuje wystarczająco, aby zapewnić rozsądny zwrot w stosunku do szybkości obliczeń?

Niezależnie od tego wydaje się, że prawdopodobnie będziesz musiał rozważyć znalezienie sposobu na zoptymalizowanie algorytmu. W tym celu potrzebujesz narzędzia do profilowania, takiego jak mrówki Redgate, aby zobaczyć, gdzie są wąskie gardła i pomóc w ustaleniu, czy istnieją sposoby na zmniejszenie niektórych kosztów ogólnych związanych z instancjami klas, przeglądaniem list, bazą danych dostęp lub cokolwiek to kosztuje tyle czasu.

S.Robins
źródło
1
Niestety na razie nie można zmienić algorytmu obliczeń, ponieważ jest to biblioteka innej firmy, która wykorzystuje zaawansowaną matematykę, która naturalnie wymaga dużej mocy obliczeniowej. Jeśli w późniejszym czasie zostanie to przerobione, na pewno sprawdzę sugerowane narzędzia do profilowania. Co więcej, obliczenia będą wykonywane dość często, czasem z identycznymi danymi wejściowymi, więc wstępne profilowanie wykazało wyraźną korzyść, nawet przy bardzo naiwnej strategii buforowania.
PersonalNexus
0

Jedną z myśli jest to, dlaczego tylko pamięć podręczna n wyników? Nawet jeśli n wynosi 300 000, zużyłbyś tylko 7,2 MB pamięci (plus cokolwiek dodatkowego dla struktury tabeli). Zakłada to oczywiście trzy podwójne 64-bitowe. Możesz po prostu zastosować zapamiętywanie do samej złożonej procedury obliczania, jeśli nie martwisz się brakiem miejsca w pamięci.

Peter Smith
źródło
Nie będzie tylko jednego bufora, ale jednego na „przedmiot”, który analizuję, i może być ich kilkaset tysięcy.
PersonalNexus
W jaki sposób ma znaczenie, z którego „przedmiotu” pochodzi wkład? czy są jakieś skutki uboczne?
jk.
@jk. Różne elementy wytwarzają bardzo różne dane wejściowe do obliczeń. Ponieważ oznacza to, że nakładanie się będzie niewielkie, nie sądzę, aby trzymanie ich w jednej pamięci podręcznej miało sens. Co więcej, różne elementy mogą żyć w różnych wątkach, więc aby uniknąć stanu współdzielenia, chciałbym zachować osobne pamięci podręczne.
PersonalNexus
@PersonalNexus Rozumiem, że w obliczeniach są zaangażowane więcej niż 2 parametry? W przeciwnym razie nadal masz f (x, y) = coś zrobić. Wydaje się, że stan współdzielony raczej pomógłby w wydajności niż w przeszkodzie?
Peter Smith
@PeterSmith Dwa parametry są głównymi wejściami. Są inne, ale rzadko się zmieniają. Jeśli tak, wyrzucę całą pamięć podręczną. Przez „stan wspólny” miałem na myśli wspólną pamięć podręczną dla wszystkich lub grupy elementów. Ponieważ musiałoby to zostać zablokowane lub zsynchronizowane w inny sposób, pogorszyłoby to wydajność. Więcej informacji na temat wpływu wspólnego stanu na wydajność .
PersonalNexus
0

Podejście z drugą kolekcją jest w porządku. Powinna to być kolejka priorytetowa, która pozwala szybko znajdować / usuwać wartości minimalne, a także zmieniać (zwiększać) priorytety w kolejce (druga część jest trudna, nie obsługiwana przez najprostsze implementacje kolejki prio). TheBiblioteka C5 ma taką kolekcję, to się nazywa IntervalHeap.

Lub, oczywiście, możesz spróbować zbudować własną kolekcję, coś w rodzaju SortedDictionary<int, List<InputCount>>. (InputCount musi być klasą łączącą twoje Inputdane z twoją Countwartością)

Aktualizowanie tej kolekcji przy zmianie wartości liczby można wdrożyć, usuwając i ponownie wstawiając element.

Doktor Brown
źródło
0

Jak wskazano w odpowiedzi Petera Smitha, wzór, który próbujesz wdrożyć, nazywa się zapamiętywaniem . W języku C # bardzo trudno jest implementować zapamiętywanie w przejrzysty sposób bez skutków ubocznych. Książka Olivera Sturma na temat programowania funkcjonalnego w C # daje rozwiązanie (kod jest dostępny do pobrania, rozdział 10).

W F # byłoby znacznie łatwiej. Oczywiście podjęcie decyzji o użyciu innego języka programowania jest sporą decyzją, ale warto rozważyć. Zwłaszcza w przypadku skomplikowanych obliczeń programowanie jest łatwiejsze niż zapamiętywanie.

Gert Arnold
źródło