Wie kann ich Socken von einem Stapel effizient koppeln?

3911

Gestern habe ich die Socken aus der sauberen Wäsche gepaart und herausgefunden, dass meine Arbeitsweise nicht sehr effizient ist. Ich machte eine naive Suche - nahm eine Socke und "iterierte" den Stapel, um sein Paar zu finden. Dies erfordert Iterieren über n / 2 * n / 4 = n 2 /8 Socken im Durchschnitt.

Als Informatiker dachte ich, was ich tun könnte? Das Sortieren (nach Größe / Farbe / ...) kam natürlich in den Sinn, um eine O (NlogN) -Lösung zu erhalten.

Hashing oder andere nicht vorhandene Lösungen sind keine Option, da ich meine Socken nicht duplizieren kann (obwohl es schön sein könnte, wenn ich könnte).

Die Frage ist also im Grunde:

Was ist bei einem Stapel von nSockenpaaren, die 2nElemente enthalten (vorausgesetzt, jede Socke hat genau ein passendes Paar), der beste Weg, um sie effizient mit bis zu logarithmischem zusätzlichen Platz zu verbinden? (Ich glaube, ich kann mich bei Bedarf an diese Menge an Informationen erinnern.)

Ich freue mich über eine Antwort, die folgende Aspekte behandelt:

  • Eine allgemeine theoretische Lösung für eine Vielzahl von Socken.
  • Die tatsächliche Anzahl der Socken ist nicht so groß, ich glaube meinem Ehepartner nicht und ich habe mehr als 30 Paare. (Und es ist ziemlich einfach, zwischen meinen und ihren Socken zu unterscheiden; kann dies auch verwendet werden?)
  • Entspricht es dem Problem der Elementunterscheidbarkeit ?
amit
quelle
448
Ich verwende das Taubenlochprinzip, um genau eines vom Wäschestapel zu koppeln. Ich habe 3 verschiedene Farben von Socken (Rot, Blau und Grün) und 2 Paare von jeder Farbe. Ich nehme jedes Mal 4 Socken und mache immer ein Paar und mache mich an die Arbeit.
Srinivas
59
Noch ein Taubenlochprinzip: Wenn Sie eine Teilmenge von n / 2 + 1 Socken nehmen, muss diese Teilmenge mindestens ein Paar enthalten.
Wildplasser
40
Gute Frage! Vielleicht interessiert Sie mein Artikel über ein verwandtes Problem, bei dem es um die Wahrscheinlichkeit geht, zwei passende Socken aus dem Stapel zu ziehen: blogs.msdn.com/b/ericlippert/archive/2010/03/22/…
Eric Lippert
336
Warum nicht ein Kind hervorbringen und waitpiddamit Sie als Eltern nicht einmal selbst Socken sortieren?
Mxyk
137
Ich habe dieses Problem gelöst, indem ich nur weiße Kniestrümpfe besaß. Sie passen alle zusammen. Ich könnte einfach zwei beliebige Socken zufällig vom Stapel nehmen und sie würden zusammenpassen. Ich vereinfache das Problem weiter, indem ich die Socken NICHT kopple. Ich habe eine Sockenschublade, in die ich einfach alle meine Socken ungepaart schmeiße. Ich nehme jeden Morgen zufällig zwei aus der Schublade. Ich habe es auf O (0) vereinfacht. Einfacher geht es nicht. :)
Lee

Antworten:

2449

Es wurden Sortierlösungen vorgeschlagen, aber das Sortieren ist etwas zu viel : Wir brauchen keine Ordnung; Wir brauchen nur Gleichstellungsgruppen .

So Hashing würde ausreichen , um (und schneller).

  1. Bilden Sie für jede Sockenfarbe einen Stapel . Iterieren Sie über alle Socken in Ihrem Eingabekorb und verteilen Sie sie auf den Farbstapeln .
  2. Iterieren Sie über jeden Stapel und verteilen Sie ihn nach einer anderen Metrik (z. B. Muster) auf den zweiten Stapelsatz
  3. Wenden Sie dieses Schema rekursiv an, bis Sie alle Socken auf sehr kleine Stapel verteilt haben, die Sie sofort visuell verarbeiten können

Diese Art der rekursiven Hash-Partitionierung wird tatsächlich von SQL Server durchgeführt, wenn ein Hash-Join oder eine Hash-Aggregation über große Datenmengen erforderlich ist. Es verteilt seinen Build-Eingabestream auf viele Partitionen, die unabhängig sind. Dieses Schema skaliert linear auf beliebige Datenmengen und mehrere CPUs.

Sie benötigen keine rekursive Partitionierung, wenn Sie einen Verteilungsschlüssel (Hash-Schlüssel) finden, der genügend Buckets bereitstellt, sodass jeder Bucket klein genug ist, um sehr schnell verarbeitet zu werden. Leider glaube ich nicht, dass Socken eine solche Eigenschaft haben.

Wenn jede Socke eine Ganzzahl namens "PairID" hätte, könnte man sie leicht in 10 Eimer gemäß PairID % 10(der letzten Ziffer) verteilen .

Die beste Partitionierung in der realen Welt, die ich mir vorstellen kann, ist das Erstellen eines Rechtecks ​​aus Stapeln : Eine Dimension ist Farbe, die andere ist das Muster. Warum ein Rechteck? Weil wir O (1) zufälligen Zugriff auf Pfähle brauchen. (Ein 3D- Quader würde auch funktionieren, aber das ist nicht sehr praktisch.)


Aktualisieren:

Was ist mit Parallelität ? Können mehrere Menschen schneller zu den Socken passen?

  1. Die einfachste Parallelisierungsstrategie besteht darin, dass mehrere Arbeiter aus dem Eingabekorb nehmen und die Socken auf die Stapel legen. Das vergrößert sich nur so sehr - stellen Sie sich 100 Menschen vor, die über 10 Stapel kämpfen. Die Synchronisationskosten (die sich in Handkollisionen und menschlicher Kommunikation äußern) zerstören die Effizienz und die Beschleunigung (siehe das Gesetz über die universelle Skalierbarkeit !). Ist dies anfällig für Deadlocks ? Nein, da jeder Arbeiter jeweils nur auf einen Stapel zugreifen muss. Mit nur einem "Schloss" kann es keinen Deadlock geben. Livelocks können möglich sein, je nachdem, wie die Menschen den Zugang zu Pfählen koordinieren. Sie könnten nur zufälliges Backoff verwendenWie Netzwerkkarten tun Sie dies auf physischer Ebene, um zu bestimmen, welche Karte ausschließlich auf das Netzwerkkabel zugreifen kann. Wenn es für Netzwerkkarten funktioniert , sollte es auch für Menschen funktionieren.
  2. Es skaliert fast unbegrenzt, wenn jeder Arbeiter seine eigenen Stapel hat . Arbeiter können dann große Stücke Socken aus dem Eingabekorb nehmen (sehr wenig Streit, da sie dies selten tun) und müssen beim Verteilen der Socken überhaupt nicht synchronisieren (weil sie fadenlokale Stapel haben). Am Ende müssen alle Arbeiter ihre Stapelsätze zusammenschließen. Ich glaube, dass dies in O (Protokoll (Anzahl der Arbeiter * Stapel pro Arbeiter)) erfolgen kann, wenn die Arbeiter einen Aggregationsbaum bilden .

Was ist mit dem Problem der Elementunterscheidbarkeit ? Wie im Artikel angegeben, kann das Problem der Elementunterscheidbarkeit in gelöst werden O(N). Dies gilt auch für das Sockenproblem (auch O(N)wenn Sie nur einen Verteilungsschritt benötigen (ich habe mehrere Schritte nur vorgeschlagen, weil Menschen schlecht in Berechnungen sind - ein Schritt reicht aus, wenn Sie weiterverteilen md5(color, length, pattern, ...), dh einen perfekten Hash aller Attribute)).

Natürlich kann man nicht schneller fahren als O(N), also haben wir die optimale Untergrenze erreicht .

Obwohl die Ausgänge nicht genau gleich sind (in einem Fall nur ein Boolescher Wert. In dem anderen Fall die Sockenpaare), sind die asymptotischen Komplexitäten gleich.

usr
quelle
72
Genau das mache ich! Ich mache Stapel abhängig von der Art der Öffnung der Socke (ich habe nur Weiß), die mir genug "Eimer" gibt, um sie schnell zusammenzubringen.
Scott Chamberlain
29
Ich habe es mit meinen Socken versucht (ich habe leicht 30+ Paare) und Mann, es ist SCHNELL. Ein Problem, das ich gefunden habe, ist, wenn ich keinen ausreichend guten Hash-Algorithmus haben kann (ich habe viele weiße Socken ohne Muster), so dass es schwierig wird. Was wäre in diesem Fall der optimale Weg, dies zu tun?
Nichts Unmöglich
56
@NothingsImpossible, so fühlen sich Hash-Kollisionsangriffe für einen armen Webserver an! Sind die weißen Socken durch ein Attribut unterscheidbar? Es muss etwas geben, auf dem Sie sie verteilen können. Andernfalls könnten Sie einfach willkürlich Paare bilden.
usr
37
Dies ist eine Radix-Sortierung, die meiner Meinung nach die richtige Antwort ist. @ MarkPeters Ich glaube nicht, dass Sie eine Nachschlagetabelle brauchen. Ein einzelner linearer Durchgang über die Socken kann die Socken in Zahlenvektoren umwandeln, wodurch die Zuordnung von "Sockensegment" zu Eimer trivial wird. Die Socken können mit einer Schnur an die Vektoren gebunden werden, so dass Sie am Ende keinen weiteren linearen Durchgang benötigen.
Pointy
49
Ein Typ, mit dem ich aufs College gegangen bin, hatte tatsächlich PairIDs. Es wurde auf jedes Paar Socken mit Faden genäht: 1, 2, 3, 4 ...
Ryan Lundy
579

Da sich die Architektur des menschlichen Gehirns völlig von einer modernen CPU unterscheidet, ist diese Frage praktisch nicht sinnvoll.

Menschen können CPU-Algorithmen für sich gewinnen, indem sie "ein passendes Paar finden" eine Operation für einen Satz sein können, der nicht zu groß ist.

Mein Algorithmus:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

Zumindest verwende ich das im wirklichen Leben und finde es sehr effizient. Der Nachteil ist, dass es eine flache Oberfläche erfordert, aber normalerweise reichlich vorhanden ist.

