1D Peak Finder



  • Hallo zusammen,

    ein Element einer Sequenz an der Position x sei ein peak, wenn gilt:

    und
    . Für die beiden Randfälle ist jeweils nur der eine Nachbar zu betrachten.

    Ich habe eine Funktion geschrieben, die angeblich einen Peak in einer Sequenz findet (Außer für eine leere, da gibt es end() zurück).

    Ich denke dass ist nicht gerade der schwerste Algorithmus, würde mich trotzdem interessieren wie andere meine Umsetzung finden (ich habe versucht das STL design mit den Iteratoren anzuwenden). Würdet ihr hier Rekursion oder eine Schleife verwenden?

    #include <iostream>
    #include <vector>
    #include <sstream>
    
    template<typename Iter>
    Iter find1Dpeek(Iter begin, Iter end)
    {
        if (begin == end) return end;             // empty sequence
        else if (begin + 1 == end) return begin;  // 1 element
        else if (begin + 2 == end)                // 2 elements
        {
            if (*begin >= *(begin + 1)) return begin;
            return begin + 1;
        }
        auto mid = begin + (end - begin) / 2;
        if (*(mid - 1) >= *mid)
        {
            return find1Dpeek(begin, mid);
        }
        else if (*(mid + 1) >= *mid)
        {
            return find1Dpeek(mid, end);
        }
        else
        {
            return mid;
        }
    }
    
    bool read_int_seq_into(std::istream& in, std::vector<int>& seq)
    {
        std::string line;
        if (!std::getline(in, line)) return false;
        std::istringstream stream(line);
        for (int num; stream >> num; )
            seq.emplace_back(num);
        return true;
    }
    
    int main()
    {   
        using namespace std;
        cout << "1D Peak Finder\n";
        std::vector<int> vec;
        cout << "Please enter a sequence of ints:\n> ";
        while (read_int_seq_into(cin, vec))
        {
            auto found = find1Dpeek(vec.begin(), vec.end());
            if (found != vec.end())
                cout << "peak: " << *found << '\n';
            else
                cout << "no peak found.\n";
            cout << "Please enter a sequence of ints:\n> ";
            vec.clear();
        }
    
        return 0;
    }
    

    Das ganze noch in ein kleines Programm verpackt, zum input testen.

    lg


  • Mod

    Kommt mir ungeheuer umständlich und eingeschränkt vor. Wieso nicht einfach durchiterieren und das Kriterium prüfen? Was hat dich geritten, da Rekursion einzubauen?



  • SeppJ schrieb:

    Kommt mir ungeheuer umständlich und eingeschränkt vor. Wieso nicht einfach durchiterieren und das Kriterium prüfen? Was hat dich geritten, da Rekursion einzubauen?

    O(n) vs O(log(n)) Komplexität, wenn ich mich nicht irre. Soll zumindest in der Theorie die "divide and conquer" Methode sein.


  • Mod

    HarteWare schrieb:

    SeppJ schrieb:

    Kommt mir ungeheuer umständlich und eingeschränkt vor. Wieso nicht einfach durchiterieren und das Kriterium prüfen? Was hat dich geritten, da Rekursion einzubauen?

    O(n) vs O(log(n)) Komplexität, wenn ich mich nicht irre. Soll zumindest in der Theorie die "divide and conquer" Methode sein.

    Blödsinn. Die Werte sind doch nicht geordnet. Und wenn sie geordnet wären, bräuchtest du nicht suchen. Du stocherst hier bloß zufällig im Nebel rum, bis du etwas findest.


  • Mod

    SeppJ schrieb:

    Blödsinn. Die Werte sind doch nicht geordnet. Und wenn sie geordnet wären, bräuchtest du nicht suchen. Du stocherst hier bloß zufällig im Nebel rum, bis du etwas findest.

    Oder hast du verschwiegen, dass bei deiner Sequenz aus s[N] >= S[N+1] auch S[N] >= S[M] für M>N folgt (und umgekehrt)? Das wäre eine extrem wichtige Zusatzinformation!



  • SeppJ schrieb:

    HarteWare schrieb:

    SeppJ schrieb:

    Kommt mir ungeheuer umständlich und eingeschränkt vor. Wieso nicht einfach durchiterieren und das Kriterium prüfen? Was hat dich geritten, da Rekursion einzubauen?

    O(n) vs O(log(n)) Komplexität, wenn ich mich nicht irre. Soll zumindest in der Theorie die "divide and conquer" Methode sein.

    Blödsinn. Die Werte sind doch nicht geordnet. Und wenn sie geordnet wären, bräuchtest du nicht suchen. Du stocherst hier bloß zufällig im Nebel rum, bis du etwas findest.

    Ich beziehe mich auf das erste Video aus dem MIT OCW 6006 Kurs. Deshalb komme ich überhaupt auf diese Aufgabe, einfach um Grundlagen aufzubauen.

    Hier der Link (24:45) : http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding/

    Vielleicht habe ich etwas wichtiges übersehen, werds mir morgen nochmal anschauen.

    s[N] >= S[N+1] auch S[N] >= S[M] für M>N folgt (und umgekehrt)?

    Kann ich mich nicht daran erinnern, dass es so wäre. (Also wenn an der Stelle n + 1 etwas größeres kommt, dann kann trotzdem n + 2 wieder kleiner sein) -> so mein bisheriges Verständnis.


  • Mod

    HarteWare schrieb:

    Hier der Link (24:45) : http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding/

    Der gute Mann macht Annahmen über die Verteilung der Zahlen, ohne diese Annahmen ausdrücklich beim Namen zu nennen. Ich mache natürlich auch gewisse Annahmen über die Art Verteilung Zahlen (nämlich dass seine Annahmen die Ausnahme sind), wenn ich sage, dass die Idee Unsinn ist.


  • Mod

    SeppJ schrieb:

    HarteWare schrieb:

    SeppJ schrieb:

    Kommt mir ungeheuer umständlich und eingeschränkt vor. Wieso nicht einfach durchiterieren und das Kriterium prüfen? Was hat dich geritten, da Rekursion einzubauen?

    O(n) vs O(log(n)) Komplexität, wenn ich mich nicht irre. Soll zumindest in der Theorie die "divide and conquer" Methode sein.

    Blödsinn. Die Werte sind doch nicht geordnet. Und wenn sie geordnet wären, bräuchtest du nicht suchen. Du stocherst hier bloß zufällig im Nebel rum, bis du etwas findest.

    Wenn du sicher bist, sollte es nicht schwer fallen ein Beispiel zu konstruieren, bei dem der Algorithmus versagt?


  • Mod

    camper schrieb:

    SeppJ schrieb:

    HarteWare schrieb:

    SeppJ schrieb:

    Kommt mir ungeheuer umständlich und eingeschränkt vor. Wieso nicht einfach durchiterieren und das Kriterium prüfen? Was hat dich geritten, da Rekursion einzubauen?

    O(n) vs O(log(n)) Komplexität, wenn ich mich nicht irre. Soll zumindest in der Theorie die "divide and conquer" Methode sein.

    Blödsinn. Die Werte sind doch nicht geordnet. Und wenn sie geordnet wären, bräuchtest du nicht suchen. Du stocherst hier bloß zufällig im Nebel rum, bis du etwas findest.

    Wenn du sicher bist, sollte es nicht schwer fallen ein Beispiel zu konstruieren, bei dem der Algorithmus versagt?

    Allgemein:
    Unabhängige, zufällige Zahlen. Dann ist iteratives Durchgehen O(1) und HarteWares Vorgehen ist weiterhin O(log(n)). HarteWares Vorgehen ist dann gut, wenn die Zahlen "stetig" sind (ja, es sind diskrete Werte, aber wir wissen, was gemeint ist).
    edit: Ich habe nicht richtig geguckt. HarteWare steigt ja nur dann ab, wenn die Zahl lokal nicht passt. In dem Fall ist auch er bei Zufallszahlen bei O(1). Dann passt meine Behauptung nicht und sein Vorgehen ist tatsächlich stets besser.


Log in to reply