dynamische Handhabung von Feldern (nicht die übliche Frage)

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.