Ist diese Aussage aus Knuths grundlegenden Algorithmen heute noch anwendbar? [geschlossen]

10

In gewisser Weise 10! (zehn Fakultäten) stellt eine ungefähre Trennlinie zwischen Dingen dar, die praktisch zu berechnen sind, und Dingen, die es nicht sind.

Dies ist aus Knuths TAOCP Fundamental Algorithms Book (1973). Ist dies noch eine gültige Aussage oder hat die Rechenleistung sie überholt?

computer-science taocp Bon Ami
quelle
Mir ist nicht klar, in welchem ​​Sinne es jemals wahr war - 10! ist nur ein paar Millionen. Zu groß für direktes Verständnis, aber nicht besonders schwer zu berechnen, selbst mit Stift und Papier.
Hobbs
11
@hobbs es geht nicht darum, den Wert von 10 zu berechnen ! Es geht darum, Berechnungen für ungefähr 10 durchzuführen ! Dinge . Das heißt, wenn Ihre Methode mehr als 10 erfordert! <Arbeitseinheiten>, es ist Zeit, eine neue Methode zu finden.
AakashM

Antworten:

21

Es ist immer noch vernünftig.

10! = 3,628,880. Jeder Schritt danach geht mindestens um eine Größenordnung nach oben.

(fact 10)
3628800

(fact 11)
39916800 -- about 40 million

(fact 12)
479001600 -- almost 500 million

(fact 13.0)
6227020800.0 -- over 6 billion

Ziemlich bald sprechen Sie über die Ausgabenzahlen des Kongresses.

John R. Strohm
quelle
15

Der gute Professor ist glücklicherweise immer noch bei uns und der beste Weg, um eine endgültige Antwort zu erhalten, besteht darin, ihm zu schreiben und seine Meinung zu erfragen.

Trotzdem denke ich nicht, dass die absolute Zahl so wichtig ist wie die Funktion, die Fakultäten darstellen. Unabhängig davon, ob Knuth dies zu dieser Zeit realisierte oder nicht, funktioniert das Modell, das er mit dieser Aussage aufgestellt hat, sehr gut, um rückwärts auf das zu blicken, was in früheren Jahrzehnten praktisch zu berechnen war, und vorwärts durch die folgenden.

1973 war unsere Kapazität zum Generieren, Speichern, Übertragen und Verarbeiten von Daten auf 10 begrenzt! eine vernünftige "Fernkante" Figur zum Schießen. Ich bezweifle, dass Knuth (oder sonst jemand) in der Lage gewesen wäre, die exponentiellen Verbesserungen in fast allem, was wir seitdem genossen haben, vorherzusagen, aber Fakultäten haben gut zu den tatsächlichen Zahlen gepasst.

Ich habe dies aus erster Hand gesehen: Vor einem Jahrzehnt habe ich an einem Projekt gearbeitet, in dem wir Möglichkeiten zum Speichern und Verarbeiten von etwa 50 Millionen Datensätzen entwickelt haben, während wir gleichzeitig darüber nachgedacht haben, wie wir eine Größenordnung mehr tun würden. Ein Jahrzehnt später mache ich ein ähnliches Projekt. Meine Zielzahlen haben sich faktoriell verschoben:

                      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

Die Gruppen, die beide Projekte durchführen, strebten nach viel runderen Zahlen als diese, aber die Fakultäten sind nicht sehr weit entfernt. Die Googles und Facebooks der Welt haben die Ressourcen, um die Dinge zu tun, von denen mein aktuelles Projekt nur träumt, aber von meinem Platz aus 13!scheint es in einem Jahrzehnt oder weniger nicht so weit außerhalb der Reichweite zu sein.

Ich habe 1992 nicht an große Datenmengen gedacht, aber im Nachhinein hätte ich wahrscheinlich alles eine Fakultät weniger betrachtet.

Blrfl
quelle