C++ Konzeptfrage zur Speicherung nach Indexnummern

[T_55]

Hallo,

mal eine Konzeptfrage zu einer Überlegung:

In eine Dauerschleife sollen je nach Durchlaufsnummer (Bild: schwarze Spalte) Werte in verschiedene Variablen oder Arrays gelegt werden. Die anderen roten und grünen Spalten entsprechen sozusagen unterschiedlichen Variablen/Arrays. Wenn das Feld Grün ist dann soll bei diesem Durchlauf die Variable genutzt werden (gespeichert und/oder gelesen). Wenn das Feld rot ist wird die Variable dort nicht genutzt.



Der Index der Schleife wird also zur ersten Dimension der Variablen und Arrays. Als Beispiel:

double variable[Schleifenindex];
double variable[42];

oder

int array[Schleifenindex][Feld2];
int array[42][1000];

Das Ganze ist für mich Newbie sehr praktisch denn wenn ein entsprechender Schleifendurchlauf stattfindet, kann dort direkt mit dem aktuellen Index des Durchlaufs immer die korrekte Variable genutzt werden weil die erste Dimension immer dem Schleifenindex entspricht.

Jetzt zu meiner eigentlichen Frage. Zum einen ist es schön strukturiert und einfach aber es werden in der Summe sehr viele Felder gar nicht genutzt (die roten) für die aber Speicherplatz genutzt wird. Sollten es mal richtig viele Felder oder große Arrays geben wird das eine ordentliche Speicherplatzverschwendung.
Gibt es in C++ alternative Ideen/Konzepte/Möglichkeiten, dass nur für die Felder die genutzt werden Speicherplatz reserviert wird aber trotzdem die Sache mit dem einfachen Zugriff wie per Schleifenindex welcher oben als erste Dimension fungiert erhalten bleibt?

lg

 

[NemesisFS]

Gibt es, du kannst statt einem Array eine andere Datenstruktur verwenden. Zum Beispiel eine Liste oder eine Map. Du solltest dir die Unterschiede genau anschauen, die verschiedenen Operationen (einfügen, iterieren, Element Zugriff) sind nämlich verschieden teuer.
Wenn ich deinen use-case richtig verstehe wäre eine map das passende. Anstelle von Indizes verwendet man dort keys, die gehasht werden. Das heißt zum Beispiel, wenn du nur die keys 1, 1000 und 10000000 hast benötigst du Speicherplatz für drei Elemente (Das ist mehr als bei einem Array, weil noch zusätzlich zB die keys gespeichert werden müssen, wenn du aber nur wenige Elemente tatsächlich belegst, lohnt sich das).
Die maps kannst du natürlich auch in einem array ablegen:

std::array<std::map<int, int>, n> variables;
variables[7][23] = 42;

 

[kuddlmuddl]

Ich stimme NemesisFS zu: Zum Sparen von Platz schreit das nach einer Map.
Im Detail sollte man aber bedenken, dass es seit C++11 nicht nur map sondern auch unordered_map gibt. Hier ist der Zugriff lesen/schreiben/einfügen schneller aber das sortierte iterieren über alle Elemente ist langsamer. Dh wenn du oft auf alle grünen Felder einer Zeile (und nicht nur eins) zugreifen willst wäre diese besser. Dh eine map ist besser, wenn du nacheinander auf jedes grüne Feld einer Zeile zugreifen willst und zwar in der "von links nach rechts" Reihenfolge deiner Tabelle.
http://www.cplusplus.com/reference/map/map/
http://www.cplusplus.com/reference/unordered_map/unordered_map/
Solange du aber nicht extrem breite Tabellen hast wirds wahrscheinlich egal sein. Außerdem kann man den Typ ja am Ende einfach mal testweise tauschen, wenn alles fertig ist und man die alternative Performance messen will.

 

[T_55]

Allerbesten Dank!, ich habe mich etwas eingelesen und das mit map sieht dafür perfekt aus. Für normale variablen hab ich es auch einigermaßen verstanden allerdings mit den Arrays hab ich nochmal eine Frage weil ich mit std::array noch keine Erfahrung habe.

