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

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?

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.

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.

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.

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.

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.