Entwickler-Ecke :: Thema anzeigen - Speicherminimierung Gruppenarbeit?

IhopeonlyReader - Di 07.05.13 18:32
Titel: Speicherminimierung Gruppenarbeit?

Guten Tag,
ich wollte euch mal Fragen ob ihr Interesse daran hättet, mit mir eine Unit zur Speicherminimierung zu schreiben?

Ich hatte zuerst überlegt, es direkt in den Bereich "Gruppenarbeiten" zu stecken, aber ich würde gerne erst einmal eure Meinung und Vorschläge oder sogar Lösungen hören..
Der Text, den ich für das Thema "Gruppenarbeit", geschrieben hatte:

Zitat:

Nachdem ich 2 Units zur Verkleinerung von "vielen" Booleans geschrieben habe,
habe ich mir vorgenommen eine Unit zu schreiben, die JEDE Art von Vielem (Zahlen, Strings, Booleans etc.) so klein wie möglich macht!

Hierfür gibt es Bereits viele "Hilfsmittel" wie ".ZIP", allerdings versuche den Schwerpunkt vor allem auf Zahlen zu legen so dass das ZIEL endgültig sein wird
alles zu verkleinern, indem man die Bits "anders" abspeichert..

als SEHR einfaches Beispiel, besteht ein String NUR aus "ÿ"s (Code: 255; BinärSystem 8x 1), so könnte einfach die Anzahl der Einsen und dass es einsen sind, abgespeichert werden.. (würde sich erst ab 2 Zeichen lohnen)...

Das oben genannte Beispiel wäre eine einfache Komprimierung, die häufig schon verwendet wird... aber was wäre wenn wir ein Projekt schreiben, dass "Zusammenhänge" erkennt und Formeln aufstellt, die dann abgespeichert werden?

Bsp.
so wäre aus dem BinärCode: 00000001 00000010 00000011 00000100 00000101 00000110 00000111 (Zahlen 1 bis 7)
einfach 00000001 00000001 00000001 00000110 (1,1,1,6)
Startwert 1
1 Mathe-Zeichen(von mir vordefiniert) (+)
Wert (der dazukommt): 1
Anzahl der Wiederholungen 6

wobei das "Mathe-Zeichen" bei Strings unnötig ist, da als Wert mindestens ein Byte verwendet wird, und somit dadurch schon alle Werte erreicht werden können...
Wenn man also bei String Abspeicherungen darauf verzichten würde, wäre man bei 3 Bytes benötigt um 7 Bytes zu speichern...

Das sind alles einfache Beispiele, aber ich denke jeder hat das Prinzip verstanden, GrundIdeen sind vorhanden...
Ich habe bereits eine "Art", die allerdings nur dann verkleinert speichert, wenn es 3 oder mehr als Punkte (Binär Werte/ Zahlen) als eine lLineare Darstellen kann...

Mathematiker - Di 07.05.13 21:51

Hallo,

platzwart hat folgendes geschrieben :

Da ist doch aber das von dir genannte ZIP wesentlich effizienter :gruebel:

Kann ich nur unterstützen. Wenn Du die Delphi-Unit zlib verwendest, kannst Du alle Dateien/Daten auf ZIP-Qualität komprimieren. Zum Beispiel wird eine Textdatei mit 1 Million Ziffern von PI nur auf 474 k komprimiert.
Von über 1 Million Stellen von Wurzel 4 :wink: bleiben mit zlib gerade mal 3600 Byte übrig.
Weiteres Beispiel: Für das einfache MIDI-Programm http://www.entwickler-ecke.de/topic_Einfaches+MIDIProgramm_111517.html habe ich 6500 Byte Notentextdatei für die Ressource mit zlib auf nur 765 Byte reduziert.
Und zlib ist mit seinen Routinen so schnell, dass das Laden und Entpacken komprimierter Daten mindestens so schnell ist, wie das Laden der ungepackten Daten allein.

