Die kleinste von 8 Variablen löschen?

[m.e.]

Andromeda schrieb:

Ich finde es gerade blöd, einen Anfänger zu sehr vor den grundlegen Prinzipien der Computerei abzuschirmen. Aber darüber gibt es ja verschiedene Ansichten.

Ich vermute mal, dass alle Top-Coder ziemlich zu Anfang eine Phase hatten, in der sie sich ausgiebig mit LowLevel-Zeugs und Maschinensprache beschäftigten. Sicher kann man das auch später lernen, aber dann baut man IMHO nicht die Assoziationen auf, die für ein Tiefenverständnis wichtig sind.

Andromeda schrieb:

Vectors, Queues, und ähliches Zeug haben immer einen gewissen Verwaltungsaufwand. Oft stecken verkette Listen dahinter.

Mein Gott, ist dir das nicht selbst peinlich? Aber schon wieder gut beim Bullshitbingo dabei ("Cantors Mengenlehre").

[Andromeda]

m.e. schrieb:

Andromeda schrieb:

Ich finde es gerade blöd, einen Anfänger zu sehr vor den grundlegen Prinzipien der Computerei abzuschirmen. Aber darüber gibt es ja verschiedene Ansichten.

Ich vermute mal, dass alle Top-Coder ziemlich zu Anfang eine Phase hatten, in der sie sich ausgiebig mit LowLevel-Zeugs und Maschinensprache beschäftigten. Sicher kann man das auch später lernen, aber dann baut man IMHO nicht die Assoziationen auf, die für ein Tiefenverständnis wichtig sind.

Andromeda schrieb:

Vectors, Queues, und ähliches Zeug haben immer einen gewissen Verwaltungsaufwand. Oft stecken verkette Listen dahinter.

Mein Gott, ist dir das nicht selbst peinlich?

Was stört dich daran?

[volkard]

wob schrieb:

Man ändert nicht nur die Reihenfolge (was bei der gestellten Aufgabe möglicherweise sogar in Ordnung wäre), sondern man muss auch die Größe von Hand tracken. Das wurde zwar von volkard verneint, aber ich frage mich, wo dann bei ihm im selben Post die Zahlen 8 und 7 herkommen (wenn er mal nicht doch die Größe trackt...) - ich hasse jedenfalls irgendwelche wilden hardgecodeten Zahlen im Programm.

Unter "tracken" verstehe ich das Mitführen in Variablen wie "arrCount--" und "arrCount++" jedes mal, wenn sich die Anzahl der gültigen Werte ändert.
Unter "nicht tracken" verstehe ich, wie in der Aufgabenstellung verlangt, genau vorher 8 und nachher 7 zu haben. Ich nehme an, er weiß genau, weshalb er vorher 8 hat, weils zum Beispiel in den Spielregeln des Kartenspiels, was er proggert genau so steht. Dann muss man nicht den Code so verallgemeinern, daß im Prinzip ein Schachbrett 121 Felder haben könnte, und man wegen sogfältigen Designs sofort anpassen kann, wenn die FIDE die Regeln ändert.
Klar, Du hast vollkommen recht, wenns irgendwie um was anderes als wörtliche Verfolgung der Aufgabenstellung geht. Niemals nie darf man es sich so einfach machen, wenn der Kunde im Vertrag bestellt hat, daß die Zooverwaltung genau 8 Tiere hat und man das mit am wenigsten Fleisch verkaufen will. Selbst wenn er den Vertrag mit Blut unterschreibt, es ist ein Naturgesetz, daß nachdem der Zoowärter die Probleme dem Zooeinkäufer und der dem Softwareverkäufer und der dem Softwareentwickler es gesagt hat, daß 90% des Gemeinten auf der Strecke geblieben ist und nach Fertigstellung verlangt wird, daß auf Kulanz 9 Tiere möglich sind. Du hast es aus Erfahrung richtig gemacht; sich einfach nicht belabern lassen.
Hier ging ich davon aus, daß die 8 aber stabil ist.

[m.e.]

Andromeda schrieb:

m.e. schrieb:

Andromeda schrieb:

