Vraag Hoe koppel je sokken efficiënt van een stapel?


Gisteren was ik de sokken aan het schone wasgoed aan het koppelen en dacht ik dat het niet erg efficiënt was. Ik deed een naïef onderzoek - een sok plukken en de stapel 'itereren' om het paar te vinden. Dit vereist itereren over n / 2 * n / 4 = n2/ 8 sokken gemiddeld.

Als computerwetenschapper dacht ik wat ik kon doen? Sortering (naar grootte / kleur / ...) kwam natuurlijk voor de geest om een ​​O (NlogN) -oplossing te bereiken.

Hashing of andere niet-in-plaats oplossingen zijn geen optie, omdat ik mijn sokken niet kan dupliceren (hoewel het leuk zou kunnen zijn als ik dat kon).

Dus de vraag is eigenlijk:

Gegeven een stapel van n paar sokken, bevattende 2n elementen (neem aan dat elke sok exact één bijpassend paar heeft), wat is de beste manier om ze efficiënt te koppelen met maximaal logaritmische extra ruimte? (Ik geloof dat ik me die hoeveelheid info kan herinneren als dat nodig is.)

Ik zal een antwoord waarderen dat de volgende aspecten behandelt:

  • Een generaal theoretisch oplossing voor een groot aantal sokken.
  • Het werkelijke aantal sokken is niet zo groot, ik geloof niet dat mijn partner en ik meer dan 30 paren hebben. (En het is vrij eenvoudig om onderscheid te maken tussen mijn sokken en die van haar, kan dit ook worden gebruikt?)
  • Is het gelijk aan de element onderscheidbaarheid probleem?

3501
2018-01-19 15:34


oorsprong


antwoorden:


Sorteeroplossingen zijn voorgesteld, maar sorteren is een beetje te veel: We hebben geen bestelling nodig; we hebben alleen gelijkheidsgroepen nodig.

Zo hashing zou genoeg (en sneller) zijn.

  1. Voor elke kleur van sokken, vormen een stapel. Itereer over alle sokken in uw invoermandje en verspreid ze op de kleurstapels.
  2. Itereer over elke stapel en distribueer het met een andere meetwaarde (bijvoorbeeld patroon) in de tweede reeks stapels
  3. Recursief dit schema toepassen totdat je alle sokken hebt verdeeld zeer kleine stapels die u onmiddellijk visueel kunt verwerken

Dit soort recursieve hash-partitionering wordt feitelijk gedaan door SQL Server wanneer het hash-join of hash-aggregaat moet zijn over enorme gegevenssets. Het verdeelt zijn build-invoerstroom in vele partities die onafhankelijk zijn. Dit schema wordt lineair geschaald naar willekeurige hoeveelheden gegevens en meerdere CPU's.

U hebt geen recursieve partitionering nodig als u een distributiesleutel (hash-sleutel) kunt vinden biedt voldoende emmers dat elke emmer klein genoeg is om zeer snel te worden verwerkt. Helaas denk ik niet dat sokken zo'n eigenschap hebben.

Als elke sok een geheel getal had dat "PairID" wordt genoemd, zou deze gemakkelijk in 10 buckets kunnen worden verdeeld volgens PairID % 10 (het laatste cijfer).

De beste real-world partitionering die ik kan bedenken is het maken van een rechthoek van palen: de ene dimensie is kleur, de andere is het patroon. Waarom een ​​rechthoek? Omdat we O (1) random toegang tot stapels nodig hebben. (Een 3D kuboid zou ook werken, maar dat is niet erg praktisch.)


Bijwerken:

Hoe zit het met parallellisme? Kunnen meerdere mensen de sokken sneller matchen?

  1. De eenvoudigste parallelliseringsstrategie is om meerdere werknemers uit de invoermand te halen en de sokken op de stapels te leggen. Dit schaalt slechts zo veel - stel je voor dat 100 mensen vechten om 10 stapels. De synchronisatie kosten (zich manifesterend als handbotsingen en menselijke communicatie) vernietig efficiëntie en versnellen (zie de Universele schaalbaarheidswet!). Is dit vatbaar voor impasses? Nee, omdat elke medewerker maar één stapel tegelijk hoeft te openen. Met slechts één "slot" kan er geen patstelling zijn. Livelocks kan mogelijk zijn, afhankelijk van hoe de mens de toegang tot stapels coördineert. Ze kunnen gewoon gebruiken willekeurige backoff zoals netwerkkaarten doen dat op fysiek niveau om te bepalen welke kaart exclusief toegang heeft tot de netwerkkabel. Als het werkt voor NIChet zou ook voor de mens moeten werken.
  2. Het schaalt bijna voor onbepaalde tijd als elke arbeider heeft zijn eigen reeks stapels. Werknemers kunnen dan grote hoeveelheden sokken uit de invoermand nemen (heel weinig geschil omdat ze het zelden doen) en ze hoeven helemaal niet te synchroniseren wanneer ze de sokken verdelen (omdat ze lokale threads hebben). Aan het einde moeten alle arbeiders hun stapel sets verenigen. Ik geloof dat dat kan worden gedaan in O (log (aantal werkers * stapels per werknemer)) als de werknemers een aggregatieboom.

