Ist es vernünftig anzunehmen, dass jede physikalische Größe durch eine 64-Bit-Ganzzahl ohne Überlauf oder Unterlauf dargestellt werden kann?

31

Der ursprüngliche binäre Suchalgorithmus im JDK verwendete 32-Bit-Ganzzahlen und hatte einen Überlauffehler, wenn (low + high) > INT_MAX( http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html ) .

Wenn wir denselben binären Suchalgorithmus mit (vorzeichenbehafteten) 64-Bit-Ganzzahlen low + highumschreiben , können wir dann davon ausgehen, dass INT64_MAX niemals überschritten wird, da es physikalisch unmöglich ist, 10 ^ 18 Byte Speicher zu haben?

Ist es bei Verwendung von (vorzeichenbehafteten) 64-Bit-Ganzzahlen zur Darstellung physikalischer Größen vernünftig anzunehmen, dass kein Unter- und Überlauf auftreten kann?

design algorithms Siqi Lin
quelle
4
Schauen Sie sich jedes physikalische Phänomen an, das eine irrationale Zahl hat. Kreise und Pi zum Beispiel. Gleitkommazahlen sind von Natur aus rational und können daher nicht fehlerfrei dargestellt werden.
Thomas Eding
92
Die Anzahl der Atome in der Sonne beträgt ungefähr 1,2e57, was in eine vorzeichenlose 190-Bit-Ganzzahl passt. Im Gegensatz dazu können 64 Bit nicht groß genug sein, um eine physikalische Größe darzustellen.
6
Ihr Fragentitel ist irreführend. Sie sollten fragen, ob es Mengen gibt, für die eine Anwendung mit einem sortierten Array mit einer Größe größer als 2 ^ 64 zu erwarten ist.
Doc Brown
7
oder die Anzahl der Yoctosekunden seit dem Beginn des Lesens dieses Kommentars.
Jodrell
4
Es gab eine Zeit, in der alle dachten, es würde niemals 2 ^ 32 Computer geben, die miteinander verbunden sind. Sie wollen doch nicht, dass Ihre Atome NAT verwenden müssen, oder?
Sebb

Antworten:

58

Die kurze Antwort lautet nein. Bei einigen Anwendungen ist Ihre Annahme jedoch möglicherweise richtig.

Angenommen, ein vorzeichenbehaftetes int, 2 ^ 63, mit Kommas zur Verdeutlichung hinzugefügt, = 9.223.372.036.854.775.808. Es ist also ungefähr 9 * 10 ^ 18. 10 ^ 18 ist eine "Exa".

Laut Wikipedia hat das World Wide Web 2013 schätzungsweise 4 Zettabyte erreicht [12], was 4000 Exabyte entspricht. Daher ist das WWW ungefähr 400-mal größer als 2 ^ 63 Bytes.

Daher gibt es mindestens eine physikalische Größe, die viel größer ist als eine 64-Bit-Ganzzahl mit oder ohne Vorzeichen. Angenommen, Ihre Einheiten sind Bytes . Wenn Ihre Einheiten viel größer wären, wie GigaBytes, dann wären Sie in Ordnung, aber Ihre Messgenauigkeit wäre gering.

Ein weiteres Beispiel sind weit entfernte Galaxien. Die Andromeda-Galaxie ist tatsächlich eine der engsten, und sie ist 2,5 * 10 ^ 6 Lichtjahre entfernt. Wenn Ihre Einheiten Meilen wären, wäre dies 14,5 * 10 ^ 18, also mehr als eine 64-Bit-Ganzzahl mit Vorzeichen. Nun hängt es natürlich von den Einheiten ab, die Sie für Ihre Messungen verwenden, aber einige Galaxien sind weit entfernt von Andromeda. ( Der am weitesten bekannte Wert ist 13 * 10 ^ 9 LY entfernt. ) Abhängig von der für Ihre Messung gewünschten Genauigkeit kann eine 64-Bit-Ganzzahl überlaufen.