Wenn die Map im Array liegt sind dann die Vorteile von Map noch da? Liegt die Belegung von Speicherplatz dann noch in der Hand von Map? Wie wird im obigen Code denn die Feldgröße des Arrays festgelegt?
Wenn ich jetzt in der alten Variante int array[Schleifenindex][Feld]; mit Schleifenindex=10 und Feldgröße=10 das ganze mit map machen will weil zB bei Schleifenindex 2,5,8 und 9 das Feld gar nicht benötigt wird wie würde das dann ungefähr aussehen?

Habe hier http://stackoverflow.com/questions/2582529/using-array-as-map-value-cant-see-the-error es noch so gefunden, dass man wohl auch das Array versucht in die Map reinzubekommen mit Struct und anderen komplizierten Methoden... Wo mir obiges pauschal erstmal wesentlich einfacher vorkommt.

 

[NemesisFS]

Das std::array ist nur eine Klasse die ein Array darstellt, von der Benutzung und der Semantik ist das sehr ähnlich zum Ansatz der in die Sprache eingebaut ist. Die Größe eines std::arrays ist ein Template Parameter, genauso wie der Typ der zu speichernden Variable. In meinem Codebeispiel von oben ist die Größe durch 'N' gesetzt.

Die 'Vorteile der map' werden durch das array nicht beeinflusst. Du hast an jeder Stelle des Arrays eine eigene map, die völlig unabhängig von den anderen ist (abgesehen davon, dass sie den gleichen Typ haben), also sind auch die Inhalte nicht notwendigerweise gleich.

Anhand deiner Beschreibung kann ich leider nicht vollständig nachvollziehen, was dein use-case ist. Der code könnte aber so aussehen:

std::array<std::map<int, int>, N> variables;

// Setzen von ein paar Werten
variables[2][4] = 1;
variables[2][7] = 1;
variables[5][4] = 2;
variables[8][7] = 3;

Du siehst, der Zugriff funktioniert genauso wie bei Arrays. Bei einer Anzahl von nur zehn Elementen wäre aber die Lösung mit einem mehrdimensionalen Array effizienter.

 

[Miuwa]

Was du im Hinterkopf behalten solltest:
Wenn deine Grafik repräsentativ ist, dann nutzt du etwa 50% der Felder (auf jeden Fall mehr als 10%). Falls du pro Feld nur ein-zwei double oder ints abspeicherst, dann bringt dir eine map keinerlei Vorteile, sondern braucht im Gegenteil viel mehr Platz und ist langsamer (letzteres wird ohnehin immer der Fall sein). Eine map von primitiven Datentypen ist einfach ein extrem ineffizientes Konstrukt.

 

[T_55]

Ich muss gestehen ich hab trotz einigem lesen und videotutorials die Verknüpfung zwischen std::array und map noch nicht vollständig durchschaut aber konnte folgendes beobachten:
- N muss mindestens den höchsten Key-Wert+1 haben
- die Größe also variables.size() entspricht immer N. Ohne Array ist es normalerweise die Anzahl der erstellten ID Werte und nicht der größte ID-Wert unabhängig von der Anzahl der erstellten IDs.
- N muss als const int erstellt werden das heißt es ist wohl nicht möglich N durch Werte aus dem Programm zu definieren...?
- sizeof(variables) gibt mir den Speicherplatzbedarf von 24Byte pro ID an.

Hab irgendwie noch nicht verstanden welcher Speicherplatz mit der Zeile variables[0][500] = 1; eigentlich reserviert/belegt wird? Ist es Zuweisung des Wertes 1 und Feldgrößendefinierung mit 500 zugleich?


Nochmal zu meinem theoretischen Usecase:

Es gibt Variablen und Arrays zB:

int a;
int b[1000];
int c[1000][1000];

und es gibt bool´s zum steuern

bool a_bool = 0;
bool b_bool = 0;
bool c_bool = 0;

In einem Block werden die Variablen/Arrays a b c verarbeitet. Ob eine Variable/Array verarbeitet wird, wird in dem Block nochmal seperat durch eine if Abfrage der bool´s gesteuert.

Es gibt eine übergeordnete Hauptsteuerung die den Block mit den Verarbeitungen mehrmals ausführen soll und jedesmal die bool´s anders einstellt. Daher muss es die Variablen/Arrays auch in mehrfacher Ausführung geben. Bei jeder Ausführung gibt es also unterschiedliche Aktivierungen der Verarbeitungsschritte.