Hoe zit het met de element onderscheidbaarheid probleem? Zoals het artikel vermeldt, kan het probleem van de elemententiteit opgelost worden O(N). Dit is hetzelfde voor het sokkenprobleem (ook O(N), als u slechts één distributiestap nodig hebt (ik heb alleen meerdere stappen voorgesteld omdat mensen slecht zijn in berekeningen - één stap is genoeg als u distribueert op md5(color, length, pattern, ...), d.w.z. perfecte hasj van alle attributen)).

Het is duidelijk dat men niet sneller kan gaan dan O(N), dus we hebben de optimale ondergrens.

Hoewel de uitgangen niet precies hetzelfde zijn (in één geval is dit slechts een booleaanse waarde.) In het andere geval, de paren sokken), zijn de asymptotische complexiteiten hetzelfde.


2176
2017-10-19 20:47



Omdat de architectuur van het menselijk brein heel anders is dan een moderne CPU, is deze vraag niet praktisch.

Mensen kunnen CPU-algoritmen winnen met het feit dat "het vinden van een bijpassend paar" een bewerking kan zijn voor een set die niet te groot is.

Mijn algoritme:

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);
}

Dit is tenminste wat ik in het echte leven gebruik en ik vind het zeer efficiënt. Het nadeel is dat het een plat oppervlak vereist, maar het is meestal overvloedig.


522
2018-05-27 19:13



Zaak 1: Alle sokken zijn identiek (dit doe ik trouwens ook in het echte leven).

Kies er twee uit om een ​​paar te maken. Constante tijd.

Case 2: Er is een constant aantal combinaties (eigendom, kleur, grootte, textuur, enz.).

Gebruik radix sort. Dit is alleen lineaire tijd aangezien vergelijking niet vereist is.

Case 3: Het aantal combinaties is niet van tevoren bekend (algemene situatie).

We moeten een vergelijking doen om te controleren of twee sokken per paar komen. Kies een van de O(n log n) op vergelijkingen gebaseerde sorteringsalgoritmen.

In het echte leven echter, wanneer het aantal sokken relatief klein (constant) is, zouden deze theoretisch optimale algoritmen niet goed werken. Het kan zelfs meer tijd kosten dan sequentieel zoeken, wat in theorie kwadratische tijd vereist.


231



Niet-algoritmisch antwoord, maar "efficiënt" wanneer ik het doe:

  • stap 1) gooi al uw bestaande sokken weg

  • stap 2) ga naar Walmart en koop ze met pakketten van 10 - n pakket witte en m pakketten zwart. Geen behoefte aan andere kleuren in alledaagse voorwerpen leven.

Toch moet ik dit keer op keer opnieuw doen (verloren sokken, beschadigde sokken, enz.), En ik haat het om te vaak goede sokken te vaak weg te gooien (en ik wou dat ze dezelfde sokkenreferentie bleven verkopen!), Dus ik heb onlangs een andere benadering.

Algoritmisch antwoord:

Overweeg dan dat als je slechts één sok voor de tweede stapel sokken trekt, zoals je aan het doen bent, je kansen op het vinden van de bijpassende sok in een naïef zoeken behoorlijk laag zijn.

  • Dus pak er willekeurig vijf van en onthoud hun vorm of lengte.

Waarom vijf? Gewoonlijk zijn mensen goed bezig zich te herinneren tussen vijf en zeven verschillende elementen in het werkgeheugen - een beetje zoals het menselijke equivalent van a RPN stack - five is een veilige standaard.

  • Pak er een op uit de stapel met 2n-5.

  • Zoek nu naar een overeenkomst (visuele patroonovereenkomst - mensen zijn goed in die met een kleine stapel) in de vijf die je tekende, als je er geen vindt, voeg die dan toe aan je vijf.

  • Blijf willekeurig sokken uit de stapel plukken en vergelijk met je 5 + 1-sokken een wedstrijd. Naarmate je stapel groeit, zal dit je prestaties verminderen, maar je kansen verhogen. Veel sneller.

