Besser Programmieren? In Arrays suchen und Arrays vergleichen

[Steffo]

@betzi1985 Das Problem ist ja, dass die Reihenfolge nicht übereinstimmt.
Da fällt mir ein, dass ein vorheriges Sortieren das Problem auch nicht löst, @wob .
Beispiel:
(1, 2, 3, 4, 5, 6,) und (2, 3, 4, 5, 6, 7) sind zwar schön sortiert, allerdings gibt es hier keine Übereinstimmung, wenn man mit dem gleichen Index i vergleicht.

Ich denke, man kommt nicht drum herum zwei ineinander verschachtelte Schleifen zu nehmen.

[wob]

@Steffo sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

@betzi1985 Das Problem ist ja, dass die Reihenfolge nicht übereinstimmt.
Da fällt mir ein, dass ein vorheriges Sortieren das Problem auch nicht löst, @wob .
Beispiel:
(1, 2, 3, 4, 5, 6,) und (2, 3, 4, 5, 6, 7) sind zwar schön sortiert, allerdings gibt es hier keine Übereinstimmung, wenn man mit dem gleichen Index i vergleicht.

Ich denke, man kommt nicht drum herum zwei ineinander verschachtelte Schleifen zu nehmen.

NEIN!

Du vergleichst 1 mit 2. 1 ist offenbar kleiner. Also gehst du im ersten Array (und nur im ersten Array) einen Index weiter. Usw. Du brauchst EINE Schleife, aber zwei Iteratoren oder Indizes.

Oder du nimmst set_intersection. Siehe Beispiel hier: https://en.cppreference.com/w/cpp/algorithm/set_intersection

[DocShoe]

@betzi1985

Das ist eigentlich ein schönes Anfängerprojekt, um sich mit den Datentypen und Algorithmen der STL (Standard Template Library) zu befassen, die seit 1998 Bestandteil von C++ ist. Sie bietet verschiedene Containertypen, die ähnlich wie C-Array funktionieren, aber wesentlich einfacher (und sicherer!) zu handhaben sind. Leider ist es unumgänglich, sich in diesem Zusammenhag auch mit Iteratoren zu beschäftigen, was als Einsteiger nicht so einfach zu verstehen ist, aber für die Benutzung der STL zwingend erforderlich ist. In C++ sollte man versuchen, handgeschriebene Schleifen weitestgehend zu vermeiden und sie durch entsprechende Funktionen aus der STL zu ersetzen. Das könnte in etwa so aussehen:

#include <array>
#include <vector>
#include <numeric>
#include <algorithm>

void lottery()
{
   // Array fester Größe  für die Lottozahlen
   std::array<unsigned int,49> numbers; 

   // Array mit fortlaufenden Zahlen ab 1 befüllen
   std::iota( numbers.begin(), numbers.end(), 1 ); 

   // Lottozahlen mischen   
   std::random_shuffle( numbers.begin(), numbers.end() ); 

   // die ersten 6 Zahlen des gemischten Arrays sind die gezogenen Zahlen. std::array<unsigned int,6> wäre mir
   // hier lieber, aber std::array hat keinen Konstruktor, über den es sich initialisieren ließe. Also std::vector, obwohl
   // der nicht ganz passend ist. 
   std::vector<unsigned int> numbers_drawn( numbers.begin(), numbers.end() +6 ); 

   // 6 bespielhaft getippte Zahlen
   std::vector<unsigned int> ticket { 3, 11, 14, 26, 34, 39 };  
   
   // Lambda, das bestimmt, ob count_if einen Treffer zählt oder nicht. Mag hier zu fortgeschritten sein, aber
   // wenigstens hast du dann mal ein Lambda gesehen.
   auto predicate = [&numbers_drawn]( unsigned int number )
   {
      return find( numbers_drawn.begin(), numbers_drawn.end(), number ) != numbers_drawn.end();
   };
   // count_if zählt die Elemente, auf die das Prädikat zutrifft. Das Prädikat prüft für die übergebene Zahl, ob sie
   // in dem Vektor der gezogenen Zahlen enthalten ist.
   unsigned int matches = std::count_if( ticket.begin(), ticket.end(), predicate );
}

