Minimum

[Xin]

Jester schrieb:

Dabei ist es wurscht, welche Datenstruktur tatsächlich drunter liegt. Sei es ein Array oder eine Liste.

Ähh... wenn Du einen Vector nimmst, wirst Du auf Dauer Schwierigkeiten haben an einem Array dran zu bleiben. Ich denke, das macht durchaus einen Unterschied.
Vektoren sind schnell, aber alles hat seine Grenzen. Die Grenze ist das Array.

Nebenher ist die Grundlage meines STL-Gemecker nicht die Geschwindigkeit, sondern die Notwendigkeit einem Anfänger STL zu verpassen.

otze schrieb:

mit templates kommt man hier aber auch nicht direkt in berührung. Ich muss ja nicht wissen, was templates sind, genauso, wie ich nicht wissen muss, wie cin oder cout funktionieren. Und was "using namespace std;" bedeuted, lernen die meisten auch erst lange nach ihrem ersten "hello world" programm. Von daher zeiht das Argument hier recht wenig.

Ich halte nichts davon mit objektorientierten Verfahren zu beginnen, bevor man weiß, was objektorientierte Programmierung bedeutet.

Ich programmiere fast ausschließlich OOP, auch in C, weil es fast immer das Mittel der Wahl ist. Aber ich halte nichts davon ein Hilfsmittel zu nutzen, wenn ich nicht weiß, warum.
Wie ich aus Deinem Posting herauslese sind wir uns da einig.

Als ich Autofahren oder Tauchen lernte, wurde man erstmal über aller notwendigen Interna aufgeklärt. Ich wurde weder ins Auto gesetzt und mit Anhänger auf die Autobahn geschickt und das erste Mal unter Wasser wurden auch keine Höhlen in 30 Metern Tiefe erkundet. Ich übte entsprechend meines Wissenstandes: Seitenstraßen und Übungen im Pool. Basierend darauf Landstraßen und Meerwasser usw. Step by Step.

Ich sehe keinen Grund, dass in der Informatik anders zu machen. Ich weiß, dass ich damit erstaunlicherweise recht alleine stehe.

Während meiner Zeit als Tutor durfte ich eigentlich jedes Semester komplett bei Null anfangen, weil die Leute aufgrund zuvieler Informationen diese überhaupt nicht sauber sortiert bekamen. Offiziell konnten die schon programmieren. Die haben schon komplexere Projekte abgegeben. Die wußten was Klassen sind und wie man Standard-Bibliotheken ruft, aber es wäre nett, wenn ich die while-Schleife nochmal erklären könnte....?!?
Hier sah ich viele Gründe, die deutlich dagegen sprechen, die Leute mit Informationen wegzubombem.

otze schrieb:

Anstatt std::sort zu nutzen, hacken sie sich nen verbugten bubble sort zusammen, und wundern sich, dass es dann nicht funktioniert(steht ja genauso da, wie im lehrbuch).
Das ganze weckt dann bei einem Anfänger auch nur den frust bei der Sprache, und ist absolut kontraproduktiv.

Ich habe den Frust der Leute eigentlich regelmäßig aufbeschworen in dem ich sie in jede mögliche Falle getrieben habe. Einer meinte später zu mir, dass er in dem paar Stunden Tutorium mehr gelernt hätte als in der Zeit davor.
Frust gehört dazu - immer. Genauso, wie die das Gefühl, dass man verstanden hat, warum man zuvor Frust hatte.

otze schrieb:

Später lernt man eh diese ganzen kleinigkeiten, ne liste kann man immernoch implementieren, wenn man sicher mit den grundmitteln der sprache ist.

Das kenne ich auch anders. Vectoren sind bekannt, aber nur als "Ding", dass irgendwie die Sachen zusammenhält.

otze schrieb:

Das mit den virtuellen funktionen solltest du näher erläutern. Klingt sehr neu und spannend für mich.

Lufthol... aushol... ähh... <buzzer>

Mit den virtuellen Funktionen habe ich mich in die Nesseln gesetzt. ^^

