Ich habe eine Frage zur dynamischen Speicherzuweisung.
Kontext: Ich schreibe ein Programm, das eine Textdatei von Wörtern liest und die Häufigkeit zählt, mit der jedes Wort auftritt (ein Wort pro Zeile).
Diese spezielle Funktion liest die Datei, zählt die Zeilen und Zeichen und weist dann dynamisch dem Array von String-Zeigern Speicher zu, einem Array, das die Anzahl der Zeichen für jede Zeile und die Zeichenfolgen selbst speichert. (Die anderen Teile sind weniger direkt relevant für meine Frage).
Frage: Wie oft sollte ich Speicher neu zuweisen, wenn der Speicherplatz knapp wird? Ich habe eine Konstante ("Memstart") gesetzt, um den anfänglichen Speicherzuweisungswert einzustellen. Im folgenden Codefragment realloc für jede Zeile über den Wert von "Memstart". Würde das Programm schneller verarbeiten, wenn ein größerer Speicherblock neu zugewiesen würde, anstatt den Speicherbereich jedes Mal um 1 "variablen Typ" zu erhöhen?
Was wäre die beste Vorgehensweise für so etwas?
Code Snip:
%Vor% Während die Frage ist, wie oft realloc aufgerufen werden sollte, wenn man sich den Code von OP ansieht, denke ich, dass es besser ist, mit sicher zu beginnen.
Die C11-Standardzustände (n1570-Entwurf, § 7.22.3.5 , Die realloc-Funktion , Hervorhebung von mir):
Übersicht
#include <stdlib.h>
void *realloc(void *ptr, size_t size);Beschreibung
Die Realloc-Funktion gibt das alte Objekt, auf das ptr verweist, frei und gibt einen Zeiger auf ein neues Objekt mit der durch die Größe angegebenen Größe zurück. Der Inhalt des neuen Objekts muss mit dem des alten Objekts übereinstimmen vor der Freigabe, bis zu den kleineren der neuen und alten Größen. Alle Bytes im neuen Objekt jenseits der Größe des alten Objekts haben unbestimmte Werte.
Wenn ptr ein Nullzeiger ist, verhält sich die realloc-Funktion wie die malloc-Funktion für die angegebene Größe. (...). Wenn Speicher für das neue Objekt nicht zugewiesen werden kann, wird das alte Objekt nicht freigegeben und sein Wert ist unverändert .
Gibt
zurück Die realloc-Funktion gibt einen Zeiger auf das neue Objekt zurück (der den gleichen Wert wie ein Zeiger auf das alte Objekt haben kann), oder einen Nullzeiger, wenn das neue Objekt nicht zugeordnet werden konnte .
Betrachten wir nun dieses Snippet aus der Frage, in der sz als int* sz;
Der Rückgabewert ist verloren, so dass wir nicht wissen können, ob der Aufruf erfolgreich war und wenn dies der Fall ist, wird sz ungültig gemacht. Darüber hinaus ist sizeof(sz) die Größe des Zeigers, nicht des spitzen Typs ( int ).
Ein sichereres (und korrekteres) Muster wäre:
%Vor% Nun, um die Frage zu beantworten, sollte realloc nur aufgerufen werden, wenn es benötigt wird, weil es potenziell umfangreiche Systemaufrufe beinhaltet. Also entweder ein großes Stück voraus oder wählen Sie eine wachsende Strategie wie Verdoppelung (oder 1,5-fache) die Größe jedes Mal.
Es ist erwähnenswert, dass das Betriebssystem die Neuzuweisung durchführen könnte, ohne ein Element des ursprünglichen Arrays zu kopieren.
Die klassische Antwort ist, jedes Mal zu verdoppeln, aber ein Faktor von 1,5 könnte besser sein . Das wichtigste ist, dass Sie Ihre Array-Größe jedes Mal um ein Vielfaches multiplizieren > anstatt zusätzlichen zusätzlichen Speicherplatz jedes Mal hinzuzufügen.
Bei jeder Neuzuweisung muss möglicherweise das vorherige Array in ein neues Array kopiert werden. Wir möchten diese Kopien minimieren. Wenn wir n -Elemente hinzufügen, beginnen wir mit einem Array der Größe a , erhöhen sie um einen Faktor von r jede Neuzuweisung, um mit einem Wert von n zu enden, die Folge von (re -) Zuweisungen werden a, ar, ar ^ 2, ar ^ 3, ..., n. Die Summe dieser Sequenz ist (nr-a) / (r-1). Somit ist der Gesamtraum von der Ordnung O (n).
Nehmen wir an, wir beginnen stattdessen mit a und fügen jedes Mal r hinzu. Die Sequenz ist a, a + r, a + 2r, a + 3r, ..., n. Die Summe dieser Sequenz ist 0,5 * ((n ^ 2-a ^ 2) / r + a + n). In diesem Fall der gesamte Raum der Ordnung O (n ^ 2). Viel schlimmer!
Bei einem konstanten Faktor von 2 ist das Array im schlechtesten Fall 1/2 leer. Das ist wahrscheinlich in Ordnung. Sie können die Zuordnung immer verkleinern, wenn Sie fertig sind und die endgültige Größe kennen.
Wie in einer anderen Antwort erwähnt, gibt es einige Fehler in der Art, wie Sie realloc() aufrufen, aber das war nicht die Frage.
Tags und Links c realloc dynamic-memory-allocation