Ich benutze hier die beiden Containertypen std::array und std::vector. std::array ist ein Array fester Größer und in etwa mit einem C-Array zu vergleichen. std::vector ist eine Art Array, dessen Größe automatisch angepasst wird, je nachdem, ob man ein Element hinzufügt oder löscht. std::vector benutze ich in meinem Beispiel nur, da std::array keinen Konstruktor hat, über den man den Inhalt direkt initialisieren könnte.

[Steffo]

@wob sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

Du vergleichst 1 mit 2. 1 ist offenbar kleiner. Also gehst du im ersten Array (und nur im ersten Array) einen Index weiter. Usw. Du brauchst EINE Schleife, aber zwei Iteratoren oder Indizes.

Ok, das geht natürlich. Das hattest du so aber nicht beschrieben gehabt.

[wob]

@DocShoe sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

   // Lambda, das bestimmt, ob count_if einen Treffer zählt oder nicht. Mag hier zu fortgeschritten sein, aber
   // wenigstens hast du dann mal ein Lambda gesehen.
   auto predicate = [&numbers_drawn]( unsigned int number )
   {
      return find( numbers_drawn.begin(), numbers_drawn.end(), number ) != numbers_drawn.end();
   };
   // count_if zählt die Elemente, auf die das Prädikat zutrifft. Das Prädikat prüft für die übergebene Zahl, ob sie
   // in dem Vektor der gezogenen Zahlen enthalten ist.
   unsigned int matches = std::count_if( ticket.begin(), ticket.end(), predicate );
}

Das ist aber weiterhin eine verschachtelte Schleife, nur dass du es nicht mehr so gut siehst, weil die eine in dem Prädikat und die andere in dem count_if versteckt ist.

[DocShoe]

@wob
Und?

[wob]

@DocShoe sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

@wob
Und?

Naja, $\mathcal{O}(n^2)$ ist halt nicht so toll, wenns auch in $\mathcal{O}(n \log n)$ geht. Ich würde daher von verschachtelten Schleifen abraten. (aus Prinzip; bei diesem speziellen Problem mit 6 aus 49 ist es wahrlich egal)

[Steffo]

@wob sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

@DocShoe sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

@wob
Und?

Naja, $\mathcal{O}(n^2)$ ist halt nicht so toll, wenns auch in $\mathcal{O}(n \log n)$ geht. Ich würde daher von verschachtelten Schleifen abraten. (aus Prinzip; bei diesem speziellen Problem mit 6 aus 49 ist es wahrlich egal)

Wenn einem Performance wirklich wichtig ist, dann kommt man um Performance-Messungen nicht drum herum. Die O-Notation greift unter Umständen erst bei (sehr) großen N. Bei kleinen bis mittelgroßen N, kann sie sogar in die Irre führen.
Eine lineare Suche mit einem std::vector kann bspw. bei mittelgroßen N deutlich performanter sein als mit std::map oder std::unordered_map sein.

[It0101]

@Steffo sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

Eine lineare Suche mit einem std::vector kann bspw. bei mittelgroßen N deutlich performanter sein als mit std::map oder std::unordered_map sein.

Kann nicht nur. ist sogar so. Wo genau der BreakEven liegt kann dann jeder selber rausfinden. Wenn ich vorher weiß, dass mein vector nur so bis zehn Einträge hat, wechsel ich gar nicht erst auf eine Map, auch wenn die natürlich recht elegant ist.

[Steffo]

@It0101 sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

Kann nicht nur. ist sogar so. Wo genau der BreakEven liegt kann dann jeder selber rausfinden. Wenn ich vorher weiß, dass mein vector nur so bis zehn Einträge hat, wechsel ich gar nicht erst auf eine Map, auch wenn die natürlich recht elegant ist.

