Ponieważ architektura ludzkiego mózgu jest zupełnie inna niż współczesny procesor, to pytanie nie ma praktycznego sensu.

Ludzie mogą wygrać algorytmy CPU, używając faktu, że "znalezienie pasującej pary" może być jedną operacją dla zestawu, który nie jest zbyt duży.

Mój algorytm:

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

Przypadek 1: wszystkie skarpetki są identyczne (tak przy okazji robię to w prawdziwym życiu).

Wybierz dowolne dwa z nich, aby utworzyć parę. Stały czas.

Przypadek 2: istnieje stała liczba kombinacji (własność, kolor, rozmiar, Tekstura itp.).

Użyj sortowania radix. Jest to tylko czas liniowy, ponieważ porównanie nie jest wymagane.

Przypadek 3 : liczba kombinacji nie jest znana z góry (przypadek ogólny).

Musimy porównanie, aby sprawdzić, czy dwie skarpety są w parze. Wybierz jeden z algorytmów sortowania O(n log n) opartych na porównaniu.

Jednak w prawdziwym życiu, gdy liczba skarpet jest stosunkowo mała( stała), te teoretycznie optymalne algorytmy nie będą działać dobrze. Może to zająć nawet więcej czasu niż wyszukiwanie sekwencyjne, które teoretycznie wymaga czasu kwadratowego.

Odpowiedź Nie algorytmiczna, ale "efektywna" kiedy to robię:

• Krok 1) wyrzuć wszystkie istniejące Skarpetki

• Krok 2) Przejdź do Walmart i kup je przez pakiety 10-N pakietu białe i czarne. Nie ma potrzeby stosowania innych kolorów w codziennych życie.

Jednak raz po raz, muszę to zrobić ponownie (zgubione skarpetki, uszkodzone skarpety, itp.), a nie znoszę zbyt często wyrzucać bardzo dobrych skarpetek (a szkoda, że nie sprzedają te same skarpetki!), więc ostatnio przyjęłam inne podejście.

Odpowiedź algorytmiczna:

Rozważ, że jeśli narysujesz tylko jedną skarpetę na drugi stos skarpet, tak jak to robisz, Twoje szanse na znalezienie pasującej skarpety w naiwnym wyszukiwaniu są dość niskie.

Więc wybierz pięć z nich losowo i zapamiętaj ich kształt lub długość.

• Podnieś jeden ze stosu 2n-5.

• Teraz poszukaj dopasowania (wizualne dopasowanie wzorców - ludzie są w tym dobrzy z małym stosem) wewnątrz wylosowanej piątki, jeśli jej nie znajdziesz, dodaj ją do swojej piątki.

• Zbieraj losowo skarpetki ze stosu i porównuj je ze swoimi skarpetami 5+1 na mecz. Jak Twój stos rośnie, to zmniejszy twoje wydajność, ale zwiększ swoje szanse. Dużo szybciej.

Możesz zapisać wzór, aby obliczyć, ile próbek musisz wylosować, aby uzyskać 50% szans na mecz. IIRC to prawo hipergeometryczne.

Robię to codziennie rano i rzadko potrzebuję więcej niż trzech losowań - ale mam n podobne pary (około 10, mniej więcej przegranych) m W kształcie białych skarpetek. Teraz możesz oszacować wielkość mojego stosu zapasów: -)

BTW , stwierdziłem, że suma koszty transakcyjne sortowania wszystkich skarpet za każdym razem, gdy potrzebowałem pary, były znacznie mniejsze niż robienie tego raz i Wiązanie skarpet. Just-In-time działa lepiej, ponieważ wtedy nie musisz wiązać skarpet, a także malejący marginalny zwrot (to znaczy, ciągle szukasz tych dwóch lub trzech skarpet, które gdzieś w pralni i że musisz zakończyć dopasowywanie skarpet i tracisz czas na to).

To, co robię, to biorę pierwszą skarpetę i odkładam ją (powiedzmy na krawędzi miski na pranie). Potem biorę kolejną skarpetę i sprawdzam, czy jest taka sama jak pierwsza skarpeta. Jeśli tak, usunę je obie. Jeśli nie, położyłem go obok pierwszej skarpety. Potem biorę trzecią skarpetkę i porównuję ją z dwiema pierwszymi (jeśli nadal tam są). Itd.

podejście to można dość łatwo zaimplementować w tablicy, zakładając, że opcja" usuwania " skarpet jest możliwa. Właściwie nie trzeba nawet "zdejmować" skarpet. Jeśli nie potrzebujesz sortowania skarpet (patrz poniżej), możesz je po prostu przesunąć i skończyć z tablicą, która ma wszystkie skarpety ułożone parami w tablicy.

Zakładając, że jedyną operacją dla socks jest porównanie równości, algorytm ten jest w zasadzie nadal n² algorytm, choć nie znam się na przeciętnym przypadku (nigdy nie nauczyłem się tego obliczać).

Sortowanie, oczywiście poprawia wydajność, szczególnie w prawdziwym życiu, gdzie można łatwo "włożyć" skarpetę między dwie inne skarpety. W obliczeniach to samo może osiągnąć drzewo, ale to jest dodatkowa przestrzeń. I, oczywiście, wracamy do NlogN (lub trochę więcej, jeśli istnieje kilka skarpet, które są takie same według kryteriów sortowania, ale nie z tej samej pary).

Poza tym, nie mogę myśleć o niczym, ale ta metoda wydaje się być dość skuteczna w prawdziwym życiu. :)

To jest zadawanie niewłaściwego pytania. Właściwe pytanie brzmi: dlaczego spędzam czas na sortowaniu skarpet? Ile kosztuje w skali roku, gdy cenisz swój wolny czas Za X dowolnie wybrane jednostki monetarne?

I często nie jest to tylko dowolny Czas Wolny, Jest toporanny Czas Wolny, który można spędzić w łóżku, popijając kawę, lub wychodząc trochę wcześniej i nie będąc złapanym w korku.

