vorletztes Element eines vector<T> ermitteln



  • kkaw schrieb:

    v.end()[-1]

    äh ... -2 für das VORetzte.


  • Mod

    Arcoth schrieb:

    -1[&v.back()]
    

    eher nicht.



  • std::vector<T>(original.begin(), original.end() - 1).back()
    


  • std::vector<int> v = ...;
    std::vector<int> idx(v.size()); std::iota(idx.begin(), idx.end(), 0);
    int n=1; for (int i=1; i<=v.size(); ++i) n*=i;
    int m = n - n/v.size()-1;
    while (m--) std::next_permutation(idx.begin(), idx.end());
    std::cout << *std::next(v.begin(), idx.front()) << '\n';
    


  • auto index = vector.size();
    while (index != vector.size() - 2)
      index = std::rand();
    auto el = vector[index];
    


  • Nathan schrieb:

    auto index = vector.size();
    while (index != vector.size() - 2)
      index = std::rand();
    auto el = vector[index];
    

    Wie ist eigentlich die theoretische Laufzeitkomplexität hierbei?


  • Mod

    Ich tippe auf O(1).


  • Mod

    Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.



  • Arcoth schrieb:

    Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.

    wieso sollte worst case nicht ∞ sein? average case dürfte O(n) sein.


  • Mod

    asfdlol schrieb:

    Arcoth schrieb:

    Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.

    wieso sollte worst case nicht ∞ sein?

    Ist das eine gültige Laufzeitkomplexität?

    average case dürfte O(n) sein.

    Das ist nicht möglich. rand() ist gleichmäßig verteilt, d.h. es macht keinen Unterschied welches N wir wählen, es wird im Durchschnitt die gleiche Anzahl Schritte benötigt.



  • Arcoth schrieb:

    asfdlol schrieb:

    Arcoth schrieb:

    Im Prinzip kann dafür ja keine worst-case-complexity gegen werden, obiges ist daher also average-case-complexity.

    wieso sollte worst case nicht ∞ sein?

    Ist das eine gültige Laufzeitkomplexität?

    ob es eine gültige notation ist weiss ich nicht, jedoch liegt die lösung inhaltlich sehr nahe.

    Arcoth schrieb:

    average case dürfte O(n) sein.

    Das ist nicht möglich. rand() ist gleichmäßig verteilt, d.h. es macht keinen Unterschied welches N wir wählen, es wird im Durchschnitt die gleiche Anzahl Schritte benötigt.

    ups, du hast recht. ich hab unsorgfältig gelesen dachte, dass die zufallszahl auf .size() begrenzt wird.



  • Die durchschnittliche Anzahl der Schleifendurchläufe ist RAND_MAX.

    Zum Rest siehe http://en.wikipedia.org/wiki/Randomized_algorithm



  • Ich weise noch darauf hin, dass eine asymptotische Laufzeitkomplexität für den rand-Algorithmus unsinnig ist, da er nur für maximal RAND_MAX Einträge funktioniert. Für eine begrenzte Anzahl Eingaben ist jeder Algorithmus O(1). Falls da ::rand()%vector.size() stehen würde (was es sollte), wäre er O(n).


  • Mod

    Falls da std::rand()%vector.size() stehen würde

    FTFY



  • camper schrieb:

    Arcoth schrieb:

    -1[&v.back()]
    

    eher nicht.

    Wieso nicht 😕
    Ist doch das selbe was du geschrieben hast, nur halt nach A[B] == B[A] anders rum hingeschrieben ... nicht?

    Oder darf v.back() immer nen Proxy zurückliefern, auch wenn T != bool ?



  • Nathan schrieb:

    auto index = vector.size();
    while (index != vector.size() - 2)
      index = std::rand();
    auto el = vector[index];
    

    Wenn du hier ne "Generator-Variable" statt std::rand verwenden würdest, die weder bei der Initialisierung noch beim "Ziehen" was macht was nicht-lokale, beobachtbare Effekte hat...
    ...dann sollten das aktuelle Compiler sogar wegoptimieren.



  • Ihr seid alle wahnsinnig.

    ...

    assert(v.size() > 1);
    
    using std::begin;
    using std::end;
    using std::next;
    using std::random_shuffle;
    using std::is_sorted;
    
    auto target = v[v.size() - 2];
    do {
      random_shuffle(begin(v), end(v));
    } while(!is_sorted(next(begin(v)), end(v)) || target != v.front());
    
    auto result = v.front();
    


  • Wundere mich gerade etwas...
    Hab folgendes mit GCC 4.8, 4.9 (experimental) und Clang 3.2 und 3.3 probiert (über http://gcc.godbolt.org/):

    int before_last(int const* v, int s)
    {
    	int i = s; 
    	while (i != s - 2) 
    		i = i * 48271 % 2147483647;
    	return v[i ]; // WTF? Ohne dem Plenk stünde da:
    //	return v;
    }
    
    int main()
    {
      int foo[] = {1, 2, 3};
      return before_last(foo, 3);
    }
    

    Nur mit -O3 , ohne -funsafe-loop-optimizations , traut sich sowieso keiner drüber.

    Mit -funsafe-loop-optimizations kann GCC 4.8 alles in main() inlinen. Erzeugt aber zusätzlich eine non-inline before_last() Implementierung wo der Loop wirklich noch drinnen ist.
    GCC 4.9 20130909 checkt das dann auch noch: sowohl main() als auch die non-inline before_last() enthalten keinen Loop mehr.
    Clang lässt sich gar nicht überreden den Loop wegzulassen (es sei denn der nötige Switch heisst dort anders).

    Nach dem wie die ganzen Compiler-Leute nicht müde wurden zu betonen, wie wichtig so Dinge wie die "must make progress" Regel sind, weil sie [i]sooooo viele* schöne Optimierungen ermöglichen... hätte ich mir mehr erwartet.

    Falls das jmd. mit nem aktuellen Clang probieren könnte... fände ich interessant.

    Achja, der Output von GCC 4.9:

    before_last(int const*, int):
    	sub	esi, 2
    	movsx	rsi, esi
    	mov	eax, DWORD PTR [rdi+rsi*4]
    	ret
    main:
    	mov	eax, 2
    	ret
    

  • Mod

    @hustbaer: Ja, das Problem ist, dass da steht -(1[&v.back()]) . Ich war schon so stolz.



  • seldon schrieb:

    Ihr seid alle wahnsinnig.

    ...

    do {
      random_shuffle(begin(v), end(v));
    } while(!is_sorted(next(begin(v)), end(v)) || target != v.front());
    

    Wird echt mal Zeit für eine std::very_slow


Anmelden zum Antworten