Czy to stwierdzenie z podstawowych algorytmów Knutha nadal obowiązuje? [Zamknięte]

10

W pewnym sensie 10! (dziesięć silnia) reprezentuje przybliżoną linię podziału między rzeczami, które są praktyczne do obliczenia, a tymi, które nie są.

To jest z książki Knuth's TAOCP Fundamental Al Algorytmy (1973). Czy to nadal jest prawidłowe stwierdzenie, czy też moc obliczeniowa sprawiła, że stało się ono przestarzałe?

computer-science taocp

— Bon Ami
źródło

Nie jest dla mnie jasne, w jakim sensie była to kiedykolwiek prawda - 10! to zaledwie kilka milionów. Zbyt duży, by można go było zrozumieć, ale nie jest szczególnie trudny do obliczenia, nawet za pomocą pióra i papieru.

— hobbs

11

@ Hobbs nie chodzi o obliczanie wartości 10 !, chodzi o robienie obliczeń na około 10! rzeczy . To znaczy, jeśli twoja metoda wymaga więcej niż około 10! <jednostki pracy>, czas znaleźć nową metodę.

— AakashM

21

To jest nadal rozsądne.

10! = 3,628,880. Z każdym krokiem AT LEAST podnosi się o rząd wielkości.

(fact 10)
3628800

(fact 11)
39916800 -- about 40 million

(fact 12)
479001600 -- almost 500 million

(fact 13.0)
6227020800.0 -- over 6 billion

Wkrótce mówisz o liczbach wydatków Kongresu.

— John R. Strohm
źródło

15

Dobry profesor jest na szczęście nadal z nami, a najlepszym sposobem na uzyskanie ostatecznej odpowiedzi jest napisanie go i spytanie o zdanie.

To powiedziawszy, nie sądzę, żeby liczba bezwzględna miała tak duże znaczenie, jak funkcja, którą reprezentują silnie. Niezależnie od tego, czy Knuth zdawał sobie z tego sprawę, model, który ustanowił z tym stwierdzeniem, działa bardzo dobrze, jeśli chodzi o spojrzenie wstecz na to, co było praktyczne do obliczenia w poprzednich dziesięcioleciach i do przodu w następnych.

W 1973 r. Nasza zdolność do generowania, przechowywania, przesyłania i przetwarzania danych była wystarczająco ograniczona, aby uzyskać 10! rozsądna postać z „dalekiej krawędzi”, o którą można strzelać. Wątpię, aby Knuth (lub ktokolwiek inny) byłby w stanie przewidzieć wykładniczą poprawę w prawie wszystkim, co nas cieszyło od tego czasu, ale silnie pasują do rzeczywistych liczb.

Widziałem to z pierwszej ręki: Dziesięć lat temu pracowałem nad projektem, w którym opracowywaliśmy sposoby przechowywania i przetwarzania około 50 milionów rekordów, jednocześnie zastanawiając się, jak moglibyśmy zrobić rząd wielkości więcej. Dziesięć lat później wykonuję podobny projekt. Moje liczby docelowe uległy zmianie, wszystkie w sposób czynnikowy:

                      2002           2012
Small Test .......  9! / 362K ... 10! / 3.6M
Large Test ....... 10! / 3.6M ... 11! /  40M
Capacity Goal .... 11! /  40M ... 12! / 479M
Capacity Dream ... 12! / 479M ... 13! / 6.3B

Grupy wykonujące oba projekty skupiały się na znacznie bardziej okrągłych liczbach, ale czynniki nie są bardzo odległe. Googles i Facebook na całym świecie mają zasoby do robienia rzeczy, o których marzy mój obecny projekt, ale z miejsca, 13!w którym siedzę, za dziesięć lat lub mniej nie wydaje się tak daleko poza zasięgiem.

Nie myślałem o dużych ilościach danych w 1992 roku, ale z perspektywy czasu wynika, że prawdopodobnie szukałem wszystkiego o jeden czynnik mniej.

— Blrfl
źródło