It ' s czesto good to take a step back, i zastanów się nad problemem.

I jest sposób!

Znajdź skarpetę, którą lubisz. Weź pod uwagę wszystkie istotne cechy: kolor w różnych warunkach oświetleniowych, ogólną jakość i trwałość, komfort w różnych warunkach klimatycznych i pochłanianie zapachów. Ważne jest również, że nie powinny tracić elastyczności w przechowywaniu, więc naturalne tkaniny są dobre i powinny być dostępne w plastikowym opakowaniu.

It 's better if there' s no difference between left and right foot skarpetki, ale to nie jest krytyczne. Jeśli skarpety są symetryczne lewo-prawo, znalezienie pary to operacja O (1), A sortowanie skarpet to przybliżona operacja O(M), gdzie M to liczba miejsc w domu, które zostały zaśmiecone skarpetami, najlepiej jakaś mała stała liczba.

Jeśli wybrałeś elegancką parę z inną lewą i prawą skarpetą, wykonując sortowanie pełnego wiadra do lewej i prawej stopy wiadra weź O (N+M), gdzie N to liczba skarpet, A M jest taka sama jak powyżej. Ktoś inny może dać wzór na średnie iteracje znalezienia pierwszej pary, ale najgorszy przypadek znalezienia pary przy ślepym poszukiwaniu to N / 2+1, co staje się astronomicznie mało prawdopodobnym przypadkiem dla rozsądnego N. można to przyspieszyć za pomocą zaawansowanych algorytmów rozpoznawania obrazu i heurystyki, podczas skanowania stosu niesortowanych skarpet z Mk1 Eyeball .

Więc algorytm osiągania o (1) wydajności parowania skarpet (zakładając skarpety symetryczne) wynosi:

1. Musisz oszacować ile par skarpetki będziesz potrzebować do końca życia, a może do emerytury i przenieść się do cieplejszych klimatów, bez konieczności noszenia Skarpetek nigdy więcej. Jeśli jesteś młody, Możesz również oszacować, jak długo potrwa, zanim wszyscy będziemy mieli roboty sortujące skarpety w naszych domach, a cały problem staje się nieistotny.

2. Musisz dowiedzieć się, w jaki sposób możesz zamówić wybrane skarpety luzem, ile to kosztuje i czy są one dostarczane.

3. Zamów skarpetki!

4. Pozbądź się starych skarpet.

Alternatywnym krokiem 3 byłoby porównanie kosztów zakupu tej samej ilości być może tańszych skarpet kilka par na raz w ciągu roku i dodanie kosztów sortowania skarpet, ale uwierz mi na słowo: kupowanie hurtowo jest tańsze! Również skarpety w magazynie wzrost wartości w tempie inflacji cen akcji, który jest więcej niż można uzyskać na wielu inwestycjach. Potem znowu jest też koszt przechowywania, ale skarpety naprawdę nie zajmuj dużo miejsca na górnej półce szafy.

Problem rozwiązany. Więc po prostu zdobądź nowe skarpetki,wyrzuć / podaruj swoje stare i żyj długo i szczęśliwie, wiedząc, że oszczędzasz pieniądze i czas każdego dnia przez resztę swojego życia.

Teoretyczną granicą jest O (n), ponieważ trzeba dotknąć każdej skarpety (chyba że niektóre są już jakoś sparowane).

Można uzyskać O (n) za pomocą sortowania radix. Musisz tylko wybrać kilka atrybutów dla wiadra.

1. najpierw możesz wybrać (jej, moja) - podzielić je na 2 stosy,
2. Następnie użyj kolorów (może mieć dowolną kolejność kolorów, np. alfabetycznie według nazwy koloru) - podziel je na stosy według koloru (pamiętaj, aby zachować początkową kolejność od kroku 1 dla wszystkich skarpety w tym samym stosie),
3. Następnie długość skarpety,
4. wtedy Tekstura, ....

Jeśli możesz wybrać ograniczoną liczbę atrybutów, ale wystarczająco dużo atrybutów, które mogą jednoznacznie zidentyfikować każdą parę, powinieneś zrobić w O (k * n), które jest O (n), jeśli możemy uznać, że k jest ograniczone.

Jako praktyczne rozwiązanie:

1. szybko wykonaj stosy łatwo rozpoznawalnych skarpet. (Powiedz przez kolor)
2. szybkie sortowanie każdego stosu i użyj długości skarpety do porównania. Jako człowiek możesz podjąć dość szybką decyzję, której skarpety użyć do podziału, aby uniknąć najgorszego przypadku. (Możesz zobaczyć wiele skarpet równolegle, użyj tego na swoją korzyść!)
3. przestań sortować stosy, gdy osiągną próg, przy którym wygodnie znajdziesz pary punktowe i niepakowane skarpety natychmiast

Jeśli masz 1000 skarpet, z 8 kolorami i średnim rozkładem, możesz zrobić 4 stosy z każdego 125 skarpet w czasie c*n. Z progiem 5 skarpet można sortować każdy stos w 6 biegach. (Licząc 2 sekundy, aby rzucić skarpetę na prawy stos, zajmie ci to niewiele poniżej 4 godzin.)

Jeśli masz tylko 60 skarpet, 3 kolory i 2 rodzaje skarpet (Twoje / twojej żony), możesz posortować każdy stos 10 skarpet w 1 biegu (ponownie próg = 5). (Licząc 2 sekundy zajmie ci to 2 min).

Wstępne sortowanie łyżek przyspieszy twój proces, ponieważ dzieli Twoje skarpety n na wiadra k w czasie c*n, więc będziesz musiał tylko wykonać c*n*log(k) pracę. (Nie uwzględniając progu). Więc w sumie robisz o n*c*(1 + log(k)) pracy, gdzie c to czas, aby rzucić skarpetę na stos.

