Czy możliwa jest pamięć wszystkich możliwych permutacji bloku kilobajtowego i wskaźników?

Jest to wystarczająco trudny pomysł, aby owinąć głowę i byłbym bardzo wdzięczny za wszelkie zmiany / pomoc, aby uczynić go bardziej czytelnym dla tych, którzy wiedzą.

Czy teoretycznie możliwe jest posiadanie dysku twardego, na którym zapisano jedną kopię każdej możliwej permutacji binarnej jednego kilobajta, a następnie reszta systemu po prostu tworzy wskaźniki do tych lokalizacji?

Czy taki system byłby szybszy niż zwykłe przechowywanie informacji bezpośrednio?

Aby wyjaśnić inny sposób, powiedz zamiast zdań:

„Cześć, jestem Bob”. i „Ta kanapka wygląda przepysznie”.

... przechowywane na dysku twardym, mielibyśmy wszystkie kombinacje alfabetu i innych znaków do pewnej liczby (powiedzmy 1000 znaków lub więcej), a następnie przechowalibyśmy nasze zdania jako coś w rodzaju:

[Wskaźnik # 21381723]

Możliwe są 2 ⁸¹⁹² różnych bloków 1K. Przechowywanie ich wszystkich zajęłoby 2 ⁸²⁰² bitów pamięci. Ponieważ wszechświat zawiera tylko około 10 ⁸⁰ (lub ~ 2 ²⁶⁶ ) cząstek, można bezpiecznie założyć, że nie można przechowywać ich wszystkich i nie musisz się zastanawiać, czy zaoszczędziłoby to czas, czy nie.

Ale istnieje bardziej interesujący sposób odpowiedzi na to pytanie. Sugerujesz utworzenie indeksu w ogromnej puli stałych. Ale skąd miałbyś wiedzieć, który wskaźnik należy odrzucić? Wyobraź sobie, ze względu na argument, że chcesz zapisać tylko 1-znakowy bloki: a, b, c... Prawdopodobnie twoi indeksy byłoby 0, 1, 2 itd., Ponieważ jest to najbardziej wydajny układ magazynowania tych bloków.

Czy zauważyłeś coś w aranżacji? Twój indeks jest w rzeczywistości zakodowaną reprezentacją przechowywanych danych ! Innymi słowy, nie musisz w ogóle rezygnować z dereferencji, wystarczy przekształcić indeks w pożądane dane.

Kiedy przechowujesz wszystkie możliwe wartości czegoś w tabeli, zawsze tak się dzieje: twój indeks staje się jedynie zakodowaną wersją samych danych, więc przechowywanie danych staje się zbędne. Dlatego w prawdziwym świecie indeksy są przydatne tylko dla rzadkich danych (np. Wszystkie odwiedzone strony internetowe, nie wszystkie strony internetowe, które mogłyby istnieć , a nawet wszystkie, które istnieją).

Jak inni już zauważyli, masz 2 ^ 8192 możliwości na blok 1k. Oznacza to, że potrzebujesz 8192 bitów do zakodowania adresu bloku, jeśli wszystkie adresy bloków są zakodowane z taką samą ilością bitów, więc twoje adresy będą miały długość 1k. Nie zyskałbyś niczego poza dodaniem warstwy pośredniej, aby nie zyskać żadnej wydajności.

Jeśli chcesz mieć krótsze adresy, musisz zakodować niektóre bloki za pomocą krótkiego adresu, a niektóre za pomocą dłuższych i sprawić, aby długie nie pojawiały się tak często, a teraz po prostu kompresujesz dane (prawdopodobnie za pomocą czegoś w rodzaju Huffman kod ). Wymagałoby to znajomości przechowywanych danych przed ich zapisaniem lub regularnych zmian w kodowaniu. Prawdopodobnie byłby również mniej wydajny niż inne algorytmy kompresji, które wykorzystują bloki o różnej długości.

Są z tym dwa problemy.

Po pierwsze, „wszystkie możliwe binarne permutacje jednego kilobajta” to ogromna ilość danych. 1024 bajty * 8 bitów na bajt = 8192 bitów w kilobajcie. Wszystkie możliwe permutacje to 2 ^ 8192. To około 1.09e+2466kilobajtów! (Dla porównania dysk o pojemności 1 TB to 1e09kilobajty).

Po drugie, nawet jeśli masz tak ogromną tabelę i indeksujesz ją za pomocą wskaźników, co byś zrobił, gdybyś chciał odwołać się do danych mniejszych niż dokładnie 1 KB?

Jak zauważyli inni plakaty, w pewnym momencie rozmiar wskaźnika potrzebnego do zindeksowania na liście wszystkich możliwych wartości niweczy zysk.

Jednak niektóre języki używają ograniczonej wersji tego, co sugerujesz, aby zoptymalizować wykorzystanie pamięci. Python używa „internowania” ciągu, aby zmniejszyć liczbę zduplikowanych ciągów w pamięci. Więcej informacji można znaleźć, wyszukując hasło „intern intern string python”.