Articles of Algorithmus

Wie Socken effizient von einem Stapel zu paaren?

Gestern habe ich die Socken aus der sauberen Wäsche gepaart und herausgefunden, dass es nicht sehr effizient ist. Ich machte eine naive Suche – eine Socke pflückend und den Haufen “iterierend”, um sein Paar zu finden. Dies erfordert eine Iteration über n / 2 * n / 4 = n 2/8 Socken im Durchschnitt. Als […]

Wie können wiederkehrende Ereignisse in einer Kalenderanwendung am besten modelliert werden?

Ich erstelle eine Gruppenkalenderanwendung, die wiederkehrende Ereignisse unterstützen muss, aber alle Lösungen, die ich für die Behandlung dieser Ereignisse entwickelt habe, erscheinen wie ein Hack. Ich kann begrenzen, wie weit man vorausschauen kann, und dann alle Ereignisse auf einmal erzeugen. Oder ich kann die Ereignisse speichern und dynamisch anzeigen, wenn man im Kalender nach vorne […]

Was ist der schnellste Algorithmus, um den Mindestabstand zwischen zwei Punktsätzen zu berechnen?

Ich möchte den Mindestabstand zwischen zwei Polygonen finden. Ich muss das Minimum der kürzesten Entfernung zwischen jedem Eckpunkt der ersten Form mit allen Eckpunkten des anderen finden. So etwas wie die Hausdorff-Distanz , aber ich brauche das Minimum statt das Maximum.

Effiziente Implementierung von log2 (__ m256d) in AVX2

SVMLs __m256d _mm256_log2_pd (__m256d a) ist auf anderen Compilern als Intel nicht verfügbar, und sie sagen, dass seine performance auf AMD-processoren behindert ist. Es gibt einige Implementierungen im Internet, auf die in AVX-Log-Intrinsics verwiesen wird (_mm256_log_ps), die in g ++ – 4.8 fehlen. und SIMD Mathematikbibliotheken für SSE und AVX , jedoch scheinen sie mehr […]

Wie kann ich ein kartesisches Produkt iterativ berechnen?

Diese Frage fragt, wie man das kartesische Produkt einer gegebenen Anzahl von Vektoren berechnet. Da die Anzahl der Vektoren im voraus bekannt und eher klein ist, wird die Lösung leicht mit verschachtelten for-Schleifen erhalten. Angenommen, Sie erhalten in Ihrer Sprache einen Vektor von Vektoren (oder eine Liste von Listen oder Mengen von Sätzen usw.): l […]

Mit dem optimierten Levenshtein-Algorithmus den nächsten Nachbarn finden

Ich habe kürzlich eine Frage über die Optimierung des Algorithmus zur Berechnung der Levenshtein-Distanz gestellt, und die Antworten führen mich zum Wikipedia-Artikel über Levenshtein Distance . Der Artikel erwähnt, dass, wenn es ein gebundenes k auf der maximalen Entfernung gibt, ein mögliches Ergebnis von der gegebenen Frage sein kann, dann kann die Laufzeit von O […]

Shuffle-Liste, um sicherzustellen, dass kein Gegenstand in der gleichen Position verbleibt

Ich möchte eine Liste einzigartiger Elemente mischen, aber nicht eine ganz zufällige Mischung. Ich muss sicher sein, dass kein Element in der gemischten Liste an der gleichen Position wie in der ursprünglichen Liste ist. Wenn also die ursprüngliche Liste (A, B, C, D, E) ist, wäre dieses Ergebnis in Ordnung: (C, D, B, E, A), […]

Schnelle Sortierung Worst Case

Ich arbeite gerade an dem Programm, das ich gerade brauche, um es besser zu verstehen. Was ist die Worst-Case-Laufzeit für Quicksort und was kann zu dieser schlechteren performance führen? Wie können wir Quicksort-Programm ändern, um dieses Problem zu verringern? Ich weiß, dass es den schlechtesten Fall O(n^2) und ich weiß, dass es auftritt, wenn das […]

In linearer Zeit sortieren?

Geben Sie einen gegebenen linearen Zeitsortieralgorithmus an, wenn Sie eine Eingabemenge von n ganzen Zahlen im Bereich [0..n ^ 3-1] angeben. Dies ist eine Überprüfung für meinen Test am Donnerstag, und ich habe keine Ahnung, wie ich dieses Problem angehen soll.

Implementieren des Hoey Shamos-Algorithmus mit C #

Okay, ich bekomme jetzt die richtigen Informationen von meinem aktuellen Algorithmus! Allerdings, mit 700.000 Polygonen zu überprüfen, ist es einfach viel zu langsam! Das vorherige Problem ist behoben (My Line2D schneidet mit der Methode war falsch) Jetzt geht es darum, meinen Engpass zu identifizieren! Dieser Algorithmus soll O (nlog-n) sein, also sollte es viel schneller […]