Takie podejście będzie korzystne w porównaniu z dowolną metodą c*x*n + O(1) mniej więcej tak długo, jak log(k) < x - 1.

W informatyce może to być pomocne: Mamy zbiór n rzeczy , kolejność na nich (Długość), a także relacja równoważności (dodatkowe informacje, np. kolor skarpet). Relacja równoważności pozwala nam na utworzenie podziału zbioru pierwotnego i w każdej klasie równoważności zachowany jest nasz porządek. Odwzorowanie rzeczy do jej klasy równoważności może być wykonane w O(1), więc tylko O(n) jest potrzebne do przypisania każdego elementu do klasy. Teraz wykorzystaliśmy nasze dodatkowe informacje i możemy postępować w dowolny sposób, aby posortować każdą klasy. Zaletą jest to, że zbiory danych są już znacznie mniejsze.

Metodę można również zagnieżdżać, jeśli mamy wiele relacji równoważności - > tworzymy stosy kolorów, niż wewnątrz każdej przegrody stosu na teksturze, niż sortujemy na długości. Każda relacja równoważności, która tworzy partycję z więcej niż 2 elementami, które mają mniej więcej parzysty rozmiar, przyniesie poprawę szybkości sortowania (pod warunkiem, że możemy bezpośrednio przypisać skarpetę do jej stosu), a sortowanie może nastąpić bardzo szybko na mniejsze zbiory danych.

To pytanie jest właściwie głęboko filozoficzne. W sercu chodzi o to, czy siła ludzi do rozwiązywania problemów ("wetware" naszych mózgów) jest równoważna temu, co można osiągnąć za pomocą algorytmów.

Oczywistym algorytmem sortowania skarpet jest:

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

Teraz Informatyka w tym problemie polega na krokach

1. "Jeśli s pary z skarpety t W N". Jak szybko możemy "zapamiętać" to, co widzieliśmy do tej pory?
2. "Usuń t z N" i "dodaj s do N". Jak drogie jest śledzenie tego, co widzieliśmy do tej pory?

W przypadku skarpet perfect recall oznacza, że patrząc na skarpetę s zawsze daje pamięć jego rodzeństwa t, w tym wystarczająco dużo informacji (gdzie znajduje się na desce do prasowania), aby zlokalizować t w stałym czasie. Osoba z fotograficzną pamięcią osiąga zarówno 1, jak i 2 w stałym czasie bez przerwy.

Ktoś z mniej niż doskonałą pamięcią może użyć kilku klas równoważności opartych na cechach w jego możliwości śledzenia: rozmiar (papa, mama, dziecko), kolor (zielonkawy, czerwonawy, itp.), wzór (argyle, zwykły itp.), stylu (stopka, kolano, itp.). Tak więc deska do prasowania byłaby podzielona na sekcje dla kategorii. Zazwyczaj pozwala to na lokalizację kategorii w stałym czasie przez pamięć, ale wtedy potrzebne jest liniowe przeszukiwanie kategorii "wiadro".

Ktoś bez pamięci lub wyobraźni w ogóle (przepraszam) będzie po prostu trzymać skarpety w jednym stosie i zrobić liniowe przeszukanie całego stosu.

Porządny świr może używać numerycznych etykiet dla par, jak ktoś zasugerował. Otwiera to drzwi do całkowitego uporządkowania, co pozwala człowiekowi użyj dokładnie tych samych algorytmów, które możemy zastosować z procesorem: wyszukiwanie binarne, drzewa, hasze itp.

Więc" najlepszy "algorytm zależy od cech wetware / sprzętu / oprogramowania, które go uruchamia i naszej gotowości do "oszukiwania" poprzez nałożenie całkowitej kolejności na pary. Z pewnością" najlepszy " meta-algorytm polega na wynajęciu najlepszego na świecie sortownika skarpet: osoby lub maszyny, która może zdobyć i szybko zapisać ogromny zestaw N zestawów atrybutów skarpet w pamięci asocjacyjnej 1-1 ze stałym wyszukiwaniem czasu, Wstaw i usuń. Można pozyskać zarówno ludzi, jak i maszyny. Jeśli masz taki, możesz sparować wszystkie skarpetki w czasie O (N) dla N par, co jest optymalne. Znaczniki total order pozwalają na użycie standardowego hashowania, aby uzyskać ten sam wynik z komputerem ludzkim lub sprzętowym.

Próbujesz rozwiązać zły problem.

Rozwiązanie 1: za każdym razem, gdy wkładasz brudne skarpetki do kosza na pranie, zawiąż je w mały węzeł. W ten sposób nie będziesz musiał sortować po praniu. Pomyśl o tym jak o zarejestrowaniu indeksu w bazie danych Mongo. Trochę pracy do przodu dla niektórych oszczędności procesora w przyszłości.

Rozwiązanie 2: jeśli jest zima, nie musisz nosić pasujących skarpet. Jesteśmy programistami. Nikt nie musi wiedzieć, o ile to działa.

Rozwiązanie 3: rozłóż pracę. Chcesz wykonać tak złożony proces procesora asynchronicznie, bez blokowania interfejsu użytkownika. Weź ten stos skarpet i zapakuj je do torby. Szukaj pary tylko wtedy, gdy jej potrzebujesz. W ten sposób ilość pracy jest znacznie mniej zauważalna.

Mam nadzieję, że to pomoże!

Oto Omega (n log n) dolna granica w modelu porównawczym. (Jedyną poprawną operacją jest porównanie dwóch skarpet.)

Załóżmy, że wiesz że Twoje 2N skarpetki są ułożone w ten sposób:

P₁ p₂ p₃ ... p _n p _{f (1)} p _f(2) ... p _{f (n)}

Gdzie f jest nieznaną permutacją zbioru {1,2,...,n}. Świadomość tego nie może utrudnić problemu. Są n! możliwe wyjścia (dopasowania pomiędzy pierwszym i druga połowa), co oznacza, że potrzebujesz log(n!) = Omega(n log n). Można to uzyskać poprzez sortowanie.