Die Diskussion gab es die Tage schonmal mit iostreams, da virtuelle Funktionen, hier werkeln Templates - keine virtuellen Funktionen.
Gleiche Geschwindigkeit zum Array ist damit möglich. ("möglich" ist nicht der Versuch einen letzten Widerstand im Sinne von 'Ich will aber recht behalten', sondern zollt der Tatsache Respekt, dass nicht spezialisierte Templates auch Informationen managen können, die für das spezielle Problem nicht von Bedeutung sind.)
Mea culpa!

otze schrieb:

finix schrieb:

robuster

Wer sich bei diesem Dreizeiler bereits Gedanken machen muss, ob er das korrekt implementiert bekommt... der hat auf jeden Fall recht, wenn er std::min_element() verwendet.

du weist wohl nicht, was robust bedeuted ;). Die Beispielschleife von dir auf Seite 7 ist zb nichtmal ansatzweise robust. Mach ich im zuge der entwicklung aus dem Array eine Liste, ist das ergebnis höchst suboptimal.

Ich denke schon, dass ich weiß, was robost lautet.
Machst Du im Zuge der Entwicklung aus dem Array eine Liste, muss das Ergebnis nicht unbedingt suboptimal sein, ist die Frage, wie die Liste implementiert ist.

Robost bedeutet für mich in erster Linie, dass ein Code mit unerwarteten Werten ohne Sonderbedingungen klarkommt.

Designänderungen für die Zukunft plane ich in der Regel nicht, sonst hätte das Design schon von vornerein einen Fehler.
Wenn es mich trifft, trifft es mich hart und das merke ich mir auch für's nächste Mal. In manchen privaten Projekten bin so kompromisslos, dass ich zugunsten einer geringfügig besseren Lösung auch wochen- und monatelange Arbeit ohne Zögern in die Tonne haue. Doch keine dieser Änderungen hätte mit der STL beschleunigt werden können.
Wenn geändert wird, dann ist die Frage 'Array oder Liste?' absolut bedeutungslos.

[Xin]

lemonhead schrieb:

Oh man das is ja lustich hier.

^^
Willkommen im Ring... äh.. Forum.

lemonhead schrieb:

Wenn ich nun all meine Werte in einem solchen container abgelegt habe (was wirklich zu empfehlen ist), dann kann ich auf verschiedene Weise das Minimum heraussuchen. Gehen wir mal davon aus, die Daten stehen in einem Array, vector<double> oder list<double>.
- das minimum finden wir, indem wir den container von Anfang bis Ende durchlaufen und die Elemente mit dem bisher gefundenen Minimum vergleichen. Genau das macht Xin mit seiner for-Schleife, und ist damit average-case-zeitoptimal, und zwar nicht nur asymptotisch. Natürlich muss man bei list<vector> mit einem iterator arbeiten. So hat Xin das gemeint.
- Dasselbe macht aber auch das min_element() aus der stl. Es läuft innendrin genau dasselbe ab, ist aber tatsächlich einfacher zu lesen.
- Bei einfachen double-Werten benutzen wir den Standard-"<"-Operator. Die Funktion min_element macht das automatisch.
- Wenn die Werte aber einen selbstgebauten Datentyp haben, dann muss man sich selber darum kümmern wie diese verglichen werden. Für mal-eben-schnell-das-minimum-finden empfehle ich da ganz klar die for-Schleife, da sieht man sofort wie verglichen wird.

Ich kann mich irren, aber ich fühle mich erstmals verstanden...

lemonhead schrieb:

Und, für den guten Ton: Ihr habt alle keine Ahnung. Ich habe das Gefühl mich mit einer Packung Zwieback zu unterhalten.

*gg*

Wobei finix in meinen Augen Kokos-Zwieback ist und das ist schon längst gegessen...

[finix]

lemonhead schrieb:

Wenn ich die Daten alle nacheinander einlese, kann ich auch gleichzeitig schon feststellen was das Minimum ist. Was ich weiter mache, ist dann wohl egal.

Zonk. *minimum_it += 42;

lemonhead schrieb:

- Wenn ich vorher die Anzahl der Eingabewerte schon kenne, dann kann ich einfach einen simplen array verwenden. Damit bin ich insgesamt aber weniger flexibel, und es verleitet dazu zuviel selber herum zu basteln.

Kannst du kurz erklären was du hier mit dem zweiten Satz meinst?

