[Networkit] Graph.shrinkToFit()

Henning Meyerhenke meyerhenke at kit.edu
Mon May 12 20:10:17 CEST 2014


It should be kept in mind that applying shrink_to_fit makes only sense 
in static scenarios. When the graph changes over time, the overhead of 
space reduction is likely to be dominant. But for static cases I agree 
that Marvin's suggestion can be beneficial.


Am 12.05.14 19:53, schrieb Christian Staudt:
> Hi Marvin,
> let’s switch to english for discussions on the list. You suggested that
> the graph data structure currently wastes a lot of memory, and that the
> std::vectors could be resized with std::vector::shrink_to_fit to free
> memory.
> I agree with your observation. I believe in the worst case the graph
> takes almost twice as much memory as needed. I was not aware of the
> shrink_to_fit method. So this could be an important improvement. I say
> „could“ because there is one thing that needs to be checked, namely
> whether shrinking significantly increases construction time. If it does
> we need to see if we want to make the tradeoff.
> You wouldn’t by any chance be interested in implementing the necessary
> changes to the graph?
> Best regards
> Chris
> Am 12.05.2014 um 18:43 schrieb Marvin Ritter
> <marvin.ritter at student.kit.edu <mailto:marvin.ritter at student.kit.edu>>:
>> Hallo,
>> die Graph Klasse nutzt viele dynamische Arrays, welche unter Umständen
>> deutlich mehr Speicherplatz allokieren and letztendlich wirklich
>> gebraucht wird.
>> Da viele Algorithmen nach dem Einlesen/Generieren eines Graphen diesen
>> nicht mehr verändern (soweit mir bekannt ist), könnte man diesen
>> problemlos wieder freigeben.
>> std::vector verfügt seit C++11 über die Methode shrink_to_fit() die
>> genau das bewerkstelligt, sodass das ganze nur ein paar Zeilen in der
>> Graph Klassen wären.
>> Viele Grüße
>> <ATT00001.c>


Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics (ITI)

Juniorprof. Dr. Henning Meyerhenke
Theoret. Informatics / Parallel Computing

Phone: +49-721-608-41876
Web: http://parco.iti.kit.edu/henningm/

KIT - University of the State of Baden-Wuerttemberg and
National Research Center of the Helmholtz Association

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 5141 bytes
Desc: S/MIME Cryptographic Signature
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140512/7b17d785/attachment.p7s>

More information about the NetworKit mailing list