Ponieważ interesują Cię powiązania z problemem odrębności elementów: udowodnienie Omega (n log n) związanej z odrębnością elementów jest trudniejsze, ponieważ wyjście jest binarne tak / nie. Tutaj wyjście musi być dopasowane i liczba możliwych wyjść wystarczy, aby uzyskać przyzwoitą Wiązanie. Istnieje jednak wariant związany z odrębnością elementów. Załóżmy, że dostajesz 2N skarpetki i ciekawe, czy można je wyjątkowo sparować. Możesz uzyskać redukcję z ED wysyłając (a₁, a₂, ..., a _n ) do (a₁, a₁, a₂, a₂, ..., a _n , a _n). (Nawiasem mówiąc, dowód twardości ED jest bardzo interesujący, poprzez topologię .)

Myślę, że powinna istnieć Omega (n²) związany z oryginalnym problemem, jeśli zezwalasz tylko na testy równości. Moja intuicja brzmi: rozważ wykres, w którym dodajesz krawędź po teście i twierdzą, że jeśli Wykres nie jest gęsty, wyjście nie jest jednoznacznie określone.

Koszt: przenoszenie skarpet - > wysokie, znajdowanie/wyszukiwanie skarpet w linii - > Małe

Chcemy zmniejszyć liczbę ruchów i skompensować liczbą wyszukiwań. Możemy również wykorzystać wielowątkowe środowisko Homo Sapiens, aby pomieścić więcej rzeczy w skrytce descision.

X = Twój, Y = twoi małżonkowie

Ze stosu a wszystkich skarpet:

Wybierz dwie skarpety, umieść odpowiednią skarpetę X w linii X, a skarpetę Y w linii Y w następnej dostępnej pozycji.

Do dopóki A nie będzie puste.

Dla każdej linii X i Y

1. Wybierz pierwszą skarpetę w linii, Szukaj wzdłuż linii, aż znajdzie odpowiednią skarpetę.

2. Umieścić w odpowiedniej linii gotowych skarpet.

3. opcjonalne podczas wyszukiwania linii i bieżąca skarpeta, na którą patrzysz, jest identyczna z poprzednią, wykonaj krok 2 dla tych skarpet.

Opcjonalnie do kroku pierwszego, Można Wybrać dwie skarpetki z tej linii zamiast z dwóch, ponieważ pamięć buforująca jest wystarczająco duża, możemy szybko zidentyfikować, czy któreś z sock pasuje do bieżącej na linii, którą obserwujesz. Jeśli masz wystarczająco dużo szczęścia, aby mieć trzy ramiona, możesz ewentualnie przeanalizować trzy skarpety w tym samym czasie, biorąc pod uwagę, że pamięć obiektu jest wystarczająco duża.

Rób, aż oba X i Y będą puste.

Zrobione

Jednakże, ponieważ ma to simillar złożoności jako sortowania wyboru, czas potrzebny jest znacznie mniej ze względu na prędkości I / O (moving socks) i Szukaj (wyszukiwanie linii w poszukiwaniu skarpety).

Tak właśnie to robię, dla P par skarpet (n = 2P poszczególnych skarpet):

• chwyć skarpetę losowo ze stosu.
• dla pierwszej skarpety lub jeśli wszystkie wcześniej wybrane skarpety zostały sparowane, po prostu umieść skarpetę w pierwszym "gnieździe" "tablicy" niesparowanych skarpet przed sobą.
• Jeśli masz jedną lub więcej zaznaczonych skarpet niesparowanych, sprawdź bieżącą skarpetę względem wszystkich niesparowanych skarpet w tablicy.
  • możliwe jest podziel skarpety na klasy ogólne lub typy (biały / czarny, kostka / załoga, athletic / strój) podczas budowania tablicy, i "drill-down", aby porównać tylko jak-dla-jak.
  • Jeśli znajdziesz akceptowalne dopasowanie, złóż oba skarpety razem i usuń je z tablicy.
  • jeśli tego nie zrobisz, włóż bieżącą skarpetkę do pierwszego otwartego gniazda w tablicy.
Powtórz z każdą skarpetą.

Najgorszy scenariusz tego schematu jest taki, że każda para skarpet jest wystarczająco Inna że musi być dokładnie dopasowana i że pierwsze N/2 skarpetki, które wybierzesz, są różne. To jest twoje O (n²) scenariusz, a to jest niezwykle mało prawdopodobne. Jeśli liczba unikalnych typów skarpet t jest mniejsza niż liczba par p = n/2 , a skarpety w każdym typie są na tyle podobne (zwykle w kategoriach związanych ze zużyciem), że każda skarpeta tego typu może być sparowana z innymi, to jak wywnioskowałem powyżej, maksymalna liczba skarpet, które kiedykolwiek będziesz mieć aby porównać do jest t, po czym następny pociągniesz będzie pasował do jednej z niesparowanych skarpet. Ten scenariusz jest znacznie bardziej prawdopodobny w przeciętnej szufladzie skarpet niż w najgorszym przypadku i zmniejsza złożoność najgorszego przypadku do O (n*t), gdzie zwykle t .

Podejście do świata rzeczywistego:

