Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 2
Lekcja 6: Test pierwszości- Wprowadzenie
- Wyzwanie: test pierwszości
- Metoda próbnych dzieleń
- Czym jest pamięć komputera?
- Wydajność algorytmu
- Poziom 3: Wyzwanie
- Sito Eratostenesa
- Poziom 4: Sito Eratostenesa
- Test pierwszości z sitem Etastotenesa
- Poziom 5: Próba podziału za pomocą sita
- Twierdzenie o liczbach pierwszych
- Spirala Ulama liczb pierwszych
- Odległość pomiędzy liczbami pierwszymi
- Kompromis czasu i pamięci
- Podsumowanie (co dalej?)
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Kompromis czasu i pamięci
Co to jest ograniczenie na pamięć? Jak można przyspieszyć działanie programu kosztem używanej pamięci? Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Nowa wiadomość. W dziale
inżynieryjnym w NASA powiedziano mi, że nowy łazik używa tej samej
platformy pamięci co „Curiosity”. Łazik „Curiosity” miał dwa komputery,
działające na zmianę. Parametry miał takie:
2 gigabajty pamięci flash, 256 megabajtów RAM-u i 256 kilobajtów
pamięci tylko do odczytu, podtrzymującej podstawowe
operacje systemowe. Chcielibyśmy przechowywać
cały program w pamięci RAM, ale ponieważ musimy dzielić
to miejsce z innymi programami, przydzielają nam 5% RAM-u
i to jest maksimum do wykorzystania. To jakieś 12,8 megabajta. Mówię o tym, bo chcę zwrócić uwagę na związek między wielkością pamięci a czasem wykonywania programów. Przejrzałem program
napisany przez IV46. Z tabelą miliona liczb pierwszych. Zatem algorytm mógł
posuwać się jedynie po liczbach pierwszych,
jak najdalej, przeprowadzając test pierwszości
metodą próbnych dzieleń. Narzuca się pytanie: „Może by przechowywać
potrzebne nam liczby pierwsze, do jakiejś granicy, w tabeli,
zamiast znajdować je na bieżąco?”. Wspomnieliśmy w poprzednim
odcinku, że byłoby to optymalne
dla algorytmu próbnych dzieleń. Choć, zauważcie, jego algorytm
nie używa wielu kroków, bardzo zwolnił i przestał działać
jeszcze przed granicą. Nie mógł szybko rozwiązać problemu
z wielkością, określonego wcześniej. W tym przypadku zyskiwali czas w postaci powtarzanych
testów podzielności, kosztem przestrzeni,
czyli pamięci do trzymania tabeli. Dlaczego to się nie udało? Obliczmy to z grubsza,
używając tego, co już wiemy, by określić, czy to możliwa metoda
przy danym ograniczeniu pamięci. Pamiętajcie: mamy sobie radzić
z liczbami powyżej 9 biliardów. Algorytmy próbnych dzieleń
będą sprawdzać czynniki do pierwiastka kwadratowego
z danej liczby, a gdy nie znajdą, to mogą powiedzieć w 100%,
czy ta liczba jest pierwsza. Ile jest liczb pierwszych
do pierwiastka z tej granicy, gdzie pierwiastek
z 9 biliardów to 94,9 mln? Ile jest liczb pierwszych
mniejszych od 95 mln? Na szczęście mamy
metodę pozwalającą znaleźć przybliżone rozwiązanie problemu:
twierdzenie o liczbach pierwszych. Ile jest liczb pierwszych
mniejszych od x? To x podzielone przez
logarytm naturalny z x. A jeśli x przekracza 94,9 mln, widzimy, że liczb pierwszych
jest około 5,1 mln. Ponieważ przechowujemy
te liczby pierwsze, musimy znać wielkość
największej z nich, czy, w tym przypadku,
liczby pierwszej nr, ok. 5,1 mln. Wiemy, że będzie to liczba
mniejsza niż 94,9 mln. Sprawdziłem w tabeli.
Prawdziwa wartość tej liczby, największej,
którą trzeba przechowywać, poniżej pierwiastka z granicy,
to 89078611. Ile pamięci potrzebuje
ta jedna liczba pierwsza? Zapiszmy ją w notacji binarnej, bo tak komputer
będzie ją przechowywał, używając małych przełączników
w pamięci. Uczyliśmy się o tym w odcinku
o pamięci komputera. W bitach, największa
liczba pierwsza wygląda tak. 24 bity lub 3 bajty są potrzebne
do przechowania tej jednej liczby. Powiedzmy, że chcemy przechować
w pamięci każdą liczbę, a skoro wiemy, że największa
wymaga 24 bitów, to możemy sobie wyobrazić
długą listę bloków 24-bitowych przechowujących każdą liczbę pierwszą. Ile trzeba bitów do całej listy? Potrzebna pamięć to liczba wartości, albo liczb pierwszych,
razy miejsce na wartość. Mamy około 5,1 mln wartości razy 24 bity na wartość, a to jest trochę więcej
niż 124 mln bitów. Jeśli przeliczymy to na bajty, wyjdzie jakieś 14,7 mln. Czyli prawie 15 megabajtów. Nie da się przechować nawet listy tych liczb w pamięci,
przy danym ograniczeniu. To był tylko przykład, nie doszacowaliśmy
naprawdę potrzebnego miejsca. Np. tabela potrzebuje miejsca
na wskaźnik każdej jednostki, a każdy wskaźnik w 32-bitowej
maszynie to 4 bajty. Zatem rzeczywista potrzebna ilość
pamięci znacznie przekracza 15MB. Czyli przechowywanie
wszystkich liczb pierwszych aż do pierwiastka kwadratowego
z tej niskiej granicy nie jest możliwe
przy naszym ograniczeniu. W ten sposób tego nie zrobimy. A może, kiedy spadną ceny, 1000 razy albo 10 000 razy…? Nowoczesne systemy kryptograficzne
używają 512 bitów, a nawet większych liczb, co uniemożliwia
wyszukiwanie i wyliczanie. Jeśli ktoś poprosi, żebyście zrobili listę
liczb pierwszych, aż do 200-cyfrowych,
nawet się nie zastanawiajcie, bo twardy dysk potrzebny
do przechowania tych liczb byłby cięższy niż masa
obserwowalnego wszechświata. Spróbujcie to sobie obliczyć,
kiedy będziecie w restauracji, mając ołówek
i papier na całym stoliku. Pamiętajcie,
w obserwowalnym wszechświecie jest 10 do potęgi 80 atomów.
To liczba 80-cyfrowa. Wiedzcie, że jest granica
dostępnego miejsca czy pamięci. Nieważne, ile czasu by to zajęło, Zawsze konieczny jest kompromis między wykorzystaniem miejsca
a czasem na rozwiązywanie zadań. Żeby rozwiązać to zadanie,
test pierwszości, przy użyciu małej ilości miejsca i w krótkim czasie, będziemy musieli podejść do niego
w zupełnie nowy sposób. Myślcie nietuzinkowo.