speicher probleme

Ponto

Ich wäre froh wenn unsere Programme nur 1.2 GB verbraten würden. Aber egal.

Kannst du nochmal das Problem genauer erklären? Irgendwie ist mir das zu konfus.

Welcher Graph ist gegeben? Wie sieht der aus? Welche Information ist gegeben? Welche wird berechnet? Was muss abgespeichert werden? Welche Information muss schnell verfügbar sein? usw.

sebastian_v_b

Ponto schrieb:

Kannst du nochmal das Problem genauer erklären? Irgendwie ist mir das zu konfus.

Welcher Graph ist gegeben? Wie sieht der aus? Welche Information ist gegeben? Welche wird berechnet? Was muss abgespeichert werden? Welche Information muss schnell verfügbar sein? usw.

wichtig für mein problem ist folgendes:
ich habe ein listen system....einen vektor mit listen. je nach eigenschaft eines knoten paares wird es in einer der listen eingeordnet.
also kommt jedes knotenpaar in genau einer der listen vor.

der zugriff auf das element wird mittels einer referenzmatrix gehandelt, jedes element der referenzmatrix speichert also einen pointer auf genau sein listenelement....also referenzmatrix[i][j] enthält den pointer auf das knotenpaar (i,j) in der liste in der es eben ist.

die referenzmatrix benötige ich, da ich in O(1) auf ein element zugreifen will und es löschen bzw in eine andere liste packen will.
die listen benötige ich um schnell an alle oder ein element der entsprechenden eigenschaft zu kommen.

problem ist folgendes...egal ob ich das knotenpaar in der liste, oder einen pointer auf ein knotenpaar (typ struct{ short i; short j} )in der liste speichere...für jedes element allokiert mir das programm 32 byte, obwohl das element nur 4byte groß ist.
in der summe führt das zu einem speicherproblem

ich benötige also eine datenstruktur die als container dient, pointer auf seine elemente zulässt, und nur die 4byte allokiert die ich benötige.

jetzt alles ein wenig klarer?

Ponto

Wie wäre es mit einer einfach verketteten Liste für jede dieser Listen und das auch noch im Array gespeichert? Zusätzlich gibt es noch die Listenköpfe:

struct Element {
   int next_element;
   //gewicht und sonstige informationen
}

Element matrix[m][n];
std::vector<int> heads;

Anmerkungen:

1. next_element kann auch ein Zeiger auf das nächste Element sein, aber das würde auf 64bit-Systemen 8 Byte kosten, obwohl deine Zeilen- und Spaltenanzahl in ein short zu passen scheinen.

2. Aus next_element kann die Position mit (next_element % n) und (next_element / n) errechnet werden. Gut ist es das in einer Klasse zu kapseln.

3. Der Speicherverbrauch ist pro Element 4byte + Nutzdaten und du hast noch das heads Array. Macht 4 * m * n + (Anzahl Listen)*4 + sizeof(vector) an Overhead

Man kann auch so eine doppelt verkettete Liste in den Elmenten machen, was den Verbrauch im ersten Term verdoppelt, aber dann auch Einfüge und Löschoperationen einfach macht.

sebastian_v_b

Ponto schrieb:

Wie wäre es mit einer einfach verketteten Liste für jede dieser Listen und das auch noch im Array gespeichert? Zusätzlich gibt es noch die Listenköpfe:
struct Element {
   int next_element;
   //gewicht und sonstige informationen
}

Element matrix[m][n];
std::vector<int> heads;
Anmerkungen:

1. next_element kann auch ein Zeiger auf das nächste Element sein, aber das würde auf 64bit-Systemen 8 Byte kosten, obwohl deine Zeilen- und Spaltenanzahl in ein short zu passen scheinen.

2. Aus next_element kann die Position mit (next_element % n) und (next_element / n) errechnet werden. Gut ist es das in einer Klasse zu kapseln.

