Odwzorowanie pamięci - algorytmy oparte na częściowo dysku

Question

Czy są jakieś dobre zasoby lub książki dla struktur danych, które można splajnować, tzn. Kolejki?

Podczas przechowywania dużych obiektów może zapełnić całą pamięć, ale jeśli można zachować, powiedzmy, najczęściej używane elementy tej struktury kolejki w pamięci, a resztę na dysku (w rodzaju stronicowania).

Podobnie, to pytanie dotyczy innych struktur, takich jak połączone listy, tablice, hashtables i tak dalej.

Answer 1

To, czego szukasz, może być tematem wydajnych algorytmów I/O. Wyszukiwarka Google nie wyszukała dla mnie żadnych książek, ale ta course page zawiera listę artykułów, które mogą lub nie mogą być dla Ciebie istotne.

Powinieneś również rzucić okiem na WikiPedia page for B-trees, szczególnie w sekcji na B-trees in filesystems.

Answer 2

Istnieje Buffer Tree (PDF, 0,6 MB):

”... opracowaliśmy efektywne zewnętrzny priorytet kolejki i batched wersje dynamika (jednowymiarowe) Zakres drzewa i drzewa segmentu . "

i

”... pozwala nam projektować efektywne algorytmy zewnętrznych pamięci ze znanych algorytmów wewnętrznych, w prosty sposób, takie, że wszystkie wejścia/wyjścia poszczególnych części są algorytmy ukryte w strukturach danych. "

To jest wymieniany jako część szerszego leczenia przedmiotu w swobodnie dostępne online książce "Algorithms and Data Structures for External Memory" Jeffrey Scott Vitter (PDF, 1 MB).

Answer 3

Czy chodzi Ci o znalezienie wydajnych analogowych dysków do podstawowych struktur danych opartych na pamięci RAM (na przykład listy połączone, stosy, kolejki, kolejki priorytetowe itp.)? Jeśli tak, odpowiedź poniżej może być lub nie być pomocna.

---

Nie jestem do końca pewien, co próbujesz zrobić. Czy w kolejce chodzi ci o kolejkę FIFO (pierwszy na początek) lub kolejkę priorytetową?

Aby zająć się kolejkami i rejestrowaniem FIFO, być może warto zajrzeć do buforów pierścieniowych i rotacji dziennika.

Aby poradzić sobie z buforowaniem danych w pamięci RAM w celu zminimalizowania dostępu do dysku, możesz lub nie, lepiej pozostawić to systemowi operacyjnemu. Jeśli nie tworzysz aplikacji dla systemu Windows, lepiej być po prostu czytającym i zapisującym na i na pliki w sposób naiwny, ponieważ system operacyjny powinien dobrze wykonywać buforowanie odczytu i zapisu. Jednak, o ile mogę powiedzieć, Windows ma okropne buforowanie odczytu/zapisu (może się mylę).

Być może pomoc w podsystemie VFS w Linuksie i studiowanie http://lxr.linux.no/#linux+v2.6.31/Documentation/filesystems/vfs.txt pomoże, ponieważ (myślę), że jest to część Linuksa, która obsługuje buforowanie.

Nie jestem ekspertem od kolejek i pamięci podręcznej, ale wiem kilka rzeczy na ten temat. Jeśli możesz podać więcej szczegółów na temat tego, co próbujesz zrobić, być może ktoś może pomóc ci w znalezieniu odpowiedniego rozwiązania.