( Hinzugefügt ) Ja, Meilen sind eine miese Einheit für astronomische Entfernungen. Eine normalere Einheit könnte eine astronomische Einheit sein , ungefähr 150 Millionen Kilometer. Unter Verwendung dieser Maßeinheit ist die am weitesten bekannte Galaxie ungefähr 10 ^ 15 AU (wenn meine Mathematik richtig ist), was in eine 64-Bit-Ganzzahl passen würde. Wenn Sie jedoch auch die Entfernung zum Mond oder zu umlaufenden Satelliten in der Nähe messen möchten, ist diese Einheit zu groß.

Ein weiteres Beispiel aus der Elektronik: der Farad (F), eine Kapazitätseinheit . Große Kondensatoren reichen bis zu 5 kF. Und diese Zahl wird wahrscheinlich mit der Zeit zunehmen, wenn sich Hybridautos, "Smart Grids" usw. verbessern. Once kann eine Kapazität von nur 10 ^ -18 F messen. Der Gesamtbereich der "realen" Kapazität, den wir heute messen können, ist also 5 * 10 ^ 21, größer als eine 64-Bit-Ganzzahl.

user949300
quelle
3
All dies ist wahr, aber aus praktischer Sicht können wir den Punkt der Messung der Entfernung der Andromeda-Galaxie von der Milchstraße in Meilen (wo genau sind die Bezugspunkte?) Oder das gesamte WWW in Bytes (mit dieser Genauigkeit) in Frage stellen. es ändert sich jede Millisekunde)
Jivan
45
@Jivan Aus praktischer Sicht sehe ich keinen Grund, warum Sie jemals mehr als 640 kB Speicher adressieren müssten. Sicherlich ist es mehr, als Sie jemals brauchen würden.
ARTS
2
Ein weiterer Nachteil bei der Messung astronomischer Entfernungen in Meilen: Es besteht die Gefahr, dass Sie mit einer Katze erwischt werden.
Williham Totland
2
@ Jivan Guter Punkt. Das erinnert mich an Richard Feynman, der sich über die Albernheit lustig macht, die Temperatur einer Gruppe von Sternen zu summieren. Ich verstehe, warum Sie den Durchschnitt, das Minimum, das Maximum, aber die Summe wollen? Welche physikalische Bedeutung hat das?
Piojo
6
@piojo - Zugegeben, die Summe ist nützlich, wenn der Mittelwert berechnet wird.
Scott Whitlock
20

Sie müssen nicht einmal kosmisch werden, wenn es um Kombinatorik geht. Es gibt 2 ^ 95 mögliche Deals in einem Brückenspiel und das ist etwas komplexer.

msw
quelle
Man könnte sich fragen, ob das als "physikalische Größe" zählt.
Paul Draper
2
Auf der anderen Seite würde die Kombinatorik in der Chemie oder Mathematik als "physikalisch" bezeichnet.
rwong
@PaulDraper Wenn Sie genug Kartendecks hätten, um alle diese Deals auf dem Boden zu platzieren, wäre das physisch. Dann hätten Sie sogar mehr als 2 ^ 95 Karten .
Brad,
1
@ Brad, ich denke, das OP fragt nach einer Menge, die "existiert" (okay, Existenz ist ein unscharfes Konzept). 2 ^ 95 Karten, die einem mathematischen Konzept entsprechen, existieren nicht (rufen Sie Guinness an, wenn sie dies tun). Es ist schwer zu sagen, was "zählt" und was nicht. Diese Antwort befriedigt einfach nicht meine matschige Vorstellung von einer physikalischen Größe.
Paul Draper
17

Die für Ihre Frage relevanteste physikalische Größe ist der Arbeitsspeicher des Computers .

Windows Server 2012 unterstützt bis zu 4 TB physischen Speicher. Das sind 2 42 Bytes. Wenn sich die RAM-Kapazitäten jedes Jahr weiter verdoppeln, unterstützt "Windows Server 2032" in nur 17 Jahren 2 62 Byte physischen Speicher. Zu diesem Zeitpunkt low + higherreichen Sie 2 63 - 2 und küssen die maximale 64-Bit-Ganzzahl mit Vorzeichen.