Jak najszybciej usuń skarpetki z niesortowanego stosu pojedynczo i umieść je w stosach przed sobą. Stosy powinny być rozmieszczone nieco przestrzennie, ze wszystkimi skarpetami skierowanymi w tym samym kierunku; liczba stosów jest ograniczona odległością, do której można łatwo dotrzeć. Dobór stosu, na którym należy założyć skarpetę, powinien być-jak najszybciej - poprzez ułożenie skarpety na stosie pozornie podobnych skarpet; okazjonalny typ I (zakładanie skarpety na stosie, do którego nie należy) lub typu II (umieszczenie skarpety we własnym stosie, gdy istnieje istniejący stos podobnych skarpet) błąd może być tolerowany - najważniejszą kwestią jest prędkość . Gdy wszystkie skarpety są w stosach, szybko przejść przez stosy multi-skarpety tworzenia par i usuwania ich (te zmierzają do szuflady). Jeśli w stosie znajdują się skarpety niepasujące do siebie, stosuj je ponownie tak, jak najlepiej (w ramach możliwie najszybszego ograniczenia). Gdy wszystkie stosy multi-sock mają zostały przetworzone, dopasować Pozostałe skarpety paidable, które nie zostały sparowane z powodu błędów typu II. A ja mam dużo skarpetek i nie prać ich, dopóki duża część nie będzie brudna. Kolejna praktyczna Uwaga: odwracam górę jednej z par skarpet na drugą, korzystając z ich elastycznych właściwości, dzięki czemu pozostają razem podczas transportu do szuflady i podczas gdy w szufladzie.

Z twojego pytania wynika, że nie masz zbyt dużego doświadczenia z praniem:). Potrzebujesz algorytmu, który działa dobrze z niewielką liczbą skarpet bez paska.

Odpowiedzi do tej pory nie wykorzystują naszych ludzkich możliwości rozpoznawania wzorców. Gra w zestaw daje wskazówkę, jak to zrobić dobrze: umieścić wszystkie skarpetki w dwuwymiarowej przestrzeni, dzięki czemu można je dobrze rozpoznać i łatwo dotrzeć do nich rękami. Ogranicza to obszar około 120 * 80 cm lub więc. Stamtąd wybierz pary, które rozpoznajesz i usuń je. Umieść dodatkowe skarpetki w wolnej przestrzeni i powtórz. Jeśli myjesz dla osób z łatwo rozpoznawalnymi skarpetkami (przychodzą na myśl małe dzieci), możesz zrobić sortowanie radix, wybierając najpierw te skarpetki. Algorytm ten działa dobrze tylko wtedy, gdy liczba pojedynczych skarpet jest niska

Weź pierwszą skarpetkę i połóż ją na stole. Teraz wybierz kolejną skarpetę; jeśli pasuje do pierwszej, umieść ją na pierwszej. Jeśli nie, umieść go na stole w niewielkiej odległości od pierwszego. Wybierz trzecią skarpetę; jeśli pasuje do jednej z dwóch poprzednich, umieść ją na nich lub umieść w niewielkiej odległości od trzeciej. Powtarzaj, dopóki nie podniesiesz wszystkich skarpet.

Aby powiedzieć, jak skuteczne jest sparowanie skarpet ze stosu, musimy najpierw zdefiniować maszynę, ponieważ parowanie nie jest wykonywane czy przez Turinga, czy przez maszynę dostępu losowego, które są zwykle używane jako podstawa analizy algorytmicznej.

Maszyna

Musimy również wziąć pod uwagę wewnętrzny czas trwania operacji atomowych, które mogą być przeprowadzane za pomocą tych instrumentów. Ze względu na ograniczenia fizyczne, operacje wykonywane przez ramię lub oko mają niestałą złożoność czasową. Dzieje się tak dlatego, że nie możemy przenieść nieskończenie dużej stosy skarpet ramieniem ani oko nie może zobaczyć górnej skarpety na nieskończenie dużej stosie skarpet. skarpetki.

Jednak fizyka mechaniczna daje nam również kilka zalet. Nie ograniczamy się do poruszania co najwyżej jedną skarpetą ręką. Możemy przenieść kilka na raz.

Zatem w zależności od poprzedniej analizy należy zastosować następujące operacje w kolejności malejącej:

• operacje logiczne i arytmetyczne
• odczyty środowiskowe
• modyfikacje środowiska

Algorytm

Oto moja propozycja:

1. rozłóż wszystkie skarpety w stosie na podłodze.
2. Znajdź parę patrząc na skarpety na podłodze.
3. Powtórz od 2, aż żadna para nie może być wykonana.
4. Powtórz od 1, aż nie będzie skarpetek na podłodze.

Operacja 4 jest konieczna, ponieważ przy rozłożeniu skarpet na podłodze niektóre skarpety mogą ukryć innych. Oto analiza algorytmu:

Analiza

Algorytm kończy się z dużym prawdopodobieństwem. Wynika to z faktu, że nie można znaleźć par skarpet w Kroku 2.

Dla poniższej analizy parowania n par skarpet, Zakładamy, że co najmniej połowa skarpet 2n nie jest ukryta po kroku 1. Tak więc w przeciętnym przypadku możemy znaleźć n/2 pary. Oznacza to, że pętla jest krokiem 4 wykonywanym O(log n) razy. Krok 2 jest wykonywany O(n^2) razy. Możemy więc stwierdzić:

• algorytm obejmuje O(ln n + n) modyfikacje środowiskowe (Krok 1 O(ln n) plus wybieranie każdej pary skarpet z podłogi)
• algorytm obejmuje O(n^2) odczyty środowiskowe z kroku 2
• algorytm obejmuje O(n^2) operacje logiczne i arytmetyczne dla porównania skarpety z innym w Kroku 2

Mamy więc całkowitą złożoność runtimeO(r*n^2 + w*(ln n + n)) gdzie r i w są czynniki dla środowiskowych operacji odczytu i zapisu odpowiednio dla rozsądnej ilości skarpet. Pomija się koszt operacji logicznych i arytmetycznych, ponieważ zakładamy, że potrzeba stałej ilości operacji logicznych i arytmetycznych, aby zdecydować, czy 2 skarpety należą do tej samej pary. Może to nie być możliwe w każdym scenariuszu.

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

Wyszedłem z innym rozwiązaniem, które nie obiecywałoby mniej operacji, ani mniej zużycia czasu, ale należy spróbować sprawdzić,czy może to być wystarczająco dobre heurystyczne, aby zapewnić mniejsze zużycie czasu w ogromnych seriach parowania skarpet.