Daher hatte ich ursprünglich einfach jeder Variable/Array noch eine erste Dimension hinzugefügt die als Index für die Durchläufe fungiert. Beispiel 100 Durchläufe:
int a[100];
int b[100][1000];
int c[100][1000][1000];
Da bei Nichtnutzung von Variablen/Arrays bei diversen Durchläufen so unnötig Speicherplatz verschwendet wird ist meine Frage entstanden. Ich hoffe der Usecase ist jetzt einigermaßen klar geworden.

Genial wäre eben wenn bei Durchläufen wo Variablen/Arrays nicht benutzt werden (bool==false) auch kein Speicherplatz verbraten wird.

lg

ps: @ Miuwa: Ja so gesehen stimmt. Es sind mit den Spalten in der Grafik aber auch recht große Arrays gemeint. Im Verhältnis zu dem Speicherplatz für die Keys müsste es doch bei Arrays sich dann doch lohnen weil ja auf einen Key ggf ein Array mit zum Beispiel 1000 Feldern kommt. Wenn das Verhälnis 50:50 ist dann macht es wirklich keinen Sinn aber ich habe definitiv vor mit Arrays zu arbeiten.

 

[Miuwa]

Ich glaube es wäre hilfreich, du würdest win paar Zeilen Beispielcode schreiben, die zeigen wie genau du die arrays im Moment verwendest. So ganz werd ich aus deinem Post nämlich nicht schlau. Wo kommt jetzt plötzlich die 3. Dimension her? Und was meinst du damit, dass auf einen Key ein Array mit 1000 feldern kommt? Konntrolliert jede Box in deinem Bild ein komplettes array? Wie schon gesagt, zeig mal wie genau du im Moment auf die Daten zugreifst.

 

[NemesisFS]

Ich muss gestehen ich hab trotz einigem lesen und videotutorials die Verknüpfung zwischen std::array und map noch nicht vollständig durchschaut aber konnte folgendes beobachten:
- N muss mindestens den höchsten Key-Wert+1 haben
- die Größe also variables.size() entspricht immer N. Ohne Array ist es normalerweise die Anzahl der erstellten ID Werte und nicht der größte ID-Wert unabhängig von der Anzahl der erstellten IDs.
- N muss als const int erstellt werden das heißt es ist wohl nicht möglich N durch Werte aus dem Programm zu definieren...?
- sizeof(variables) gibt mir den Speicherplatzbedarf von 24Byte pro ID an.

Hab irgendwie noch nicht verstanden welcher Speicherplatz mit der Zeile variables[0][500] = 1; eigentlich reserviert/belegt wird? Ist es Zuweisung des Wertes 1 und Feldgrößendefinierung mit 500 zugleich?

N ist die Anzahl an Zeilen in deiner Tabelle. In dem Bild deines ersten Posts wäre das 42. Wenn du die 'variables' im Stack speichern möchtest, musst du schon zur Compilezeit wissen wie groß das Array ist, deswegen muss das N eine constexpr sein. Es ist aber vermutlich ohnehin sinnvoller die Struktur auf dem Heap abzulegen, dann kann N auch zur Laufzeit bestimmt werden:

// Alter code
auto variables = new std::array<std::map<int, int>, N>();
// ...
delete variables;
// Moderner code
auto variables = std::make_unique<std::array<std::map<int, int>, N>>()

Ich nehme an 'ID-Werte' sind die einzelnen Einträge? Die Größe von variables weicht dann vom normalen code ab, weil sie die Einträge auf dem Heap dem heap speichern. variables.size() wäre zum Beispiel 42 im Bild des ersten Posts.

 

[T_55]

Danke das schaue ich mir an. Mit Heap klingt nicht schlecht wenn man damit N flexibler bestimmen kann. Vielleicht könnte man auch die Feldgröße je nach Durchlauf anders definieren...

Hier nochmal der Code von meiner ersten nicht optimalen ersten Variante:
Das hier nur 6x der Block aufgerufen wird dient nur als Beispiel, könnten hier bis 100 sein.

#include <iostream>
#include <windows.h>
using namespace std;

int durchlauf;

int a[100];
int b[100][500];
int c[100][500][500];

bool a_bool = 0;
bool b_bool = 0;
bool c_bool = 0;

void block()
{
    cout << "Durchlauf Nr: " << durchlauf << "     a = " << a[durchlauf] << endl;
    Sleep (500);

    if(a_bool)
    {
        // arbeite mit a
        a[durchlauf]++;
    }
    if(b_bool)
    {
        // arbeite mit b
        b[durchlauf][123]++;
        b[durchlauf][234]++;
    }
    if(c_bool)
    {
        // arbeite mit c
        c[durchlauf][123][123]++;
        c[durchlauf][20][1]++;
        c[durchlauf][6][444]++;
    }
}