Ich hoffe, dass keine sicherheitskritischen Systeme ausfallen, davon auszugehen, dass 64 Bit immer ausreichen werden.

Für eine etwas allgemeinere Verwendung ist die relevanteste physikalische Größe der Speicheradressraum . (Es ist nützlich, einen viel größeren Adressraum als den physischen Speicher zu haben, z. B. um viele Stapel im Speicher abzulegen, die alle Platz zum Wachsen bieten .) Aktuelle x86-64- Implementierungen unterstützen virtuelle 48-Bit-Adressen, sodass wir nur 14 Jahre Zeit haben, bevor diese CPUs erreicht werden die 2 62- Byte-Adressraumbegrenzung.

Und dann gibt es einen verteilten gemeinsam genutzten Speicher, "in dem die (physisch getrennten) Speicher als ein (logisch gemeinsam genutzter) Adressraum adressiert werden können".

Jerry101
quelle
4
+1 Ihre Antwort ist fast genau richtig, außer dass bestimmte Arten der heutigen Software bereits auf Speicheradressen im Bereich 0xFFFFFFFFxxxxxxxx(dh der höheren Hälfte ) stoßen , zum Beispiel auf das Betriebssystem oder Gerätetreiber.
rwong
2
@ SiqiLin wahrscheinlich nicht so weit wie Personal Computing betroffen ist. Der verteilte freigegebene Speicher oder das DGAS (das in dem Artikel erwähnt wird) sind jedoch real; Supercomputer arbeiten seit Jahren in diesem Stil, und es ist möglich, dass dies zur Norm für multinationale Cloud-Computing-Infrastrukturen wird. Offensichtlich wird der typische Software-Code, der vom typischen Programmierer geschrieben wurde, in einer solchen Umgebung nicht ausgeführt - in ungewöhnlichen Umgebungen wird ungewöhnliche (dh infrastrukturelle) Software ausgeführt. Aber ein Bruchteil der P.SE-Leser könnte gerade auf einer solchen Karrierestrecke landen; nur für den Fall.
rwong
1
@Joshua: Mit der aktuellen Technologie (32 GB DDR4) wären dies 7 m oder 23 ns, damit sich das Licht bewegen kann, was den modernen CAS-Latenzen perfekt zu entsprechen scheint. Wenn Sie es auf das Landauer-Prinzip-Extrem bringen, erhalten Sie mit der Dichte von Silizium 31 nm oder 10 ^ -16 Sekunden für die physikalische Grenze. Das scheint nicht zu verrückt zu sein ... na ja, vielleicht nur ein bisschen.
Charles
3
@Joshua Das ist eine technologische Grenze, keine physikalische. (Wie in der Vergangenheit besteht das Problem darin, dass wir nicht wissen, wie man es praktisch macht, und dass einige physikalische Gesetze es nicht verbieten.) Daher könnte es sich, obwohl es in dieser Woche relevant ist, jederzeit mit einem neuen Durchbruch ändern. Vor ungefähr 60 Jahren hätten die Leute ähnliche Kommentare abgegeben wie Sie. Etwa 50 Kilobyte Speicher galten als RAM, da handgewickelte Drahtspulen, die damals als Teile von Speicherkernen verwendet wurden, nicht nur nur so klein und still werden konnten Funktion, aber erforderlicher Abstand zwischen ihnen, um EM-Übersprechen zu vermeiden.
Matthew Najmon
2
Ich erinnere mich, als 24 Bit Adressraum (16 Megabyte) mehr waren, als irgendjemand jemals benötigt hätte - oder sich leisten konnte. :-)
Bob Jarvis - Reinstate Monica
10

Ist es vernünftig anzunehmen, dass jede physikalische Größe durch eine 64-Bit-Ganzzahl ohne Überlauf oder Unterlauf dargestellt werden kann?

Nicht genau. Es gibt viele Zahlen, die sowohl größer als auch kleiner sind. Deshalb haben wir Gleitkommazahlen. Gleitkommazahlen tauschen weniger Präzision gegen bessere Reichweite aus.