Voel je vrij om de formule op te schrijven om te berekenen hoeveel monsters je moet tekenen voor een kans van 50% op een wedstrijd. IIRC het is een hypergeometrische wet.

Ik doe dat elke ochtend en heb zelden meer dan drie draws nodig - maar ik wel n vergelijkbare paren (rond de 10, geven of nemen de verloren) van m gevormde witte sokken. Nu kun je de grootte van mijn stapel aandelen schatten :-)

BTW, Vond ik dat de som van de transactiekosten van het sorteren van alle sokken elke keer dat ik een paar nodig had veel minder was dan het een keer doen en het binden van de sokken. Een just-in-time werkt beter omdat je dan de sokken niet hoeft te binden, en er is ook een afnemend marginaal rendement (dat wil zeggen, je blijft zoeken naar die twee of drie sokken die ergens in de was zitten en die je nodig hebt om het matchen van je sokken te voltooien en daar verlies je tijd aan).


144



Wat ik doe is dat ik de eerste sok oppak en neerzet (zeg aan de rand van de waskom). Dan pak ik nog een sok en controleer of het hetzelfde is als de eerste sok. Als dat zo is, verwijder ik ze allebei. Als dat niet zo is, leg ik het naast de eerste sok. Dan pak ik de derde sok en vergelijk dat met de eerste twee (als ze er nog steeds zijn). Enz.

Deze benadering kan vrij eenvoudig in een array worden geïmplementeerd, ervan uitgaande dat het verwijderen van sokken een optie is. Eigenlijk hoeft u zelfs geen sokken te "verwijderen". Als u de sokken niet hoeft te sorteren (zie hieronder), dan kunt u ze gewoon verplaatsen en eindigen met een array waarin alle sokken in paren in de array zijn gerangschikt.

Ervan uitgaande dat de enige operatie voor sokken is om te vergelijken voor gelijkheid, is dit algoritme in feite nog steeds een n2 algoritme, hoewel ik niet weet van de gemiddelde zaak (nooit geleerd om dat te berekenen).

Sorteren, verbetert natuurlijk de efficiëntie, vooral in het echte leven, waar je gemakkelijk een sok tussen twee andere sokken kunt "invoegen". Bij het berekenen kan hetzelfde worden bereikt door een boom, maar dat is extra ruimte. En natuurlijk zijn we terug bij NlogN (of een beetje meer, als er verschillende sokken zijn die hetzelfde zijn door sorteercriteria, maar niet van hetzelfde paar).

Verder kan ik niets bedenken, maar deze methode lijkt in het echt behoorlijk efficiënt. :)


92



Dit stelt de verkeerde vraag. De juiste vraag is: waarom besteed ik tijd aan het sorteren van sokken? Hoeveel kost het op jaarbasis, wanneer u uw vrije tijd waardeert voor X-geldeenheden van uw keuze?

En vaker wel dan niet, dit is niet alleen ieder vrije tijd, dat is het ochtend- vrije tijd, die je in je bed zou kunnen uitgeven, of een kopje koffie drinkt, of een beetje vroeg weggaat en niet wordt betrapt in het verkeer.

Het is vaak goed om een ​​stap terug te doen en een manier te vinden om het probleem te omzeilen.

En er is een manier!

Zoek een sok die je leuk vindt. Houd rekening met alle relevante kenmerken: kleur in verschillende lichtomstandigheden, algemene kwaliteit en duurzaamheid, comfort in verschillende klimatologische omstandigheden en geurabsorptie. Het is ook belangrijk dat ze tijdens opslag hun elasticiteit niet verliezen, dus natuurlijke stoffen zijn goed en moeten beschikbaar zijn in een plastic verpakking.

Het is beter als er geen verschil is tussen linker- en rechtervoet sokken, maar het is niet kritisch. Als sokken links-rechts symmetrisch zijn, is het vinden van een paar O (1) -bewerking, en het sorteren van de sokken is bij benadering O (M), waarbij M het aantal plaatsen in uw huis is, dat u hebt bezaaid met sokken, idealiter sommige klein constant getal.

Als je een chique paar hebt gekozen met verschillende linker en rechter sok, neem dan O (N + M), waarbij N het aantal sokken is en M hetzelfde is als hierboven. Iemand anders kan de formule geven voor gemiddelde iteraties van het vinden van het eerste paar, maar het ergste geval voor het vinden van een paar met blind zoeken is N / 2 + 1, wat astronomisch onwaarschijnlijk wordt voor redelijk N. Dit kan worden versneld door een geavanceerd beeld te gebruiken herkenningsalgoritmen en heuristieken, bij het scannen van de stapel ongesorteerde sokken met Mk1 Eyeball.