dpc.ucore.info
quelle
229
Mit zunehmender Anzahl von Socken wird die SIMD des Menschen nicht besser als eine CPU.
Lie Ryan
25
Die beste Antwort, IMO. Während es Spaß macht und klug (und für SO geeignet) ist, ein alltägliches Problem auf einen Computeralgorithmus zu reduzieren, ist es viel sinnvoller, das Auflösungsvermögen von Auge / Gehirn des Menschen für ein Set mit nur ~ 60 Socken zu verwenden.
drug_user841417
13
@LieRyan Wenn die Socken gleichmäßig verteilt sind, werden Sie aufgrund des Geburtstagsparadoxons ein Paar in ausreichend kleinen Socken bemerken (es sei denn, Sie können Farben mit willkürlicher Genauigkeit unterscheiden, was ich bezweifle), sodass der Engpass hier nicht besteht der menschliche Farbanpassungsalgorithmus, aber der Ausbreitungsschritt.
Thomas
13
@ dpc.ucore.info Nein, weil sie unterschiedliche gewebte Manschettenmuster, Manschettenlängen, Gesamtlängen und Schwarztöne haben (meine Frau würde mich bei diesem letzten wahrscheinlich körperlich verletzen).
Christian
200
Sie sollten besser hoffen, dass Sie eine gerade Anzahl von Socken haben, sonst werden Sie für eine lange Zeit Socken falten ...
Patrick James McDougle
258

Fall 1 : Alle Socken sind identisch (das mache ich übrigens im wirklichen Leben).

Wählen Sie zwei davon aus, um ein Paar zu bilden. Ständige Zeit.

Fall 2 : Es gibt eine konstante Anzahl von Kombinationen (Besitz, Farbe, Größe, Textur usw.).

Verwenden Sie die Radix-Sortierung . Dies ist nur eine lineare Zeit, da kein Vergleich erforderlich ist.

Fall 3 : Die Anzahl der Kombinationen ist nicht im Voraus bekannt (allgemeiner Fall).

Wir müssen einen Vergleich durchführen, um zu überprüfen, ob zwei Socken paarweise geliefert werden. Wählen Sie einen der O(n log n)vergleichsbasierten Sortieralgorithmen.

Im wirklichen Leben, wenn die Anzahl der Socken relativ klein (konstant) ist, würden diese theoretisch optimalen Algorithmen jedoch nicht gut funktionieren. Es kann sogar noch länger dauern als die sequentielle Suche, die theoretisch eine quadratische Zeit erfordert.

Terry Li
quelle
8
> Es kann sogar noch länger dauern als die sequentielle Suche, die theoretisch eine quadratische Zeit erfordert. Ja, deshalb hasse ich es, das zu tun. Vielleicht sollte ich alle meine Socken wegwerfen und mit Fall 1 beginnen.
Nils
57
Der Nachteil aller identischen Socken ist, dass sie dazu neigen, unterschiedlich schnell zu altern. Am Ende versuchen Sie also immer noch, sie anhand ihrer Abnutzung anzupassen. (was schwieriger ist als nur nach Muster
DEZA
118
Das Problem mit 60 Paaren identischer Socken, "weil dies das Pairing erleichtert", besteht darin, dass die Leute den Eindruck haben, mit Computern zu arbeiten.
Steve Ives
13
Fall 1 ist keine konstante Zeit, wenn es sich um eine Operation handelt, z. B. das Zusammenfalten von Paaren. In diesem Fall ist es eine lineare Zeit mit dem kleinsten konstanten Faktor (dessen Beweis dem Leser als Übung überlassen bleibt). Man kann unmöglich die gleiche Zeit damit verbringen, ein Paar und einen Eimer voller Socken zu falten. Es skaliert jedoch linear. Nach Amdahls Gesetz ist die Geschwindigkeit unbegrenzt und der Overhead wird ignoriert. Nach dem Gesetz von Gustafson können Sie so viele Paare falten, wie nötig sind, um ein Paar zu falten, wenn genügend Arbeiter vorhanden sind (deren Menge als Übung für den Leser übrig bleibt), ohne den Aufwand zu berücksichtigen.
Acelent
7
@PauloMadeira Die Sortierung ist zeitlich konstant - Sie nehmen einfach den Stapel und legen ihn in Ihre Schublade. Die einzige Operation in diesem Fall ist das Anziehen der Socken an Ihren Füßen, was ebenfalls konstant ist. Die Leistung wird durch verzögertes Ausführen des Tragens der Socken erzielt, möglicherweise mit einigen Platzverlusten (der verbrauchte Platz von nicht gefalteten Socken ist größer als gefaltet). Ich behaupte, das ist es wert; Normalerweise verliere ich diesen Streit mit meiner Frau.
Travis
157

Nicht algorithmische Antwort, aber "effizient", wenn ich es tue:

  • Schritt 1) ​​Entsorgen Sie alle vorhandenen Socken

  • Schritt 2) Gehen Sie zu Walmart und kaufen Sie sie in Paketen mit 10 - n Päckchen Weiß und m Päckchen Schwarz. Keine Notwendigkeit für andere Farben im Alltag.

Aber von Zeit zu Zeit muss ich das noch einmal machen (verlorene Socken, beschädigte Socken usw.), und ich hasse es, perfekt gute Socken zu oft wegzuwerfen (und ich wünschte, sie verkaufen immer die gleiche Sockenreferenz!), Also habe ich kürzlich genommen Ein anderer Versuch.

Algorithmische Antwort:

Bedenken Sie, dass Ihre Wahrscheinlichkeit, bei einer naiven Suche die passende Socke zu finden, sehr gering ist, wenn Sie nur eine Socke für den zweiten Sockenstapel ziehen.

  • Nehmen Sie also fünf davon zufällig auf und merken Sie sich ihre Form oder Länge.

Warum fünf? Normalerweise sind Menschen gut darin, sich an fünf bis sieben verschiedene Elemente im Arbeitsspeicher zu erinnern - ein bisschen wie das menschliche Äquivalent eines RPN- Stapels - fünf ist ein sicherer Standard.

  • Nimm einen vom Stapel 2n-5.

  • Suchen Sie nun nach einer Übereinstimmung (visuelle Musterübereinstimmung - Menschen können das gut mit einem kleinen Stapel) innerhalb der fünf, die Sie gezeichnet haben. Wenn Sie keine finden, fügen Sie diese zu Ihren fünf hinzu.

  • Wähle weiterhin zufällig Socken vom Stapel und vergleiche sie mit deinen 5 + 1-Socken für ein Match. Wenn Ihr Stack wächst, wird dies Ihre Leistung verringern, aber Ihre Chancen erhöhen. Viel schneller.

Schreiben Sie die Formel auf, um zu berechnen, wie viele Stichproben Sie für eine 50% ige Gewinnchance ziehen müssen. IIRC ist ein hypergeometrisches Gesetz.

Ich mache das jeden Morgen und brauche selten mehr als drei Draws - aber ich habe nähnliche Paare (ungefähr 10, gib oder nimm die verlorenen) mgeformter weißer Socken. Jetzt können Sie die Größe meines Lagerstapels schätzen :-)

Übrigens stellte ich fest, dass die Summe der Transaktionskosten für das Sortieren aller Socken jedes Mal, wenn ich ein Paar benötigte, weitaus geringer war als einmal und das Binden der Socken. Ein Just-in-Time funktioniert besser, weil Sie dann die Socken nicht binden müssen und es auch eine abnehmende marginale Rendite gibt (das heißt, Sie suchen immer nach den zwei oder drei Socken, die Sie irgendwo in der Wäsche haben und die Sie brauchen um das Matching Ihrer Socken zu beenden und Sie verlieren Zeit dafür).

Guylhem
quelle
25
Upvote für 'nicht algorithmische' Antwort. Genau das mache ich und es funktioniert wunderbar. Das Ersatzproblem ist kein Problem, wenn Sie Ihren Sockenvorrat "drehen", indem Sie gewaschene Socken in den Rücken legen und morgens von der Vorderseite der Schublade ziehen. Alle Socken tragen sich gleichmäßig. Wenn ich anfange, Abnutzungserscheinungen an einer zu bemerken, habe ich sie auf die Einkaufsliste gesetzt, um die gesamte Klasse der Socken vollständig zu ersetzen. Für die alten Socken gebe ich Goodwill die besten 20% (gebunden in einen Einkaufssack, damit sie sich nicht wieder einmischen) und stelle den Rest auf. Sie verschwenden keine Socken, zu diesem Zeitpunkt haben die 80% ohnehin nur noch 6 Monate Zeit.
FastAl
2
Übrigens (1) Wenn Sie Ihre Socken binden, wird die elastische Dehnung gedehnt gelagert und die Socken fallen viel schneller aus. Wenn Sie die Art der einzigartigen Socken, die Sie haben, einschränken, wird die Bindung aufgehoben. (2) Ein Nachteil der Begrenzung einzigartiger Socken besteht darin, dass die Methode für Personen mit bestimmten Modeproblemen möglicherweise ungeeignet ist.
FastAl
3
Ich bin speziell hierher gekommen, um Ihre "nicht algorithmische" Antwort zu posten. Wie in der echten Informatik schenken die meisten Menschen den Daten und ihrer Struktur nie genug Aufmerksamkeit.
Bkconrad
Ich benutze diesen algorithmischen Ansatz jeden Morgen und er funktioniert wie ein Zauber! Außerdem habe ich abgenutzte Socken auf einen anderen Stapel gelegt, um sie später wegzuwerfen (leider schaffen sie es, wieder zum ursprünglichen Stapel zu gelangen, bevor ich die Zeit finde, ihn wegzuwerfen).
Donatas Olsevičius
3
«N Päckchen Weiß und m Päckchen Schwarz. Keine Notwendigkeit für andere Farben im Alltag »Eine gute Standardregel für die einfache Auswahl von Socken ist, dass sie entweder der Farbe Ihrer Hose oder der Farbe Ihres Gürtels entsprechen sollten. Aus diesem Grund sind die am häufigsten verwendeten Farben wahrscheinlich Schwarz, Blau, Grau und etwas Braun. Es ist kaum zu glauben, dass man viele weiße Socken braucht.
Andrea Lazzarotto
106

Ich nehme die erste Socke und lege sie hin (z. B. am Rand der Wäscheschale). Dann nehme ich eine andere Socke und überprüfe, ob sie mit der ersten Socke identisch ist. Wenn ja, entferne ich beide. Wenn nicht, lege ich es neben die erste Socke. Dann nehme ich die dritte Socke und vergleiche sie mit den ersten beiden (wenn sie noch da sind). Usw.

Dieser Ansatz kann ziemlich einfach in einem Array implementiert werden, vorausgesetzt, dass das "Entfernen" von Socken eine Option ist. Eigentlich müssen Sie nicht einmal Socken "entfernen". Wenn Sie die Socken nicht sortieren müssen (siehe unten), können Sie sie einfach verschieben und erhalten ein Array, in dem alle Socken paarweise im Array angeordnet sind.

Unter der Annahme, dass die einzige Operation für Socken darin besteht, die Gleichheit zu vergleichen, ist dieser Algorithmus im Grunde immer noch ein n 2 -Algorithmus, obwohl ich nichts über den Durchschnittsfall weiß (ich habe nie gelernt, das zu berechnen).