Ich vermute, es wird schwer werden, mit einem anderen Verfahren eine stärkere Kompression zu erreichen.

Beste Grüße
Mathematiker

jaenicke - Di 07.05.13 22:12

Mathematiker hat folgendes geschrieben :

Wenn Du die Delphi-Unit zlib verwendest, kannst Du alle Dateien/Daten auf ZIP-Qualität komprimieren. Zum Beispiel wird eine Textdatei mit 1 Million Ziffern von PI nur auf 474 k komprimiert.

Selbst mit 7zip sind es noch rund 400 KiB.

Zlib würde ich nun nicht unbedingt nehmen, schließlich gibt es z.B. mit Abbrevia ja bessere Möglichkeiten (7zip, Zip, ...) und das kostenlos.

Wie dem auch sei, die oben genannten Ideen bringen nur in den seltensten Fällen einen Vorteil, insofern helfen sie auch in den seltensten Fällen.

Mr_Emre_D - Mi 08.05.13 19:48

Zitat:

Hierfür gibt es Bereits viele "Hilfsmittel" wie ".ZIP", allerdings versuche den Schwerpunkt vor allem auf Zahlen zu legen so dass das ZIEL endgültig sein wird

Du scheinst zwischen Zahlen und Bits/Bytes zu unterscheiden...
Eine Bitfolge repräsentiert eine Zahl; letzendlich sind alles Zahlen!
Ein String ist eine Zeichenkette, wo jedes Zeichen auch wiederum eine Bitfolge ist, was zu einer größeren Bitfolge zusammenaddiert.

Weiters sind Kompressionsalgorithmen allgemein definiert und beziehen sich nicht auf bestimmte Datentypen.
Klar, verschiedene Kompressionsalgos komprimieren verschieden gut mit verschiedenem Input - sie erfüllen halt ihren Zweck. Deshalb werden sie auch damit in Zusammenhang gebracht. RLE ist z.B. gut für Input, wo Daten wiederholt hintereinander vorkommen. Huffman dahingegen kodiert nach Entropie - Daten, die öfter vorkommen, bekommen kleinere Codes. Ich sage absichtlich Daten und nicht Zeichen oder sonstiges - du kannst nämlich selbst definieren, was deine Daten sind.
...

IhopeonlyReader - Mi 08.05.13 20:18

Ja, ich unterscheide die verschiedenen Systeme (Decimal- und Binärsystem), da wenn man sich jedes gesetzte Bit in verschiedenen Systemen anschaut, ist es nicht gleich!
Bsp.
Hexadezimal 1F 20
Dezimal 31 32
Binär 11111 100000

Wenn man sich jede Zahl der verschiedenen Systeme in einem Graph vorstellt und jede Zahl als Punkt betrachtet, (1|31 2|32 wären die Punkte des Decimalsystems)
So ist es ein Unterschied, wenn man einen Zusammenhang zwischen den Zahlen sucht!

Und ich weiß, dass andere Kompressionsalgorithmen für andere Daten gut sind. Eventuell könnte man den "besten" für die vorhanden Daten raussuchen und dann mit abspeichern, womit es komprimiert wurde, um die "Beste" Komprimierung zu erreichen

jaenicke - Mi 08.05.13 20:34

IhopeonlyReader hat folgendes geschrieben :

Bits können nur 0 oder 1 sein. Deine Zahl sieht zwar in Hexadezimaldarstellung als String anders aus, aber die Zahl dahinter sieht im Speicher ja immer noch nicht anders aus als die Zahl in Binärdarstellung...

IhopeonlyReader - Mi 08.05.13 21:25

ja, das stimmt! aber hättest du mein Kommentar gelesen, geht es darum eine Funktion dafür zu finden...
Betrachtet man die Zahl (11111 /31) im Decimalsystem OHNE casten (also 11 tausend 1 hundert - elf) und die nächste zahl ebenso, und stellt diese dann Graphisch dar, ist es mal mit Binärsystem leichter mal mit dem Decimalsystem leichter zusammenhänge zu finden (bei +1 pro zahl ist es im Decimalsystem leichter)