In dem konkreten Beispiel, das Sie zitiert haben, ist es sehr unwahrscheinlich, dass Sie jemals eine größere Zahl benötigen würden. 64 Bit entsprechen ungefähr 18 Trillionen Elementen. Aber sag niemals nie.

Robert Harvey
quelle
7

Ihre Annahme behandelt keine physikalischen Größen, die nur durch Gleitkommazahlen dargestellt werden können. Und selbst wenn Sie sich entschlossen haben, alle Zahlen zu skalieren, indem Sie beispielsweise alle Zahlen mit 10000 multiplizieren (die Werte sind also immer noch ganze Zahlen, können aber in Zehntausendsteln dargestellt werden), schlägt dieses Schema für Zahlen nahe Null, beispielsweise die Elektronenmasse, immer noch fehl (9,1094 * 10 & supmin; ¹ kg).

Das ist eine sehr reale (und extrem kleine) physikalische Größe . Hier sind noch einige , mit denen Sie Probleme haben werden. Und wenn Sie argumentieren, dass dies keine reale physikalische Größe ist (obwohl sie in kg angegeben ist), bedenken Sie Folgendes:

10 kg (obviously physical quantity)
1 kg (same)
10⎻² kg (1/100 kg, or about 1/3 ounce) (also quite real)

Sie sehen also, wohin ich damit gehe. Das letzte, mit dem du nicht fertig wirst.

Natürlich können Sie ein spezielles Feld in der Zahl haben, um einen ganzzahligen Teil mit einem variablen Multiplikator nach oben oder unten zu skalieren. Jetzt hast du das Fließkomma erfunden.

Tcrosley
quelle
1
Sie können jedoch einen minimalen physikalischen Wert zuweisen (IIRC, für Masse war es die Masse, die 1 Elektronenvolt entspricht). Beispielsweise können Sie die Universumslänge mit Planck-Längeneinheiten mit (IIRC) 200 Stellen messen. Man kann mental über 1/10 einer Planck-Länge sprechen, aber physisch hat es keinen Sinn.
SJuan76,
Meinen Sie nicht durch 10000 teilen? Das Multiplizieren mit 10000 würde nur die Wahrscheinlichkeit erhöhen, dass die Annahme des Thread-Öffners fehlschlägt. Vielleicht zeigt mein Gerät die Elektronenmasse auch nicht richtig an, aber es sollte 10 ^ -31 sein
Mike
Ich meine mit 10000 multiplizieren. Wenn Sie 1.0001 als Ganzzahl speichern möchten, müssen Sie es mit 10000 multiplizieren, bevor Sie es als 10001 speichern. Ich habe hochgestellte Zeichen für die -31 verwendet, möglicherweise werden sie nicht in allen Browsern korrekt angezeigt . In Firefox gut aussehen.
Tcrosley
@ SJuan76 Es gibt so etwas wie Zukunftssicherheit. Im Jahr 1850 konnten wir von einer Einheit von 10 ^ -20 Metern sprechen (viel kleiner als ein Atom, aber immer noch viel größer als eine Planck-Länge), aber physikalisch ergab dies keinen Sinn. Dann haben die Menschen die innere Struktur eines Atoms herausgefunden. Sicher, Quarks sehen grundlegend aus, aber wir können wirklich nur sagen, (a) dass sie sich so verhalten, wie wir das Verhalten grundlegender Partikel erwarten, und (b) dass wir noch keine nächste Schildkröte gefunden haben. Im Jahr 1850 konnten wir die gleichen zwei Dinge über Atome sagen. Wenn wir eine nächste Schildkröte finden, werden Einheiten von 1/10 Planck sehr nützlich.
Matthew Najmon
Es ist ein weit verbreitetes Missverständnis, dass Raum oder Zeit in Planck-Einheiten quantisiert werden! Sie können das Universum nicht durch ein 4-dimensionales Array darstellen, zumindest nicht in den aktuellen Theorien ... Bruchteile von Planck-Längen sind also physikalisch bedeutsam (aber die Ergebnisse, die aus der Allgemeinen Relativitätstheorie und / oder dem QM resultieren, beginnen zu explodieren oder sich widersprechen).
Yatima2975
5

