Archiv verlassen und diese Seite im Standarddesign anzeigen : Container mit variabler Kapazität
Hallo zusammen,
Folgendes Problem:
Ich benutze in einem Programm (Programmiersprache ist C, aber im Prinzip ist das sprachenunabhängig) Container variabler Größe. Um nicht jedes Mal, wenn ein neues Element in einen Container eingefügt wird, neuen Speicher allokieren zu müssen, wird jeder Container standardmäßig mit einer bestimmten Kapazität erstellt, die bei Bedarf vergrößert wird.
Jetzt stellt sich die Frage, in welchen Schritten die Kapazität am besten erhöht werden sollte. Bisher ist das so umgesetzt, dass die Kapazität linear erhöht wird, d.h. sie beträgt initial z.B. N Elemente, und wird dann immer um N Elemente vergrößert. Eventuell ist daran jedoch nachteilig, dass wenn man N zu klein wählt, in Fällen wo viele Elemente eingefügt werden, die Kapazität entsprechend oft angehoben werden und dazu eine Speicherallokation durchgeführt werden muss, was auf die Performance drückt. Wählt man umgekehrt N zu groß, so fallen zwar weniger Speicherallokationen an, dafür wird in Fällen, in denen in einen Container nur sehr wenige Elemente eingefügt werden, Speicher verschwendet wird, weil die Kapazität nur zu einem kleinen Teil ausgenutzt wird.
Eine andere Möglichkeit wäre, die Kapazität nicht linear zu erhöhen, sondern jeweils um einen bestimmten Faktor, also z.B. initial eine Kapazität von N bereitzustellen und diese dann immer um den Faktor 2 zu erhöhen, also in den Schritten
N -> 2N -> 4N -> 8N -> ...
Gibt es da allgemeingültige Erfahrungswerte, welche Methode am effizientesten ist, d.h. den besten Kompromiss zwischen Speicherverbrauch und Performance darstellt? Vielleicht eine Kombination beider Methoden oder noch eine ganz andere?
Danke euch.
Normalerweise wählt man den multiplikativen Ansatz, das ist auch nötig um in durchschnittlicher Zeit O(1) für das Hinzufügen von Elementen am Ende zu haben.
Also ich würde es so machen:
wenn 80% des Speichers voll ist verdoppel den Speicher(bis zu einem Maximum).
wenn nur 20% des Speichers belegt ist halbiere ihn wieder(bis zu einem Minimum).
Monger
2012-07-19, 18:55:08
Ich glaube, der relativ weit akzeptierte Daumenwert ist: sobald Count = Capacity, dann Capacity verdoppeln. Verkleinert wird grundsätzlich nur, wenn der Speicherplatz voll wird. Zumindest bei den managed Sprachen (afaik mindestens .NET , Java) macht man das wohl so
wenn 80% des Speichers voll ist verdoppel den Speicher(bis zu einem Maximum).
Was sollen die 80% gegenüber 100% für einen Nutzen haben?
Ich glaube, der relativ weit akzeptierte Daumenwert ist: sobald Count = Capacity, dann Capacity verdoppeln. Verkleinert wird grundsätzlich nur, wenn der Speicherplatz voll wird. Zumindest bei den managed Sprachen (afaik mindestens .NET , Java) macht man das wohl so
C++ std::vector gibt den Speicher nichtmal bei .clear() oder .resize(0) frei. Man muss den Container komplett löschen, oder .swap() mit einem leeren aufrufen.
PatkIllA
2012-07-19, 19:59:19
C++ std::vector gibt den Speicher nichtmal bei .clear() ... frei. Macht System.Collections.Generic.List<T>.Clear() genauso. Capacity { set; } macht aber das was man erwartet.
Das ganze Topic klingt eh so als ob jemand meint mit eigener Implementierung die Standardklassen schlagen zu können, was eher selten der Fall ist.
der vorteil bei 80% den Speicher zu verdoppeln ist mehr theoretischer natur. Es soll verhindern das das Speicherlimit eventuellen überschritten wird.
der vorteil bei 80% den Speicher zu verdoppeln ist mehr theoretischer natur. Es soll verhindern das das Speicherlimit eventuellen überschritten wird.
Wenn man über die Größe hinausschreibt ist das ein Programmfehler.
Das ist nicht theoretischer Natur, das ist praktischer Pfusch.
Hat schon Gründe warum dynamische Listen (Hasmaps etc) nach diesem diesem Prinzip Speicher verwalten wenn ich mich recht entsinne (Lass mich aber gerne eines besseren belehren).
Ist wie im wahren Leben, da tankst du dein Auto nicht erst wenn es leer ist, sondern dann wenn es fast leer ist.
PatkIllA
2012-07-19, 21:18:10
Hat schon Gründe warum dynamische Listen (Hasmaps etc) nach diesem diesem Prinzip Speicher verwalten wenn ich mich recht entsinne (Lass mich aber gerne eines besseren belehren).
Hast du da Quellen für? Mir fällt auch kein Grund warum das vorher machen sollte.
Ist wie im wahren Leben, da tankst du dein Auto nicht erst wenn es leer ist, sondern dann wenn es fast leer ist.Wenn mein Auto beim Benzin anfordern direkt was nachkippen könnte würde ich das auch ganz leer fahren
Hat schon Gründe warum dynamische Listen (Hasmaps etc) nach diesem diesem Prinzip Speicher verwalten wenn ich mich recht entsinne (Lass mich aber gerne eines besseren belehren).
Eine Hashmap ist kein dynamisches Array. Dort hat man statistisch völlig andere Anforderungen. Das die Verteilung perfekt auf die einzelnen Buckets ist, ist sehr gering, deshalb wählt man eher eine etwas mehr Platz.
std::vector realloziert exakt dann, wenn der Speicher nicht mehr reicht in allen mir bekannten Implementierungen.
Kann dir leider keine Quellen mehr geben, habe meine ganzen Paper nach dem Studium entfernt(auch schon ein bissel her).
Auto beispiele passen halt nicht immer hunderprozentig :-P.
Die Überlegung dahinter ist auch mehr foglende:
schreibe rein und der Speicher überschreitet 80% (fertig mit schreiben)
nichts zu tun nutzte die möglichkeit speicher zu reservieren.
anstelle von
probiere zu schreiben, merke Speicher überschreite die Kapazität mache schreiben rückgängig, reserviere zusätzlichen speicher und schreibe erneut.
Eine Hashmap ist kein dynamisches Array. Dort hat man statistisch völlig andere Anforderungen. Das die Verteilung perfekt auf die einzelnen Buckets ist, ist sehr gering, deshalb wählt man eher eine etwas mehr Platz.
std::vector realloziert exakt dann, wenn der Speicher nicht mehr reicht in allen mir bekannten Implementierungen.
Ah ok dann habe ich da eventuell was durcheinander gebracht. Lange her das ganze.
Nur als Hinweis. Bei std::vector hat man noch die Möglichkeit, die Anfangskapazität festzulegen.
Threadersteller
2012-07-20, 09:36:57
Das ganze Topic klingt eh so als ob jemand meint mit eigener Implementierung die Standardklassen schlagen zu können, was eher selten der Fall ist.in C gibt es keine Standardklassen (in Ermangelung von Klassen als solchen), die man schlagen wollen könnte.
Sicherlich wird es im Netz fertige Implementierungen für solche Container auch für C geben, jedoch gibt es da noch eine weitere Anforderung, nämlich dass die Elemente im Container sortiert sein sollen und über einen Schlüssel auffindbar sein sollen. Üblicherweise nimmt man dazu eine Hash-Map, die aber wird in dem Programm nicht verwendet, da sie - so der Projektleiter - einen zu hohen Speicherverbrauch hätte.
Ectoplasma
2012-07-20, 11:00:15
Üblicherweise nimmt man dazu eine Hash-Map, die aber wird in dem Programm nicht verwendet, da sie - so der Projektleiter - einen zu hohen Speicherverbrauch hätte.
Öhm, was habt ihr vor? So dicke ist der Verbrauch doch gar nicht. Ansonsten schau dier mal die Implementierung von std::map an. Die ist meistens als Tree implementiert.
Nicht meistens, sondern immer, weil std::map sortiert sein muss. std::unordered_map ist eine hash map.
GloomY
2012-07-24, 23:47:20
Mir fällt als Datenstruktur nur ein B-Baum ein, der die Eigenschaft hat, dass man ihn eventuell vergrößern muss, auch wenn er noch nicht komplett gefüllt ist. Nämlich dann wenn im zum Schlüssel zugehörigen Knoten kein Platz mehr ist und man den Knoten aufteilen muss.
Im schlimmsten Fall ist ein B-Baum nur zur Hälfte gefüllt.
Threadersteller
2012-07-26, 10:17:16
Hallo,
Es hat sich nunmehr im positiven Sinne erledigt, und zwar dadurch, dass ich von der Debug- auf die Release-Version umgeschaltet habe. Dadurch wurde das Programm um knapp den Faktor 10 schneller, und das weitgehend unabhängig von der Größe N der Schritte, in denen die Kapazität erhöht wird :)
Ectoplasma
2012-07-30, 11:14:19
Hallo,
Es hat sich nunmehr im positiven Sinne erledigt, und zwar dadurch, dass ich von der Debug- auf die Release-Version umgeschaltet habe. Dadurch wurde das Programm um knapp den Faktor 10 schneller, und das weitgehend unabhängig von der Größe N der Schritte, in denen die Kapazität erhöht wird :)
Manchmal frage ich mich, ob man hier verschaukelt werden soll, ich einfach nur auf dem falschen Planeten lebe, oder irgendwo ein Riss in der Matrix ist. Da kommst du jetzt mit einer Lösung, die jeder noch so grüne Anfänger als erstes wissen sollte. Sorry ne, aber irgendwie ist das hier verkehrte Welt.
Exxtreme
2012-07-30, 11:50:59
Manchmal frage ich mich, ob man hier verschaukelt werden soll, ich einfach nur auf dem falschen Planeten lebe, oder irgendwo ein Riss in der Matrix ist. Da kommst du jetzt mit einer Lösung, die jeder noch so grüne Anfänger als erstes wissen sollte. Sorry ne, aber irgendwie ist das hier verkehrte Welt.
Tja, das ist wohl der Grund warum fast alle Software-Klitschen Entwickler mit 10 Jahren Berufserfahrung suchen. ;)
Manchmal frage ich mich, ob man hier verschaukelt werden soll, ich einfach nur auf dem falschen Planeten lebe, oder irgendwo ein Riss in der Matrix ist. Da kommst du jetzt mit einer Lösung, die jeder noch so grüne Anfänger als erstes wissen sollte. Sorry ne, aber irgendwie ist das hier verkehrte Welt.
Zwei Dinge:
Wenn in der Debug-Version ein großer Geschwindigkeitsunterschied zwischen zwei Varianten (große und kleine Schrittweite) festzustellen ist, dann liegt es erstmal nahe, davon auszugehen, dass auch in der Release-Version ein vergleichbarer Geschwindigkeitsunterschied auftreten wird, wenngleich die Geschwindigkeit jeder Variante über der ihres Debug-Pendants liegen wird.
Der Projektleiter, dem ich meine Überlegungen betreffend des Ausprobierens der Release-Version ja mitgeteilt hatte, war der Ansicht, dass eine Umstellung auf die Release-Version keinen nennenswerten Performance-Vorteil bringen würde, besonders im Hinblick darauf, dass die meiste Zeit durch mallocs und memmoves verbraten wird, die seiner Ansicht nach in der Debug-Version nicht langsamer sein würden als in der Release-Version (was sich dann aber wohl als unzutreffend erwiesen hat).
Ectoplasma
2012-07-30, 16:23:33
Zwei Dinge:
Der Projektleiter, ...
Kann man ja noch verstehen, wenn der Projektleiter einem das sagt. Ich wollte aber schon weiter oben fragen, was das für ein Projektleiter ist? Wieviele Jahre Berufserfahrung hat der denn? Wenn der vorher nur Java gemacht hat, dann täte mich das nicht wundern.
Ich hatte mich bereits bei diesem Statement ein wenig gewundert.
Üblicherweise nimmt man dazu eine Hash-Map, die aber wird in dem Programm nicht verwendet, da sie - so der Projektleiter - einen zu hohen Speicherverbrauch hätte.
Malloc und free machen in der Debug-Version so einiges mehr, als in der Release-Version. Der Debug-Code unterscheidet sich im gesamten Projekt schon massiv von der Release-Version. Das ist auch der Grund warum man eine Release-Version auch ab und an testen sollte. Das hat nicht nur was mit der Performance zu tun, sondern auch mit der überprüfung der Funktionalität. Das Ganze hätte jemanden doch schon längst auffallen müssen.
Wenn in der Debug-Version ein großer Geschwindigkeitsunterschied zwischen zwei Varianten (große und kleine Schrittweite) festzustellen ist, dann liegt es erstmal nahe, davon auszugehen, dass auch in der Release-Version ein vergleichbarer Geschwindigkeitsunterschied auftreten wird, wenngleich die Geschwindigkeit jeder Variante über der ihres Debug-Pendants liegen wird.
Falsche Annahme. Da habe ich schon etliche Gegenbeispiele gesehen. Erst die Woche habe ich nochmal erlebt, dass ein Codeabschnitt im Debug 90% der Rechenleistung verbraten hat und im Release Mode in der Messungenauigkeit unterging. Reagiert ein solcher Codeabschnitt stark auf deinen Parameter ist jede Vorhersage für die Katz.
Die zwei Grundregeln für Performanceoptimierungen:
- Mache keine Vorhersagen wo, wann, warum Rechenzeit verloren geht.
- Der Profiler hat immer recht.
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.