dynamische Handhabung von Feldern (nicht die übliche Frage)

daishi

Hi,
ich habe folgendes Problem mit meiner Datenstruktur:
1. muß dynamisch gehalten werden
2. muß notfalls auslagerbar sein
3. darf einen PIII 500 nich überlasten

Zu 1.:
die Struktur ist wiefolgt implementiert,

int ***feld,i,j,k;
int x,y,z;
...
feld=(int***)malloc(x*sizeof(int));
for(i=0;i<x;i++)
{
  feld=(int**)malloc(y*sizeof(int));
  for(j=0;j<y;j++)
  {
    feld[i][j]=(int*)malloc(z*sizeof(int));
    for(k=0;k<z;k++)
    {
      feld[i][j][k]=....
    }
  }
}
// Größe kann jeder Zeit mit realloc verändert werden

es ist mir klar, daß es sich hierbei um C und nicht um C++ handelt. Ich würde diese Struktur nun gerne nach C++ portieren, aber die die Möglichkeit der Größenveränderung via [i]realloc* nicht verlieren oder umständlich neu zu gestalten.

Zu 2.:
Das Problem mit der Auslagerbarkeit, habe ich mit fprintf gelöst, was sicherlich auch nicht der eleganteste Weg ist, falls es was besseres gibt, wäre ich für Anregungen dankbar.

Zu 3.:
Tja, das System ist auch so ein Problem, wie schon erwähnt handelt es sich um einen PIII 500 mit 256MB und an diesem System lässt sich erstmal nichts ändern.

1ntrud0r

gibt doch genügend dynamische stl container mit resize member funktion ...

daishi

1ntrud0r schrieb:

gibt doch genügend dynamische stl container mit resize member funktion ...

Die habe ich schon versucht, sind aber deutlich langsamer als die bisherige Umsetzung.

Walli

Igitt, und nehm bitte new für die Speicheranforderung. malloc ist KEIN C++ und dessen Rückgabewert sollte man NIEMALS casten. Ich kann mir nicht vorstellen, dass das schneller als eine std::deque sein soll.

Walli

Und was soll bitte auslagerbar sein? Hat dein System keinen virtuellen Speicher??? Wenn du mit auslagerbar meinst in eine Datei schreiben dann würde ich dir ein binäres Format ans Herz legen und nicht deine Lösung mit printf. Gutgemeinter Rat: Gucke die fstream und deque an, das scheint genau das zu sein was du brauchst.

Achso, und wenn du soetwas schon unbedingt machen willst um dir den Code zu versauen dann bitte so, auch wenn auf vielen Platformen sizeof(int) gleich sizeof(int***) ist :

feld=(int***)malloc(x*sizeof(int**)); // EDIT: bei dem int** war ein Sternchen zuviel

RHBaum

Die habe ich schon versucht, sind aber deutlich langsamer als die bisherige Umsetzung

Analysier dein Programm mal dahingehend, was genau du machst und wo deine Zeit verbraten wird .... dann ueberdenk noch mal, welchen container du nimmst.
Wenn du 324753 mal pro sekunde Daten hinzufuegst, ist das was anderes als wenn du 324753 mal per index drauf zugreifen willst.

Dynamische groessenAnpassung beim Vector ist z.B. suendhaft teuer, wenn man ned gescheit beim erzeugen die Groesse festlegt !
Brauchst du ueberhaupt den Index ? ... etc ....

Schreib mal genauer, was du gemacht hast, dann koennen wir dir vielleicht auch helfen !

Ciao ...

daishi

Aslo gut, ich habe die Daten im *.asc Format auf dem Rechner (txt-Datei mit 3 Zahlen pro Zeile <%f\t%f\t%f\n>).
Diese Datei wird in zwei Schritten in den Speicher gelesen, beim ersten Schritt bestimme ich die Feldgröße und initialisiere dann das Feld. Im zweiten Schritt lese ich dann die Werte aus und schreibe sie direkt in das erstellte Feld. Damit umgehe ich die realloc Falle, die sonst zur Instabilität führen kann.