int main()
{
    while(1)
    {
            a_bool = 0;     b_bool = 0;    c_bool = 0;
            durchlauf++;
            block();

            a_bool = 1;     b_bool = 0;    c_bool = 0;
            durchlauf++;
            block();

            a_bool = 1;     b_bool = 1;     c_bool = 0;
            durchlauf++;
            block();

            a_bool = 1;     b_bool = 1;     c_bool = 1;
            durchlauf++;
            block();

            a_bool = 0;     b_bool = 1;     c_bool = 0;
            durchlauf++;
            block();

            a_bool = 0;     b_bool = 1;     c_bool = 1;
            durchlauf++;
            block();


            durchlauf = 0;
    }

    return 0;
}

 

[NemesisFS]

// ....

// gewöhn dir an, kein 'using namespace std' zu verwenden, sondern immer die konkreten Elemente zu wählen die du brauchst.
using std::array;
using std::map;

// ....

const int n = 100
std::array<int, n> a;
std::array<std::map<int, int>, n> b;
std::array<std::map<int, std::map<int, int>>, n> c;

// ....

void block()
{
    cout << "Durchlauf Nr: " << durchlauf << "     a = " << a[durchlauf] << endl;
    Sleep (500);

    if(a_bool)
    {
        // arbeite mit a
        a[durchlauf]++;
    }
    if(b_bool)
    {
        // arbeite mit b
        if (b[durchlauf].find(123) == b.end()) { b[durchlauf][123] = 0; }
        b[durchlauf][123]++;
        if (b[durchlauf].find(234) == b.end()) { b[durchlauf][234] = 0; }
        b[durchlauf][234]++;
    }
    if(c_bool)
    {
        // arbeite mit c
        if (c[durchlauf][123].find(123) == c.end()) { c[durchlauf][234] = 0; }
        c[durchlauf][123][123]++;
        if (c[durchlauf][20].find(1) == c.end()) { c[durchlauf][20][1] = 0; }
        c[durchlauf][20][1]++;
        if (c[durchlauf][6].find(444) == c.end()) { c[durchlauf][6][444] = 0; }
        c[durchlauf][6][444]++;
    }
}

Das wäre der code mit den maps. Beachte dass die in diesem Beispiel global sind, also muss die Größe der arrays vorher bekannt sein. Vergleich den Code genau an den Stellen wo er sich geändert hat um nachzuvollziehen was der Unterschied ist, die Benutzung ist ja fast identisch. Die if-statements habe ich eingefügt, um den Fall abzufangen in dem das Element noch nicht in der map ist. Da gibt es aber bestimmt auch schönere Lösungen für, eventuell kann da jemand was zu sagen der sich damit besser auskennt.
Ich hab ein paar relevante

 

[T_55]

Total gut danke. Dann verbraucht kein Feld Platz bevor es verarbeitet oder = 0 gesetzt wurde. Das ist richtig gut
ps: Bei den if Statements hab ich noch den error: no match for 'operator=='

 

[NemesisFS]

Bei mir funktioniert das:

#include <iostream>
#include <map>

int main() {
	std::map<int, int> map;
	if (map.find(0) == map.end()) { map[0] = 0; }
	map[0]++;
	std::cout << map[0] << std::endl;
	return 0;
}

Wenn du den Zugriff öfter hast, solltest du eventuell einen Wrapper

template<typename T, typename R> 
T& getDefault(std::map<T, R> map&, R index);

schreiben um Codeduplikation zu vermeiden. Die templates kannst du auch weglassen und R und T durch int ersetzen. Zur Übung könntest du stattdessen auch von der map erben und eine default_map mit einem default Wert erstellen.

 

[Miuwa]

N ist die Anzahl an Zeilen in deiner Tabelle. In dem Bild deines ersten Posts wäre das 42. Wenn du die 'variables' im Stack speichern möchtest, musst du schon zur Compilezeit wissen wie groß das Array ist, deswegen muss das N eine constexpr sein.

Falls das nicht klar ist: Für std::array muss N immer eine Compilezeitkosntante sein. Egal, ob das array auf dem stack oder heap liegt.