3. Der Speicherverbrauch ist pro Element 4byte + Nutzdaten und du hast noch das heads Array. Macht 4 * m * n + (Anzahl Listen)*4 + sizeof(vector) an Overhead

Hallo,

das klingt ja mal nach ner super tollen idee.
nur damit ich es richtig verstanden hab:
du simulierst die listen in einer matrix, indem du für jedes element den index/id seines nachfolgers (ich bräuchte auch noch vorgänger) speicherst und zusätzlich in einem vektor die heads speicherst.

mensch klingt voll super, das bissle overhead könnte man sogar verkraften...is zumindest weniger als die 32byte listen methode.
ich probiers mal aus und berichte dann...danke erstmal!

PS: in welchem bereich darfst du dich mit solchen datenmengen rumschlagen?

Ponto

sebastian_v_b schrieb:

PS: in welchem bereich darfst du dich mit solchen datenmengen rumschlagen?

Tools im VLSI Design.

Wann werden die Listen verändert? Nach einem Zugriff über die Matrix oder nach einer Iteration über die Liste?

xGhost

Ponto schrieb:

Es hängt vom Verhältnis der Kanten zu den Knoten ab, nicht nur von den Knoten.

stimmt, vergas ich zu schreiben.

Ponto schrieb:

Zusätzlich kann man in vielen Anwendungsfeldern zusätzliche Informationen nutzen, um die Graphen effizient zu speichern. Wir arbeiten zum Beispiel mit Graphen, die mehrere Billionen an Knoten haben. Das geht explizit ganz schlecht und erst recht nicht mit einer map.

Naja, mit Billionen knoten mit x kanten geht es nicht.

So ne interessens frage, wie wuerde man es in diesem fall machen?

Gg

Konrad Rudolph

1310-Logik schrieb:

Will ev. Bioinformatik studieren, drum frag ich..

Eine gute Wahl.

xGhost

Ponto schrieb:

Wie wäre es mit einer einfach verketteten Liste für jede dieser Listen und das auch noch im Array gespeichert? Zusätzlich gibt es noch die Listenköpfe:
struct Element {
   int next_element;
   //gewicht und sonstige informationen
}

Element matrix[m][n];
std::vector<int> heads;

Die liste ist ja ned schecht. Aber waehre es nicht so besser implementiert?

#define ANZAHL_KNOTEN 10 

struct Node{

    int next;
    int wert;
    // Eigene Werte

};

std::list<Node> Graph[ANZAHL_KNOTEN];
// Darum kann man auch nicht zu viel speichern damit
// Und ist mehr fuer kleine Grahpen geeignet, dafuer aber schnell

//...

Node *tmp =  new Node;
tmp->next = 2;
Graph[0].push(tmp);

//...

tmp->next = 4;
Graph[2].push(tmp);
// Sind nun verknuepft
//...

Bitte fehler verzeihen, ist mehr pseudo code.

Gg

//Edit//
Mit vector ist das problem, dass das Array dynamisch ist, aber der Graph nicht.
Ein wert loeschen oder verschieben bring dann den Grahpen durcheinander...

Ponto

xGhost schrieb:

Naja, mit Billionen knoten mit x kanten geht es nicht.

So ne interessens frage, wie wuerde man es in diesem fall machen?

Gg

Das geht nur, weil viele Knoten die selben Eigenschaften haben und der Graph ein Gittergraph ist. Da kann man viele Knoten zu Knotenintervallen zusammenfassen.

sebastian_v_b

Hi ihrs,

also Ponto, deine Lösung ist optimal!!!
die listen werden verändert bei jedem matrixzugriff...und zwar auch genau das element auf das ich in der matrix zugreife.
deine idee als objekt gekapselt ist eine optimale und saubere Lösung...danke!!

zu xGhost...dein letzter ansatz funktioniert zwar auch, aber durch das erzeugen der Node objekte mit new hat man wieder genau das gleiche problem, es werden wieder 32byte pro element allokiert.

ich danke nochmal in die runde.
bis zum nächsten problem
Sebastian