Zunächst würde ich die Frage beantworten, welche physikalischen Werte durch eine ganze Zahl dargestellt werden können / sollen.

Eine Ganzzahl ist eine Darstellung einer natürlichen Zahl (und ihrer Unterschiede) in einem Computersystem, daher ist es falsch, sie auf irgendetwas anderes anzuwenden. Das Aufrufen von Entfernungen oder anderen Größen, die zu einer kontinuierlichen Domäne gehören, ist daher kein Argument. Für solche Größen gibt es reelle Zahlendarstellungen. Und Sie können immer eine beliebig große Einheit auswählen und jeden Wert mit einer bestimmten Genauigkeit anpassen.

Was sind also physikalische Werte, die natürliche Zahlen sind und 64-Bit-Ganzzahlen überlaufen können?

Ich kann mir zwei vorstellen. Anzahl physikalischer Objekte (wie Atome) und Energieniveaus, in denen sich ein Quantensystem befinden kann. Dies sind zwei Dinge, die streng ganzzahlig sind. Nun, ich weiß, Sie können ein Atom teilen, aber es erzeugt immer noch eine ganze Zahl und Sie können es nicht auf unbestimmte Zeit teilen. Beide können den 64-Bit-Bereich vorzeichenloser Ganzzahlen leicht übertreffen . Die Anzahl der Atome ist höher und ein Atom kann sich in mehr als einem Energiezustand befinden.

Ob Informationen physisch sind oder nicht, ist sehr umstritten. Ich würde sagen, dass es nicht ist. Daher würde ich nicht sagen, dass die Informationsmenge eine physische Sache ist. Ist also nicht die Größe des Arbeitsspeichers oder so etwas. Wenn Sie dies zulassen würden, dann würde die Anzahl der Atome diese Anzahl leicht überschreiten, da Sie mit der heutigen Technologie mehr als ein Atom benötigen, um ein Bit zu speichern.

luk32
quelle
Die Menge N natürlicher Zahlen enthält nur nicht negative ganze Zahlen. Ich weiß, was Sie meinten, aber "natürliche Zahl" hat eine spezifische mathematische Definition, die nicht mit Ihrer Verwendung übereinstimmt.
Ich bin mir nicht ganz sicher. Integer-Typen repräsentieren natürliche Zahlen (innerhalb eines bestimmten Bereichs, der impliziert wird). Ist das nicht wahr Ich glaube, Sie haben angenommen, ich impliziere Gleichheit zwischen den Sätzen. Dies ist nicht wahr, jede natürliche Zahl kann durch eine ganze Zahl dargestellt werden. Bitte beachten Sie, dass ich auch Unterschiede zwischen ihnen sagte. Ich hatte nicht das Gefühl, dass es notwendig wäre, signiert / nicht signiert zu werden. Singed Type ist nur erforderlich, wenn Sie mit Unterschieden umgehen.
Luk32,
Während die Physikalität der gespeicherten Informationen umstritten ist und eher für Philosophen als für Physiker eine Frage ist, ist die Physikalität der Mechanismen, durch die sie gespeichert werden, ziemlich sicher. Daher ist, während die Anwendbarkeit auf eine Anzahl von Informationsbits fraglich ist, die Anzahl von RAM-Chips im Wert von Bits nicht fraglich .
Matthew Najmon
@MatthewNajmon Natürlich stimme ich zu, deshalb habe ich den letzten Satz verlassen. Die Anzahl der Bits eines RAM-Chips ist für einige Zeit geringer als die Anzahl der Atome, so dass Sie letztere verwenden können. Mit anderen Worten, warum sollten Sie die Anzahl der Bits verwenden, wenn Sie die Anzahl der Atome desselben RAM-Chips verwenden können? Momentan wird ein bisschen Information durch einen Zustand dargestellt, in dem sich ein physikalisches System befindet, sodass Sie mehr als ein Bit pro Atom speichern können, aber es ist heutzutage weit von der Anwendung entfernt, und ich sehe immer noch nicht, wie es mehr als die Anzahl sein kann Quantenzustände eines solchen Systems. Aber ich stimme Ihrer Prämisse voll und ganz zu.
Luk32
4