Ich finde es gerade blöd, einen Anfänger zu sehr vor den grundlegen Prinzipien der Computerei abzuschirmen. Aber darüber gibt es ja verschiedene Ansichten.

Ich vermute mal, dass alle Top-Coder ziemlich zu Anfang eine Phase hatten, in der sie sich ausgiebig mit LowLevel-Zeugs und Maschinensprache beschäftigten. Sicher kann man das auch später lernen, aber dann baut man IMHO nicht die Assoziationen auf, die für ein Tiefenverständnis wichtig sind.

Andromeda schrieb:

Vectors, Queues, und ähliches Zeug haben immer einen gewissen Verwaltungsaufwand. Oft stecken verkette Listen dahinter.

Mein Gott, ist dir das nicht selbst peinlich?

Was stört dich daran?

Ach, gar nichts. Ich habe den Fehler gemacht anzunehmen, dass man dich Troll nur im NadrW-Forum ignorieren sollte.

[Andromeda]

m.e. schrieb:

Ach, gar nichts.

Du willst also nur Stunk machen.
Mach nur. Ich bin unempfänglich für sowas.

m.e. schrieb:

Ich habe den Fehler gemacht anzunehmen, dass man dich Troll nur im NadrW-Forum ignorieren sollte.

Ach so ist das. Du bist einer von den rechten Hatern dort.
Na, dann wundert mich dein Verhalten nicht.

[wob]

Andromeda schrieb:

Vectors, Queues, und ähliches Zeug haben immer einen gewissen Verwaltungsaufwand. Oft stecken verkette Listen dahinter.

m.e. meinte sicher, dass du irgendwie vector und verkettete Listen zusammenbringst, wo vector das genau NICHT ist.

Deine andere genannte Datenstruktur, nämlich die Queue, ist im ist auch nicht viel besser. std::queue hat, wie man nachlesen kann, std::deque als Default-Container. Wie deque implementiert wird, ist nicht vorgeschrieben, aber http://www.cplusplus.com/reference/deque/deque/ sagt:

Specific libraries may implement deques in different ways, generally as some form of dynamic array.

Hört sich auch nicht direkt nach einer verketteten Liste an... Aber gut, du hast ja nur geschrieben, dass es "oft" verkettete Listen sind, für welche Definition von "oft" auch immer. Wahrscheinlich bezieht sich das "oft" auf "ähnliches Zeug", nehme ich mal zu deinen Gunsten an...

[volkard]

wob schrieb:

Andromeda schrieb:

Vectors, Queues, und ähliches Zeug haben immer einen gewissen Verwaltungsaufwand. Oft stecken verkette Listen dahinter.

m.e. meinte sicher, dass du irgendwie vector und verkettete Listen zusammenbringst, wo vector das genau NICHT ist.

Deine andere genannte Datenstruktur, nämlich die Queue, ist im ist auch nicht viel besser. std::queue hat, wie man nachlesen kann, std::deque als Default-Container. Wie deque implementiert wird, ist nicht vorgeschrieben, aber http://www.cplusplus.com/reference/deque/deque/ sagt:

Specific libraries may implement deques in different ways, generally as some form of dynamic array.

Hört sich auch nicht direkt nach einer verketteten Liste an... Aber gut, du hast ja nur geschrieben, dass es "oft" verkettete Listen sind, für welche Definition von "oft" auch immer. Wahrscheinlich bezieht sich das "oft" auf "ähnliches Zeug", nehme ich mal zu deinen Gunsten an...

Das erinnert mich daran, daß ich neulich im Zuge eines C++-Kurses nebenbei mit der Gruppe zusammen std::vector als Vector reimplementiert hatte, minimal nur mit op[] und push_back()/pop_back() und auf win UND linux ca 50% je mit maximaler Optimierung schneller war als std:: mit ebendieser. Es hätte den Zeitrahmen gesprengt, das zu ergründen.
Ich hab auch keinen Bock mehr nachzujagen, wo irgendwelche Standard-Bibliotheken welche Schwächen haben. Den Apparat hat man ja in ein oder zwei Bildschirmen getippselt und redet dann mit dem Compiler und der macht es gut.