Ich habe mal einen Vortrag gesehen. Lass mich nicht lügen, aber ich meine, dass selbst bei einer Millionen Elemente ein std::vector schneller ist als std::map.
Man muss das wie gesagt messen.

[SeppJ]

Ja, da hatten wir neulich einen langen Thread zu, den ich gerade nicht mehr finden kann. Die map, und besonders die unordered_map, haben beide total versagt.

[DocShoe]

Neulich ist gut
https://www.c-plusplus.net/forum/topic/289230/performance-map-vs-set-vs-unordered_map

Edit:
Obwohl... war der das tatsächlich?

[SeppJ]

@DocShoe sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

Neulich ist gut
https://www.c-plusplus.net/forum/topic/289230/performance-map-vs-set-vs-unordered_map

Edit:
Obwohl... war der das tatsächlich?

Nee, das war in den letzten 6 Monaten. Mit mehr Muße finde ich den auch sicher noch, aber die fehlt mir in dieser Sekunde, außer es besteht brennendes Interesse an den Details, über meine Zusammenfassung hinaus. Zumal ich in dem Thread auch noch falsch lag, weil ich vor der Messung mein Geld auf die map gesetzt hatte

[wob]

Wir haben damals aber 2 $\mathcal{O}(n \log n)$-Lösungen verglichen. Nicht eine mit $n^2$! (und ja: bei wenigen Elementen kann natürlich $n^2$ schneller sein - weil es da auf ganz andere Dinge ankommt)

[yahendrik]

Gemeint ist wohl der hier:
https://www.c-plusplus.net/forum/topic/350354/felder-auf-gleichheit-überprüfen

[Mechanics]

@Steffo sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

Lass mich nicht lügen, aber ich meine, dass selbst bei einer Millionen Elemente ein std::vector schneller ist als std::map

Das wäre sicher zu viel. Ich denke beim Suchen nach einzelnen Werten wäre eine Map "ziemlich schnell" schneller als ein unsortieres Array. Ich würde spontan auf 100 Elemente oder weniger tippen, aber sowas habe ich noch nie so genau verglichen.
Ein sortiertes Array/Vector dürfte sich allerdings ganz gut schlagen. Das benutze ich oft lieber als maps oder hash maps.

[Steffo]

@Mechanics sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

Das wäre sicher zu viel. Ich denke beim Suchen nach einzelnen Werten wäre eine Map "ziemlich schnell" schneller als ein unsortieres Array. Ich würde spontan auf 100 Elemente oder weniger tippen, aber sowas habe ich noch nie so genau verglichen.
Ein sortiertes Array/Vector dürfte sich allerdings ganz gut schlagen. Das benutze ich oft lieber als maps oder hash maps.

Das kann gut sein. Ich hatte das wohl nicht mehr ganz exakt in Erinnerung. Hier wird auch berücksichtigt wie viel Zeit es braucht Elemente hinzuzufügen:

https://youtu.be/LFv7XwgsdLY?t=3359

[betzi1985]

So ich verstehe teilweise nur Bahnhof, was Map und Co und Geschwindigkeit angeht. Ich habe mir jetzt das Buch der C++ Programmierer von Ulrich Breyman gegönnt. Neuste Ausgabe gebraucht für 15€ im Top Zustand werde mich da mal durchkämpfen und damit lernen. Als nächstes Projekt möchte ich ein Kniffelprojekt entwickeln, ohne KI und Grafik natürlich.

Gruß

Betzi

[DocShoe]

@betzi1985 sagte in Besser Programmieren? In Arrays suchen und Arrays vergleichen:

So ich verstehe teilweise nur Bahnhof, was Map und Co und Geschwindigkeit angeht. Ich habe mir jetzt das Buch der C++ Programmierer von Ulrich Breyman gegönnt. Neuste Ausgabe gebraucht für 15€ im Top Zustand werde mich da mal durchkämpfen und damit lernen. Als nächstes Projekt möchte ich ein Kniffelprojekt entwickeln, ohne KI und Grafik natürlich.

Gruß

Betzi

Glückwunsch, damit hast du nen guten Griff getan!