Das Sortieren verbessert natürlich die Effizienz, insbesondere im wirklichen Leben, wo Sie leicht eine Socke zwischen zwei andere Socken "einführen" können. Bei der Berechnung könnte das gleiche durch einen Baum erreicht werden, aber das ist zusätzlicher Platz. Und natürlich sind wir wieder bei NlogN (oder ein bisschen mehr, wenn es mehrere Socken gibt, die nach Sortierkriterien gleich sind, aber nicht aus demselben Paar).

Davon abgesehen fällt mir nichts ein, aber diese Methode scheint im wirklichen Leben ziemlich effizient zu sein. :) :)

Vilx-
quelle
7
Dies ist auch, was ich tue (beachten Sie, dass, wenn Sie einfach Leerzeichen lassen, Einfügungen auch O (1) sind), aber es skaliert schlecht mit theoretisch einer großen Anzahl von Socken.
Mooing Duck
15
skaliert schlecht mit theoretisch einer großen Anzahl von Arten von Socken
Steven Lu
@StevenLu - wie gesagt - es ist n * n oder nLogn, je nachdem, ob Sie es sortieren oder nicht. Es skaliert also ungefähr so ​​schlecht wie jeder Sortieralgorithmus. Wenn Sie schneller wollen, nummerieren Sie sie und verwenden Sie die Radix-Sortierung.
Vilx
Dies speichert im Wesentlichen gefundene, aber nicht übereinstimmende Socken in einer Hash-basierten Suche. Bei einem idealen Hash ist es O (n), aber wenn Sie genug Socken gespeichert haben, dass der Hash zu degenerieren beginnt, wird er entsprechend komplexer.
Jon Hanna
3
Welchen Wert hat das Einfügen einer Socke zwischen zwei anderen Socken für das Ziel, Socken zu paaren? Es gibt keine Kardinalität von Socken. : -x
JoeBrockhaus
60

Dies stellt die falsche Frage. Die richtige Frage ist, warum ich Zeit damit verbringe, Socken zu sortieren. Wie viel kostet es jährlich, wenn Sie Ihre Freizeit für X Geldeinheiten Ihrer Wahl bewerten?

Und meistens ist dies nicht irgendeine Freizeit, sondern eine morgendliche Freizeit, die Sie im Bett verbringen, an Ihrem Kaffee nippen oder etwas früher abreisen und nicht im Verkehr gefangen werden können.

Es ist oft gut, einen Schritt zurückzutreten und das Problem zu umgehen.

Und es gibt einen Weg!

Finde eine Socke, die du magst. Berücksichtigen Sie alle relevanten Merkmale: Farbe bei unterschiedlichen Lichtverhältnissen, Gesamtqualität und Haltbarkeit, Komfort bei unterschiedlichen Klimabedingungen und Geruchsabsorption. Wichtig ist auch, dass sie bei der Lagerung nicht an Elastizität verlieren, sodass natürliche Stoffe gut sind und in einer Plastikverpackung erhältlich sein sollten.

Es ist besser, wenn es keinen Unterschied zwischen linken und rechten Fußsocken gibt, aber es ist nicht kritisch. Wenn die Socken von links nach rechts symmetrisch sind, ist das Finden eines Paares eine O (1) -Operation, und das Sortieren der Socken ist eine ungefähre O (M) -Operation, wobei M die Anzahl der Stellen in Ihrem Haus ist, die Sie mit Socken übersät haben, idealerweise einige kleine konstante Zahl.

Wenn Sie sich für ein ausgefallenes Paar mit unterschiedlichen linken und rechten Socken entschieden haben, nehmen Sie O (N + M), wobei N die Anzahl der Socken und M die gleiche wie oben ist. Jemand anderes kann die Formel für durchschnittliche Iterationen des Findens des ersten Paares angeben, aber der schlechteste Fall für das Finden eines Paares mit blinder Suche ist N / 2 + 1, was für vernünftiges N astronomisch unwahrscheinlich wird. Dies kann durch Verwendung eines erweiterten Bildes beschleunigt werden Erkennungsalgorithmen und Heuristiken beim Scannen des Stapels unsortierter Socken mit Mk1 Eyeball .

Ein Algorithmus zum Erreichen der Effizienz der O (1) -Sockenpaarung (unter der Annahme einer symmetrischen Socke) lautet also:

  1. Sie müssen abschätzen, wie viele Paar Socken Sie für den Rest Ihres Lebens benötigen, oder vielleicht bis Sie in Rente gehen und in ein wärmeres Klima ziehen, ohne jemals wieder Socken tragen zu müssen. Wenn Sie jung sind, können Sie auch abschätzen, wie lange es dauert, bis wir alle Socken-Sortierroboter in unseren Häusern haben, und das ganze Problem wird irrelevant.

  2. Sie müssen herausfinden, wie Sie Ihre ausgewählte Socke in loser Schüttung bestellen können, wie viel sie kostet und wie sie geliefert wird.

  3. Bestellen Sie die Socken!

  4. Werde deine alten Socken los.

Ein alternativer Schritt 3 würde darin bestehen, die Kosten für den Kauf der gleichen Menge vielleicht billigerer Socken über die Jahre hinweg paarweise zu vergleichen und die Kosten für das Sortieren von Socken zu addieren, aber nehmen Sie mein Wort: Der Kauf in loser Schüttung ist billiger! Außerdem erhöhen Socken im Lager mit der Inflationsrate des Aktienkurses an Wert, was mehr ist, als Sie bei vielen Investitionen erhalten würden. Andererseits gibt es auch Lagerkosten, aber Socken nehmen im obersten Regal eines Schranks wirklich nicht viel Platz ein.

Problem gelöst. Holen Sie sich einfach neue Socken, werfen / spenden Sie Ihre alten weg und leben Sie glücklich, nachdem Sie wissen, dass Sie für den Rest Ihres Lebens jeden Tag Geld und Zeit sparen.

Hyde
quelle
Eine lebenslange (vorausgesetzt 75 Jahre) Versorgung mit Socken (vorausgesetzt, Sie verbrauchen 4 Paare / Monat, was 3600 Paare ergibt) würde insgesamt 1 1/2 Kubikmeter in Anspruch nehmen (vorausgesetzt, ein neues Paar Socken nimmt 20 Kubikzoll ein). Das ist enorm viel Platz. Angenommen, sie liefern es Ihnen in einer Schachtel, die ungefähr ein Würfel ist, dann ist diese Kiste ungefähr 3 Fuß 4 Zoll auf einer Seite.
AJMansfield
2
@AJMansfield gültiges Anliegen. Ich bin jedoch mit einigen Ihrer Zahlen nicht einverstanden. Ich würde eine Zeitspanne von nur 40 Jahren (25 ... 65) in Anspruch nehmen (Zeit zwischen dem Nichtleben bei den Eltern / dem Wohnheim / usw. und der Pensionierung, siehe oben). Ich denke auch, dass ein Paar in der Originalverpackung eher 0,5 x 4 x 6 Zoll benötigt. Diese Zahlen senken Ihre Raumzeit erheblich!
Hyde
Schritt 4 ist unnötig verschwenderisch, -1.
Dan Bechard
2
Leitfaden für andere, die durch AJMansfields Messungen verwirrt sein könnten, eine Übersetzung in Metrik: »würde (vorausgesetzt, ein neues Paar Socken nimmt 327 cm³ ein) insgesamt 1,14 m³ einnehmen. Das ist enorm viel Platz. Angenommen, sie liefern es Ihnen in einer Schachtel, die ungefähr ein Würfel ist, dann ist diese Kiste ungefähr 1,04 m auf einer Seite. «
Joey
Wie kann eine neugierige Frage "die falsche Frage" sein? Classic StackOverflow ...
Timmmm
52

Die theoretische Grenze ist O (n), da Sie jede Socke berühren müssen (es sei denn, einige sind bereits irgendwie gepaart).

Sie können O (n) mit Radix-Sortierung erreichen . Sie müssen nur einige Attribute für die Eimer auswählen.

  1. Zuerst kannst du wählen (ihre, meine) - teile sie in 2 Stapel auf,
  2. Verwenden Sie dann Farben (kann eine beliebige Reihenfolge für die Farben haben, z. B. alphabetisch nach Farbnamen) - teilen Sie sie nach Farbe in Stapel auf (denken Sie daran, die ursprüngliche Reihenfolge ab Schritt 1 für alle Socken im selben Stapel beizubehalten).
  3. dann Länge der Socke,
  4. dann Textur, ....

Wenn Sie eine begrenzte Anzahl von Attributen auswählen können, aber genügend Attribute, die jedes Paar eindeutig identifizieren können, sollten Sie in O (k * n) arbeiten, was O (n) ist, wenn wir berücksichtigen können, dass k begrenzt ist.

andredor
quelle
3
Socken werden oft in 4er-Packs und größer geliefert, da dies billiger ist, aber dadurch auch nicht zu unterscheiden ist. Um dem entgegenzuwirken, näht meine Frau auf jedes neue Paar Socken, das ich kaufe, eine winzige Markierung. Die Markierung hat für jedes Paar eine andere Farbe oder eine andere Form, wenn ihr die Farben ausgehen. Bei diesem Ansatz benötigen Sie nicht einmal einen begrenzten Satz von Attributen. Nähen Sie einfach eine eindeutige Nummer auf jedes Paar. :) Verwenden Sie für zusätzliche Punkte binär.
Vilx
29
@ Vilx- WARUM?!? Ist es nicht der springende Punkt, dass sie nicht zu unterscheiden sind?
Flup
2
@flup - Ich denke, der springende Punkt ist, in größeren Bündeln zu verkaufen. :) Was mich betrifft, hilft dies, sie paarweise zu zermürben. Ansonsten kann ich drei sehr abgenutzte Socken und eine brandneue haben. Ein bisschen albern.
Vilx
13
Ich bin mit der Berechnung von O (n) nicht einverstanden. Was ist $ k $? $ k $ ist die Anzahl der Attribute. Ich würde argumentieren, dass $ k $ $ O (log n) $ ist, weil es ausreichen muss, um jedes Paar eindeutig zu identifizieren. Wenn Sie 2 Paare (schwarz und weiß) haben, reicht die Farbe ($ k = 1, n = 2 $) aus. Wenn Sie ein Paar Schwarz haben, kurz; ein Paar schwarz, lang; ein Paar weiß, kurz; und ein Paar Weiß, lang - dann $ k = 2, n = 4 $. Wenn wir dann $ k $ begrenzen, begrenzen wir gleichzeitig $ n $. Wenn wir $ n $ begrenzen wollen, ist die Auftragsberechnung nicht mehr sinnvoll.
Emory
3
@emory, ich denke, du suchst nach dem Backtick, nicht nach dem $Charakter, damit deine Sachen code-y aussehen.
Xymostech
33