Mr_Emre_D - Do 09.05.13 00:03

Sofern ich dich richtig verstehe, denkst du, dass, weil die Repräsentation in anderen Systemen von der Entropie her ander ist, eine bessere Kompression erreicht werden kann.
Der Punkt ist, dass die Repräsentation in anderen Systemen Balast mit sich schleppt.

Wenn du ein Byte in Hex darstellst, benötigst du genau 2 Zeichen, wobei dann ein Zeichen wieder ein Byte groß ist (200%).
Fürs Dezimalsystem gilt das genauso, da benögist du dann 3 Zeichen (255) = 300%

Die Kompression, die du nun entwickeln willst, muss aber, sofern du die jetztigen übertreffen willst (sonst wärs ja sinnlos), 200-300% mal besser sein.
Ich will dir aber den Spaß nicht rauben... wenn du ne geniale Idee hast, go ahead!
Ill be reading

IhopeonlyReader - Fr 10.05.13 21:10

Mr_Emre_D hat folgendes geschrieben :

200-300% mal besser sein

Ja, es funktioniert, wenn 3 oder mehr punkte sich linearisieren lassen !

Beispiel:
2,3,4,5,10,12,15,20

So wäre zwar 2 3 4 5 eine 4er Folge und somit sparender, aber
10, 12, 15, 20 lassen sich nicht direkt linearisieren, so würden diese JE 3x soviel einnehmen...
also
75% des speichers von 4 Zahlen und 300% des speichers von 4 Zahlen
= 7/15 SpeicherZUVIELnutzung...
wenn man allerdings noch eine weitere BooleanVariable speichern würde, um anzugeben ob die nächste zahl im System (per Funktion) oder direkt als Zahl angegeben wird, und gehen wir von einer Zahl im Byte-Bereich aus

2, 3, 4, 5 würden genau so groß dargestellt werden können, wie als Zahl (da SizeOf(Boolean) = SizeOf(Byte))
10, 12, 15, 20 wären dann allerdings doppelt so groß.. (die Zahl selber muss gespeichert werden 8 Bit und der Boolean wert ob es mit einer Funktion weitergeht, oder der "einzelnen" Zahl (Boolean -> 8 Bit))
wären somit 4x8 Bit größer

um also das ganze Problem auszulöschen, würde ich ein dyn. Array erzeugen of NRecord (Bsp. Zahlen: Array of NRecord) erzeugen
in NRecord (=record) steht jetzt wieder 2 dyn. Array
1. FunktionsArt: Array of RFunktion //Falls es eine Funktion ist
2. ZahlSelbst: Array of Byte; // können alle zahlen im Bereich zwischen 2 gefundenen Linearisierungen gespeichert werden