Warunki wstępne: Nie ma gwarancji, że są te same skarpety. Jeśli są tego samego koloru, nie oznacza to, że mają ten sam rozmiar lub wzór. Skarpetki są losowo tasowane. Może być nieparzysta liczba skarpet (niektórych brakuje, nie wiemy ilu). Przygotuj się do zapamiętania zmiennej "index" i ustaw ją na 0.

Wynik będzie miał jedną lub dwie stosy: 1. "matched" i 2. "missing"

heurystyka:

1. Znajdź najbardziej charakterystyczną skarpetę.
2. znajdź swoje dopasowanie.
3. jeśli nie ma dopasowania, umieść go na "brakującym" stosie.
4. Powtórz od 1. dopóki nie będzie już najbardziej charakterystycznych skarpet.
5. jeśli jest ich mniej niż 6, przejdź do 11.
6. sparuj na ślepo wszystkie skarpetki do sąsiada (nie Pakuj)
7. Znajdź wszystkie dopasowane pary, spakuj je i przenieś spakowane pary na "dopasowany" stos; If there were no new matches-increment "index" by 1
8. jeśli "index" jest większy niż 2 (może to być wartość zależna od sock Liczba, ponieważ przy większej liczbie skarpet jest mniejsza szansa na połącz je ślepo) idź do 11
9. przetasuj resztę
10. idź do 1
11. zapomnij o "indeksie"
12. Wybierz a skarpeta
13. Znajdź swoją parę
14. jeśli nie ma pary dla skarpety, przenieś ją na" brakujący " stos
15. jeśli znaleziono dopasowanie, spakuj je i przenieś do "dopasowanego" stosu
16. jeśli jest jeszcze więcej, to jedna skarpetka idzie do 12
17. jeśli został tylko jeden przejdź do 14
18. uśmiech zadowolony:)

Można też dodać sprawdzanie uszkodzonych skarpet, tak jakby ich usunięcie. Można go wstawić między 2 a 3, a między 13 a 14.

Z niecierpliwością czekam na jakieś doświadczenia lub poprawki.

Skarpety, czy to rzeczywiste, czy jakaś analogiczna struktura danych, byłyby dostarczane parami.

Najprostszą odpowiedzią jest to, że przed zezwoleniem na rozdzielenie pary, należy zainicjować pojedynczą strukturę danych dla pary, która zawierała wskaźnik do lewej i prawej skarpety, umożliwiając w ten sposób odwoływanie się do skarpet bezpośrednio lub za pośrednictwem ich pary. Skarpeta może być również rozszerzona, aby zawierała wskaźnik do swojego partnera.

To rozwiązuje każdy problem parowania obliczeniowego, usuwając go z warstwą abstrakcji.

Stosując ten sam pomysł do praktycznego problemu parowania skarpet, pozorna odpowiedź brzmi: nie pozwól, aby Twoje skarpety kiedykolwiek były nieparowane. Skarpetki są dostarczane jako para, wkładane do szuflady jako para( być może przez łączenie ich razem), noszone jako para. Ale punkt, w którym rozpylanie jest możliwe, znajduje się w pralce, więc wszystko, co jest wymagane, to fizyczny mechanizm, który pozwala skarpetom trzymać się razem i być efektywnie pranym.

Istnieją dwa fizyczne możliwości:

Dla obiektu "Para", który utrzymuje wskaźnik do każdej skarpety, możemy mieć torbę z tkaniny, której używamy do trzymania skarpet razem. To wygląda na ogromne koszty.

Ale dla każdej skarpetki, aby zachować odniesienie do drugiej, istnieje zgrabne rozwiązanie: popper (lub "przycisk zatrzaskowy", jeśli jesteś Amerykaninem), takie jak te:

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

Wtedy wszystko, co robisz, to pstrykasz skarpetki tuż po tym, jak zdejmij je i włóż do kosza do prania, A ponownie wyeliminowałeś problem konieczności sparowania skarpet z fizyczną abstrakcją koncepcji "pary".

Kiedy sortuję skarpetki, robię przybliżony sortowanie radix , upuszczając skarpetki w pobliżu innych skarpet tego samego koloru/wzoru. Z wyjątkiem przypadku, gdy widzę dokładne dopasowanie w / w pobliżu miejsca, w którym mam zamiar upuścić skarpetę, wyciągam parę w tym momencie.

Prawie wszystkie inne algorytmy (w tym najwyżej punktowana odpowiedź usr) sortują, a następnie usuwają pary. Uważam, że jako człowiek lepiej jest zminimalizować liczbę skarpet rozważanych w jednym czasie.

I do this by:

1. Wybieranie charakterystycznej skarpety(cokolwiek wpadnie mi w oko jako pierwsze w stosie).
2. rozpoczynając sortowanie radix od tego konceptualnego miejsca, wyciągając skarpety ze stosu na podstawie podobieństwa do tego.
3. umieść nową skarpetę blisko obecnego stosu, z odległością w zależności od tego, jak różni się ona od siebie. Jeśli znajdziesz się kładąc skarpetę na innym, ponieważ jest identyczna, uformuj tam parę i usuń je. Oznacza to, że przyszłe porównania przyjmują mniej wysiłku, aby znaleźć właściwe miejsce.

Wykorzystuje to ludzką zdolność do rozmytego dopasowania w czasie O (1), co jest w pewnym sensie równoważne ustanowieniu mapy hash na urządzeniu komputerowym.

Najpierw wyciągając charakterystyczne skarpetki, zostawiasz miejsce, aby "przybliżyć" cechy, które są mniej charakterystyczne, na początek.

Po wyeliminowaniu koloru fluro, skarpet z paskami i trzech par długich skarpet, możesz skończyć z głównie białymi skarpetki z grubsza posortowane według ich zużycia.