Als praktische Lösung:

  1. Machen Sie schnell Stapel von leicht unterscheidbaren Socken. (Sprich nach Farbe)
  2. Quicksortieren Sie jeden Stapel und verwenden Sie zum Vergleich die Länge der Socke. Als Mensch können Sie ziemlich schnell entscheiden, welche Socke zum Partitionieren verwendet werden soll, um den schlimmsten Fall zu vermeiden. (Sie können mehrere Socken parallel sehen, nutzen Sie das zu Ihrem Vorteil!)
  3. Hören Sie auf, Stapel zu sortieren, wenn sie eine Schwelle erreicht haben, bei der Sie bequem sofort Paare und ungepaarte Socken finden können

Wenn Sie 1000 Socken mit 8 Farben und einer durchschnittlichen Verteilung haben, können Sie 4 Stapel von jeweils 125 Socken in c * n-Zeit herstellen. Mit einer Schwelle von 5 Socken können Sie jeden Stapel in 6 Läufen sortieren. (Wenn Sie 2 Sekunden zählen, um eine Socke auf den richtigen Stapel zu werfen, benötigen Sie weniger als 4 Stunden.)

Wenn Sie nur 60 Socken, 3 Farben und 2 Arten von Socken (Ihre / die Ihrer Frau) haben, können Sie jeden Stapel von 10 Socken in 1 Durchläufen sortieren (erneut Schwelle = 5). (Nach 2 Sekunden dauert es 2 Minuten).

Die anfängliche Sortierung der Eimer beschleunigt Ihren Prozess, da Ihre n Socken c*nrechtzeitig in k Eimer aufgeteilt werden, sodass Sie nur noch c*n*log(k)arbeiten müssen. (Ohne Berücksichtigung der Schwelle). Alles in allem erledigen Sie also Ihre n*c*(1 + log(k))Arbeit, wobei c die Zeit ist, eine Socke auf einen Stapel zu werfen.

Dieser Ansatz ist im Vergleich zu jeder c*x*n + O(1)Methode ungefähr so ​​lange günstig wie log(k) < x - 1.


In der Informatik kann dies hilfreich sein: Wir haben eine Sammlung von n Dingen , eine Reihenfolge (Länge) und auch eine Äquivalenzbeziehung (zusätzliche Informationen, zum Beispiel die Farbe von Socken). Die Äquivalenzbeziehung ermöglicht es uns, eine Partition der ursprünglichen Sammlung zu erstellen, und in jeder Äquivalenzklasse wird unsere Reihenfolge weiterhin beibehalten. Die Zuordnung eines Objekts zu seiner Äquivalenzklasse kann in O (1) erfolgen, sodass nur O (n) erforderlich ist, um jedes Element einer Klasse zuzuweisen. Jetzt haben wir unsere zusätzlichen Informationen verwendet und können jede Klasse auf beliebige Weise sortieren. Der Vorteil ist, dass die Datensätze bereits deutlich kleiner sind.

Die Methode kann auch verschachtelt werden, wenn wir mehrere Äquivalenzbeziehungen haben -> Farbstapel erstellen, als innerhalb jeder Stapelpartition auf Textur, als nach Länge sortieren. Jede Äquivalenzbeziehung, die eine Partition mit mehr als 2 Elementen mit ungefähr gleicher Größe erstellt, führt zu einer Geschwindigkeitsverbesserung gegenüber dem Sortieren (vorausgesetzt, wir können dem Stapel direkt eine Socke zuweisen), und das Sortieren kann bei kleineren Datensätzen sehr schnell erfolgen.

Samuel
quelle
3
Menschliche Optimierung: Ich würde argumentieren, dass Sie als Mensch für Schritt 2 die Socken in ungefähr aufsteigender Reihenfolge ablegen und dann mit immer feinerer Granularität wiederholen sollten, bis sie sortiert sind, ein bisschen wie bei der Muschelsortierung. Dies wäre für einen Menschen viel schneller (visuelle Schätzung) als ein auf Vergleichstausch basierender Ansatz.
AndrewC
28

Sie versuchen, das falsche Problem zu lösen.

Lösung 1: Binden Sie schmutzige Socken jedes Mal, wenn Sie sie in Ihren Wäschekorb legen, zu einem kleinen Knoten zusammen. Auf diese Weise müssen Sie nach dem Waschen keine Sortierung mehr durchführen. Stellen Sie sich vor, Sie registrieren einen Index in einer Mongo-Datenbank. Ein wenig Arbeit voraus für einige CPU-Einsparungen in der Zukunft.

Lösung 2: Wenn es Winter ist, müssen Sie keine passenden Socken tragen. Wir sind Programmierer. Niemand muss es wissen, solange es funktioniert.

Lösung 3: Verteilen Sie die Arbeit. Sie möchten einen so komplexen CPU-Prozess asynchron ausführen, ohne die Benutzeroberfläche zu blockieren. Nehmen Sie diesen Stapel Socken und stopfen Sie sie in eine Tasche. Suchen Sie nur dann nach einem Paar, wenn Sie es brauchen. Auf diese Weise fällt der Arbeitsaufwand viel weniger auf.

Hoffe das hilft!

Nikolay Dyankov
quelle
5
Das Binden von Socken (oder Kleidungsstücken) in einem Knoten verringert die Fähigkeit der Waschmaschine, die Kleidung zu waschen, und erschwert das Lösen der Kleidung zum Tragen erheblich. Lösung 2 erschwert die Wartung, je länger der Stand der Dinge andauert. Nach 6 Monaten, wenn Sie zwei schwarze Söckchen zum Tragen mit Shorts und Turnschuhen benötigen, ist es nach 6 Monaten weniger wahrscheinlich, dass Sie dieses Paar im gleichen Zustand (schmutzig / sauber, ähnliche Abnutzung) finden. Lösung 3 ist weniger "asynchron" und direkter "faul"; Machen Sie die minimale Arbeit, die Sie brauchen, genau dann, wenn Sie sie brauchen.
KeithS
Betreff: Lösung 2: Die Leute werden wissen, dass ich keine passenden Socken trage, weil sie sie in meinen Birken sehen werden :)
Bob Probst
@ BobProbst Ja, aber Ihre Programmierkollegen werden auch unübertroffene Socken mit Birks tragen und sich daher nur freuen, wenn sie bemerken, dass sie nicht die einzigen sind.
Francesco Pasa
27

Diese Frage ist eigentlich zutiefst philosophisch. Im Kern geht es darum, ob die Fähigkeit der Menschen, Probleme zu lösen (die "Wetware" unseres Gehirns), dem entspricht, was mit Algorithmen erreicht werden kann.

Ein offensichtlicher Algorithmus zum Sortieren von Socken ist:

Let N be the set of socks that are still unpaired, initially empty
for each sock s taken from the dryer
  if s matches a sock t in N
    remove t from N, bundle s and t together, and throw them in the basket
  else
    add s to N

Jetzt dreht sich in der Informatik in diesem Problem alles um die Schritte

  1. "wenn s mit einer Socke t in N paart". Wie schnell können wir uns an das "erinnern", was wir bisher gesehen haben?
  2. "entferne t von N" und "füge s zu N hinzu". Wie teuer ist es, den Überblick über das zu behalten, was wir bisher gesehen haben?

Menschen werden verschiedene Strategien anwenden, um diese zu bewirken. Das menschliche Gedächtnis ist assoziativ , so etwas wie eine Hash-Tabelle, in der Feature-Sets gespeicherter Werte mit den entsprechenden Werten selbst gepaart werden. Zum Beispiel wird das Konzept des "roten Autos" allen roten Autos zugeordnet, an die sich eine Person erinnern kann. Jemand mit einem perfekten Gedächtnis hat eine perfekte Zuordnung. Die meisten Menschen sind in dieser Hinsicht unvollkommen (und die meisten anderen). Die assoziative Karte hat eine begrenzte Kapazität. Zuordnungen können piepen unter verschiedenen Umständen nicht mehr existieren (ein Bier zu viel), irrtümlich aufgezeichnet werden ("Ich dachte, ihr Name war Betty, nicht Nettie") oder niemals überschrieben werden, obwohl wir beobachten, dass sich die Wahrheit geändert hat ("Papas Auto" ruft hervor "orange Firebird", als wir tatsächlich wussten, dass er das gegen den roten Camaro eingetauscht hatte).

Im Fall von Socken bedeutet perfekter Rückruf, dass das Betrachten einer Socke simmer die Erinnerung an ihr Geschwister erzeugt t, einschließlich genügend Informationen (wo sie sich auf dem Bügelbrett befindet), um sie tin konstanter Zeit zu lokalisieren . Eine Person mit fotografischem Gedächtnis erreicht sowohl 1 als auch 2 in konstanter Zeit ohne Fehler.

Jemand mit weniger als perfektem Gedächtnis könnte einige Commonsense-Äquivalenzklassen verwenden, die auf Merkmalen innerhalb seiner Fähigkeit basieren, zu verfolgen: Größe (Papa, Mama, Baby), Farbe (grünlich, rötlich usw.), Muster (Argyle, Plain usw.) , Stil (Footie, kniehoch usw.). Das Bügelbrett würde also in Abschnitte für die Kategorien unterteilt. Dies ermöglicht normalerweise, dass die Kategorie in konstanter Zeit nach Speicher lokalisiert wird, dann ist jedoch eine lineare Suche durch die Kategorie "Bucket" erforderlich.

Jemand ohne Gedächtnis oder Vorstellungskraft (sorry) wird nur die Socken auf einem Stapel behalten und eine lineare Suche des gesamten Stapels durchführen.

Ein ordentlicher Freak könnte numerische Bezeichnungen für Paare verwenden, wie jemand vorgeschlagen hat. Dies öffnet die Tür zu einer vollständigen Reihenfolge, die es dem Menschen ermöglicht, genau die gleichen Algorithmen zu verwenden, die wir mit einer CPU verwenden könnten: binäre Suche, Bäume, Hashes usw.

Der "beste" Algorithmus hängt also von den Eigenschaften der Wetware / Hardware / Software ab, auf der er ausgeführt wird, und von unserer Bereitschaft, zu "schummeln", indem wir Paaren eine Gesamtreihenfolge auferlegen. Sicherlich ist es ein "bester" Meta- Algorithmus, den weltbesten Socken-Sortierer einzustellen: eine Person oder Maschine, die eine große Menge N von Sockenattribut-Sets in einem 1-1-assoziativen Speicher mit konstanter Zeitsuche, Einfügen, Einfügen, schnell erwerben und speichern kann. und löschen. Sowohl Menschen als auch Maschinen wie diese können beschafft werden. Wenn Sie eine haben, können Sie alle Socken in O (N) Zeit für N Paare koppeln, was optimal ist. Mit den Gesamtauftrags-Tags können Sie Standard-Hashing verwenden, um das gleiche Ergebnis mit einem menschlichen oder einem Hardware-Computer zu erzielen.