Zusätzlich zur Antwort von Jerry101 möchte ich diesen sehr einfachen und praktischen Test für die Richtigkeit anbieten:

Angenommen, Sie weisen mallocin einem 64-Bit-Betriebssystem etwas Speicher über zu . Angenommen, der Speicherzuordner gibt einen gültigen Speicherblock mit der von Ihnen angeforderten Größe zurück, wobei jedoch das 63. Bit gesetzt ist.

Mit anderen Worten, nehmen wir an, es gibt einige Programmierumgebungen, in denen 0xFFFFFFFFxxxxxxxxes sich um legitime Speicherbereiche handelt, die von einem Aufruf an zurückgegeben werden können malloc.

Die Frage ist, wird Ihr Code noch wie vorgesehen funktionieren?

Wenn die analoge Situation für 32-Bit-Betriebssysteme auftritt, funktionierte einige Software nicht ordnungsgemäß, wenn ihnen Speicheradressen "in der oberen Hälfte" zugewiesen wurden. Ursprünglich galt die Verfügbarkeit solcher Speicheradressen nur für den privilegierten Code (Betriebssysteme, Gerätetreiber und Peripheriegeräte). Aufgrund der Knappheit des 32-Bit-Adressraums entschieden sich die Anbieter von Betriebssystemen, einen Teil des reservierten Speicherplatzes zur Verfügung zu stellen Anwendungen, die danach fragen.

Glücklicherweise ist es ziemlich unwahrscheinlich, dass diese Situation für eine Weile bei 64-Bit-Programmen auftritt, zumindest nicht in einem Jahrzehnt.

Wenn diese Situation endlich eintritt, bedeutet dies, dass 128-Bit-adressierbare Prozessoren und Betriebssysteme zu diesem Zeitpunkt zum Mainstream geworden wären und dass sie eine "64-Bit-Emulationsumgebung" bereitstellen könnten, um den Betrieb dieser "Legacy-Anwendungen" zu ermöglichen unter Annahmen ähnlich den heutigen 64-Bit-Betriebssystemen.

Beachten Sie schließlich, dass sich diese Diskussion nur auf Speicheradressen konzentriert. Ein ähnliches Problem mit Zeitstempeln muss mit größerer Vorsicht behandelt werden, da bestimmte Zeitstempelformate den Mikrosekunden viele Bits an Genauigkeit zuweisen und daher in Zukunft weniger Bits für die Darstellung der Zeit zur Verfügung stehen. Diese Probleme sind im Wikipedia-Artikel zum Problem des Jahres 2038 zusammengefasst .

rwong
quelle
4

Dies ist eine Frage, die Sie von Fall zu Fall stellen müssen. Sie sollten nicht generell davon ausgehen, dass die 64-Bit-Arithmetik nicht überläuft, da eine böswillige Datenquelle auch dann zu unzumutbaren Mengen führen kann, die möglicherweise überlaufen auf diese Situation vorbereitet, als unerwartet von ihr getroffen zu werden.

In einigen Fällen ist es sinnvoll, Code zu schreiben, der vom Nichtüberlauf von 64-Bit-Zahlen abhängt. Die Hauptklasse des Beispiels, die ich kenne, sind Zähler, bei denen der Zähler jedes Mal erhöht wird, wenn er verwendet wird. Selbst bei einer Rate von einem Inkrement pro Nanosekunde (nicht praktikabel) würde ein Überlauf mehr als ein Jahrhundert dauern.

Beachten Sie, dass es auf den ersten Blick "im Prinzip immer falsch" scheint, sich auf "Zeit bis zum Ausfall" zu verlassen, um die Richtigkeit eines Systems zu gewährleisten. Dies geschieht jedoch immer mit Authentifizierung / Anmeldung. Wenn genügend Zeit vorhanden ist (um brachiales Forcen zu ermöglichen), ist ein solches System (unabhängig davon, ob es auf Passwörtern, privaten Schlüsseln, Sitzungstoken usw. basiert) defekt.