lemonhead schrieb:

- Bei std::list<double> kann man auch zwischendrin Elemente einfügen, und vor allem einzelne Elemente löschen. Sie kostet aber im allgemeinen mehr Speicher als ein Array, und ist etwas schwerfälliger.

"Schwerfälliger"?

lemonhead schrieb:

- Es gibt noch weitere Möglichkeiten (zB map), aber das reicht jetzt mal.

Für eine Menge?

lemonhead schrieb:

Für mal-eben-schnell-das-minimum-finden empfehle ich da ganz klar die for-Schleife, da sieht man sofort wie verglichen wird.

Wo ist da der Unterschied zu std::min_element ?

lemonhead schrieb:

Warum sortieren?

Ja genau, warum? Vielleicht geht es um eine Sequenz?

[finix]

Xin schrieb:

Wobei finix in meinen Augen Kokos-Zwieback ist und das ist schon längst gegessen...

Naja, immerhin ein Hauch geschickter als der Schwarze Ritter...

[otze]

Xin schrieb:

otze schrieb:

du weist wohl nicht, was robust bedeuted ;). Die Beispielschleife von dir auf Seite 7 ist zb nichtmal ansatzweise robust. Mach ich im zuge der entwicklung aus dem Array eine Liste, ist das ergebnis höchst suboptimal.

Ich denke schon, dass ich weiß, was robost lautet.
Machst Du im Zuge der Entwicklung aus dem Array eine Liste, muss das Ergebnis nicht unbedingt suboptimal sein, ist die Frage, wie die Liste implementiert ist.

ZONK! schau dir nochmal deine Schleife an die arbeitet mit indexen und dem operator[]. nicht viele Listen unterstützen das ;). Im gegensatz zum iterator der zumindest von allen stl containern+dem standard array verfügbar ist ;).
Das Problem ist einfach, dass sich dann so kleine änderungen durch den kompletten code ziehen. Und jedes nachträgliche ändern und anpassen ist fehleranfällig (wenn nicht sogar fehleranfälliger).

Designänderungen für die Zukunft plane ich in der Regel nicht, sonst hätte das Design schon von vornerein einen Fehler.
Wenn es mich trifft, trifft es mich hart und das merke ich mir auch für's nächste Mal. In manchen privaten Projekten bin so kompromisslos, dass ich zugunsten einer geringfügig besseren Lösung auch wochen- und monatelange Arbeit ohne Zögern in die Tonne haue. Doch keine dieser Änderungen hätte mit der STL beschleunigt werden können.
Wenn geändert wird, dann ist die Frage 'Array oder Liste?' absolut bedeutungslos.

Designänderung != Fehler korrigieren. Die anforderungen können sich einfach geändert haben(soll ja vorkommen), und die solln dann mal eben schnell eingebaut werden.
Es kann aber auch ein einfaches: "Der algorithmus aus projekt a passt perfekt hier rein, nur der container ist anders" sein.
Ich finds immer cool, wenn ich ne halbwegs komplexe funktion wiederverwenden kann, ohne mich nochmal damit befassen zu müssen, wie genau sie aufgebaut ist(und das müsste ich, wenn ich sie neu anpassen müsste).

[lemonhead]

finix schrieb:

lemonhead schrieb:

Wenn ich die Daten alle nacheinander einlese, kann ich auch gleichzeitig schon feststellen was das Minimum ist. Was ich weiter mache, ist dann wohl egal.

Zonk. *minimum_it += 42;

? meine worte = 42

finix schrieb:

lemonhead schrieb:

- Wenn ich vorher die Anzahl der Eingabewerte schon kenne, dann kann ich einfach einen simplen array verwenden. Damit bin ich insgesamt aber weniger flexibel, und es verleitet dazu zuviel selber herum zu basteln.

Kannst du kurz erklären was du hier mit dem zweiten Satz meinst?

Wenn du ein Array hast, dann willst du doch trotzdem gern die Anzahl der Elemente speichern. Eventuell fallen dir noch eine Menge Sachen ein die dein selbst gebasteltes Array können soll. Dabei passieren dann Fehler.

finix schrieb:

lemonhead schrieb:

