vorletztes Element eines vector<T> ermitteln
-
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.
-
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).
-
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 nachA[B] == B[A]
anders rum hingeschrieben ... nicht?Oder darf
v.back()
immer nen Proxy zurückliefern, auch wennT != 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 inmain()
inlinen. Erzeugt aber zusätzlich eine non-inlinebefore_last()
Implementierung wo der Loop wirklich noch drinnen ist.
GCC 4.9 20130909 checkt das dann auch noch: sowohlmain()
als auch die non-inlinebefore_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
-
@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
-
Arcoth schrieb:
@hustbaer: Ja, das Problem ist, dass da steht
-(1[&v.back()])
. Ich war schon so stolz.Achje, Operator precedence. Hmpf.
Dann halt(-1)[&v.back()]
- sieht ja auch nett aus.