Gen
quelle
Ok, das ist besser, obwohl es immer noch ziemlich falsch ist ... bei dieser Frage geht es nicht darum. Unabhängig davon, ob die These von Church-Turing richtig ist oder nicht, können sowohl Menschen als auch unsere Computer Socken sortieren. (Die Realität ist, dass Menschen, die sehr endliche Einheiten sind, weitaus weniger Rechenleistung haben als Turing-Maschinen ... und dasselbe gilt für unsere Computer, aber die Einschränkungen sind unterschiedlich.)
Jim Balter
Ich stimme dir nicht zu. Natürlich ist jeder unserer aktuellen Computer im Wesentlichen ein enormer DFA (Modulo I / O-Unterschiede) und kein TM. Jedes analoge Gerät wie unser Körper kann jedoch ein unendliches Band emulieren. Wir haben noch keine nützliche Charakterisierung der Art und Weise, wie unser Verstand rechnet.
Gene
Kein unendliches Band für Menschen oder andere physische Geräte, denn nichts im menschlichen Gehirn hat eine unendliche Auflösung und könnte es auch nicht. Es würde auch helfen, etwas Neurowissenschaft zu lernen. Auf jeden Fall gab es hier keine tiefe philosophische Frage, unabhängig von Ihrem Wunsch, eine zu injizieren. Aber glauben Sie, was Sie wollen ... dies ist nicht der Ort für diese Art von Debatte, und ich hatte es schon zu oft. Aber ich bin immer amüsiert von Leuten, die kaum die einfachsten Probleme lösen können (das sind wir alle) und sich vorstellen, dass sie TM-äquivalent sind.
Jim Balter
22

Kosten: Socken bewegen -> hoch, Socken in der Schlange finden / suchen -> klein

Wir möchten die Anzahl der Züge reduzieren und durch die Anzahl der Suchvorgänge kompensieren. Außerdem können wir die Multithred-Umgebung des Homo Sapiens nutzen, um mehr Dinge im Entscheidungscache zu speichern.

X = Ihre, Y = Ihre Ehepartner

Von Stapel A aller Socken:

Wählen Sie zwei Socken aus, platzieren Sie die entsprechende X-Socke in der X-Linie und die Y-Socke in der Y-Linie an der nächsten verfügbaren Position.

Tun Sie, bis A leer ist.

Für jede Zeile X und Y.

  1. Wählen Sie die erste Socke in der Reihe aus und suchen Sie entlang der Linie, bis die entsprechende Socke gefunden wird.

  2. In die entsprechende fertige Sockenreihe legen.

  3. Optional Führen Sie Schritt 2 für diese Socken aus, während Sie die Linie durchsuchen und die aktuelle Socke, die Sie betrachten, mit der vorherigen identisch ist.

Optional zu Schritt eins nehmen Sie zwei Socken von dieser Zeile anstelle von zwei, da der Caching-Speicher groß genug ist, können wir schnell feststellen, ob eine der Socken mit der aktuellen in der beobachteten Zeile übereinstimmt. Wenn Sie das Glück haben, drei Arme zu haben, können Sie möglicherweise drei Socken gleichzeitig analysieren, da die Erinnerung an das Motiv groß genug ist.

Tun Sie dies, bis sowohl X als auch Y leer sind.

Erledigt

Da dies jedoch eine ähnliche Komplexität als Auswahlsortierung aufweist, ist die benötigte Zeit aufgrund der Geschwindigkeit von E / A (sich bewegende Socken) und Suchen (Durchsuchen der Linie nach einer Socke) weitaus geringer.

1 ----- 1
quelle
22

Hier ist eine Omega (n log n) -Untergrenze im vergleichsbasierten Modell. (Die einzig gültige Operation ist der Vergleich zweier Socken.)

Angenommen, Sie wissen, dass Ihre 2n-Socken folgendermaßen angeordnet sind:

p 1 p 2 p 3 ... p n p f (1) p f (2) ... p f (n)

Dabei ist f eine unbekannte Permutation der Menge {1,2, ..., n}. Das zu wissen kann das Problem nicht erschweren. Es gibt n! Mögliche Ausgaben (Übereinstimmungen zwischen der ersten und der zweiten Hälfte), was bedeutet, dass Sie log (n!) = Omega (n log n) Vergleiche benötigen. Dies ist durch Sortieren möglich.

Da Sie an Verbindungen zum Problem der Elementunterscheidbarkeit interessiert sind, ist es schwieriger zu beweisen, dass Omega (n log n) für die Elementunterscheidbarkeit gebunden ist, da die Ausgabe binär Ja / Nein ist. Hier muss die Ausgabe übereinstimmen und die Anzahl der möglichen Ausgaben reicht aus, um eine anständige Grenze zu erhalten. Es gibt jedoch eine Variante, die mit der Unterscheidbarkeit von Elementen verbunden ist. Angenommen, Sie erhalten 2n Socken und fragen sich, ob sie eindeutig gepaart werden können. Sie können eine Reduzierung von ED erhalten, indem Sie (a 1 , a 2 , ..., a n ) an (a 1 , a 1 , a 2 , a ) senden 2 , ..., a n , a n ) . (In Klammern ist der Nachweis der Härte von ED über die Topologie sehr interessant.)

Ich denke, dass es ein Omega (n 2 ) für das ursprüngliche Problem geben sollte, wenn Sie nur Gleichheitstests zulassen. Meine Intuition lautet: Betrachten Sie ein Diagramm, in dem Sie nach einem Test eine Kante hinzufügen, und argumentieren Sie, dass die Ausgabe nicht eindeutig bestimmt wird, wenn das Diagramm nicht dicht ist.

sdcvvc
quelle
19

So mache ich das eigentlich für p Paar Socken ( n = 2p einzelne Socken):

  • Nimm zufällig eine Socke vom Stapel.
  • Für die erste Socke oder wenn alle zuvor ausgewählten Socken gepaart wurden, legen Sie die Socke einfach in den ersten "Schlitz" eines "Arrays" ungepaarter Socken vor Ihnen.
  • Wenn Sie eine oder mehrere ungepaarte Socken ausgewählt haben, vergleichen Sie Ihre aktuelle Socke mit allen ungepaarten Socken im Array.
    • Es ist möglich, Socken beim Aufbau Ihres Arrays in allgemeine Klassen oder Typen (weiß / schwarz, Knöchel / Crew, Sport / Kleidung) zu unterteilen und "Drilldown" durchzuführen, um nur vergleichbare Vergleiche durchzuführen.
    • Wenn Sie eine akzeptable Übereinstimmung finden, setzen Sie beide Socken zusammen und entfernen Sie sie aus dem Array.
    • Wenn Sie dies nicht tun, stecken Sie die aktuelle Socke in den ersten offenen Steckplatz im Array.
  • Wiederholen Sie mit jeder Socke.

Das schlimmste Szenario dieses Schemas ist, dass jedes Sockenpaar so unterschiedlich ist, dass es genau übereinstimmen muss und dass die ersten n / 2 Socken, die Sie auswählen, alle unterschiedlich sind. Dies ist Ihr O (n 2 ) -Szenario und äußerst unwahrscheinlich. Wenn die Anzahl der eindeutigen Sockentypen t geringer ist als die Anzahl der Paare p = n / 2 und die Socken in jedem Typ gleich genug sind (normalerweise in Bezug auf den Verschleiß), kann jede Socke dieses Typs mit jeder gepaart werden andere, dann, wie ich oben gefolgert habe, ist die maximale Anzahl von Socken, mit denen Sie jemals vergleichen müssen, t , wonach die nächste, die Sie ziehen, wirdpassen Sie zu einer der ungepaarten Socken. Dieses Szenario ist in der durchschnittlichen Sockenschublade viel wahrscheinlicher als im schlimmsten Fall und reduziert die Komplexität im schlimmsten Fall auf O (n * t), wobei normalerweise t << n ist .

KeithS
quelle
1
Dies ist wahrscheinlich ziemlich nah an meinem mentalen Prozess. Ich habe eine zusätzliche Ebene der Vorsortierungsoptimierung. Meine Sportsocken werden mit den Weißen gewaschen und meine Kleidersocken werden mit Farben gewaschen. Dies bedeutet, dass meine Socken bereits nach Typ gruppiert sind, solange ich nicht zwei Ladungen Wäsche zusammen entsorge. Die weiße Ladung geht sehr schnell (viele identische Socken), aber die Kleidersocken dauern länger. Andere Schlüsselspitze - make mehr verfügbaren Speicher für die Art (falten und alle nicht-Socken zuerst entfernen und dann den Pairing - Algorithmus laufen)
orh
17

Realer Ansatz:

Entfernen Sie so schnell wie möglich die Socken einzeln vom unsortierten Stapel und legen Sie sie in Stapel vor sich. Die Stapel sollten etwas platzsparend angeordnet sein, wobei alle Socken in die gleiche Richtung zeigen. Die Anzahl der Stapel ist durch die Entfernung begrenzt, die Sie leicht erreichen können. Die Auswahl eines Stapels, auf den eine Socke gelegt werden soll, sollte - so schnell wie möglich - erfolgen, indem eine Socke auf einen Stapel scheinbar ähnlicher Socken gelegt wird. Der gelegentliche Fehler vom Typ I (eine Socke auf einen Stapel legen, zu dem er nicht gehört) oder vom Typ II (eine Socke in einen eigenen Stapel legen, wenn ein Stapel ähnlicher Socken vorhanden ist) kann toleriert werden - die wichtigste Überlegung ist die Geschwindigkeit .

Sobald sich alle Socken in Stapeln befinden, gehen Sie schnell durch die Stapel mit mehreren Socken, bilden Paare und entfernen sie (diese gehen in Richtung Schublade). Wenn sich nicht passende Socken auf dem Stapel befinden, stapeln Sie sie wieder auf den besten Stapel (innerhalb der möglichst schnellen Beschränkung). Wenn alle Stapel mit mehreren Socken verarbeitet wurden, stimmen Sie die verbleibenden paarweisen Socken ab, die aufgrund von Typ-II-Fehlern nicht gepaart wurden. Wusch, du bist fertig - und ich habe viele Socken und wasche sie erst, wenn ein großer Teil schmutzig ist. Noch ein praktischer Hinweis: Ich klappe die Oberseite eines Paares Socken über das andere und nutze dabei ihre elastischen Eigenschaften, damit sie beim Transport zur Schublade und in der Schublade zusammen bleiben.

Peter Mortensen
quelle
15

Aus Ihrer Frage geht hervor, dass Sie nicht viel Erfahrung mit Wäsche haben :). Sie benötigen einen Algorithmus, der mit einer kleinen Anzahl nicht paarbarer Socken gut funktioniert.

Die bisherigen Antworten nutzen unsere Funktionen zur Erkennung menschlicher Muster nicht gut aus. Das Spiel Set bietet einen Hinweis darauf, wie man das gut macht: Legen Sie alle Socken in einen zweidimensionalen Raum, damit Sie sie gut erkennen und leicht mit Ihren Händen erreichen können. Dies beschränkt Sie auf eine Fläche von ca. 120 * 80 cm. Wählen Sie dort die Paare aus, die Sie erkennen, und entfernen Sie sie. Legen Sie zusätzliche Socken in den freien Raum und wiederholen Sie. Wenn Sie sich für Personen mit leicht erkennbaren Socken waschen (kleine Kinder kommen in den Sinn), können Sie eine Radix-Sortierung durchführen, indem Sie zuerst diese Socken auswählen. Dieser Algorithmus funktioniert nur dann gut, wenn die Anzahl der einzelnen Socken gering ist