- Bei std::list<double> kann man auch zwischendrin Elemente einfügen, und vor allem einzelne Elemente löschen. Sie kostet aber im allgemeinen mehr Speicher als ein Array, und ist etwas schwerfälliger.

"Schwerfälliger"?

Es dauert etwas länger darin zu iterieren, verglichen mit einem Array/stl::vector. Und man hat kein random access.

finix schrieb:

lemonhead schrieb:

- Es gibt noch weitere Möglichkeiten (zB map), aber das reicht jetzt mal.

Für eine Menge?

Für eine Menge nehme ich ein set oder multiset. Eine map könnte zum Beispiel sinnvoll sein wenn ich O(log n) zugriffszeit haben will , elemente zwischendrin hinzufügen und löschen, und eine festgelegte reihenfolge habe. dann muss die datensammlung aber irgendeinen aspekt haben den man als key benutzen kann.
Aber eigentlich war das ja nur so am rande erwähnt. hat keine bedeutung.

finix schrieb:

lemonhead schrieb:

Für mal-eben-schnell-das-minimum-finden empfehle ich da ganz klar die for-Schleife, da sieht man sofort wie verglichen wird.

Wo ist da der Unterschied zu std::min_element ?

Es geht hier um non-standard Datentypen ohne vordefinierte "<" Beziehung. Da muss man entweder einen Vergleichsfunktor übergeben, oder den "<" Operator überladen. Beides ist irgendwie umständlich, wenn man nur einmal das Minimum finden muss.

finix schrieb:

lemonhead schrieb:

Warum sortieren?

Ja genau, warum? Vielleicht geht es um eine Sequenz?

Irgendwo im tunnel hat einer sortieren gesagt. Das ist nur mein Echo

[lemonhead]

otze schrieb:

ZONK! schau dir nochmal deine Schleife an die arbeitet mit indexen und dem operator[]. nicht viele Listen unterstützen das . Im gegensatz zum iterator der zumindest von allen stl containern+dem standard array verfügbar ist .
Das Problem ist einfach, dass sich dann so kleine änderungen durch den kompletten code ziehen. Und jedes nachträgliche ändern und anpassen ist fehleranfällig (wenn nicht sogar fehleranfälliger).

Das mit dem Code ändern ist auf jeden Fall ein gutes Argument.

Ich glaube das mit dem operator [] bei Xin sollten wir jetzt nicht auf die Goldwaage legen, ich denke er wollte da auf die Grundidee hinaus daß man die Werte alle durchlaufen muss. Bei einer Liste würde man da eben einen Iterator verwenden. Und selbst bei arrays wäre ein Iterator bzw pointer etwas schneller, denke ich. Damit sähe die Schleife auf jeden Fall komplizierter aus als der Aufruf von min_element. Aber da liegt natürlich auch der Punkt mit dem Code ändern. Oder doch nicht?

MyContainer my_container;
Data minvalue = ...;
for(MyContainer::iterator it=my_container.begin(); it!=my_container.end(); ++it) {
    if(...) ...;
}

Den einzigen Vorteil sehe ich nur noch in der Sache mit dem Vergleichsoperator.

[hustbaer]

THX 1138 schrieb:

hustbaer schrieb:

Wenn er weiss wie man es selbst ausprogrammiert, aber wissen möchte ob's nicht was "fertiges" gibt um genau so eine Schleife zu ersetzen dann ist "min_element" die "richtige" Antwort.

becks21 schrieb:

Hallo!
Ich hab mehrere Werte und ich muss das Minimum der Werte herausfinden, gibt's da eine Funktion oder muss ich das selbst programmieren?

Ich denke, die Frage war klar: "Gibs da nich was fertiges?" Und diese Frage stellt man sich als Anfänger oft.
(...)

Ups, das wusste ich nimmer. Und war zu faul nachzusehen *pfeiff*. Sorry

[Xin]

otze schrieb:

Xin schrieb:

Machst Du im Zuge der Entwicklung aus dem Array eine Liste, muss das Ergebnis nicht unbedingt suboptimal sein, ist die Frage, wie die Liste implementiert ist.

ZONK! schau dir nochmal deine Schleife an die arbeitet mit indexen und dem operator[]. nicht viele Listen unterstützen das ;).

