Riesige Arrays möglich oder was anderes

Für allgemeine Fragen zur Programmierung mit PureBasic.
Heinz Mendax
Beiträge: 50
Registriert: 29.03.2013 12:25
Wohnort: Eisenach

Riesige Arrays möglich oder was anderes

Beitrag von Heinz Mendax »

Hallo !
Habe noch ein Problem mit Arrays. In einem Programm möchte ich die Farbzusammensetzung eines Bildes bearbeiten. Dazu müssen die Farben des
Bildes gezählt werden. Die obere Grenze sind 16 Mio, aber das kommt meist nicht vor, sondern zum Beispiel n=400000 Farben. In einem ersten
Schritt wird das Bild pixelweise durchgegangen, dessen Farbe bestimmt, und in einem Array, das als index die Farbnummer hat, das vorhandensein
der Farbe gezählt. z.b. f(212)=f(212)+1 für Farbe 212. Die Dimensionierung wird auch bei 16 Mio erfüllt. Mit der Summe (Häufung) bestimmter
Farben muss dann weitergerechnet werden. Der Algorithmus verlangt ein Array der Grösse n*(n-1)/2 im Beispiel 79999800000 bei 16 Mio ist eine
Indexgröße von 140737479966720 nötig. Sind solche Arrays machbar, abgesehen davon, das der Rechner wahrscheinlich für den Programmablauf
Jahre braucht. Ich werde die Farbzahl wahrscheinlich durch Zusammenfassung stark verringern müssen. Bis zu welchem n spielt PB mit seinen
Arrays noch mit (64 bit). ?

Heinz
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Re: Riesige Arrays möglich oder was anderes

Beitrag von NicTheQuick »

Wenn du in einem Bild mit 24 Bit Farbtiefe die Farben zählen möchtest, brauchst du ein Array der Größe 16777216. Wie genau kommst du auf die Gauß'sche Summenformel n*(n-1)/2? Was hat die damit zu tun?
Ein Byte-Array der Größe 140.737.479.966.720 verbraucht insgesamt 128 TB Speicher. Natürlich kannst du kein solches Array erzeugen. Soviel RAM hast du nicht. Ich habe das Gefühl du überdenkst hier irgendwas.
Bild
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Riesige Arrays möglich oder was anderes

Beitrag von STARGÅTE »

Nach dem was ich gerade getestet habe, ist der Array-Index und damit die Array-Große auf 2^31-1 begrenzt (also eine Long).
Demnach liegt das Maximum bei ~2*10^9.
Es ist somit nicht möglich so ein n*(n-1)/2 Array zu erstellen.
Es ist aber auch so nicht möglich solch eine Indextabelle zu erzeugen. Selbst wenn du immer nur 1 Byte bräuchtest, bräuchtest du ja bei einer Größe von "140737479966720" mal eben so 140 TB RAM, also ich habe das nicht.

Da musst du deinen Algo noch mal überdenken.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Heinz Mendax
Beiträge: 50
Registriert: 29.03.2013 12:25
Wohnort: Eisenach

Re: Riesige Arrays möglich oder was anderes

Beitrag von Heinz Mendax »

Die Grösse n*(n-1)/2 kommt von einem Algorithmus, der eine Clusterung namens Average linkage beinhaltet. Diesen Algorithmus habe ich schon
programmiert und war bisher für kleine Mengen (z.B. 50) und kleine Merkmalszahl (z.B. 7) gedacht. Ich wollte ihn jetzt mit dem Farbanalyseprogramm
verbinden.Dabei ergeben sich die Probleme mit der Arraygrösse. Aufgrund der Unmöglichkeit, diese Arrays zu erstellen, werde ich die Farbzahl
erheblich aber auch nicht zu sehr verringern müssen. Entscheidungsmerkmal wird eine Farbabstandsmessung (-rechnung) sein, die zu den stark
unterschiedlichen Pixelfarben nächste Nachbarn sucht und diese dann zusammenfaßt, ähnlich einer Palette. Sobald das Abstandsmaß eine bestimmte
Größe überschreitet, wird die geprüfte Farbe als weitere Farbe gezählt und neuer Bezug. Mal sehen ob diese Reduzierung ausreicht.
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Re: Riesige Arrays möglich oder was anderes

Beitrag von NicTheQuick »

Das, was du im zweiten Teil beschreibst, klingt nach Median-Filter: https://de.wikipedia.org/wiki/Rangordnungsfilter
Und bezüglich der Farbabstandmessung habe ich hier was gefunden: https://www.compuphase.com/cmetric.htm

Oder ich verstehe immer noch nicht genau, was du machen willst. Hast du Beispiele? Gibt es das schon irgendwo? Oder erfindest du gerade was neues?
Bild
Benutzeravatar
NicTheQuick
Ein Admin
Beiträge: 8675
Registriert: 29.08.2004 20:20
Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti
Wohnort: Saarbrücken
Kontaktdaten:

Re: Riesige Arrays möglich oder was anderes

Beitrag von NicTheQuick »

Achso, und bezüglich des Average Linkage Clustering findest du hier einige OpenSource Software, die das kann: https://en.wikipedia.org/wiki/Hierarchi ... g#Software
Vielleicht kannst du dir da auch etwas von abgucken oder einfach fertige Libraries nutzen. Ich gehe davon aus, dass die mit Heuristiken arbeiten bei solch großen Farbbereichen wie du sie analysieren möchtest. Oder aber sie nutzen dünnbesetzte Matrizen, wobei ich nicht sicher bin, ob es da auch Implementierung für 1D- oder 3D-Matrizen (RGB) gibt.
Bild
Antworten