Mam nadzieję, że mogę wnieść coś nowego do rozwiązania tego problemu. Zauważyłem, że wszystkie odpowiedzi pomijają fakt, że istnieją dwa punkty, w których można wykonać przetwarzanie wstępne , bez spowalniania ogólnej wydajności prania.
Ponadto nie musimy zakładać dużej liczby skarpet, nawet dla dużych rodzin. Skarpetki są wyjmowane z szuflady i noszone, a następnie są wrzucane do miejsca (na przykład do kosza), w którym pozostają, zanim zostaną wyprane. Chociaż nie nazwałbym wspomnianego bin stosem LIFO, powiedziałbym, że można to bezpiecznie założyć
- ludzie rzucają obu skarpetami mniej więcej w tym samym obszarze kosza,
- bin nie jest losowy w żadnym momencie i dlatego
- jakikolwiek podzbiór pobrany z góry tego pojemnika ogólnie zawiera obie skarpety pary.
Ponieważ wszystkie pralki, o których wiem, mają ograniczony rozmiar (niezależnie od liczby skarpet, które musisz wyprać), a faktyczna losowość zachodzi w pralce, bez względu na to, ile mamy skarpet, zawsze mamy małe podzbiory, które prawie nie zawierają singletony.
Nasze dwa etapy przetwarzania wstępnego to „zakładanie skarpet na sznurki” i „zdejmowanie skarpet z sznurka”, co musimy zrobić, aby uzyskać skarpetki, które są nie tylko czyste, ale również suche. Podobnie jak w przypadku pralek, sznurki na ubrania są skończone i zakładam, że mamy całą linię, w której widzimy skarpetki.
Oto algorytm 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 marnuj czasu na przenoszenie skarpet i szukanie najlepszego dopasowania, wszystko to powinno być zrobione w O (n), którego również potrzebowalibyśmy po prostu umieszczając je na linii nieposortowane. Skarpetki nie są jeszcze sparowane, w linii mamy tylko kilka podobieństw. Pomocne jest to, że mamy tutaj ograniczony zestaw skarpet, ponieważ pomaga nam to tworzyć „dobre” klastry (na przykład, jeśli w zestawie skarpet znajdują się tylko czarne skarpetki, grupowanie według kolorów nie byłoby dobrym rozwiązaniem)
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 zaznaczyć, że aby poprawić szybkość pozostałych kroków, rozsądnie jest nie wybierać losowo następnej skarpety, ale kolejno pobierać skarpetę za skarpetą z każdej grupy. Oba etapy przetwarzania wstępnego nie zajmują więcej czasu niż samo włożenie skarpetek do linii lub do kosza, co musimy zrobić bez względu na wszystko, więc powinno to znacznie poprawić wydajność prania.
Po tym łatwo jest wykonać algorytm partycjonowania mieszającego. Zwykle około 75% skarpet jest już sparowanych, co pozostawia mi bardzo mały podzbiór skarpet, a ten podzbiór jest już (nieco) zgrupowany (nie wprowadzam dużej 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łużyć od razu, więc można wyjąć całą grupę z koszyka.
Oto algorytm sort_remaining_clusters ():
while(clusters present in basket) {
Take out the cluster and spread it
Process it immediately
Leave remaining socks where they are
}
Potem zostało już tylko kilka skarpet. Tutaj wprowadzam do systemu wcześniej niesparowane skarpety i przetwarzam pozostałe skarpetki bez specjalnego algorytmu - pozostałe skarpetki są bardzo nieliczne i mogą być przetwarzane wizualnie bardzo szybko.
W przypadku wszystkich pozostałych skarpet zakładam, że ich odpowiedniki są nadal niemyte i odkładam je na następną iterację. Jeśli z czasem zauważysz wzrost liczby niesparowanych skarpet („wyciek skarpetki”), powinieneś sprawdzić swój kosz - może się losować (czy masz tam koty, które tam śpią?)
Wiem, że algorytmy te przyjmują wiele założeń: kosz, który działa jak pewien stos LIFO, ograniczona, normalna pralka i ograniczona, normalna linia ubrań - ale to nadal działa z bardzo dużą liczbą skarpet.
O równoległości: o ile wrzucisz obie skarpetki do tego samego pojemnika, możesz z łatwością równolegle wykonać wszystkie te kroki.