jetzt wird das ganze erste dyn. Array durchgegangen (Zahlen) (bis High(Zahlen) und gepüft ob length(FunktionsArt)=0 dann wird aus ZahlSelbst abgelesen, sonst aus FunktionsArt

Die Frage ist dabei:

Delphi-Quelltext

1:	setlength(ZahlSelbst, 0);

wie groß ist das dyn. Array ZahlSelbst?
Mein Delphi sagt, ein Dyn. Array sei IMMER 4 Byte groß, wobei ich das nicht glaube^^

jfheins - Fr 10.05.13 21:45

Also mit sowas ("lineare Funktionen") ist heutzutage eigentlich nicht mehr viel zu machen... weil wer speichert schon simple aufsteigende Zahlenfolgen?

Was zum Beispiel bei JPEG benutzt wird, sind auch Funktionen nur ungleich komplexer. Ein 16x16 Pixel Block wird mit Hilfe von cosinus Funktionen dargestellt. Gewisse Anteile werden dann weggelassen, so dass wenig Information verloren geht.
Andere Sachen wäre z.B. wavelet gibt es auch noch, sind aber wieder ein ganzes Stück komplexer.

Zu deinem dynamischen Array: Ja, die Länge ist tatsächlich 0. Da deine Variable ein Pointer ist, ergibt sizeof() immer 4. Der Speicherbereich beginnt folgereichtig an der Stelle arr[0].
Die Idee, die Daten "in einem anderen System zu betrachten" (ich nehme mal an, du meinst Zahlensystem) hatten schon andere, mit mäßigem Erfolg: http://www.delphipraxis.net/172780-tutorial-arbeiten-mit-dateien-auf-binaerer-ebene.html

IhopeonlyReader - Fr 10.05.13 21:59

simple aufsteigende Zahlenfolge abspeichern... mhh...

mir ging es nur darum:
ich habe es mal geschafft 1000 willkürliche natürliche Zahlen in 1 Funktion zu bringen !
Die Funktion war 3 Grades und die Funktion lieferte die 3 Exponenten der nächsten 3 Funktion ( Wert 1 bis 9 in Funktion einsetzten) und die werte(10-18 waren die Faktoren der entsprechenden zahlen) der wert (19) war der Wert, der dazuaddiert wurde..
nun speicherte ich die Anzahl ab, wieviel neue Funktionen die aktuelle füllt, dazu erstellte ich eine parallelfunktion

Und ich merkte mir wie oft ich das ganze "auspacken" muss...

so musste ich mir insgesamt "nur" 14 zahlen merken, anstatt 1000... soetwas will ich nun programmieren, allerdings finde ich selbst "zusammenhänge" schneller als mein pc :(... bzw. ich weiß nicht wie ich den pc direkt nach einer Funktion für eine Zahlenfolge suchen lassen kann

Mathematiker - Fr 10.05.13 22:17

Hallo,

IhopeonlyReader hat folgendes geschrieben :

... allerdings finde ich selbst "zusammenhänge" schneller als mein pc :(... bzw. ich weiß nicht wie ich den pc direkt nach einer Funktion für eine Zahlenfolge suchen lassen kann

Bis Du mit Diskreter Fourier-Transformation (http://de.wikipedia.org/wiki/Diskrete_Fourier-Transformation) und ähnlichen Verfahren für eine mögliche Zahlenreihe ein Polynom konstruiert hast, sind andere Kompressionsalgorithmen schon lange, lange fertig.

Entschuldige bitte, aber seit 3 Tagen erläuterst Du immer wieder Deine Idee auf's Neue. Fang doch einfach mal an.
Und wenn es dann Probleme gibt, wird Dir sicher hier jemand helfen.

Beste Grüße
Mathematiker

IhopeonlyReader - Fr 10.05.13 22:26

Mathematiker hat folgendes geschrieben :

mir geht es ja nicht um Schnelligkeit, sondern um Minimierung des Speichers und dass sich es auch so wieder "entpacken" kann, dass es genau das selbe ist, was am Anfang verkleinert wurde...

Oder wie wichtig ist dabei die Dauer des Verfahrens?

Etwas weiteres was ich wissen müsste: wie kann ich die Bitfolge einer Datei auslesen?
z.B. einer Exe? sie ist ja mit Bits auf der Festplatte gespeichert, wie komm ich da ran?

Mathematiker - Fr 10.05.13 23:20

IhopeonlyReader hat folgendes geschrieben :

Etwas weiteres was ich wissen müsste: wie kann ich die Bitfolge einer Datei auslesen? z.B. einer Exe? sie ist ja mit Bits auf der Festplatte gespeichert, wie komm ich da ran?

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

var datei : file of byte;
     b : byte;
begin
     ...
     assignfile(datei, 'dateiname.exe');
     reset(datei);
     repeat
        read(datei,b);
        ...
     until eof(datei);
     closefile(datei);
end;

Beste Grüße
Mathematiker

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!