Stephan Eggermont
quelle
So mache ich das normalerweise. Funktioniert viel besser, als jedes Mal alle verbleibenden Socken zu durchlaufen.
Yu_ominae
Netter Ansatz und ich denke, er kann auch auf einige echte CS-Probleme angewendet werden. Können Sie bitte ein Beispiel dafür hinzufügen (ein CS-Problem, bei dem wir einen ähnlichen Ansatz zur Lösung von Problemen verwenden könnten)? Wie skaliert diese Lösung für Millionen von Socken?
Amit
Ich denke, dies ist im Grunde das Gleiche wie die andere Antwort hier, stackoverflow.com/a/14423956 , vom 20. Januar. Beide +1. Das menschliche Sichtsystem ist massiv parallel.
Will Ness
15

Nimm eine erste Socke und lege sie auf einen Tisch. Wählen Sie jetzt eine andere Socke; Wenn es mit dem zuerst ausgewählten übereinstimmt, legen Sie es auf das erste. Wenn nicht, legen Sie es in geringem Abstand vom ersten auf den Tisch. Wählen Sie eine dritte Socke; Wenn es mit einem der beiden vorherigen übereinstimmt, legen Sie es darauf oder platzieren Sie es in geringem Abstand vom dritten. Wiederholen, bis Sie alle Socken aufgenommen haben.

justinfay
quelle
1
Dies ist die einzig gültige Antwort. Alle anderen ignorieren die Tatsache, dass die meiste Zeit damit verbracht wird, zwischen ähnlichen Socken zu unterscheiden (so dass es noch schlimmer ist, sie alle nach ihrem Aussehen zusammenzufassen).
Entonio
Zum Spaß schrieb ich diese Methode des Stapelns
Justin Fay
12

Um zu sagen, wie effizient es ist, Socken von einem Stapel zu koppeln, müssen wir zuerst die Maschine definieren, da die Paarung weder durch eine Turing- noch durch eine Direktzugriffsmaschine erfolgt, die normalerweise als Grundlage für eine verwendet wird algorithmische Analyse.

Die Maschine

Die Maschine ist eine Abstraktion eines realen Elements namens Mensch. Es kann mit zwei Augen aus der Umgebung lesen. Und unser Maschinenmodell kann die Umgebung mit zwei Armen manipulieren. Logische und arithmetische Operationen werden mit unserem Gehirn berechnet (hoffentlich ;-)).

Wir müssen auch die intrinsische Laufzeit der atomaren Operationen berücksichtigen, die mit diesen Instrumenten ausgeführt werden können. Aufgrund physikalischer Einschränkungen weisen Operationen, die von einem Arm oder Auge ausgeführt werden, eine nicht konstante zeitliche Komplexität auf. Dies liegt daran, dass wir weder einen endlos großen Stapel Socken mit einem Arm bewegen können, noch ein Auge die obere Socke auf einem endlos großen Stapel Socken sehen kann.

Die mechanische Physik gibt uns jedoch auch einige Vorteile. Wir sind nicht darauf beschränkt, höchstens eine Socke mit einem Arm zu bewegen. Wir können ein paar von ihnen gleichzeitig bewegen.

Abhängig von der vorherigen Analyse sollten daher folgende Operationen in absteigender Reihenfolge verwendet werden:

  • logische und arithmetische Operationen
  • Umwelt liest
  • Umweltveränderungen

Wir können auch die Tatsache nutzen, dass Menschen nur eine sehr begrenzte Anzahl von Socken haben. Eine Umgebungsänderung kann also alle Socken im Stapel betreffen.

Der Algorithmus

Also hier ist mein Vorschlag:

  1. Verteilen Sie alle Socken im Stapel auf dem Boden.
  2. Finde ein Paar, indem du dir die Socken auf dem Boden ansiehst.
  3. Wiederholen Sie ab 2, bis kein Paar mehr hergestellt werden kann.
  4. Wiederholen Sie von 1 bis keine Socken mehr auf dem Boden sind.

Operation 4 ist notwendig, da beim Verteilen von Socken auf dem Boden einige Socken andere verbergen können. Hier ist die Analyse des Algorithmus:

Die Analyse

Der Algorithmus endet mit hoher Wahrscheinlichkeit. Dies liegt an der Tatsache, dass man in Schritt 2 keine Sockenpaare finden kann.

Für die folgende Laufzeitanalyse der Paarung nvon Sockenpaaren nehmen wir an, dass mindestens die Hälfte der 2nSocken nach Schritt 1 nicht ausgeblendet ist. Im Durchschnitt können wir also n/2Paare finden . Dies bedeutet, dass die Schleife Schritt 4 O(log n)mal ausgeführt wird. Schritt 2 wird O(n^2)mal ausgeführt . Daraus können wir schließen:

  • Der Algorithmus beinhaltet O(ln n + n)Umgebungsmodifikationen (Schritt 1 O(ln n)plus Aufnehmen jedes Paar Socken vom Boden)
  • Der Algorithmus beinhaltet O(n^2)Umgebungslesungen aus Schritt 2
  • Der Algorithmus beinhaltet O(n^2)logische und arithmetische Operationen zum Vergleichen einer Socke mit einer anderen in Schritt 2

Wir haben also eine Gesamtkomplexität der Laufzeit, O(r*n^2 + w*(ln n + n))wo rund wsind die Faktoren für Lese- und Schreibvorgänge in der Umgebung für eine angemessene Anzahl von Socken. Die Kosten für die logischen und arithmetischen Operationen entfallen, da wir davon ausgehen, dass eine konstante Anzahl logischer und arithmetischer Operationen erforderlich ist, um zu entscheiden, ob zwei Socken zu demselben Paar gehören. Dies ist möglicherweise nicht in jedem Szenario möglich.

SpaceTrucker
quelle
1
Dies ist das gleiche wie stackoverflow.com/a/14423956 und stackoverflow.com/a/14468913, denke ich.
Will Ness
@ WillNess Yep, mit ein bisschen mehr Erklärung
SpaceTrucker
12
List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}
Tschad
quelle
12

Ich habe eine andere Lösung herausgebracht, die weder weniger Operationen noch weniger Zeitverbrauch verspricht, aber es sollte versucht werden, herauszufinden, ob sie eine ausreichend gute Heuristik ist, um bei großen Serien von Sockenpaarungen weniger Zeitverbrauch zu erzielen.

Voraussetzungen: Es gibt keine Garantie dafür, dass es die gleichen Socken gibt. Wenn sie dieselbe Farbe haben, bedeutet dies nicht, dass sie dieselbe Größe oder dasselbe Muster haben. Socken werden zufällig gemischt. Es kann eine ungerade Anzahl von Socken geben (einige fehlen, wir wissen nicht wie viele). Bereiten Sie sich darauf vor, sich eine Variable "index" zu merken, und setzen Sie sie auf 0.

Das Ergebnis enthält ein oder zwei Stapel: 1. "übereinstimmend" und 2. "fehlend"

Heuristik:

  1. Finden Sie die markanteste Socke.
  2. Finde seine Übereinstimmung.
  3. Wenn es keine Übereinstimmung gibt, legen Sie sie auf den "fehlenden" Stapel.
  4. Wiederholen Sie von 1. bis es keine markanteren Socken mehr gibt.
  5. Wenn weniger als 6 Socken vorhanden sind, fahren Sie mit 11 fort.
  6. Koppeln Sie blind alle Socken mit dem Nachbarn (packen Sie sie nicht ein)
  7. Finde alle passenden Paare, packe sie und verschiebe die gepackten Paare auf den "passenden" Stapel. Wenn es keine neuen Übereinstimmungen gab - erhöhen Sie "Index" um 1
  8. Wenn "Index" größer als 2 ist (dies kann ein Wert sein, der von der Sockenzahl abhängt, da bei einer größeren Anzahl von Socken die Wahrscheinlichkeit geringer ist, dass sie blind gekoppelt werden), gehen Sie zu 11
  9. Mische den Rest
  10. Gehe zu 1
  11. Vergiss "Index"
  12. Wähle eine Socke
  13. Finde sein Paar
  14. Wenn für die Socke kein Paar vorhanden ist, legen Sie sie auf den "fehlenden" Stapel
  15. Wenn ein Match gefunden wurde, packe es, packe das Paar und verschiebe es auf den "passenden" Stapel
  16. Wenn es noch mehr gibt, gehen die Socken auf 12
  17. Wenn nur noch eine übrig ist, gehen Sie zu 14
  18. Lächeln zufrieden :)

Es könnte auch eine Überprüfung auf beschädigte Socken hinzugefügt werden, als ob diese entfernt würden. Es könnte zwischen 2 und 3 und zwischen 13 und 14 eingefügt werden.

Ich freue mich auf Erfahrungen oder Korrekturen.

Sasa
quelle
Nachdem ich das geschrieben habe, benutze ich es jedes Mal. Es hat mir geholfen, ein bisschen effizienter zu werden und der Job ist jetzt weniger langweilig.
Sasa
11

Wenn ich Socken sortiere, mache ich eine ungefähre Radix-Sortierung und lasse Socken in der Nähe anderer Socken des gleichen Farb- / Mustertyps fallen. Außer in dem Fall, in dem ich eine genaue Übereinstimmung an / in der Nähe des Ortes sehe, an dem ich die Socke fallen lassen werde, extrahiere ich das Paar an diesem Punkt.

Fast alle anderen Algorithmen (einschließlich der Antwort mit der höchsten Punktzahl von usr ) sortieren und entfernen dann Paare. Ich finde, dass es als Mensch besser ist, die Anzahl der Socken zu minimieren, die gleichzeitig in Betracht gezogen werden.

Ich mache das durch:

  1. Eine unverwechselbare Socke auswählen (was auch immer mir zuerst im Stapel auffällt).
  2. Starten einer Radix-Sortierung von diesem konzeptionellen Ort aus, indem Sie Socken aus dem Stapel ziehen, basierend auf der Ähnlichkeit mit diesem.
  3. Platzieren Sie die neue Socke in der Nähe des aktuellen Stapels, wobei der Abstand davon abhängt, wie unterschiedlich sie ist. Wenn Sie feststellen, dass Sie die Socke über eine andere legen, weil sie identisch ist, bilden Sie dort das Paar und entfernen Sie sie. Dies bedeutet, dass zukünftige Vergleiche weniger Aufwand erfordern, um den richtigen Ort zu finden.

Dies nutzt die Fähigkeit des Menschen, in O (1) -Zeit Fuzzy-Matches durchzuführen, was in gewisser Weise der Erstellung einer Hash-Map auf einem Computergerät entspricht.