Ich arbeite selten mit der STL, da ich mir ein eigenes Framework gebastelt habe. Nein, es ist nicht STL kompatibel, ja, ich weiß, dass darin Fehler sein könnten, nein, es ist getestet und funktioniert einwandfrei, ja ich habe meine Gründe und ja, operator[] ist in allen Array und Listencontainern auch implementiert, ebenso wie Iteratoren.

Aber wie schon anderswo geschrieben, geht es um die Bedeutung der Zeilen, nicht dass die Zeilen exakt so ausformuliert sein müssen. Statt operator[] ist ein .Get() oder sonstwas durchaus akzeptiert.

otze schrieb:

Designänderungen für die Zukunft plane ich in der Regel nicht, sonst hätte das Design schon von vornerein einen Fehler.
Wenn es mich trifft, trifft es mich hart und das merke ich mir auch für's nächste Mal. In manchen privaten Projekten bin so kompromisslos, dass ich zugunsten einer geringfügig besseren Lösung auch wochen- und monatelange Arbeit ohne Zögern in die Tonne haue. Doch keine dieser Änderungen hätte mit der STL beschleunigt werden können.
Wenn geändert wird, dann ist die Frage 'Array oder Liste?' absolut bedeutungslos.

Designänderung != Fehler korrigieren. Die anforderungen können sich einfach geändert haben(soll ja vorkommen), und die solln dann mal eben schnell eingebaut werden.

Das Wechseln eines Containers ist keine Fehlerkorrektur, sondern eine Änderung im Design.

otze schrieb:

Es kann aber auch ein einfaches: "Der algorithmus aus projekt a passt perfekt hier rein, nur der container ist anders" sein.
Ich finds immer cool, wenn ich ne halbwegs komplexe funktion wiederverwenden kann, ohne mich nochmal damit befassen zu müssen, wie genau sie aufgebaut ist(und das müsste ich, wenn ich sie neu anpassen müsste).

Bei einem Dreizeiler suche ich nicht erst bereits geschriebene Klassen ab. Bis ich das gefunden habe, habe ich den Dreizeiler neugeschrieben.
Bis ich das als sauber und ausreichend abstrakt in meinem Framework abgelegt habe und durchdokumentiert habe... so oft kann ich ein Minimum im Leben gar nicht suchen...
Um die Templates dann wieder auf das spezielle Problem zu beschreiben... das wird auch nicht kürzer, als die drei Zeilen direkt zu schreiben.
Da spare ich mir die zusätzlichen Abhängigkeiten zwischen den Dateien lieber.

[Jester]

lemonhead schrieb:

Den einzigen Vorteil sehe ich nur noch in der Sache mit dem Vergleichsoperator.

Okay, wenn die Vergleichsfunktion einfach ist, dann mag es evtl nett sein die direkt hinzuprogrammieren. Aber wenn der Vergleich ein bißchen komplizierter ist schätze ich durchaus die Möglichkeit dem Komparator nen schönen Namen zu geben, der ausdrückt wonach er vergleicht.

@Xin: Der Unterschied zwischen Array und vector ist mir auch klar. Ich meinte den Vergleich zwischen: "Schleife arbeitet auf Datenstruktur" "min_element arbeitet auf der selben Datenstruktur". Da ist nix schneller. Das kann man ganz objektiv mal feststellen. Natürlich macht es keinen Sinn die beiden Möglichkeiten mit unterschiedlichen Datenstrukturen zu vergleichen.

[finix]

lemonhead schrieb:

finix schrieb:

lemonhead schrieb:

Für mal-eben-schnell-das-minimum-finden empfehle ich da ganz klar die for-Schleife, da sieht man sofort wie verglichen wird.

Wo ist da der Unterschied zu std::min_element ?

Es geht hier um non-standard Datentypen ohne vordefinierte "<" Beziehung. Da muss man entweder einen Vergleichsfunktor übergeben, oder den "<" Operator überladen. Beides ist irgendwie umständlich, wenn man nur einmal das Minimum finden muss.

Ja, da hast du Recht. Allerdings denke dass solche Fälle < .x% ausmachen; wenn es den Begriff Minimum von foo gibt, dann wird in aller Regel eine Relation von foo oder foo.bar auch sonst irgendwie sinnvoll sein.