Felder auf Gleichheit überprüfen

[HarteWare]

Ich bin jetzt verwirrt... Es ist also doch am schnellsten mit std::sort (wenn man std::sort, std::map und std::unordered_map betrachtet)?

P.S.: @hustbaer In Deinem Post fehlt glaub noch oben (aber ist ja nicht so wichtig...)

std::sort[100]

---

integer_sort is a fast templated in-place hybrid radix/comparison algorithm

Spreadsort - integer sort

[Finnegan]

@HarteWare sagte in Felder auf Gleichheit überprüfen:

Ich bin jetzt verwirrt... Es ist also doch am schnellsten mit std::sort (wenn man std::sort, std::map und std::unordered_map betrachtet)?

Für Vektoren bis etwa 68 Millionen ($2^{26}$) ints definitiv ja. Weiter nicht getestet, da die unordered_mapdafür schon etwa 2 Minuten brauchte (vs. 10 Sekunden mit std::sort).

Zumindest in der Theorie sollten die sich aber irgendwann treffen bei $n = 2^c$ ($\Leftrightarrow cn=n\log_2 n$) für irgendein konstantes $c$. Wenn ich raten müsste, würde ich das $c$ irgendwo in der Größenordnung von 300 verorten ($2^{26}c /120\text{ Sekunden}=2^{26} \log_2 2^{26}/10\text{ Sekunden}\Leftrightarrow c=312$).

Sollte das tatsächlich stimmen, braucht man viel Zeit, eine Menge RAM und ne neue CPU-Architektur die den adressieren kann.
... kann aber auch sein, dass ich grad halbgaren Bullshit phantasiere

[hustbaer]

@HarteWare

Es ist also doch am schnellsten mit std::sort (wenn man std::sort, std::map und std::unordered_map betrachtet)?

Korrekt.

In Deinem Post fehlt glaub noch oben (aber ist ja nicht so wichtig...)

std::sort[100]

Ebenso korrekt. Ich hab' beim Kopieren wohl nicht weit genug hinaufgescrollt und zu wenig kopiert. Es fehlen auch noch alle 4 Einträge mit [10]. Aber ja, sollte reichlich egal sein, denn auch da schlagen beide Sorts beide Maps.