Een algoritme voor het bereiken van O (1) sokparingefficiëntie (uitgaande van een symmetrische sok) is dus:

  1. Je moet inschatten hoeveel paar sokken je de rest van je leven nodig hebt, of misschien totdat je met pensioen gaat en naar warmere klimaten verhuist zonder ooit opnieuw sokken te moeten dragen. Als je jong bent, kun je ook inschatten hoelang het duurt voordat we allemaal sokken-sorterende robots in huis hebben en het hele probleem niet meer relevant is.

  2. U moet weten hoe u uw geselecteerde sok in bulk kunt bestellen en hoeveel het kost, en leveren ze.

  3. Bestel de sokken!

  4. Weg met je oude sokken.

Een alternatieve stap 3 zou het vergelijken van de kosten van het kopen van hetzelfde aantal misschien goedkopere sokken van een paar paren per keer in de loop van de jaren en het toevoegen van de kosten van het sorteren van sokken met zich meebrengen, maar neem mijn woord voor: het in bulk kopen is goedkoper! Ook stijgen sokken in opslag in waarde met de koersinflatie, wat meer is dan je zou krijgen bij veel investeringen. En dan zijn er ook opslagkosten, maar sokken nemen echt niet veel ruimte in op de bovenste plank van een kast.

Probleem opgelost. Dus, koop nieuwe sokken, gooi / schenk je oude exemplaren weg en leef nog lang en gelukkig nadat je weet dat je elke dag geld en tijd spaart voor de rest van je leven.


50



De theoretische limiet is O (n) omdat je elke sok moet aanraken (tenzij sommige al op de een of andere manier zijn gekoppeld).

Je kunt O (n) bereiken met radix sort. Je hoeft alleen wat attributen voor de emmers te kiezen.

  1. Eerst kun je kiezen (van haar, van mij) - opsplitsen in 2 stapels,
  2. gebruik dan kleuren (kan elke volgorde voor de kleuren hebben, bijvoorbeeld alfabetisch op kleurnaam) - deel ze in stapels op kleur (vergeet niet om de initiële volgorde van stap 1 voor alle sokken op dezelfde stapel te behouden),
  3. dan de lengte van de sok,
  4. dan textuur, ....

Als u een beperkt aantal kenmerken kunt kiezen, maar voldoende attributen die elk paar uniek kunnen identificeren, moet u dat doen in O (k * n), wat O (n) is als we kunnen overwegen dat k beperkt is.


47



Als praktische oplossing:

  1. Maak snel stapels gemakkelijk te onderscheiden sokken. (Zeg op kleur)
  2. Quicksort elke stapel en gebruik de lengte van de sok ter vergelijking. Als een mens kun je een redelijk snelle beslissing nemen die je moet gebruiken om te verdelen en de worst case te vermijden. (U kunt meerdere sokken parallel zien, gebruik dat in uw voordeel!)
  3. Stop met het sorteren van stapels wanneer ze een drempel bereikten waar je het op je gemak vindt om onmiddellijk spotparen en niet-te repareren sokken te vinden

Als je 1000 sokken hebt, met 8 kleuren en een gemiddelde verdeling, kun je 4 stapels van elke 125 sokken in c * n tijd maken. Met een drempel van 5 sokken kun je elke stapel sorteren in 6 runs. (Tel 2 seconden om een ​​sok op de juiste stapel te gooien, het kost je iets minder dan 4 uur.)

Als je slechts 60 sokken, 3 kleuren en 2 soorten sokken (die van je / je vrouw) hebt, kun je elke stapel van 10 sokken in 1 keer sorteren (opnieuw drempel = 5). (Het tellen van 2 seconden duurt 2 minuten).

De eerste emmersortering versnelt je proces, omdat het je n-sokken verdeelt in k-buckets c*n tijd dus dan hoeft u alleen maar te doen c*n*log(k) werk. (Geen rekening houdend met de drempelwaarde). Dus al met al doe je het over n*c*(1 + log(k)) werk, waarbij c de tijd is om een ​​sok op een stapel te gooien.

Deze aanpak zal gunstig zijn in vergelijking met andere c*x*n + O(1) methode zo lang als log(k) < x - 1.


In de informatica kan dit nuttig zijn: We hebben een verzameling van n dingen, een volgorde op deze (lengte) en ook een equivalentie-relatie (extra informatie, bijvoorbeeld de kleur van sokken). De equivalentierelatie stelt ons in staat om een ​​partitie te maken van de originele verzameling, en in elke equivalentieklasse wordt onze bestelling nog steeds onderhouden. Het in kaart brengen van een ding naar de equivalentieklasse kan worden gedaan in O (1), dus alleen O (n) is nodig om elk item aan een klasse toe te wijzen. Nu hebben we onze extra informatie gebruikt en kunnen we op elke manier doorgaan met het sorteren van elke klas. Het voordeel is dat de datasets al aanzienlijk kleiner zijn.