W pewnym momencie różnice między skarpetkami są na tyle małe, że inni nie zauważą różnicy, a dalsze dopasowywanie nie jest potrzebne.

Kiedy podniesiesz skarpetę, umieść ją w jednym miejscu. Następnie następna skarpeta, którą podniesiesz, jeśli nie pasuje do pierwszej skarpety, ustaw ją obok pierwszej. Jeśli tak, to jest para. W ten sposób nie ma znaczenia, ile kombinacji istnieje, i są tylko dwie możliwości dla każdej skarpety, którą odbierasz - albo ma dopasowanie, które jest już w tablicy skarpet, albo nie, co oznacza, że dodajesz je do miejsca w tablicy.

Oznacza to również, że będziesz prawie z pewnością nigdy nie miej wszystkich skarpet w tablicy, ponieważ skarpety zostaną usunięte, jak są dopasowane.

Rozważmy tabelę hashową o rozmiarze "N".

Jeśli przyjmiemy rozkład normalny, to Szacunkowa liczba "wstawek", które mają przynajmniej jedną skarpetę odwzorowaną na jednym wiadrze, to NlogN (tzn. wszystkie wiadra są pełne)

Wywnioskowałem to jako część innej układanki, ale z przyjemnością udowodnię, że się mylę. Oto mój artykuł na blogu o tym samym

Niech " N " odpowiada przybliżonej górnej granicy na liczbę unikalnych kolorów / wzorów skarpet, które ty mam.

Gdy masz kolizję (a.K.A : mecz) po prostu usuń tę parę skarpet. Powtórz ten sam eksperyment z kolejną porcją skarpet NlogN. Piękno tego jest to, że można być dokonywanie porównań równoległych NlogN (rozdzielczość kolizji) ze względu na sposób, w jaki działa ludzki umysł. :-)

Jeśli operacja " przenieś "jest dość droga, a operacja" porównaj " jest tania, a i tak trzeba przenieść cały zestaw do bufora, w którym wyszukiwanie jest znacznie szybsze niż w oryginalnym magazynie... wystarczy zintegrować sortowanie z obowiązkowym ruchem.

Odkryłem, że integracja procesu sortowania do powieszenia do wyschnięcia sprawia, że jest to proste. I tak muszę odebrać każdą skarpetę i powiesić ją (przenieść) i nic mnie nie kosztuje powieszenie jej w konkretnym miejscu na sznurkach. Teraz tylko nie zmuszać wyszukiwanie całego bufora (ciągów) wybieram umieszczenie skarpet według koloru/odcienia. Ciemniejszy lewy, jaśniejszy prawy, bardziej kolorowy przód itp. Teraz zanim powieszę każdą skarpetkę, patrzę w jej "właściwą okolicę", czy pasująca już tam jest - to ogranicza" skanowanie " do 2-3 innych skarpet - a jeśli tak, to wieszam drugą tuż obok. Następnie zwijam je w pary, zdejmując ze sznurków, gdy wyschną.

Teraz może się to wydawać zupełnie inne od" formowania stosów według koloru " sugerowanego przez top odpowiedzi ale po pierwsze, nie wybierając dyskretnych stosów, ale zakresów, nie mam problemu z klasyfikacją, czy "fioletowy" idzie do" czerwonego "czy" niebieskiego " stosu; po prostu przechodzi między. A następnie poprzez zintegrowanie dwóch operacji (powiesić na sucho i posortować) narzut sortowania podczas zawieszania wynosi około 10% tego, co byłoby oddzielnym sortowaniem.

Mam nadzieję, że mogę wnieść coś nowego do tego problemu. Zauważyłem, że wszystkie odpowiedzi pomijają fakt, że istnieją dwa punkty, w których można wykonać wstępne przetwarzanie , bez spowalniania ogólnej wydajności prania.

1. ludzie rzucają obie skarpetki mniej więcej w tym samym miejscu bin,
2. kosz nie jest randomizowany w żadnym punkcie, a zatem
3. każdy podzbiór wzięty z góry tego kosza zazwyczaj zawiera zarówno skarpetki z pary.

Ponieważ wszystkie pralki, o których Wiem, są ograniczone rozmiarami( niezależnie od tego, ile skarpet trzeba wyprać), a faktyczna randomizacja występuje w pralce, bez względu na to, ile mamy zawsze małe podzbiory, które nie zawierają prawie żadnych singletonów.

Nasze dwa etapy wstępnego przetwarzania to "zakładanie skarpet na sznur" i "zdejmowanie skarpet z sznurka", co musimy zrobić, aby uzyskać skarpety, które są nie tylko czyste, ale także suche. Podobnie jak w przypadku pralek, sznurki na ubrania są skończone i zakładam, że mamy całą część linii, w której wkładamy skarpetki.

Oto algorytm dla 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 
 }
}

Nie trać czasu na przenoszenie skarpet lub szukanie najlepszego dopasowania, to wszystko powinno być zrobione w O (n), które również potrzebujemy po prostu umieścić je na linii niesortowane. Skarpetki nie są jeszcze sparowane, mamy tylko kilka klastrów podobieństwa na linii. Dobrze, że mamy tutaj ograniczony zestaw skarpet, ponieważ pomaga nam to tworzyć "dobre" klastry (na przykład, jeśli w zestawie są tylko czarne skarpety, Grupowanie według kolorów nie byłoby way to go)

Oto algorytm 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
 }

Powinienem zwrócić uwagę, że aby poprawić prędkość pozostałych kroków, mądrze jest nie wybierać losowo następnej skarpety, ale sekwencyjnie pobierać skarpety po skarpetach z każdego klastra. Oba etapy wstępnego przetwarzania nie zajmują więcej czasu niż tylko umieszczenie skarpetek na linii lub w koszu, co musimy zrobić bez względu na wszystko, więc powinno to znacznie zwiększyć wydajność prania.