Das so erzeugte Feld, wird dann mittels ICP (iterative closest point) auf einen zweiten Datensatz gematched und modifiziert. Dabei halten sich die Schreib-/Lesezugriffe im Mittel die Wage.

Ich habe diese Datenstruktur nur verwendet, da sie im bisherigen Programm schon implementiert war und ich nicht das ganze Programm neuschreiben wollte, da es schon über 6000 Zeilen hatte und einige gute Funktionen besitzt.

PAD

Das rauschreiben würde ich auf jeden fall mit fwrite machen.
Folgende Aufbau

//- Schreiben der 3 indices  
fwrite(x,sizeof(int),1,ofp);
fwrite(y,sizeof(int),1,ofp);
fwrite(z,sizeof(int),1,ofp);

//- schreiben der Zahlen

for
 for
  for
  fwrite(feld[i][j][k],sizeof(float),1,ofp);

//- Lese der 3 indices  
fread(&x,sizeof(int),1,ofp);
fread(&y,sizeof(int),1,ofp);
fread(&z,sizeof(int),1,ofp);

//- lesen der Zahlen

for
 for
  for
  fread(feld[i][j][k],sizeof(float),1,ofp);

Das dürfte schneller sein, weniger Platz verbrauchen und bei floats keine Genauigkeitsverluste erzeugen.

Übrigens ist da eine Diskrepanz du allocierst int´s und speicherts floats im fprintf,

daishi

Ja, die Diskrepanz zwischen int und float ist mir auch aufgefallen, in meinem programm habe ich es aber richtig gemacht.

daishi

MaSTaH schrieb:

feld=(int***)malloc(x*sizeof(int***));

In diesem Zusammenhang, kann es sein, daß sizeof(int)* einen anderen Wert als sizeof(int)** liefert?

Walli

Nein, guck mal genau hin. Es ist nicht garantiert, dass int dieselbe Größe hat wie int*** . Ist zwar auf vielen Plattformen so aber dennoch keine Selbstverständlichkeit.
Edit: Bei mir war rechts in der Zeile von der Logik her ein Sternchen zuviel, ändert aber nichts am Ergebnis, weil du ja ein Feld von Pointern anforderst im ersten und zweiten Schritt und dann erst ein Feld von Integern.

int*** zeigt auf ein int**-Feld
int** zeigt auf ein int*-Feld
int* zeigt auf ein int-Feld

Merkst du worauf ich hinaus will? In den ersten beiden Schritten ist es nicht mehr nur ein logischer Fehler sondern kann dich den Kopf kosten wenn sizeof(int*) größer als sizeof(int) sein sollte. Dann hast du zuwenig Speicher angefordert und läufst Gefahr eine Access-violation zu verursachen.

peterchen