Wenn Sie zuerst an den markanten Socken ziehen, lassen Sie Platz, um die weniger markanten Merkmale zu "zoomen".

Nachdem Sie die Flurofarbe, die Socken mit Streifen und die drei Paar lange Socken entfernt haben, erhalten Sie möglicherweise überwiegend weiße Socken, die grob nach Abnutzung sortiert sind.

Irgendwann sind die Unterschiede zwischen den Socken so gering, dass andere Menschen den Unterschied nicht bemerken, und es sind keine weiteren Anpassungsbemühungen erforderlich.

Andrew Hill
quelle
10

Wenn Sie eine Socke aufheben, legen Sie sie an einen Ort. Wenn die nächste Socke, die Sie abholen, nicht zur ersten passt, legen Sie sie neben die erste. Wenn ja, gibt es ein Paar. Auf diese Weise spielt es keine Rolle, wie viele Kombinationen es gibt, und es gibt nur zwei Möglichkeiten für jede Socke, die Sie abholen - entweder hat es eine Übereinstimmung, die bereits in Ihrer Sockenreihe enthalten ist, oder es gibt keine, was bedeutet, dass Sie Fügen Sie es an einer Stelle im Array hinzu.

Dies bedeutet auch, dass Sie mit ziemlicher Sicherheit nie alle Ihre Socken im Array haben werden, da die Socken entfernt werden, wenn sie übereinstimmen.

trpt4him
quelle
Dies ist, was ich tue ... O (n)
Pykler
2
@ Pykler - Es ist O (n) im besten Fall und O (n * n) im schlechtesten Fall.
Vilx
2
Dies setzt voraus, dass Sie nicht in Ihrem Kopf einen vollständig eindeutigen Hash für alle Socken erstellen können, die Sie bereits gesehen haben.
Dies
10

Betrachten Sie eine Hash-Tabelle der Größe 'N'.

Wenn wir von einer Normalverteilung ausgehen, ist die geschätzte Anzahl von 'Einfügungen', bei denen mindestens eine Socke einem Eimer zugeordnet ist, NlogN (dh alle Eimer sind voll).

Ich hatte dies als Teil eines anderen Puzzles abgeleitet, würde mich aber freuen, wenn ich mich als falsch erweisen würde. Hier ist mein Blog-Artikel dazu

Lassen Sie 'N' einer ungefähren Obergrenze für die Anzahl der eindeutigen Farben / Muster der Socken entsprechen, die Sie haben.

Sobald Sie eine Kollision haben (auch bekannt als: ein Streichholz), ziehen Sie einfach dieses Paar Socken aus. Wiederholen Sie das gleiche Experiment mit der nächsten Charge von NlogN-Socken. Das Schöne daran ist, dass Sie aufgrund der Funktionsweise des menschlichen Geistes NlogN-Parallelvergleiche (Kollisionsauflösung) durchführen können. :-)

Arvind
quelle
10

Socken, ob echte oder eine analoge Datenstruktur, würden paarweise geliefert.

Die einfachste Antwort ist, bevor das Paar getrennt werden kann, sollte eine einzelne Datenstruktur für das Paar initialisiert worden sein, die einen Zeiger auf die linke und rechte Socke enthält, sodass Socken direkt oder über ihr Paar referenziert werden können. Eine Socke kann auch erweitert werden, um einen Zeiger auf ihren Partner zu enthalten.

Dies löst jedes Problem der rechnerischen Paarung, indem es mit einer Abstraktionsebene entfernt wird.

Wenn Sie dieselbe Idee auf das praktische Problem der Paarung von Socken anwenden, lautet die offensichtliche Antwort: Lassen Sie nicht zu, dass Ihre Socken jemals ungepaart werden. Socken werden als Paar geliefert, als Paar in die Schublade gelegt (möglicherweise durch Zusammenballen) und als Paar getragen. Der Punkt, an dem eine Entkopplung möglich ist, befindet sich in der Waschmaschine. Alles, was erforderlich ist, ist ein physikalischer Mechanismus, der es den Socken ermöglicht, zusammen zu bleiben und effizient gewaschen zu werden.

Es gibt zwei physikalische Möglichkeiten:

Für ein 'Paar'-Objekt, das einen Zeiger auf jede Socke hält, könnten wir einen Stoffbeutel haben, mit dem wir die Socken zusammenhalten. Dies scheint ein massiver Overhead zu sein.

Aber damit jede Socke einen Bezug zur anderen hat, gibt es eine gute Lösung: einen Popper (oder einen Schnappknopf, wenn Sie Amerikaner sind), wie diese:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

Dann schnappen Sie Ihre Socken nur noch zusammen, nachdem Sie sie ausgezogen und in Ihren Wäschekorb gelegt haben. Wiederum haben Sie das Problem beseitigt, dass Sie Ihre Socken mit einer physischen Abstraktion des "Paar" -Konzepts kombinieren müssen.

Mozboz
quelle
Die Frage wird nicht beantwortet, da der Umgang mit bereits gepaarten Daten einfach ist. Die Frage ist, was zu tun ist, wenn die Daten UNPAIRED sind und Sie sie koppeln möchten.
Am
8

Wenn die "Verschieben" -Operation ziemlich teuer ist und die "Vergleichen" -Operation billig ist und Sie den gesamten Satz trotzdem in einen Puffer verschieben müssen, in dem die Suche viel schneller ist als im ursprünglichen Speicher ... integrieren Sie einfach die Sortierung in die obligatorische Bewegung.

Ich fand, dass die Integration des Sortierprozesses in das Aufhängen zum Trocknen ein Kinderspiel ist. Ich muss sowieso jede Socke aufheben und sie aufhängen (bewegen) und es kostet mich ungefähr nichts, sie an einer bestimmten Stelle an den Saiten aufzuhängen. Um die Suche nicht nach dem gesamten Puffer (den Zeichenfolgen) zu erzwingen, platziere ich Socken nach Farbe / Farbton. Links dunkler, rechts heller, bunter vorne usw. Bevor ich jetzt jede Socke aufhänge, schaue ich in ihre "rechte Umgebung", ob bereits eine passende vorhanden ist - dies beschränkt den "Scan" auf 2-3 andere Socken - und wenn ja Ich hänge den anderen direkt daneben. Dann rolle ich sie paarweise, während ich sie trocken von den Saiten entferne.

Nun scheint dies nicht allzu verschieden zu sein von "Bilden von Stapeln nach Farbe", wie es in den Top-Antworten vorgeschlagen wird, aber zuerst habe ich kein Problem damit, zu klassifizieren, ob "lila" zu "rotem" oder "blauem" Stapel wird, indem ich keine diskreten Stapel, sondern Bereiche auswähle. es geht einfach dazwischen. Durch die Integration von zwei Vorgängen (zum Trocknen und Sortieren aufhängen) beträgt der Aufwand für das Sortieren beim Aufhängen etwa 10% des separaten Sortieraufwands.

SF.
quelle
Dieser Ansatz hat zwei weitere Vorteile: Das Trocknen in der Leitung verliert IME viel weniger Socken als der Wäschetrockner, und der Sortiervorgang kann auf den Rest der Wäsche ausgedehnt werden, sodass (z. B.) alle Handtücher nahe beieinander liegen, um von der Wäsche gefaltet zu werden Linie und gruppiert und direkt zu ihrer Lagerung gebracht. Es funktioniert auch in zwei Durchgängen mit geringem Aufwand, bei denen die Kleidung auf- und wieder abgenommen wird.
Cphlewis
8

Ich habe gerade meine Socken gepaart und festgestellt, dass der beste Weg, dies zu tun, der folgende ist:

  • Wählen Sie eine der Socken und legen Sie sie weg (erstellen Sie einen "Eimer" für dieses Paar)
  • Wenn das nächste das Paar des vorherigen ist, legen Sie es in den vorhandenen Bucket, andernfalls erstellen Sie einen neuen.

Im schlimmsten Fall bedeutet dies, dass Sie n / 2 verschiedene Eimer haben und Sie n-2 Bestimmungen darüber haben, welcher Eimer das Paar der aktuellen Socke enthält. Offensichtlich funktioniert dieser Algorithmus gut, wenn Sie nur wenige Paare haben. Ich habe es mit 12 Paaren gemacht.

Es ist nicht so wissenschaftlich, aber es funktioniert gut :)

Maestro
quelle
Dies ist immer noch ein O (n ^ 2) -Algorithmus, da Sie jeden Eimer durchlaufen müssen, wenn Sie eine neue Socke herausziehen. Aber angesichts der Tatsache, dass selbst die Socken, die innerhalb derselben Charge gekauft wurden, geringfügige Unterschiede aufweisen, die sie effektiv paarweise (oder sogar einzeln) machen, gibt es sowieso keinen besseren Weg
Semisonic
Stimmen Sie zu, aber mein Algorithmus geht davon aus, dass der Mensch die Paarung vornimmt. Daher wird es bei der Suche nach dem passenden Bucket eine Art Cache in Ihrem Kopf geben, sodass Sie die Buckets sowieso nicht wirklich durchlaufen müssen. Ich bin mir nicht sicher, welche Art von Datenstruktur für diesen Caching-Mechanismus in meinem Kopf während des Pairings erstellt wird.
Maestro
8

Meine Lösung entspricht nicht genau Ihren Anforderungen, wie es formal erforderlich ist O(n) "zusätzlichen" Speicherplatz benötigt. In Anbetracht meiner Bedingungen ist es jedoch in meiner praktischen Anwendung sehr effizient. Daher denke ich, dass es interessant sein sollte.

Mit anderer Aufgabe kombinieren

Die besondere Bedingung in meinem Fall ist, dass ich keine Trocknungsmaschine benutze, sondern meine Tücher einfach an einen normalen Wäschetrockner hänge. Das Aufhängen von Tüchern erfordert O(n)Operationen (ich denke übrigens immer an das Verpacken von Behältern hier das Problem der ), und das Problem erfordert naturgemäß den linearen "zusätzlichen" Raum. Wenn ich eine neue Socke aus dem Eimer nehme, versuche ich, sie neben das Paar zu hängen, wenn das Paar bereits aufgehängt ist. Wenn es eine Socke von einem neuen Paar ist, lasse ich etwas Platz daneben.

Oracle Machine ist besser ;-)

Es erfordert offensichtlich einige zusätzliche Arbeit, um zu überprüfen, ob die passende Socke bereits irgendwo hängt, und es würde eine Lösung O(n^2)mit einem Koeffizienten 1/2für einen Computer ergeben. Aber in diesem Fall ist der "menschliche Faktor" tatsächlich ein Vorteil - ich kann O(1)die passende Socke normalerweise sehr schnell (fast ) identifizieren, wenn sie bereits aufgehängt war (wahrscheinlich handelt es sich um ein nicht wahrnehmbares Caching im Gehirn) - betrachten Sie es als eine Art begrenztes "Orakel" wie bei Oracle Machine ;-) Wir, die Menschen, haben diese Vorteile in einigen Fällen gegenüber digitalen Maschinen ;-)