Po tym, to łatwo zrobić algorytm partycjonowania hash. Zazwyczaj około 75% skarpet jest już sparowanych, pozostawiając mi bardzo mały podzbiór skarpet, a ten podzbiór jest już (nieco) klastrowy (nie wprowadzam zbyt wiele entropii do mojego koszyka po etapach wstępnego przetwarzania). Inną rzeczą jest to, że pozostałe klastry są na tyle małe, że można je obsługiwać jednocześnie, więc możliwe jest wyjęcie całego klastra z koszyka.

Oto algorytm dla sort_remaining_clusters ():

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

Dla wszystkich pozostałych Skarpetek, zakładam, że ich odpowiedniki są nadal nieumyte i odkładam je na następną iterację. Jeśli zarejestrujesz wzrost niesparowanych skarpet w czasie ("wyciek skarpet"), powinieneś sprawdzić swój kosz - może być randomizowany (czy masz koty, które tam śpią?)

Wiem, że te algorytmy przyjmują wiele założeń: kosz, który działa jak jakiś stos LIFO, ograniczona, normalna pralka i ograniczona, normalna linia na ubrania - ale to nadal działa z bardzo dużą liczbą skarpet.

O paralelizmie: Tak długo, jak wrzucisz oba skarpety do tego samego kosza, możesz łatwo równoległe wszystkie te kroki.

Podjąłem proste kroki, aby zredukować mój wysiłek do procesu, który zajmuje O(1) czas.

Poprzez zmniejszenie moich wejść do jednego z dwóch rodzajów skarpet (białe skarpety rekreacyjne, czarne skarpety do pracy), muszę tylko określić, które z dwóch skarpet mam w ręku. (Technicznie, ponieważ nigdy nie są myte razem, zmniejszyłem proces do czasu O (0))

Aby znaleźć pożądane skarpetki, i zakupić je w wystarczającej ilości, aby wyeliminować potrzebę istniejących skarpetki. Ponieważ zrobiłem to przed potrzebą czarnych skarpet, mój wysiłek był minimalny, ale przebieg może się różnić.

Taki wysiłek z góry widać już wiele razy w bardzo popularnym i skutecznym kodzie. Przykłady obejmują # DEFINE ' ING pi do kilku miejsc po przecinku (inne przykłady istnieją, ale to właśnie teraz przychodzi mi na myśl).

Utwórz tabelę hash, która będzie używana dla niezrównanych skarpet, używając wzorca jako hash. Powtarzaj skarpety Jeden po drugim. Jeśli skarpeta ma wzór dopasowany w tabeli hash, wyjmij skarpetę ze stołu i stwórz parę. Jeśli skarpeta nie ma zapałki, umieść ją w tabeli.

Problem sortowania Twoich N par skarpet to O (n). Zanim wrzucisz je do Kosza , przewlecz lewy do prawego. Wyjmując je, przecinasz nić i wkładasz każdą parę do szuflady - 2 operacje na N parach, więc O (n).

Teraz następne pytanie brzmi, czy robisz własne pranie, a twoja żona robi swoje. Jest to problem prawdopodobnie w zupełnie innej domenie problemów . :)

Właśnie skończyłam parować skarpetki i stwierdziłam, że najlepszym sposobem na to jest:

• Wybierz jedną ze skarpet i odłóż ją (Utwórz "wiadro" dla tej pary)
• jeśli następna jest parą poprzedniej, umieść ją w istniejącym wiadrze, w przeciwnym razie utwórz nowe.

W najgorszym przypadku oznacza to, że będziesz miał n / 2 różne wiadra i będziesz miał N-2 oznaczenia o tym, które wiadro zawiera parę bieżąca skarpeta. Oczywiście, algorytm ten działa dobrze, jeśli masz tylko kilka par; zrobiłem to z 12 par.

To nie jest takie naukowe, ale działa dobrze:)

Moje rozwiązanie nie do końca odpowiada Twoim wymaganiom, ponieważ formalnie wymaga O(n) "dodatkowej" przestrzeni. Jednak, biorąc pod uwagę moje Warunki, jest to bardzo skuteczne w moim praktycznym zastosowaniu. Dlatego myślę, że powinno być interesujące.

Połącz z innymi zadaniami

Specjalnym warunkiem w moim przypadku jest to, że nie używam suszarki, po prostu wieszam moje ubrania na zwykłej suszarce. Wiszące ściereczki wymagają O(n) operacji (przy okazji zawsze rozważam pakowanie do kosza problem tutaj) i problem ze swej natury wymaga liniowej "dodatkowej" przestrzeni. Kiedy biorę nową skarpetę z wiadra, staram się powiesić ją obok pary, jeśli para jest już zawieszona. Jeśli to skarpeta z nowej pary, zostawiam trochę miejsca obok.

Maszyna Oracle jest lepsza; -)

Oczywiście wymaga dodatkowej pracy, aby sprawdzić, czy gdzieś wisi już pasująca skarpeta i wyrenderuje rozwiązanie {[2] } o współczynniku około 1/2 dla komputera. Ale w tym przypadku "czynnik ludzki" jest w rzeczywistości zaletą-Zwykle mogę bardzo szybko (prawie O(1)) zidentyfikować pasującą skarpetkę, jeśli była już zawieszona (prawdopodobnie dotyczy to niezauważalnego buforowania w mózgu) -- Uznaj ją za rodzaj ograniczonej "oracle", jak w Maszyna Oracle ; -) my, ludzie, w niektórych przypadkach mamy te zalety nad maszynami cyfrowymi ; -) {]}

Miej to prawie O(n)!

W ten sposób łącząc problem parowania skarpet z problemem wiszących ściereczek dostaję O(n) "extra przestrzeń " za darmo, i mieć rozwiązanie, które jest o O(n) w czasie, wymaga tylko trochę więcej pracy niż proste tkaniny wiszące i pozwala na natychmiastowy dostęp do pełnej pary skarpet nawet w bardzo zły poniedziałek rano... ;-)