Ich vertraue std::-Sachen erstmal gar nicht mehr. Heute einen Tokenizer gebaut, der 100-mal (auf Win) so schnell wie std::ifstream/std::string liest. Und er ist einfacher zu bedienen.

Einfach es stets so machen und ausdrücken, wie man es als Mensch auf Papier machen würde. Zappzarrapp, braucht man viel weniger geheime Informatikertricks (die ich alle schon gelangweilt kenne, die Du kennst) und viel weniger Debugging ist nötig (in angespannter Lage eine Zeile pro Monat Rückläufer) und performant isses auch (Faktor >100 ebenheute).

Mir mißfällt es wirklich ganz massiv, wenn Halbinformatiker es zum Gesetz erheben, daß es neben der std:-Bibliothek keine anderen Götter geben darf. Es ist leicht, einen Fall zu haben, wo std:: lahm und dumm und fehleranfällig ist im Gegensatz zum Papier-Ansatz. Dieses ewige "Nur mit std::vector" ist es "C++" nervt mich. "C++" ist es, wenn es maximal kundenauslieferungsfehlersicher ist, optimale Performace ist Bonus. Beide Ziele sind supi harmonisch: Proggern ist nunmal kein Ponyhof, sonst hätten wir schon eine Proggerbot in LEGO gebaut.

[Andromeda]

wob schrieb:

Wahrscheinlich bezieht sich das "oft" auf "ähnliches Zeug", nehme ich mal zu deinen Gunsten an...

Du musst nichts zu "meinen Gunsten" annehmen. In puncto C++ bin ich ein wahrer Noob und darf mir Fehler erlauben.

Btw, mein Vorschlag:

#define DELETED -1
int delSmallest (int *arr, int size)
{
    int idx = 0;
    int min = INT_MAX;  // limits.h
    int s;
    for (s=0; s<size; s++)
    {
        if (arr[s] < min)
        {
            min = arr[s];
            idx = s;
        }
    } 
    arr[idx] = DELETED;
    return idx;
}

"Löscht" das erste Vorkommen des kleinsten Wertes in einem int-Array.
Ist doch mega-simpel, oder?

[wob]

@Andromeda: Das ist doch wieder das in-band-Signaling. Mit all seinen Problemen.

zu: #define DELETED -1 : Das ist definitiv C. Warum als Macro in C++? --> constexpr auto DELETED = -1;
Und zu int delSmallest (int *arr, int size) lies mal bitte: https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Ri-array
Insbesondere der erste Satz "(pointer, size)-style interfaces are error-prone." sagt eigentlich alles.

@volkard:
hast du dir schon einmal https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md angeschaut? In der Beschreibung heißt es "The improvements are always non-negative, almost always measurable, frequently significant, sometimes dramatic, and occasionally spectacular." Insbesondere sagt Facebook, dass der Wachstumsfaktor in std::vector zu groß ist. Wie hast du das gemacht? (ansonsten ergibt sich immer noch die Frage, ob man ein Objekt einfach mit memmove umkopieren darf oder ob man constructor&destruktor aufrufen muss. Hast du das in deiner Klasse alles beachtet?)

Und allgemein: ich habe mit google::dense_hash_map auch schon mal ein Programm um ein Vielfaches gegenüber einer std::unordered_map beschleunigt, ABER im Normalfall tun die std::*-Klassen einen guten Job. Ich nutze was anderes nur dann, wenn es irgendwo Performance-Probleme gibt.

[Andromeda]

wob schrieb:

@Andromeda: Das ist doch wieder das in-band-Signaling. Mit all seinen Problemen.

zu: #define DELETED -1 : Das ist definitiv C. Warum als Macro in C++? --> constexpr auto DELETED = -1;
Und zu int delSmallest (int *arr, int size) lies mal bitte: https://github.com/isocpp/CppCoreGuidelines/blob/master/CppCoreGuidelines.md#Ri-array
Insbesondere der erste Satz "(pointer, size)-style interfaces are error-prone." sagt eigentlich alles.

Ja, natürlich ist mein Code hinsichtlich der C++ best practices völlig suboptimal.

Ich persönlich finde es aber total gut, dass C++ solche Dinge zulässt.
Den "Sprit of C" hat C++ nicht getötet, nur in Ketten gelegt.