De methode kan ook worden genest, als we meerdere equivalentie-relaties hebben -> kleurenpalen maken, dan binnen elke stapelverdeling op textuur, dan sorteren op lengte. Elke gelijkwaardigheidsrelatie die een partitie met meer dan 2 elementen creëert die ongeveer even groot is, zal een snellere verbetering opleveren dan alleen sorteren (op voorwaarde dat we een sok rechtstreeks toewijzen aan de stapel) en het sorteren kan erg snel gebeuren op kleinere gegevenssets.


31



Deze vraag is eigenlijk diep filosofisch. In essentie gaat het erom of de kracht van mensen om problemen op te lossen (de "wetware" van onze hersenen) gelijk is aan wat kan worden bereikt door algoritmen.

Een voor de hand liggend algoritme voor soksortering is:

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

Nu gaat de informatica in dit probleem helemaal over de stappen

  1. "als s paren met een sok t in N". Hoe snel kunnen we ons herinneren wat we tot nu toe hebben gezien?
  2. "verwijder t van N" en "voeg s toe aan N". Hoe duur is het bijhouden van wat we tot nu toe hebben gezien?

Mensen zullen verschillende strategieën gebruiken om deze te bewerkstelligen. Menselijk geheugen is associatief, zoiets als een hash-tabel waar functiesets opgeslagen waarden worden gekoppeld aan de overeenkomstige waarden zelf. Het concept van "rode auto" -kaarten bijvoorbeeld voor alle rode auto's die een persoon kan onthouden. Iemand met een perfect geheugen heeft een perfecte mapping. De meeste mensen zijn in dit opzicht (en de meeste anderen) onvolmaakt. De associatieve kaart heeft een beperkte capaciteit. Mappings kunnen oproepen uit het bestaan ​​onder verschillende omstandigheden (één bier te veel), wordt per ongeluk geregistreerd ("Ik dacht dat haar naam Betty was, niet Nettie"), of wordt nooit overschreven, ook al merken we dat de waarheid is veranderd ("dad's car" roept op "oranje vuurvogel" toen we wisten dat hij dat had ingeruild voor de rode Camaro).

In het geval van sokken betekent perfect herinneren het kijken naar een sok s produceert altijd het geheugen van zijn broer of zus t, inclusief voldoende informatie (waar het zich op de strijkplank bevindt) om te lokaliseren t in constante tijd. Een persoon met een fotografisch geheugen volbrengt zowel 1 als 2 in constante tijd zonder falen.

Iemand met minder dan perfect geheugen kan een paar commonsense-equivalentieklassen gebruiken op basis van functies die hij kan traceren: grootte (papa, mama, baby), kleur (groenachtig, roodachtig, enz.), Patroon (argyle, gewoon, etc.) , stijl (footie, kniekousen, etc.). Dus de strijkplank zou worden verdeeld in secties voor de categorieën. Dit maakt het meestal mogelijk om de categorie in constante tijd te plaatsen in het geheugen, maar dan is een lineaire zoekopdracht door de categorie "bucket" nodig.

Iemand zonder geheugen of verbeeldingskracht (sorry) zal de sokken gewoon op één stapel houden en een lineaire zoekactie uitvoeren op de hele stapel.

Een nette freak zou numerieke labels voor paren kunnen gebruiken, zoals iemand suggereerde. Dit opent de deur naar een totale ordening, waardoor de mens exact dezelfde algoritmen kan gebruiken als een CPU: binair zoeken, bomen, hashes, enz.

Het "beste" algoritme is dus afhankelijk van de eigenschappen van de wetware / hardware / software die het uitvoert en onze bereidheid om "vals te spelen" door een totale volgorde op paren op te leggen. Zeker een "beste" meta-algoritme is om 's werelds beste sok-sorteerder in te huren: een persoon of machine die een gigantisch stel N van sokattribuutsets kan verzamelen en opslaan in een 1-1 associatief geheugen met constante tijdopzoeking, invoegen en verwijderen. Zowel mensen als machines zoals deze kunnen worden aangeschaft. Als je er een hebt, kun je alle sokken in O (N) tijd koppelen voor N-paar, wat optimaal is. Met de totale orderlabels kunt u standaardhash gebruiken om hetzelfde resultaat te bereiken met een mens- of hardwarecomputer.


25