R ..
quelle
2

Ist es MÖGLICH, dass eine physikalische Größe nicht in 64 Bit passt? Na sicher. Andere haben darauf hingewiesen, die Anzahl der Atome in der Sonne oder die Anzahl der Millimeter bis zur nächsten Galaxie zu zählen. Ob solche Fälle für Ihre Anwendung relevant sind, hängt von Ihrer Anwendung ab. Wenn Sie die Anzahl der Artikel in einem bestimmten Fach in Ihrem Lager zählen, sind wahrscheinlich 16 Bits ausreichend. Wenn Sie Statistiken über die Anzahl der Menschen auf der Welt erstellen, die verschiedene Bedingungen erfüllen, müssen Sie in der Lage sein, Milliarden aufzuzeichnen. Daher benötigen Sie mehr als 32 Bits. Zu diesem Zeitpunkt würden Sie vermutlich auf 64 wechseln (ebenso wenige Computer) haben eingebaute Unterstützung für 37-Bit-Nummern usw.). Wenn es sich um eine Chemieanwendung handelt, die Atome in Mol zählt, sind 64 Bit nicht ausreichend.

Nur weil heutzutage kein Computer über 2 ^ 64 Bytes Arbeitsspeicher verfügt, bedeutet dies technisch nicht zwangsläufig, dass ein Array-Index niemals mehr als 2 ^ 64 sein kann. Es gibt ein Konzept, das als "spärliches Array" bezeichnet wird, bei dem viele Elemente des Arrays nirgendwo physisch gespeichert werden und für solche nicht gespeicherten Werte ein Standardwert wie null oder null angenommen wird. Aber ich nehme an, dass, wenn Sie eine Funktion schreiben, um ein Array oder eine Liste zu durchsuchen, und die Größe des Felds, das Sie verwenden, um den Index im Array zu speichern, mehr als doppelt so groß ist wie die größtmögliche Adresse, und dann nach einem Überlauf suchen, wenn Das Hinzufügen von zwei Indizes wäre nicht unbedingt erforderlich.

Jay
quelle
Guter Punkt zu spärlichen Arrays. Selbst mit einem Array, das vollständig gefüllt ist, ist es durchaus möglich, wenn auch ziemlich langsam, und in einigen Fällen durchaus erforderlich, mit einem Array zu arbeiten, das zu groß ist, um das gesamte Array auf einmal in den Arbeitsspeicher zu passen. Dies geschieht einfach dadurch, dass das Ganze auf einem langsameren, aber viel größeren Medium wie einer Festplatte gespeichert wird und dann nur die wenigen Elemente, mit denen Sie gerade arbeiten, in den Arbeitsspeicher verschoben werden. Selbst eine kleine Festplatte ist groß genug, um ein Array aufzunehmen, das viel größer ist, als das OP annehmen möchte.
Matthew Najmon
0

Es ist nicht zumutbar anzunehmen, dass eine 64-Bit-Ganzzahl alle Zahlen enthalten kann. Mehrere Gründe:

  1. Die 64-Bit-Ganzzahlen max und min sind endliche Zahlen. Für jede endliche Zahl existiert eine größere und eine kleinere endliche Zahl.

  2. Berechnungen mit 128-Bit- und 256-Bit-Zahlen werden derzeit an verschiedenen Stellen verwendet. Viele Prozessoren verfügen über spezifische Anweisungen, die 128-Bit-Ganzzahlen verarbeiten.

  3. Vor 20 Jahren galt eine 1-GB-Festplatte als "groß". Heutzutage wird eine 1-TB-Festplatte als klein angesehen. Vor 20 Jahren hatten durchschnittliche Desktops etwa 16 MB RAM. Mein aktueller Desktop hat mehr als 16 GB RAM. Festplattenspeicher und RAM sind in der Vergangenheit exponentiell gewachsen und werden in Zukunft voraussichtlich exponentiell wachsen. Es macht keinen Sinn anzunehmen, dass jemand aufhört zu wachsen, es sei denn, er hat einen guten Grund, warum er aufhören sollte.

Peter
quelle