Felder auf Gleichheit überprüfen
-
@SeppJ sagte in Felder auf Gleichheit überprüfen:
Faustregel: Sortieren stets vermeiden, außer es geht explizit darum, hinterher eine sortierte Menge zu haben. Sortieren als Zwischenschritt ist nur seltenst nötig, dafür aber sehr kostspielig. Siehe beispielsweise wobs Beitrag für eine viel bessere Umsetzung der gleichen Grundidee.
In eine Map eintragen ist aber auch ein implizites Sortieren. Ist Performance relevant? Wenn wobs Interpretation der Aufgabe gilt, rulft man einfach das hier auf: https://en.cppreference.com/w/cpp/algorithm/is_permutation
-
@SeppJ sagte in Felder auf Gleichheit überprüfen:
Faustregel: Sortieren stets vermeiden, außer es geht explizit darum, hinterher eine sortierte Menge zu haben. Sortieren als Zwischenschritt ist nur seltenst nötig, dafür aber sehr kostspielig. Siehe beispielsweise wobs Beitrag für eine viel bessere Umsetzung der gleichen Grundidee.
Man sollte vielleicht noch erwähnen, dass das nur der Fall ist, wenn es sich bei der map, die wob erwähnt, um eine mit -Zugriffen handelt.
Ansonsten sind beide Lösungen gleich "kostspielig" und die Sortier-Variante mit so etwas simplem wie
return a.size() == b.size() && equal(sort(a), sort(b))
sogar noch kürzer und eleganter.Das mit der Faustregel sehen ich auch nicht so ehern, für geometrische Algorithmen z.B. braucht man das durchaus häufiger. Allerdings finde ich es auch nicht gut, unterschiedslos zu sortieren und diese praktische Eigenschaft nach dem Funktionsaufruf einfach wegzuwerfen. Mir gefiele es besser, wenn "ist sortiert" eine Vorbedingung für die Funktion wäre, so dass bereits sortierte Eingabedaten nicht erneut sortiert werden müssen (was die Funktion dann allerdings zu einem banalen
equal
-Wrapper macht, vielleicht noch mit neris_sorted
-Assertion).Nachtrag:
@TGGC sagte in Felder auf Gleichheit überprüfen:
Wenn wobs Interpretation der Aufgabe gilt, rulft man einfach das hier auf: https://en.cppreference.com/w/cpp/algorithm/is_permutation
Heh, coole Idee - aber die angegebene Laufzeit! Uiui
Ich frage mich gerade warum und obis_permutation
nicht auch mit dem doppelten Sortieren geht. Eventuell problematisch wegen den anderen Iterator-Anforderungen... muss da nochmal drüber nachdenken.
-
@TGGC sagte in Felder auf Gleichheit überprüfen:
@SeppJ sagte in Felder auf Gleichheit überprüfen:
Faustregel: Sortieren stets vermeiden, außer es geht explizit darum, hinterher eine sortierte Menge zu haben. Sortieren als Zwischenschritt ist nur seltenst nötig, dafür aber sehr kostspielig. Siehe beispielsweise wobs Beitrag für eine viel bessere Umsetzung der gleichen Grundidee.
In eine Map eintragen ist aber auch ein implizites Sortieren. Ist Performance relevant? Wenn wobs Interpretation der Aufgabe gilt, rulft man einfach das hier auf: https://en.cppreference.com/w/cpp/algorithm/is_permutation
Ja, da habe ich im Kopf
map
mitunordered_map
gleichgesetzt
Wie es schon buchstäblich im Namen vorkommt, ist dieunordered_map
hier die bessere Wahl, da man die Sortiereigenschaft gar nicht braucht und daher auch nicht teuer bezahlen möchte.
-
Ich hab's BTW gestern ausprobiert: mitunordered_map
ist die Sache auf meinem PC ab bestimmten N tatsächlich schneller als mit Sortieren.EDIT: Ne, sort ist überall schneller, siehe spätere Beiträge.
-
@hustbaer sagte in Felder auf Gleichheit überprüfen:
Ich hab's BTW gestern ausprobiert: mit
unordered_map
ist die Sache auf meinem PC ab bestimmten N tatsächlich schneller als mit Sortieren.Muss es ja. Ich bin eher überrascht, dass es N gibt, bei denen es nicht so ist. Was ist den ungefähr die Größenordnung des N beim Übergang?
-
@hustbaer
Kommt sicher auch auf den genauen Input an, z.B. wenns keine sinnvolle Hashfunktion gibt oder einen eingeschränkten Wertebereich. is permutation braucht weder Hash noch Vergleichsoperator, kann daher diese Aufgabe auf einem abstrakterem Level lösen, gibt aber z.B. nicht aus, welcher int genau fehlt. Daher fällt eine sinnvolle Antwort schwer ohne die Rahmenbedingungen zu kennen. Mein persönlicher Ansatz wäre die std Algorithmen zu nutzen bis es ein Problem damit gibt (z.b. gemessener Bottleneck, weil die Vectoren ständig größer N sind). Dann kann man nochmal nachdenken.
-
@SeppJ
Break-even für)unordered_map<int, int>
vs.2x sort(vector<int>)
ist irgendwo zwischen 1k und 10k, vermutlich im Bereich 2k~5k. (BTW:map<int, int>
ist bis 10M die langsamste Variante, und > 10M hab' ich nicht getestet.Das alleine wundert mich nicht, wundert mich eher noch dass der break-even so früh kommt. So neunordered_map
hat halt doch Overhead: braucht mehr Speicher, muss dauernd Hashwerte berechnen etc. Und ich bin nicht sicher ob der Speicher für die erste "Value" eines Buckets im Table derunordered_map
eingebaut ist. Wenn nicht käme noch eine Allocation pro Value dazu, trotzreserve
.Was aber strange ist: alle drei von mir getesteten Varianten skalieren ab ~10K ziemlich genau linear. Dabei sollten die dochN log N
skalieren.EDIT: Ne, sort ist überall schneller, siehe spätere Beiträge.
Code hab' ich leider nicht zur Hand, bin in der Arbeit, und Code liegt zu Hause. Kann ich heute Abend posten. Ist aber auch in ein paar Minuten selbst geschrieben.
-
@Finnegan sagte in Felder auf Gleichheit überprüfen:
Heh, coole Idee - aber die angegebene Laufzeit! Uiui
Ich frage mich gerade warum und obis_permutation
nicht auch mit dem doppelten Sortieren geht. Eventuell problematisch wegen den anderen Iterator-Anforderungen... muss da nochmal drüber nachdenken.Jede Lösung hat im Grenzfall diese Laufzeit, z.B. wenn alle Werte den gleichen Hash liefern wird die unordererd map alles in einen Bucket einsortieren und dann auch einen Vergleich auf alle Paare aufrufen. Nur wenn man alles mit allem vergleicht kann man am Ende ja sehen, ob auch alles übereingestimmt hat, wenn man nicht durch "Glück" (geschicktes Sortieren, geschicktes Anordnen nach Hash etc.) zufällig direkt die richtigen Sachen vergleicht.
-
@TGGC Ja, es kommt immer auf die genauen Umstände an. Wenn der Fall häufig ist dass die meisten Zahlen in
a
überhaupt nicht inb
vorkommen, dann wirdstd::is_permutation
vermutlich alles andere abhängen. Oder auch wenn die Sequenzen oft identisch sind (also auch identisch sortiert).Ansonsten muss man halt wissen wie wichtig die Performance bei grösseren Inputs ist. Wenn man Grund zur Annahme hat dass
O(N^2)
gut genug sein könnte, spricht sicher nichts dagegen erstmalstd::is_permutation
zu verwenden.
-
@TGGC sagte in Felder auf Gleichheit überprüfen:
@Finnegan sagte in Felder auf Gleichheit überprüfen:
Heh, coole Idee - aber die angegebene Laufzeit! Uiui
Ich frage mich gerade warum und obis_permutation
nicht auch mit dem doppelten Sortieren geht. Eventuell problematisch wegen den anderen Iterator-Anforderungen... muss da nochmal drüber nachdenken.Naja
std::is_permutation
kann IMO nichtmal im Durchschnitt besser als N^2 sein, weil sie vom Value-Type nichts fordert ausser dass man auf Gleichheit testen kann. Ich glaube nicht dass das genug für irgendwelche schlauen Algorithmen ist. Natürlich könnte eine Library-Implementierungstd::is_permutation
für Dinge wie Integers speziell implementieren, aber das ist dann wieder ein anderes Thema. Für generische T muss N^2 mMn. der Normalfall sein und nicht der Grenzfall.Jede Lösung hat im Grenzfall diese Laufzeit
Jede linear schnelle Lösung. Mit Sortieren (z.B. Merge-Sort) oder Bäumchen schafft man problemlos N log N.
-
Ich glaube das ist nicht garantiert, weil das Kriterium der Sortierung ein Anderes als das für Identität sein könnte oder das Ergebnis von > und < komplett unbestimmt.
-
Oh, da hat meine 08/15 Antwort ja noch für Gesprächsstoff gesorgt . Interessant was so über die verschiedenen Möglichkeiten geschrieben wurde. Danke, hab wieder einiges gelernt
-
@TGGC sagte in Felder auf Gleichheit überprüfen:
Ich glaube das ist nicht garantiert, weil das Kriterium der Sortierung ein Anderes als das für Identität sein könnte oder das Ergebnis von > und < komplett unbestimmt.
Und ich glaube dass du damit vollkommen richtig liegst Ich wollte auch gar nicht die Design-Entscheidung kritisieren das so zu machen. Ich wollte nur erklären warum N^2 hier "normal" ist und nicht bloss worst-case.
-
Ich meine mich daran zu erinnern, dass man für Integer in einem begrenzten Wertebereich auch schnellere Sortierverfahren hat (radix sort?). Wie würde es sich damit verhalten?
-
@PeterPanzer31 sagte in Felder auf Gleichheit überprüfen:
if (v1[0] = v2[i] )
ganz böse fehlerquelle btw.
-
@HarteWare Radix-Sort ist dann aber fast schon das selbe wie die hier vorgeschlagene Map-Variante. Nur mit einer weniger effizienten Map-Implementierung, nämlich einem Radix-Tree. Dann lieber gleich (Hash)Map.
-
War neugierig und hab mir auch mal die alte Programmierer-Weisheit zu Herzen genommen (Messen!!!einself!). Gut möglich, dass ich was verbockt habe, aber ich konnte die Überlegenheit der
unordered_map
zumindest bis nicht bestätigen:Vektoren bis
Vektoren bis
Vektoren bisGemessen wurde mit Vektoren, die mit
int
-Werten von 0 bis N-1 gefüllt und dann mittelsstd::shuffle
zufällig permutiert wurden.Quellcode (benötigt Google Benchmark):
benchmark-vecequal.cpp
benchmark-vecequal-64k.cpp (mostly Copy&Paste)
benchmark-vecequal-1k.cpp (mostly Copy&Paste)Vielleicht hat ja jemand von Euch eine Idee, wieso ich auf solche Messwerte komme. Ich tippe darauf, dass ich irgendwo einen Fehler gemacht oder etwas ineffizientes geschrieben habe (
rehash
/reserve
?). Wenn sich dieunordered_map
nichtmal bei lohnt, dann fände ich das schon bemerkenswert, obwohl die schon eine stadtbekannte Cache-Sau ist@hustbaer Wie war das noch mit deinem Code, jetzt am Abend? Den würd ich gern mal vergleichen die Tage.
Nachtrag: Vektoren von 0-1024, weil ich eh noch alles offen hatte. Seltsam schnurgerade das alles und ohne irgendwelche Cache-Hüpfer. Bestärkt mich eher darin, dass etwas nicht stimmt, obwohl es hübsch aussieht. Frage mich auch ob die CPU Time im Gegensatz zur Real Time (Wall Time) der bessere Wert ist. Intuitiv denke ich ja, weil dort weniger OS/Hardware-Aussetzer drin sein sollten.
-
@Finnegan Habs nur mal überflogen. Aber
std::unordered_map<int, int> c; std::for_each(std::begin(a), std::end(a), [&](int v) { ++c[v]; });
scheint mir potentiell schonmal merkwürdig. Sicher dass hier mit 0 initialisiert wird?
-
@DNKpp sagte in Felder auf Gleichheit überprüfen:
scheint mir potentiell schonmal merkwürdig. Sicher dass hier mit 0 initialisiert wird?
Yep: unordered_map::operator[]:
When the default allocator is used, this results in the key being copy constructed from key and the mapped value being value-initialized.
...
value initialization
...
4) otherwise, the object is zero-initialized.
-
@Finnegan
Oops!
Gut dass du das geschrieben hast. Ich hab Mist gebaut...std::vector<MyType> rand_vec(size_t size) { std::default_random_engine engine; engine.seed(123); std::uniform_int_distribution<MyType> distribution(1, 1000); // Oops std::vector<MyType> v; v.reserve(size); for (size_t i = 0; i < size; i++) v.push_back(distribution(engine)); engine.seed(std::random_device{}()); std::shuffle(v.begin(), v.end(), engine); return v; }
Ist dann auch sehr verwunderlich dass der Break-Even bei knapp über 1000 war
Keine Ahnung warum ich da 1000 reingeschrieben hab. Vermutlich weil ich beim Schreiben bloss an diesort
Variante gedacht hab, und für die is das ziemlich wörscht. (Naja, genaugenommen auch da nicht, und der Grund warum nicht erklärt dann auch genau warum ich lineare Skalierung gesehen hab statt N log N -- was jetzt auch nicht mehr der Fall ist... hachjeh.)Wenn man das mit etwas sinnvollerem wie
10 * size
ersetzt sehen die Ergebnisse auf einmal ganz anders aus.Vollständig:
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <unordered_map> #include <random> #include <chrono> #include <stddef.h> typedef int MyType; std::vector<MyType> rand_vec(size_t size) { std::default_random_engine engine; engine.seed(123); std::uniform_int_distribution<MyType> distribution(1, static_cast<MyType>(10 * size)); std::vector<MyType> v; v.reserve(size); for (size_t i = 0; i < size; i++) v.push_back(distribution(engine)); engine.seed(std::random_device{}()); std::shuffle(v.begin(), v.end(), engine); return v; } bool compare_via_sort(std::vector<MyType> a, std::vector<MyType> b) { std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end()); return a == b; } bool compare_via_tmap(std::vector<MyType> const& a, std::vector<MyType> const& b) { std::map<MyType, ptrdiff_t> tmap; for (auto v : a) tmap[v]++; for (auto v : b) tmap[v]--; for (auto e : tmap) if (e.second != 0) return false; return true; } bool compare_via_umap(std::vector<MyType> const& a, std::vector<MyType> const& b) { std::unordered_map<MyType, ptrdiff_t> umap; umap.reserve(a.size() * 2); for (auto v : a) umap[v]++; for (auto v : b) umap[v]--; for (auto e : umap) if (e.second != 0) return false; return true; } volatile bool result_dummy = false; volatile void const* ptr_dummy = nullptr; volatile long long t_dummy = 0; template <class F> long long bench(F f, size_t n) { auto const a = rand_vec(n); ptr_dummy = a.data(); auto const b = rand_vec(n); ptr_dummy = b.data(); using clock = std::chrono::high_resolution_clock; auto const t0 = clock::now(); result_dummy = f(a, b); auto const t1 = clock::now(); auto const dur = t1 - t0; auto const dur_ns = std::chrono::duration_cast<std::chrono::nanoseconds>(dur).count(); t_dummy = dur_ns; return dur_ns; } template <class F> void bench2(F f, size_t n, char const* name) { auto best = std::numeric_limits<long long>::max(); for (size_t i = 0; i < 10; i++) { auto const d = bench(f, n); if (d < best) best = d; } std::cout << name << "[" << n << "]: " << best << " ns\n"; } int main() { for (size_t n = 10; n <= 1'000'000; n *= 10) { bench2([](auto a, auto b) { return compare_via_sort(a, b); }, n, "sort"); bench2([](auto a, auto b) { return compare_via_tmap(a, b); }, n, "tmap"); bench2([](auto a, auto b) { return compare_via_umap(a, b); }, n, "umap"); } }
Output:
sort[10]: 700 ns tmap[10]: 2000 ns umap[10]: 1800 ns sort[100]: 6200 ns tmap[100]: 20800 ns umap[100]: 19400 ns sort[1000]: 82500 ns tmap[1000]: 244600 ns umap[1000]: 143200 ns sort[10000]: 1008500 ns tmap[10000]: 3306700 ns umap[10000]: 1435800 ns sort[100000]: 13107800 ns tmap[100000]: 62987400 ns umap[100000]: 22860400 ns sort[1000000]: 159867600 ns tmap[1000000]: 1874229500 ns umap[1000000]: 497277000 ns
Fazit: umap hasn't got a prayer.
Was dann auch mehr meiner ursprünglichen Vermutung entspricht. Wenigstens das.