Besser Programmieren? In Arrays suchen und Arrays vergleichen

[It0101]

@betzi1985
also wenn du als kompletter Neueinsteiger innerhalb weniger Tage ein kompilierbares und funktionierendes Lottoprogramm gebaut hast, dann ist das top! Das sagt zumindest aus, dass du ein gewisses Verständnis und Vorstellungsvermögen hast.
Wenn dir das Spaß macht, war es auf jeden Fall die richtige Entscheidung. Ob es dir beruflich was bringt, ist dann wiederum eine andere Sache.
Ich sag mal: willkommen in der C++-Community

Wenn du Discord-Nutzer bist gibt es hier auch einen Chat.

[Mechanics]

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

Schon alleine, dass die main Teil einer Klasse sein soll?

Ja, ich kenn diese ganzen Argumente War schon so, als ich noch studiert habe. Und vermutlich auch nochmal 10 Jahre davor, als ich mir zum ersten mal Java angeschaut hatte. Und ja, mir gefällt es jetzt auch nicht unbedingt.
Aber es spielt einfach keine Rolle. Wie oft schreibst du in einem Programm schon die main Funktion? Irgendwann ist es doch völlig egal. Und bei Projekten ist es sehr oft so, dass die Programmiersprache schon vorgegeben ist. Oder wenn nicht, und man die Anforderungen evaluiert und sich für eine Programmiersprache entscheidet, dann werden auch ganz andere Dinge eine Rolle spielen, ob man unbedingt alles in eine Klasse packen muss, oder nicht.
Am Ende des Tages stört es auch einfach überhaupt nicht, und man hat dafür vielleicht viele andere, konkret greifbare Vorteile (oder Nachteile).

Also, ich lass das Argument gern gelten, wenn man sich drüber auslassen will, dass man Java nicht mag Aber es ist kein gültiges Argument, wenn man sich eine Sprache für ein Projekt aussucht, oder sich überlegt, welche Sprachen man für die Zukunft lernen sollte.

[Steffo]

Zuerst einmal: Arrays sind Bestandteil der Sprache C++ und du wirst im Laufe deines Berufsleben auf diese stoßen, auch wenn das vielleicht nicht schön ist. Deshalb solltest du Arrays sicher handhaben können und nicht unbedingt sofort auf std::vector oder std::array umsteigen.

Ferner finde ich auch, dass das für zwei Tage Programmierenlernen verdammt gut ist! Und ich würde auch nicht die Firma wechseln, nur weil du dort in Deutsch programmieren musst. Im Gegenteil: Da du schon in der Firma bist, hast du bessere Chancen als Programmierer übernommen zu werden. Viel schlimmer wäre es, wenn du wechselst und dann ziemlich auf die Schnauze fliegst, weil du den Anforderungen noch nicht genügst.

Weiter hast du dir einer der schwierigsten Sprachen ausgesucht. Wenn ich damit nicht beruflich zu tun hätte, würde ich mir das nicht antun.
Ich glaube Java und C# sind deutlich Einsteigerfreundlicher und sie bringen auch schon von Haus aus Oberflächen-Bibliotheken mit.

Zu deinen Fragen:
Klar kann man in Arrays suchen. Du iterierst einfach über Arrays und vergleichst mit einer If-Anweisung über den == Operator.
So kannst du entsprechend auch zwei Arrays miteinander vergleichen. Wenn du sicherstellen kannst, dass beide Arrays dieselbe Größe haben, dann reicht dir eine Schleife aus und du greifst mit dem Index "i" auf beide Arrays zu.
Haben die beiden Arrays nicht dieselbe Größe, dann brauchst du zwei verschachtelte Schleifen.

[wob]

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

Zu deinen Fragen:
Klar kann man in Arrays suchen. Du iterierst einfach über Arrays und vergleichst mit einer If-Anweisung über den == Operator.
So kannst du entsprechend auch zwei Arrays miteinander vergleichen. Wenn du sicherstellen kannst, dass beide Arrays dieselbe Größe haben, dann reicht dir eine Schleife aus und du greifst mit dem Index "i" auf beide Arrays zu.
Haben die beiden Arrays nicht dieselbe Größe, dann brauchst du zwei verschachtelte Schleifen.

Moment, moment! Erstens: haben die Arrays nicht dieselbe Größe, brauchst du gar keine Schleife, dann sind die Arrays niemals gleich. Denk doch auch mal über den Zusammenhang Lotto nach! Das heißt, die Reihenfolge der 6 Zahlen spielt keine Rolle. Du kannst nicht einfach so mit einer Loop vergleichen. Und das hatte @betzi1985 auch schon richtig verstanden. Das Problem ist, dass die beiden verschachtelten Schleifen nach "ineffizient" schreien. Bei 6 Zahlen sicher egal, aber es ging hier ja darum, wie es besser geht. Generell fallen einem da 2 Möglichkeiten ein:

1. Beide Arrays sortieren und dann mit einer Schleife vergleichen (*).
2. Die 6 Zahlen bilden auch eine Menge. Es bietet sich also ein std::set an. Das ist vielleicht etwas langsamer als die sortierten Arrays, aber drückt die Absicht dafür super aus.

(*) zum Vergleichen nimmt man nicht eine manuelle Scheife, sondern z.B. std::equal oder std::mismatch

[Steffo]

@wob Hast recht. Ich habe den Beitrag nur überflogen und habe direkt die Fragen gelesen.

[betzi1985]

@wob hi, erstmal danke für die vielen Antworten, hätte ich nicht mit gerechnet. Klar, kann man Java ihn Oop machen, aber dafür war es nicht gedacht. C++ kann man da schon eher ohne Oop machen. Zumal bei Java so gut wie nix ohne Objekte geht, sogar eine einfache Consolenausgabe braucht man dieses System.out.printline oder so.

Also ich weiß jetzt nicht, wie ich die 2 Arrays mit nur einer Schleife vergleichen soll. Beispiel Array1(1;2;3;4;5;6) Array2(2;3;4;5;6;7) ich nehme das erste Element von Array1 vergleiche es mit dem 1. Element von Array 2 nicht gleich. Dann 2. mit 2. usw. Ergebnis: keine Überstimmung, obwohl 5 Elemente übereinstimmen und es ja genau das ist, was ich möchte, wieviele sind gleich nicjt ob die beiden Arrays gleich sind. Oder habe ich mal wieder Denkfehler?:(

[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)