speicher probleme

volkard

sebastian_v_b schrieb:

anhand von diesen anforderungen, gibt es eine andere datenstrukur, mit der ich die speicherkörnung umgehen kann?

die standard-antwort ist jetzt, du sollst die nen feinen allocator benutzten und die list mit dem neuen allocator betreiben.

aber ich glaube nicht, daß das extrem klug ist und in sachen einfachheit und performance von lösungen (wenn es sie denn gibt) weggeputzt wird, die nur andere datenstrukturen nehmen.

volkard

sebastian_v_b schrieb:

mit vektoren klappt das nicht gut, weil die iteratoren der vektoren keine wirklichen pointer sind...also hab ich den standard library listen typ genommen.

und wenn du integers nimmst statt vector::iterator?

xGhost

Es gibt ne fausregel fuer Grafen:

Knoten | Art
1-5000 = A.Matrixen
1-20000 = Eine verkettete liste. (List<struct>[])
1-10000000 und mehr = map

Bei sehr vielen Knoten im graphen muss man eine map nehmen.
alles andere ist mord.

map<string, map<string, int> > Graph;
Graph["Bern"]["Zurie"] = 10; // Km oder kosten, ect

Nun kann man ihn mit einem algorithm durchlaufen.

// Edit //
Was fuer einen Algo brauchst du?
Ich kann dir vl. helfen.

Ponto

xGhost schrieb:

Es gibt ne fausregel fuer Grafen:

Knoten | Art
1-5000 = A.Matrixen
1-20000 = Eine verkettete liste. (List<struct>[])
1-10000000 und mehr = map

Bei sehr vielen Knoten im graphen muss man eine map nehmen.
alles andere ist mord.
map<string, map<string, int> > Graph;
Graph["Bern"]["Zurie"] = 10; // Km oder kosten, ect
Nun kann man ihn mit einem algorithm durchlaufen.

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

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.

sebastian_v_b

Hallo an alle,

danke erstmal für die vielen Antworten.
zu 1.)

volkard schrieb:

die standard-antwort ist jetzt, du sollst die nen feinen allocator benutzten und die list mit dem neuen allocator betreiben.

was meinst du mit einem feinen allocator? könntest du ein kleines code beispiel bringen, damit ich weiß was du meinst!?

zu 2.)

volkard schrieb:

sebastian_v_b schrieb:

mit vektoren klappt das nicht gut, weil die iteratoren der vektoren keine wirklichen pointer sind...also hab ich den standard library listen typ genommen.

und wenn du integers nimmst statt vector::iterator?

wäre das gleiche problem. ich würde zwar in O(1) auf ein element in der liste zugreifen können, müsste danach aber in meinem referenzen array alle nachfolgenden indizes aktualisieren. deswegen benötige ich echte pointer

zu 3.)
eine map benutzen....mmhh, benutze ich aus dem grunde nicht, weil ich dachte die zugriffszeit pro element wäre dann worst-case O(n)...was bei einer großen knotenanzahl nicht so gut wäre.

der graph selber ist vielleicht in meiner anwendung sehr lichte, aber da ich überall gewichte speichern muss, benötige ich im endeffekt eh eine volle ausgefüllte matrix.
allerdings ist die gewichtungs und adjazenzmatrix eh nicht das problem. wie angesprochen ist es die liste der knotenpaare.

für die jenigen die es interessiert: ich bastle einen algorithmus in der bioinformatik. der algorithmus wird auch parametrisierter algorithmus genannt und besticht dadurch, dass er probleme die sonst NP-vollständig wären vielleicht in P lösen kann.
um die effizienz des algorithmus hoch zu halten, muss auch der zugriff auf die datenstrukturen schnell sein. aus diesem grunde speichere ich in einem array pointer auf die listenelemente.
im moment arbeite ich bloß an der kleinen version des algorithmus....spricht er wird vermutlich nur wenige stunden dauern...die erweiterung vermutlich mehrere tage...dann werd ich euch wieder ausfragen

danke euch nochmal,
Sebastian

THX 1138

sebastian_v_b schrieb:

für die jenigen die es interessiert: ich bastle einen algorithmus in der bioinformatik. der algorithmus wird auch parametrisierter algorithmus genannt und besticht dadurch, dass er probleme die sonst NP-vollständig wären vielleicht in P lösen kann.
um die effizienz des algorithmus hoch zu halten, muss auch der zugriff auf die datenstrukturen schnell sein. aus diesem grunde speichere ich in einem array pointer auf die listenelemente.
im moment arbeite ich bloß an der kleinen version des algorithmus....spricht er wird vermutlich nur wenige stunden dauern...die erweiterung vermutlich mehrere tage...dann werd ich euch wieder ausfragen

danke euch nochmal,
Sebastian

Tönt interessant. Was berechnest Du mit dem Algo? Was wird es für eine Anwendung?
Will ev. Bioinformatik studieren, drum frag ich..

sebastian_v_b

der algorithmus modeliert gen-verwandschaften. jeder knoten repräsentiert ein gen einer spezies. kanten sind verwandschaften. wenn die biologie perfekt wäre würden bei 3 organismen immer 3-er cliquen entstehen ( ein vollständiger graph, sprich jede kante ist gezogen)...das heißt in jedem organismus gibt es das gleiche gen noch einmal. da dies aber nicht so ist, suche ich jetzt die minimale anzahl von operationen (einfügen/löschen) um immer n-große cliquen zu erzeugen.

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