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


23

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]



Ciekawe może być działanie git , zwane treścią adresowalną .
JDługosz

5
github.com/philipl/pifs Opiera się na tej samej zasadzie co twój pomysł, z tym wyjątkiem, że zamiast wszystkich permutacji kb, używa pi.
Wosk

12
Wskaźniki musiałyby mieć długość 1 kilobajta. Możesz nie zapisywać bloków, które nie mają sensu w języku angielskim - w takim przypadku samodzielnie wymyśliłeś pomysł kompresji!
user253751

Podstawowa odpowiedź brzmi NIE - jest to niemożliwe ze względu na # i rozmiar permutacji. Ale jaka aplikacja mogłaby być przydatna, gdyby była możliwa?
Archanioł

Odpowiedzi:


91

Możliwe są 2 8192 różnych bloków 1K. Przechowywanie ich wszystkich zajęłoby 2 8202 bitów pamięci. Ponieważ wszechświat zawiera tylko około 10 80 (lub ~ 2 266 ) 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ą).


17
W pewnym sensie już korzystamy z tego systemu - ale robimy to z leniwą oceną wzorców bitowych wielkości kilobajtów, co pozwala nam zaoszczędzić mnóstwo miejsca!
Theodoros Chatzigiannakis

3
Pamięć jest nieznacznie zmniejszona z powodu nakładania się (1024 zer, a następnie 1024 zawierają 1025 unikalnych wzorów) ... zmniejszona, ale wciąż niemożliwie duża. Ponadto blok 1 KB ma 2 <sup> 13 </sup> bitów, a nie 2 <sup> 10 </sup>.
Ben Voigt

2
Pamiętaj, że limit 10 ^ 80 cząstek we wszechświecie nie oznacza bezpośrednio, że nie możesz przechowywać więcej niż, powiedzmy, 10 ^ 80 bitów we wszechświecie - ponieważ z każdą cząsteczką możesz potencjalnie przechowywać więcej niż jeden bit informacji ( na podstawie jego pozycji we wszechświecie i ewentualnie jego prędkości itp.). Nie oznacza to jednak, że możesz zapisać każdy blok 1K - ich liczba przekracza zdumiewająco duży czynnik, więc nadal jest bardzo bezpieczny zakład, że nie możesz przechowywać wszystkich!
psmears

2
@ Neil Jeśli masz system kodowania, który pozwala przechowywać 10 ^ 80, kodując je jako „10 ^ 80”, to jak przechowujesz „10 ^ 80”? Jeśli niektóre fragmenty danych są zakodowane krócej niż dane rzeczywiste, inne muszą zostać zakodowane dłużej. Lub jeśli wszystkie twoje dane są liczbami, to zapisujesz każdą cyfrę dziesiętną jako cały bajt.
Random832

3
W przypadku sekwencji de Bruijna wystarczy 2 ^ 1024 bitów.
gronostaj

20

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.


1

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?


2
Przechowywanie dodatkowo wszystkich bloków mniejszych niż 1 KB nie zajmie dużo więcej miejsca. Zakładając tylko bloki wielkości bajtów, rozmiar mniejszych bloków razem wynosi nieco nieco ponad 1/256 wielkości bloków 1 KB. Zakładając bloki wielkości bitowej, dodajesz ponownie mniej więcej ten sam rozmiar.
Paŭlo Ebermann

-1

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”.


1
OP pyta o gęsty zestaw, zawierający każdą permutację. Wskaźniki są użyteczne tylko w przypadku rzadkich danych, w których bity wymagane do utrzymania wskaźnika są mniejsze niż wskazane bity. Internowanie może sprawić, że przestrzeń będzie rzadsza, jeśli są duplikaty, więc istnieje połączenie, ale twoja odpowiedź nie jest zbyt dobrze sformułowana.
Peter Cordes,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.