Habe es fast O(n)!

Wenn ich also das Problem des Paarens von Socken mit dem Problem des Aufhängens von Tüchern verbinde, bekomme ich O(n)"zusätzlichen Platz" kostenlos und habe eine Lösung, die ungefähr O(n)rechtzeitig ist, nur ein wenig mehr Arbeit erfordert als einfache Hängetücher und den sofortigen Zugriff auf ein komplettes Paar Stoff ermöglicht Socken auch an einem sehr schlechten Montagmorgen ... ;-)

wrzasa
quelle
8

Ich hoffe, ich kann etwas Neues zu diesem Problem beitragen. Mir ist aufgefallen, dass alle Antworten die Tatsache vernachlässigen, dass es zwei Punkte gibt, an denen Sie eine Vorverarbeitung durchführen können , ohne Ihre gesamte Wäscheleistung zu beeinträchtigen.

Auch für große Familien müssen wir keine große Anzahl von Socken annehmen. Socken werden aus der Schublade genommen und getragen, und dann werden sie an einen Ort (vielleicht einen Mülleimer) geworfen, an dem sie bleiben, bevor sie gewaschen werden. Obwohl ich besagten Behälter nicht als LIFO-Stapel bezeichnen würde, würde ich sagen, dass es sicher ist, dies anzunehmen

  1. Leute werfen beide Socken ungefähr in den gleichen Bereich der Tonne,
  2. Der Bin ist zu keinem Zeitpunkt randomisiert und daher
  3. Jede Teilmenge, die oben in diesem Fach entnommen wird, enthält im Allgemeinen beide Socken eines Paares.

Da alle mir bekannten Waschmaschinen eine begrenzte Größe haben (unabhängig davon, wie viele Socken Sie waschen müssen) und die eigentliche Randomisierung in der Waschmaschine erfolgt, haben wir immer kleine Untergruppen, die fast keine enthalten Singletons.

Unsere beiden Vorverarbeitungsschritte sind "die Socken auf die Wäscheleine legen" und "die Socken von der Wäscheleine nehmen", was wir tun müssen, um Socken zu erhalten, die nicht nur sauber, sondern auch trocken sind. Wie bei Waschmaschinen sind Wäscheleinen endlich, und ich gehe davon aus, dass wir den gesamten Teil der Linie haben, in dem wir unsere Socken in Sichtweite bringen.

Hier ist der Algorithmus für put_socks_on_line ():

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

Verschwenden Sie nicht Ihre Zeit damit, Socken zu bewegen oder nach der besten Übereinstimmung zu suchen. Dies alles sollte in O (n) erfolgen, was wir auch benötigen würden, um sie einfach unsortiert auf die Linie zu bringen. Die Socken sind noch nicht gepaart, wir haben nur einige Ähnlichkeitscluster auf der Linie. Es ist hilfreich, dass wir hier nur eine begrenzte Anzahl von Socken haben, da dies uns hilft, "gute" Cluster zu erstellen (wenn sich beispielsweise nur schwarze Socken in der Gruppe der Socken befinden, ist das Clustering nach Farben nicht der richtige Weg).

Hier ist der Algorithmus für take_socks_from_line ():

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

Ich sollte darauf hinweisen, dass es zur Verbesserung der Geschwindigkeit der verbleibenden Schritte ratsam ist, nicht zufällig die nächste Socke auszuwählen, sondern Socken nach Socken nacheinander aus jedem Cluster zu entnehmen. Beide Vorverarbeitungsschritte nehmen nicht mehr Zeit in Anspruch, als nur die Socken auf die Leine oder in den Korb zu legen, was wir auf jeden Fall tun müssen. Dies sollte die Wäscheleistung erheblich verbessern.

Danach ist es einfach, den Hash-Partitionierungsalgorithmus auszuführen. Normalerweise sind ungefähr 75% der Socken bereits gepaart, so dass ich eine sehr kleine Untergruppe von Socken habe, und diese Untergruppe ist bereits (etwas) gruppiert (ich füge nach den Vorverarbeitungsschritten nicht viel Entropie in meinen Korb ein). Eine andere Sache ist, dass die verbleibenden Cluster in der Regel klein genug sind, um sofort verarbeitet zu werden, sodass es möglich ist, einen ganzen Cluster aus dem Warenkorb zu nehmen.

Hier ist der Algorithmus für sort_remaining_clusters ():

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

Danach sind nur noch wenige Socken übrig. Hier füge ich zuvor ungepaarte Socken in das System ein und verarbeite die verbleibenden Socken ohne speziellen Algorithmus - die verbleibenden Socken sind sehr wenige und können visuell sehr schnell verarbeitet werden.

Für alle verbleibenden Socken gehe ich davon aus, dass ihre Gegenstücke noch ungewaschen sind, und lege sie für die nächste Iteration weg. Wenn Sie im Laufe der Zeit ein Wachstum von ungepaarten Socken feststellen (ein "Sockenleck"), sollten Sie Ihren Behälter überprüfen - er könnte zufällig werden (haben Sie Katzen, die dort schlafen?)

Ich weiß, dass diese Algorithmen viele Annahmen treffen: einen Behälter, der als eine Art LIFO-Stapel fungiert, eine begrenzte, normale Waschmaschine und eine begrenzte, normale Wäscheleine - aber dies funktioniert immer noch mit einer sehr großen Anzahl von Socken.

Informationen zur Parallelität: Solange Sie beide Socken in denselben Behälter werfen, können Sie alle diese Schritte problemlos parallelisieren.

Philipp Flenker
quelle
Socken sind nur eine Metapher für das Pairing beliebiger Objekte in einer Datenbank.
Am
1
Verstanden, habe nicht gesehen, dass du der Autor bist. Wenn Sie eine generische Lösung wollten, hätten Sie das wirklich sagen sollen. Es ist jedenfalls nichts Falsches daran, die von Ihnen berücksichtigten Informationen zu berücksichtigen, es sei denn, Sie müssen eine allgemeine Lösung finden. Wenn Sie die Wiederverwendbarkeit der Lösung aufgeben, kann dies zu einer erheblich besseren Leistung führen. In diesem Fall ist es von Vorteil, den Anwendungsfall und die verfügbare Datenbank als Ganzes zu berücksichtigen. Diese spezielle Antwort auf Ihre spezielle Frage hat jedoch Probleme mit ähnlich aussehenden Socken, z. B. schwarzen Socken in verschiedenen Größen, sodass sie in einigen Fällen nicht anwendbar ist.
Philipp Flenker
1
Außerdem haben Sie keine> 2k Upvotes erhalten, weil Sie eine Frage zum Pairing beliebiger Objekte in der Datenbank gestellt haben. Sie haben die Frage aufgrund der Natur der Socken (die Sie im Gegensatz zu Daten nicht duplizieren können) ausdrücklich eingeschränkt. Sie haben sogar empfohlen, die Tatsache zu nutzen, dass Sie Ihre Socken leicht von den Socken Ihres Ehepartners unterscheiden können. Wenn Sie eine Frage zu Socken stellen, erwarten Sie nicht, dass sich die Antworten auf Datenbanken beziehen ;-)
Philipp Flenker
1
Es gibt einige Annahmen: eine normale Waschmaschine, eine normale Wäscheleine und die Tatsache, dass Sie beide Socken gleichzeitig in den Papierkorb werfen, was bedeutet, dass sich in den meisten Fällen beide Socken in derselben Maschine befinden und wie viele übrig gebliebene zu sortierende Socken sind daher klein. Aber da Sie wirklich eine Antwort zum Speichern beliebiger Objekte in der Datenbank wollten, ist es wirklich nützlich, meine Lösung weiter zu diskutieren?
Philipp Flenker
1
Wie gesagt, ich denke, ich habe alles angesprochen, wonach Sie gefragt haben, mit Ausnahme des Problems der Elementunterscheidbarkeit, das von anderen Personen beantwortet wurde. Ich versuche hier nicht, ein Trottel zu sein, aber ich habe vor einiger Zeit viel Mühe in diese Antwort gesteckt und bin leicht enttäuscht, dass Sie jetzt einige der Antworten durchgehen und behaupten, dass sie die ursprüngliche Frage nicht beantwortet haben . Warum lässt du nicht einfach den ganzen Thread in Ruhe - es ist immer noch eine interessante Lektüre, über 2 Jahre nachdem du sie gefragt hast?
Philipp Flenker
8

Ich habe einfache Schritte unternommen, um meinen Aufwand auf einen Prozess zu reduzieren, der O (1) Zeit benötigt.

Indem ich meine Eingaben auf eine von zwei Arten von Socken reduziere (weiße Socken zur Erholung, schwarze Socken für die Arbeit), muss ich nur feststellen, welche von zwei Socken ich in der Hand habe. (Technisch gesehen habe ich den Prozess auf O (0) reduziert, da sie nie zusammen gewaschen werden.)

Es sind einige Vorarbeiten erforderlich, um die gewünschten Socken zu finden und in ausreichender Menge zu kaufen, damit Ihre vorhandenen Socken nicht mehr benötigt werden. Da ich dies getan hatte, bevor ich schwarze Socken brauchte, war mein Aufwand minimal, aber die Laufleistung kann variieren.

Eine solche Vorabanstrengung wurde schon oft in sehr populärem und effektivem Code gesehen. Beispiele sind # DEFINE'ing pi auf mehrere Dezimalstellen (es gibt andere Beispiele, aber das ist das, was mir gerade in den Sinn kommt).

Scott Brickey
quelle
7

Erstellen Sie eine Hash-Tabelle, die für nicht übereinstimmende Socken verwendet wird, wobei Sie das Muster als Hash verwenden. Iterieren Sie nacheinander über die Socken. Wenn die Socke eine Musterübereinstimmung in der Hash-Tabelle hat, nehmen Sie die Socke aus der Tabelle und machen Sie ein Paar. Wenn die Socke keine Übereinstimmung hat, legen Sie sie in den Tisch.

viper110110
quelle
Wie geht das nicht an Ort und Stelle, wie in der Frage ausdrücklich erwähnt?
Am
7

Das Problem beim Sortieren Ihrer n Paar Socken ist O (n) . Bevor Sie sie in der Wäsche werfen Korb , fädeln Sie die linke nach rechts ein. Beim Herausnehmen schneiden Sie den Faden ab und legen jedes Paar in Ihre Schublade - 2 Operationen an n Paaren, also O (n).

Jetzt ist die nächste Frage einfach, ob Sie Ihre eigene Wäsche machen und Ihre Frau ihre. Das ist ein Problem, das wahrscheinlich in einem ganz anderen Bereich von Problemen auftritt . :) :)

Fred Mitchell
quelle
Dies beantwortet nicht die Frage, wo die Socken nur eine Metapher sind.
Am
Die Frage war, wie man die Socken von einem ungepaarten Stapel koppelt und nicht, wie man es vermeidet, gekoppelt zu werden.
Am