...es ist nicht mal garantiert das Zeiger auf unterschiedliche typen die gleiche Größe haben (und es gibt minddestens eine Platform, auf der sizeof(char tatsächlich größer ist als sizeof(int *))

realloc hat gegenüber new nur selten Performance-Vorteile - nämlich wenn man die Größe immer inkrementell um ein Element ändert, und/oder keine anderen Allokationen durchführt. In dem Fall sollte man sowieso in größeren Blöcken allozieren.

Allerdings würd' ich malloc auch nicht verteufeln - new ruft's schließlich auch bloß auf

Abspeichern:

Binärdaten ist schneller, textformat ist protabler. Wie groß werden denn deine Arrays?

Und - washast du mit denem vor, was dauert so lang etc?

daishi

@peterchen
Bei der Veränderung der Feldgröße, gehe ich immer so vor, daß ich die Größe verdoppele, wenn ich die Grenze erreicht habe und nach der Berechnung wird es die tatsächliche Größe gesetzt um Platz zusparen. Die Sache mit der Vergrößerung immer nur um ein Element, ist mir in diesem Fall etwas zu Aufwendig (auch rechentechnisch).

Wegen des Abspeicherns, die momentane Testdatei hat ein Göße von ~900k (28500 Punkte) es können aber auch bis 10^40 Punkte werden. Die Ausgabe in eine Textdatei habe ich nur gewählt, da die Eingabedatei auch im Textformat vorliegt, und sich so ein externes vergleichen der beiden Dateien einfacher abwickeln lässt.

Im Moment geht die meiste Rechenzeit beim vergleichen von zwei Datensätzen drauf, da ich jeden Punkt aus dem einen Satz mit allen aus den anderen vergleichen muß. Zu diesem Zweck habe ich mir schon Teilfelder generiert, auf denen ich die Operationen ausführe, um so die Anzahl der Punkte zu verkleinern.
Mir geht es jetzt darum, wie ich evtl. die Datenstruktur noch effizienter machen kann, um bei Zugriffen auf diese nicht zuviel Zeit zu investieren, da die Berechnung nicht weiter optimiert werden kann.

Jester

Also einen schnelleren Zugriff als per Index wirste kaum hinkriegen. Obwohl es sein könnte, daß es günstiger ist das ganze als 1D-Array abzulegen und die Indexber. Mit index = x+width*(y+z*height) zu berechnen, weil das der Prozessor in wenigen Takten schafft. Für die Zeiger muß er möglicherweise auf den Speicher zugreifen und das könnte Zeit dauern.

Und Du mußt jeden Punkt mit jedem anderen Vergleichen?
Dann überleg Dir doch ne Ordnungsrelation, sortiere beide und Vergleiche jeweils nur die ersten beiden. Den größeren wirfste weg und vergleichst die nächsten beiden...
MfG Jester

daishi

@Jester
Das Vergleichen der Punkte geschieht nach dem ICP-Algorithmus.
http://www.informatik.uni-freiburg.de/~burgard/postscripts/haehnel-robotik2002.pdf
Unter diesem Link findest Du eine einfache und kurze Erklärung des Verfahrens,
daran kann ich erstmal nichts ändern. In einem Buch habe ich schon eine Möglichkeit gefunden wie sich das Verfahren ändern läßt um die Geschwindigkeit zu erhöhen, mir fehlt nur im Moment etwas die Zeit es mal zu implementieren.

Walli

peterchen schrieb:

...es ist nicht mal garantiert das Zeiger auf unterschiedliche typen die gleiche Größe haben (und es gibt minddestens eine Platform, auf der sizeof(char tatsächlich größer ist als sizeof(int *))

Echt, welche denn?

peterchen

Wenn du am Algo nichts mehr machen kannst (hab ich mir aber nicht angeguckt...)

a) Die Daten sollten in der Reihenfolge im Speciehr liegen, wie sie in der innersten Schleife hintereinander abgearbeitet werden.

b) Wenn du float-Rechenoperationen durchführst, solltest du die Daten auch als float im Speicher abgelegt haben, und die Konvertierung nicht erst in der innersten Schleife durchführen

c) zumindest in der innersten Schleife solltest du die dreifache indizierung "manuell" in Zeiger-Increments umwandeln, also z.B. statt

for(...)
  for(int y1=0..xn-1)
    for(int z2=0..yn-1)
      x = calc(feld[x][y1][z] + feld[x][y][z2])

solltest du

for(...)
{
  float * y1ptr   = &(feld[x][0][z]);
  float * y1end   = &(feld[x][yn][z]);
  int     y1Inc   = &(feld[0][1][0]) - &(feld[0][0][0]);
  for(; y1ptr < y1end; y1ptr += y1Inc)
  {
    float * z2ptr   = &(feld[x][y][0]);
    float * z2end   = &(feld[x][y][zn]);
    int     z2Inc   = &(feld[0][0][1]) - &(feld[0][0][0]);
    for(; z2ptr < z2end; z2ptr += z2inc)
    { 
      x = *y1ptr + *z2ptr; 
    }
  }
}

verwenden (wie schon gesagt: in der innersten Schleife sollte wenigstens ein index inkrementell laufen - und natürlich möglichst lang sein)

Kommt halt ein bi0chen auf deinen Algorithmus an, wieviel Freiheiten du hast...

peterchen

@Mastah: Keine Ahnung, irgend ein alter Mainframe glaub ich.

Mit einem "int" großen zeiger konnte man nur auf ganzen Adressen liegende ints adressieren. wenn man an ein einzelnes "Sub-Byte" ranwollte, brauchte man noch ein paar bits extra. Eigentlich clever.