Wczoraj parowałem skarpetki z czystego prania i zorientowałem się, jak to robię, nie jest bardzo wydajne. Robiłem naiwne poszukiwania - wybrałem jedną skarpetę i „iterowałem” stos, aby znaleźć jego parę. Wymaga to iteracyjnie na N / 2 * n / 4 = N ² /8 skarpet średniej.

Jako informatyk zastanawiałem się, co mogę zrobić? Sortowanie (według rozmiaru / koloru / ...) oczywiście przyszło na myśl, aby uzyskać rozwiązanie O (NlogN).

Hashowanie lub inne nie na miejscu rozwiązania nie są opcją, ponieważ nie jestem w stanie powielić moich skarpet (choć byłoby miło, gdybym mógł).

Tak więc pytanie brzmi:

Biorąc pod uwagę stos npar skarpet zawierających 2nelementy (zakładając, że każda skarpeta ma dokładnie jedną pasującą parę), jaki jest najlepszy sposób na ich skuteczne sparowanie z dodatkową przestrzenią logarytmiczną? (Myślę, że w razie potrzeby pamiętam taką ilość informacji).

Będę wdzięczny za odpowiedź dotyczącą następujących aspektów:

• Ogólne rozwiązanie teoretyczne dla ogromnej liczby skarpet.
• Rzeczywista liczba skarpet nie jest tak duża, nie sądzę, że mój małżonek i mam więcej niż 30 par. (I dość łatwo jest odróżnić moje skarpetki od jej; czy można tego również użyć?)
• Czy jest to równoważne z problemem odróżnialności elementu ?

Zaproponowano rozwiązania dotyczące sortowania , ale sortowanie to trochę za dużo : nie potrzebujemy porządku; potrzebujemy tylko grup równości .

Tak więc haszowanie byłoby wystarczające (i szybsze).

1. Dla każdego koloru skarpet ułóż stos . Iteruj po wszystkich skarpetach w koszyku wejściowym i rozmieszczaj je na stosach kolorów .
2. Iteruj po każdym stosie i rozprowadź go za pomocą innej metryki (np. Wzoru) do drugiego zestawu stosów
3. Rekurencyjnie stosuj ten schemat, dopóki nie rozdzielisz wszystkich skarpet na bardzo małe stosy, które możesz natychmiast przetworzyć wizualnie

Ten rodzaj rekurencyjnego partycjonowania skrótu jest faktycznie wykonywany przez program SQL Server, gdy musi on łączyć lub agregować skróty w przypadku dużych zestawów danych. Dystrybuuje strumień wejściowy kompilacji na wiele niezależnych partycji. Ten schemat skaluje się do dowolnych ilości danych i wielu procesorów liniowo.

Nie potrzebujesz partycjonowania rekurencyjnego, jeśli możesz znaleźć klucz dystrybucyjny (klucz skrótu), który zapewnia wystarczającą liczbę segmentów, aby każdy segment był wystarczająco mały, aby można go było bardzo szybko przetworzyć. Niestety nie sądzę, że skarpetki mają taką właściwość.

Jeśli każda skarpeta ma liczbę całkowitą o nazwie „PairID”, można ją łatwo podzielić na 10 segmentów zgodnie z PairID % 10(ostatnią cyfrą).

Najlepszym podziałem na partycje w świecie rzeczywistym, jaki mogę sobie wyobrazić, jest utworzenie prostokąta stosów : jeden wymiar to kolor, a drugi wzór. Dlaczego prostokąt? Ponieważ potrzebujemy losowego dostępu do stosów O (1). ( Prostopadłościan 3D również by działał, ale nie jest to zbyt praktyczne).

Aktualizacja:

Co z równoległością ? Czy wielu ludzi może szybciej dopasować skarpetki?

1. Najprostsza strategia paralelizacji polega na tym, że wielu pracowników bierze z koszyka wejściowego i wkłada skarpetki na stosy. To tylko tyle zwiększa - wyobraź sobie 100 osób walczących o ponad 10 stosów. Koszty synchronizacji (objawiające się jako kolizje rąk i komunikacja międzyludzka) niszczą wydajność i przyspieszenie (patrz ustawa o uniwersalnej skalowalności !). Czy to jest podatne na impasy ? Nie, ponieważ każdy pracownik musi mieć dostęp tylko do jednego stosu na raz. Z jednym „zamkiem” nie może być impasu. Blokady Livelocks mogą być możliwe w zależności od tego, jak ludzie koordynują dostęp do stosów. Mogą po prostu użyć losowego wycofaniapodobnie jak karty sieciowe robią to na poziomie fizycznym, aby ustalić, która karta może uzyskać dostęp wyłącznie do przewodu sieciowego. Jeśli działa w przypadku kart sieciowych , powinien również działać w przypadku ludzi.
2. Skaluje się prawie w nieskończoność, jeśli każdy pracownik ma swój własny zestaw stosów . Pracownicy mogą wtedy pobierać duże kawałki skarpet z koszyka wejściowego (bardzo mało rywalizacji, ponieważ robią to rzadko) i nie muszą wcale synchronizować podczas dystrybucji skarpet (ponieważ mają stosy lokalne). Na koniec wszyscy pracownicy muszą związać swoje stosy. Wierzę, że można to zrobić w O (log (liczba pracowników * stosy na pracownika)), jeśli pracownicy utworzą drzewo agregacji .

Co z problemem odróżnienia elementu ? Jak stwierdzono w artykule, problem odróżnienia elementu można rozwiązać O(N). To samo dotyczy problemu ze skarpetami (także O(N), jeśli potrzebujesz tylko jednego kroku dystrybucji (zaproponowałem kilka kroków tylko dlatego, że ludzie są kiepscy w obliczeniach - wystarczy jeden krok, jeśli się rozprowadzasz md5(color, length, pattern, ...), tj. Idealny skrót wszystkich atrybutów)).

Oczywiście nie można jechać szybciej O(N), więc osiągnęliśmy optymalną dolną granicę .

Chociaż wyniki nie są dokładnie takie same (w jednym przypadku to tylko wartość logiczna. W drugim przypadku pary skarpet), asymptotyczne złożoności są takie same.

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

Ludzie mogą pozyskać algorytmy procesora wykorzystując fakt, ż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);
}

Przynajmniej tego używam w prawdziwym życiu i uważam to za bardzo wydajne. Minusem jest to, że wymaga płaskiej powierzchni, ale zwykle jest obfite.

Przypadek 1 : Wszystkie skarpetki są identyczne (tak na marginesie to robię w prawdziwym życiu).

Wybierz dowolne dwa z nich, aby stworzyć 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 wcześniej znana (przypadek ogólny).

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

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

Odpowiedź nie algorytmiczna, ale „wydajna”, kiedy to robię:

• krok 1) odrzuć wszystkie istniejące skarpetki

• krok 2) idź do Walmart i kup je za pakiety 10 - n paczki białej i m paczki czarnej. Nie potrzebujesz innych kolorów w życiu codziennym.

Jednak od czasu do czasu muszę to robić ponownie (zgubione skarpetki, uszkodzone skarpetki itp.) I nienawidzę zbyt często odrzucać idealnie dobrych skarpet (i żałuję, że wciąż nie sprzedają tego samego oznaczenia skarpet!), Więc niedawno wziąłem inne podejście.

Algorytmiczna odpowiedź:

Zastanów się, czy nie dobierając tylko jednej skarpety na drugi stos skarpet, szanse na znalezienie pasującej skarpety w naiwnym wyszukiwaniu są dość niskie.

• Wybierz losowo pięć z nich i zapamiętaj ich kształt lub długość.

Dlaczego pięć? Zwykle ludzie są dobrzy, pamiętają od pięciu do siedmiu różnych elementów w pamięci roboczej - trochę jak ludzki odpowiednik stosu RPN - pięć to bezpieczne ustawienie domyślne.

• Wybierz jeden ze stosu 2n-5.

• Teraz poszukaj dopasowania (wizualne dopasowanie wzorca - ludzie są w tym dobrzy z małym stosem) w pięciu wylosowanych, jeśli go nie znajdziesz, dodaj go do swojej piątki.

• Zachowaj losowe wybieranie skarpet ze stosu i porównaj je ze swoimi skarpetkami 5 + 1. Wraz ze wzrostem twojego stosu, zmniejszy to twoją wydajność, ale zwiększy twoje szanse. O wiele szybciej.

Zapisz wzór, aby obliczyć, ile próbek musisz narysować, aby uzyskać 50% szansy na dopasowanie. IIRC to prawo hipergeometryczne.

Robię to każdego ranka i rzadko potrzebuję więcej niż trzy losowania - ale mam npodobne pary (około 10, dawaj lub biorę zgubione) mbiałych skarpet w kształcie. Teraz możesz oszacować rozmiar mojego stosu zapasów :-)

BTW , odkryłem, że suma kosztów transakcyjnych sortowania wszystkich skarpet za każdym razem, gdy potrzebowałem pary, była znacznie mniejsza niż zrobienie tego raz i związanie skarpet. Just-in-time działa lepiej, ponieważ wtedy nie musisz wiązać skarpet, a także maleje marginalny zwrot (to znaczy, wciąż szukasz dwóch lub trzech skarpet, które gdzieś w pralni i których potrzebujesz aby dokończyć dopasowywanie skarpet i tracisz na tym czas).

To, co robię, polega na tym, że biorę pierwszą skarpetę i kładę ją (powiedzmy na brzegu miski na pranie). Potem biorę kolejną skarpetę i sprawdzam, czy jest taka sama jak pierwsza skarpeta. Jeśli tak, usuwam je oba. Jeśli nie, odkładam go obok pierwszej skarpety. Następnie biorę trzecią skarpetę i porównuję ją do pierwszych dwóch (jeśli nadal tam są). Itp.

Takie podejście można dość łatwo zaimplementować w tablicy, zakładając, że „usunięcie” skarpet jest opcją. W rzeczywistości nie trzeba nawet „usuwać” skarpet. Jeśli nie potrzebujesz sortować skarpet (patrz poniżej), możesz je po prostu przenieść i otrzymać tablicę, w której wszystkie skarpetki są ułożone parami.

Zakładając, że jedyną operacją dla skarpet jest porównanie w celu zapewnienia równości, algorytm ten jest nadal w zasadzie algorytmem n ² , chociaż nie znam średniego przypadku (nigdy nie nauczyłem się go obliczać).

Sortowanie oczywiście poprawia wydajność, szczególnie w prawdziwym życiu, w którym można łatwo „wstawić” skarpetę między dwiema innymi skarpetami. W obliczeniach to samo można osiągnąć za pomocą drzewa, ale to dodatkowa przestrzeń. I oczywiście wróciliśmy do NlogN (lub nieco więcej, jeśli istnieje kilka skarpet, które są takie same pod względem kryteriów sortowania, ale nie z tej samej pary).

Poza tym nie mogę nic wymyślić, ale ta metoda wydaje się być całkiem skuteczna w prawdziwym życiu. :)

To zadaje złe pytanie. Właściwe pytanie brzmi: dlaczego spędzam czas na sortowaniu skarpet? Ile kosztuje rocznie, gdy cenisz swój wolny czas na X wybranych jednostek pieniężnych?

I częściej niż nie, to nie jest po prostu każdy wolny czas, to rano czas wolny, który można spędzać w łóżku, lub popijając kawę lub pozostawiając trochę za wcześnie i nie przyłapania w ruchu.

Często dobrze jest cofnąć się o krok i przemyśleć problem.

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 oraz pochłanianie zapachu. Ważne jest również to, że nie powinny tracić elastyczności podczas przechowywania, więc naturalne tkaniny są dobre i powinny być dostępne w plastikowym opakowaniu.

Lepiej, jeśli nie ma różnicy między skarpetami na lewą i prawą stopę, ale to nie jest krytyczne. Jeśli skarpetki są symetryczne od lewej do prawej, znalezienie pary to operacja O (1), a sortowanie skarpet to przybliżona operacja O (M), gdzie M to liczba miejsc w twoim domu, które zaśmieciłeś skarpetami, najlepiej niektóre mała stała liczba.

Jeśli wybierzesz fantazyjną parę z różnymi lewymi i prawymi skarpetami, wykonanie pełnego sortowania do wiader lewej i prawej stopy weź O (N + M), gdzie N jest liczbą skarpet, a M jest takie samo jak powyżej. Ktoś inny może podać wzór na średnie iteracje znalezienia pierwszej pary, ale najgorszym przypadkiem znalezienia pary z ślepym wyszukiwaniem jest N / 2 + 1, co staje się astronomicznie mało prawdopodobne dla rozsądnej N. Można to przyspieszyć, używając zaawansowanego obrazu algorytmy rozpoznawania i heurystyka podczas skanowania stosu nieposortowanych skarpet za pomocą gałki ocznej Mk1 .

Tak więc algorytm do osiągnięcia wydajności parowania skarpety O (1) (przy założeniu skarpety symetrycznej) to:

1. Musisz oszacować, ile par skarpet będziesz potrzebować przez resztę życia, a może aż do przejścia na emeryturę i przejścia do cieplejszego klimatu bez potrzeby noszenia skarpet. Jeśli jesteś młody, możesz również oszacować, ile czasu zajmie nam, zanim wszyscy będziemy mieć roboty sortujące skarpety w naszych domach, a cały problem stanie się nieistotny.

2. Musisz dowiedzieć się, w jaki sposób możesz zamówić wybraną skarpetę luzem oraz ile to kosztuje i czy dostarczają.

3. Zamów skarpetki!

4. Pozbądź się starych skarpet.

Alternatywny krok 3 wymagałby porównania kosztów zakupu tej samej ilości, być może tańszych skarpet, kilku par jednocześnie na przestrzeni lat i dodania kosztów sortowania skarpet, ale uwierz mi na słowo: kupowanie hurtowe jest tańsze! Również skarpety w magazynie rosną na wartości w tempie inflacji cen akcji, co jest więcej niż w przypadku wielu inwestycji. Z drugiej strony są też koszty przechowywania, ale skarpetki 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 codziennie oszczędzasz pieniądze i czas do końca życia.

Teoretyczny limit wynosi O (n), ponieważ musisz dotknąć każdej skarpety (chyba że niektóre są już w jakiś sposób sparowane).

Możesz osiągnąć O (n) za pomocą sortowania radix . Musisz tylko wybrać atrybuty dla segmentów.

1. Najpierw możesz wybrać (jej, moje) - podziel 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 skarpet w jednym stosie),
3. następnie długość skarpety,
4. potem tekstura ...

Jeśli możesz wybrać ograniczoną liczbę atrybutów, ale wystarczającą liczbę atrybutów, które jednoznacznie identyfikują każdą parę, powinieneś to zrobić w O (k * n), czyli O (n), jeśli uznamy, że k jest ograniczone.

Jako praktyczne rozwiązanie:

1. Szybko rób stosy łatwo rozpoznawalnych skarpet. (Powiedz według koloru)
2. Szybko posortuj każdy stos i dla porównania użyj długości skarpety. 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 jest natychmiast znaleźć pary punktowe i nieskompletowane skarpetki

Jeśli masz 1000 skarpet o 8 kolorach i średnim rozkładzie, możesz wykonać 4 stosy po 125 skarpet w czasie c * n. Z progiem 5 skarpet można sortować każdy stos w 6 seriach. (Licząc 2 sekundy, aby rzucić skarpetę na odpowiedni stos, zajmie ci to mniej niż 4 godziny).

Jeśli masz tylko 60 skarpet, 3 kolory i 2 rodzaje skarpet (twoich / twojej żony), możesz posortować każdy stos 10 skarpet w 1 cyklu (ponownie próg = 5). (Odliczanie 2 sekund zajmie Ci 2 minuty).

Początkowe sortowanie wiader przyspieszy proces, ponieważ dzieli twoje n skarpetek na k wiader w c*nczasie, więc nie będziesz musiał tylko wykonywać c*n*log(k)pracy. (Nie biorąc pod uwagę progu). Więc w sumie robisz z n*c*(1 + log(k))pracy, gdzie c to czas rzucić skarpetę na stos.

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

W informatyce może to być pomocne: mamy zbiór n rzeczy , porządek na nich (długość), a także relację równoważności (dodatkowe informacje, na przykład kolor skarpet). Relacja równoważności pozwala nam utworzyć partycję oryginalnej kolekcji, aw każdej klasie równoważności nasze zamówienie jest nadal utrzymywane. Odwzorowanie rzeczy na jej klasę równoważności można wykonać 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 uporządkować każdą klasę. Zaletą jest to, że zestawy danych są już znacznie mniejsze.

Metodę można również zagnieżdżać, jeśli mamy wiele relacji równoważności -> twórz stosy kolorów, niż w obrębie każdej partycji stosu na fakturze, niż sortuj według długości. Każda relacja równoważności, która tworzy partycję zawierającą więcej niż 2 elementy o mniej więcej równym rozmiarze, przyniesie poprawę prędkości w porównaniu z sortowaniem (pod warunkiem, że możemy bezpośrednio przypisać skarpetę do stosu), a sortowanie może nastąpić bardzo szybko na mniejszych zestawach danych.

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 w przyszłości dla 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ć, dopóki to działa.

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

Mam nadzieję że to pomoże!

To pytanie jest głęboko filozoficzne. W istocie chodzi o to, czy siła ludzi do rozwiązywania problemów („wetware” naszych mózgów) jest równoważna z tym, 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. msgstr "jeśli s łączy się ze skarpetą t w N". Jak szybko możemy „zapamiętać” to, co do tej pory widzieliśmy?
2. „usuń t z N” i „dodaj s do N”. Jak drogie jest śledzenie tego, co do tej pory widzieliśmy?

Ludzie zastosują różne strategie, aby je zrealizować. Pamięć ludzka jest skojarzona , podobnie jak tablica skrótów, w której zestawy funkcji przechowywanych wartości są sparowane z odpowiednimi wartościami. Na przykład koncepcja „czerwonego samochodu” odwzorowuje wszystkie czerwone samochody, które osoba jest w stanie zapamiętać. Ktoś z doskonałą pamięcią ma doskonałe mapowanie. Większość ludzi jest niedoskonała pod tym względem (i większość innych). Mapa asocjacyjna ma ograniczoną pojemność. Mapowania mogą wydawać sygnały dźwiękowe nieistniejące w różnych okolicznościach (o jedno piwo za dużo), należy je zapisać błędnie („Myślałem, że miała na imię Betty, nie Nettie”) lub nigdy nie zostać nadpisane, nawet jeśli zauważymy, że prawda się zmieniła („samochód ojca”) „pomarańczowy Firebird”, kiedy faktycznie wiedzieliśmy, że zamienił go na czerwone Camaro).

W przypadku skarpet idealne przypomnienie oznacza, że ​​spojrzenie na skarpetę szawsze tworzy pamięć o jej rodzeństwie t, w tym wystarczającą ilość informacji (tam, gdzie jest na desce do prasowania), aby można było ją zlokalizować tw stałym czasie. Osoba z pamięcią fotograficzną osiąga zarówno 1, jak i 2 bez przerwy.

Ktoś z mniej niż doskonałą pamięcią może użyć kilku klas równoważności zdrowego rozsądku w oparciu o funkcje w jego zdolności do śledzenia: rozmiar (tata, mama, dziecko), kolor (zielonkawy, czerwonawy itp.), Wzór (argyle, zwykły itp.) , styl (footie, podkolanówki itp.). Deska do prasowania byłaby podzielona na sekcje dla kategorii. Zwykle pozwala to na lokalizację kategorii w stałym czasie przez pamięć, ale wtedy potrzebne jest liniowe przeszukiwanie kategorii „segment”.

Ktoś bez pamięci ani wyobraźni (przepraszam) po prostu zatrzyma skarpetki w jednym stosie i przeprowadzi liniowe przeszukiwanie całego stosu.

Zgrabny dziwak może używać par numerycznych, jak ktoś sugeruje. Otwiera to drzwi do całkowitego uporządkowania, które pozwala człowiekowi używać dokładnie tych samych algorytmów, które moglibyśmy zastosować do procesora: wyszukiwanie binarne, drzewa, skróty itp.

Tak więc „najlepszy” algorytm zależy od jakości uruchomionego oprogramowania / sprzętu / oprogramowania mokrego oraz od naszej chęci „oszukiwania” przez nałożenie całkowitego par na pary. Z pewnością „najlepszym” meta- algorytmem jest zatrudnienie najlepszego na świecie sortera skarpet: osoby lub maszyny, które mogą zdobyć i szybko przechowywać ogromny zestaw N zestawów atrybutów skarpet w pamięci asocjacyjnej 1-1 z ciągłym wyszukiwaniem czasu, wstawianie, i usuń. Można zdobyć zarówno ludzi, jak i maszyny. Jeśli masz, możesz sparować wszystkie skarpetki w czasie O (N) dla N par, co jest optymalne. Tagi sumy zamówień pozwalają na użycie standardowego haszowania, aby uzyskać ten sam wynik na komputerze ludzkim lub sprzętowym.

Koszt: Przenoszenie skarpet -> wysokie, wyszukiwanie / wyszukiwanie skarpet w linii -> małe

Chcemy zmniejszyć liczbę ruchów i zrekompensować liczbę wyszukiwań. Możemy również wykorzystać wielowątkowe środowisko Homo Sapiens do przechowywania większej ilości rzeczy w pamięci podręcznej decyzji.

X = Pozdrawiam, Y = Twoi małżonkowie

Ze stosu A wszystkich skarpet:

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

Rób, 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ść w odpowiedniej gotowej linii skarpet.

3. Opcjonalne Podczas przeszukiwania linii, a bieżąca skarpeta, na którą patrzysz, jest identyczna z poprzednią, wykonaj krok 2 dla tych skarpet.

Opcjonalnie w kroku pierwszym, wybierasz dwie skarpetki z tej linii zamiast dwóch, ponieważ pamięć podręczna jest wystarczająco duża, abyśmy mogli szybko stwierdzić, czy którakolwiek skarpeta pasuje do bieżącej linii, którą obserwujesz. Jeśli masz szczęście, że masz trzy ramiona, możesz przeanalizować trzy skarpetki jednocześnie, biorąc pod uwagę, że pamięć tego obiektu jest wystarczająco duża.

Rób, dopóki X i Y nie będą puste.

Gotowy

Ponieważ jednak ma to złożoność podobną do sortowania selekcyjnego, czas potrzebny jest znacznie mniej ze względu na prędkości operacji we / wy (ruchome skarpety) i wyszukiwania (szukanie skarpety w linii).

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

Załóżmy, że wiesz, że Twoje skarpetki 2n są ułożone w następujący 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. Jest n! możliwe wyniki (dopasowania między pierwszą a drugą połową), co oznacza, że ​​potrzebujesz porównań log (n!) = Omega (n log n). Można to uzyskać przez sortowanie.

Ponieważ jesteś zainteresowany połączeniami z problemem odrębności elementu: udowodnienie, że Omega (n log n) związany z odrębnością elementu jest trudniejsze, ponieważ wynik jest binarny tak / nie. W tym przypadku wynik musi być zgodny, a liczba możliwych wyników wystarcza, aby uzyskać przyzwoite powiązanie. Istnieje jednak wariant związany z odrębnością elementów. Załóżmy, że otrzymujesz skarpetki 2n i zastanawiasz się, czy można je wyjątkowo sparować. Możesz uzyskać redukcję z ED, wysyłając ( ₁ , ₂ , ..., _n ) do ( ₁ , ₁ , ₂ , ₂ , ..., _n , _n ). (Nawiasowo dowód twardości zaburzeń erekcji jest bardzo interesujący z punktu widzenia topologii.)

Myślę, że powinna istnieć Omega (n ² ) związana z pierwotnym problemem, jeśli pozwolisz tylko na testy równości. Moja intuicja brzmi: rozważmy wykres, na którym dodajemy krawędź po teście, i argumentujemy, że jeśli wykres nie jest gęsty, wynik nie jest jednoznacznie określony.

To jak ja rzeczywiście to zrobić, na str par skarpet ( n = 2p pojedynczych skarpet):

• Chwyć skarpetę losowo ze stosu.
• W przypadku pierwszej skarpety lub jeśli wszystkie wcześniej wybrane skarpetki zostały sparowane, po prostu umieść skarpetę w pierwszym „gnieździe” „szeregu” niesparowanych skarpet przed sobą.
• Jeśli masz jedną lub więcej wybranych niesparowanych skarpet, sprawdź swoją bieżącą skarpetę względem wszystkich niesparowanych skarpet w tablicy.
  • Możliwe jest podzielenie skarpet na ogólne klasy lub typy (biały / czarny, kostka / załoga, wysportowane / ubranie) podczas budowania swojego zestawu i „drążenie w dół”, aby porównać tylko podobne.
  • Jeśli znajdziesz akceptowalne dopasowanie, złóż obie skarpetki razem i usuń je z tablicy.
  • Jeśli nie, włóż bieżącą skarpetę do pierwszego otwartego gniazda w tablicy.
• Powtórz z każdą skarpetą.

Najgorszym scenariuszem tego schematu jest to, że każda para skarpet jest na tyle inna, że ​​musi być dokładnie dopasowana, i że wszystkie pierwsze wybrane skarpetki n / 2 są różne. To jest twój scenariusz O (n ² ) i jest to bardzo mało prawdopodobne. Jeśli liczba unikalnych rodzajów skarpet t jest mniejsza niż liczba par p = n / 2 , a skarpety każdego rodzaju są wystarczająco podobne (zwykle pod względem zużycia), że każdą skarpetę tego typu można sparować z dowolną drugi, a potem jak już wywnioskować powyżej, maksymalna ilość skarpetek będzie kiedykolwiek trzeba porównać do jest t , po czym następny wyciągnąć wolidopasuj jedną z niesparowanych skarpet. Ten scenariusz jest znacznie bardziej prawdopodobny w przeciętnej szufladzie skarpety niż w najgorszym przypadku i zmniejsza złożoność najgorszego przypadku do O (n * t), gdzie zwykle t << n .

Podejście realne:

Jak najszybciej usuń skarpetki z nieposortowanego stosu pojedynczo i ułóż je w stosy przed sobą. Pale powinny być ułożone nieco oszczędnie, wszystkie skarpety powinny być skierowane w tym samym kierunku; liczba stosów jest ograniczona odległością, którą można łatwo dotrzeć. Wybór stosu, na który należy położyć skarpetę, powinien być - tak szybko, jak to możliwe - poprzez umieszczenie skarpety na stosie podobno skarpet; sporadyczny błąd typu I (wkładanie skarpety na stos, do którego nie należy) lub typ II (wkładanie skarpety do własnego stosu, gdy istnieje stos podobnych skarpet) może być tolerowany - najważniejszą kwestią jest szybkość .

Gdy wszystkie skarpetki znajdą się w stosach, szybko przechodź przez stosy wielu skarpet, tworząc pary i usuwając je (idą do szuflady). Jeśli na stosie znajdują się niepasujące skarpety, ułóż je ponownie na stosie najlepszym (w ramach możliwie najszybszego ograniczenia). Po przetworzeniu wszystkich stosów z wieloma skarpetami dopasuj pozostałe skarpetki, które nie zostały sparowane z powodu błędów typu II. Whoosh, skończyłeś - a ja mam dużo skarpet i nie piorę ich, dopóki duża część nie będzie brudna. Kolejna praktyczna uwaga: przewracam jedną skarpetkę w dół nad drugą, korzystając z ich elastycznych właściwości, dzięki czemu pozostają one razem podczas transportu do szuflady i do szuflady.

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 niesparowanych.

Odpowiedzi do tej pory nie wykorzystują dobrze naszych możliwości rozpoznawania ludzkich wzorców. Gra w Set jest wskazówką, jak to zrobić dobrze: umieść wszystkie skarpetki w dwuwymiarowej przestrzeni, abyś mógł je dobrze rozpoznać i łatwo do nich dotrzeć rękami. Ogranicza to do obszaru około 120 * 80 cm lub więcej. 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 skarpetami (przychodzą na myśl małe dzieci), możesz zrobić porządek, wybierając najpierw te skarpetki. Ten algorytm działa dobrze tylko wtedy, gdy liczba pojedynczych skarpet jest niska

Podnieś pierwszą skarpetę i połóż ją na stole. Teraz wybierz inną skarpetę; jeśli pasuje do pierwszego wybranego, umieść go na pierwszym. Jeśli nie, połóż go na stole w niewielkiej odległości od pierwszego. Wybierz trzecią skarpetę; jeśli pasuje do jednego z poprzednich dwóch, umieść go na nich lub umieść w niewielkiej odległości od trzeciego. Powtarzaj, dopóki nie odbierzesz wszystkich skarpet.

Aby powiedzieć, jak efektywne jest parowanie skarpet ze stosu, musimy najpierw zdefiniować maszynę, ponieważ parowanie nie jest wykonywane ani przez maszynę Turinga, ani przez maszynę o swobodnym dostępie, które zwykle są używane jako podstawa analiza algorytmiczna.

Maszyna

Maszyna jest abstrakcją elementu świata rzeczywistego zwanego istotą ludzką. Jest w stanie czytać z otoczenia przez parę oczu. Nasz model maszyny jest w stanie manipulować otoczeniem za pomocą 2 ramion. Operacje logiczne i arytmetyczne są obliczane za pomocą naszego mózgu (mam nadzieję ;-)).

Musimy również wziąć pod uwagę wewnętrzny czas wykonywania operacji atomowych, które można przeprowadzić za pomocą tych instrumentów. Ze względu na ograniczenia fizyczne operacje wykonywane przez rękę lub oko mają nie stałą złożoność czasową. Wynika to z faktu, że nie możemy poruszyć nieskończenie dużym stosem skarpet za pomocą ramienia, ani też oko nie może zobaczyć górnej skarpety na nieskończenie dużym stosie skarpet.

Jednak fizyka mechaniczna daje nam również pewne zalety. Nie ograniczamy się do przenoszenia maksymalnie jednej skarpety z ramieniem. Możemy przenieść kilka z nich jednocześnie.

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

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

Możemy również skorzystać z faktu, że ludzie mają bardzo ograniczoną liczbę skarpet. Tak więc modyfikacja środowiskowa może obejmować wszystkie skarpetki w stosie.

Algorytm

Oto moja propozycja:

1. Rozłóż wszystkie skarpetki w stosie na podłodze.
2. Znajdź parę, patrząc na skarpetki na podłodze.
3. Powtarzaj od 2, dopóki nie można utworzyć pary.
4. Powtarzaj od 1, aż na podłodze nie będzie skarpet.

Operacja 4 jest konieczna, ponieważ podczas rozkładania skarpet na podłodze niektóre skarpetki mogą ukrywać inne. Oto analiza algorytmu:

Analiza

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

W poniższej analizie wykonawczej par npar skarpet przypuszczamy, że co najmniej połowa 2nskarpet nie jest ukryta po kroku 1. Tak więc w przeciętnym przypadku możemy znaleźć n/2pary. Oznacza to, że pętla w kroku 4 jest wykonywana 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 zrywanie 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 służące do porównania skarpety z inną w kroku 2

Mamy więc całkowitą złożoność środowiska wykonawczego, O(r*n^2 + w*(ln n + n))gdzie ri wsą czynniki odpowiednio dla odczytu środowiskowego i zapisu środowiskowego dla rozsądnej ilości skarpet. Koszt operacji logicznych i arytmetycznych jest pomijany, ponieważ przypuszczamy, że podjęcie stałej liczby operacji logicznych i arytmetycznych wymaga ustalenia stałej liczby skarpet należących do tej samej pary. Może to nie być wykonalne 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);
  }
}

Wymyśliłem inne rozwiązanie, które nie obiecywałoby mniejszej liczby operacji, ani mniejszego zużycia czasu, ale należy spróbować sprawdzić, czy może to być wystarczająco dobra heurystyka, aby zapewnić mniejsze zużycie czasu w ogromnej serii parowania skarpet.

Warunki wstępne: Nie ma gwarancji, że są takie same skarpetki. 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 ile). Przygotuj się na zapamiętanie zmiennej „indeks” i ustaw ją na 0.

Wynik będzie miał jeden lub dwa stosy: 1. „dopasowane” i 2. „brakujące”

Heurystyczny:

1. Znajdź najbardziej charakterystyczną skarpetę.
2. Znajdź swoje dopasowanie.
3. Jeśli nie ma dopasowania, połóż go na stosie „brakującym”.
4. Powtarzaj od 1., aż nie będzie już najbardziej charakterystycznych skarpet.
5. Jeśli jest mniej niż 6 skarpet, przejdź do 11.
6. Połącz na oślep wszystkie skarpetki z sąsiadem (nie pakuj go)
7. Znajdź wszystkie dopasowane pary, spakuj je i przenieś spakowane pary do stosu „dopasowanego”; Jeśli nie było nowych dopasowań - zwiększ „indeks” o 1
8. Jeśli „indeks” jest większy niż 2 (może to być wartość zależna od numeru skarpety, ponieważ przy większej liczbie skarpet istnieje mniejsza szansa na ich ślepe sparowanie), przejdź do 11
9. Przetasuj resztę
10. Idź do 1
11. Zapomnij o „indeksie”
12. Wybierz skarpetę
13. Znajdź jego parę
14. Jeśli nie ma pary skarpet, przenieś ją na stos „brakujących”
15. Jeśli znaleziono pasującą parę, spakuj ją i przenieś na stos „dopasowany”
16. Jeśli nadal jest ich więcej niż jedna, przejdź do 12
17. Jeśli pozostała tylko jedna, przejdź do 14
18. Uśmiech zadowolony :)

Można również dodać kontrolę uszkodzonych skarpet, tak jakby je usunąć. Można go wstawić między 2 a 3 oraz między 13 a 14.

Nie mogę się doczekać, aby usłyszeć o wszelkich doświadczeniach lub poprawkach.

Kiedy sortuję skarpetki, dokonuję przybliżonego sortowania radix , upuszczając skarpetki w pobliżu innych skarpet tego samego koloru / wzoru. Z wyjątkiem przypadku, gdy mogę zobaczyć dokładne dopasowanie w / w pobliżu miejsca, w którym zamierzam upuścić skarpetę, wydobywam parę w tym punkcie.

Prawie wszystkie inne algorytmy (w tym odpowiedź na najwyższe oceny przez usr ) sortują, a następnie usuwają pary. Uważam, że jako człowiek lepiej jest zminimalizować liczbę skarpet branych pod uwagę jednocześnie.

Robię to przez:

1. Wybór charakterystycznej skarpety (cokolwiek, co najpierw przyciągnie mój wzrok na stosie).
2. Rozpoczęcie sortowania podstawki od tego koncepcyjnego miejsca poprzez wyciągnięcie skarpet ze stosu w oparciu o podobieństwo do tego.
3. Umieść nową skarpetę w pobliżu aktualnego stosu, w odległości zależnej od jej różnicy. Jeśli znajdziesz skarpetę na innej, ponieważ jest identyczna, ułóż tam parę i usuń je. Oznacza to, że przyszłe porównania wymagają mniej wysiłku, aby znaleźć właściwe miejsce.

Wykorzystuje to ludzką zdolność dopasowywania rozmytego w czasie O (1), co jest nieco równoważne z ustanowieniem mapy skrótu na urządzeniu obliczeniowym.

Najpierw pociągając za charakterystyczne skarpety, pozostawiasz miejsce na „powiększenie” funkcji mniej charakterystycznych na początek.

Po wyeliminowaniu koloru fluro, skarpet z paskami i trzech par długich skarpet, możesz otrzymać w większości białe skarpetki z grubsza posortowane według ich zużycia.

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

Za każdym razem, gdy podnosisz skarpetę, umieść ją w jednym miejscu. Następnie podnieś następną skarpetę, jeśli nie pasuje do pierwszej skarpety, ustaw ją obok pierwszej. Jeśli tak, istnieje para. W ten sposób tak naprawdę nie ma znaczenia, ile jest kombinacji, i są tylko dwie możliwości dla każdej skarpety, którą wybierzesz - albo ma dopasowanie, które jest już w twojej gamie skarpet, albo nie, co oznacza, że dodaj go do miejsca w tablicy.

Oznacza to również, że prawie na pewno nigdy nie będziesz mieć wszystkich swoich skarpet w tablicy, ponieważ skarpetki zostaną usunięte, gdy zostaną dopasowane.

Rozważ tablicę skrótów o rozmiarze „N”.

Jeśli założymy rozkład normalny, wówczas szacunkowa liczba „wstawek” mających co najmniej jedną skarpetę zamapowaną na jednym segmencie to NlogN (tzn. Wszystkie segmenty są pełne)

Wyprowadziłem to jako część innej układanki, ale byłbym szczęśliwy, gdyby udowodniono, że się mylę. Oto mój blog na ten sam temat

Niech „N” odpowiada przybliżonej górnej granicy liczby unikalnych kolorów / wzorów skarpet, które masz.

Po kolizji (aka: dopasowanie) po prostu usuń tę parę skarpet. Powtórz ten sam eksperyment z kolejną partią skarpet NlogN. Piękno tego polega na tym, że możesz wykonywać równoległe porównania NlogN (rozwiązywanie kolizji) z powodu sposobu, w jaki działa ludzki umysł. :-)

Skarpetki, zarówno prawdziwe, jak i analogiczne struktury danych, byłyby dostarczane w parach.

Najprostsza odpowiedź polega na tym, aby umożliwić rozdzielenie pary, powinna zostać zainicjowana pojedyncza struktura danych dla pary, która zawiera wskaźnik do lewej i prawej skarpety, umożliwiając w ten sposób bezpośrednie lub za pośrednictwem pary odwoływanie się do skarpet. Skarpetę można również rozszerzyć, aby zawierała wskaźnik do swojego partnera.

Rozwiązuje to każdy problem parowania obliczeniowego poprzez usunięcie go warstwą abstrakcji.

Stosując ten sam pomysł do praktycznego problemu parowania skarpetek, oczywistą odpowiedzią jest: nie pozwól, aby skarpetki były niesparowane. Skarpetki są dostarczane w parze, wkładane do szuflady jako para (być może poprzez ich połączenie), noszone jako para. Ale punkt, w którym możliwe jest sparowanie, znajduje się w pralce, więc wszystko, czego potrzeba, to fizyczny mechanizm, który pozwala skarpetom pozostać razem i wydajnie wyprać.

Istnieją dwie fizyczne możliwości:

W przypadku „pary” przedmiotu, który utrzymuje wskaźnik do każdej skarpety, moglibyśmy mieć woreczek z tkaniny, którego używamy do trzymania skarpet razem. Wydaje się, że to ogromny koszt.

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

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

Następnie po prostu zdejmij skarpetki zaraz po ich zdjęciu i włożeniu do kosza do prania, i ponownie wyeliminowałeś problem konieczności parowania skarpet z fizyczną abstrakcją koncepcji „parowania”.

Jeśli operacja „przenieś” jest dość droga, a operacja „porównaj” jest tania, a mimo to musisz przenieść cały zestaw do bufora, w którym wyszukiwanie jest znacznie szybsze niż w oryginalnej pamięci ... po prostu zintegruj sortowanie z obowiązkowym ruszaj się.

Odkryłem, że zintegrowanie procesu sortowania z wieszaniem do wyschnięcia sprawia, że ​​jest to bardzo proste. I tak muszę podnieść każdą skarpetę i zawiesić ją (przenieść), a mnie nic nie kosztuje powieszenie jej w określonym miejscu na sznurkach. Teraz, aby nie wymuszać wyszukiwania całego bufora (ciągów), wybieram umieszczanie skarpet według koloru / odcienia. Ciemniejszy lewy, jaśniejszy prawy, bardziej kolorowy przód itp. Teraz zanim powiesę każdą skarpetę, patrzę w jej „prawym sąsiedztwie”, jeśli pasująca już tam jest - ogranicza to „skanowanie” do 2-3 innych skarpet - i jeśli tak jest , Zawieszam drugi tuż obok niego. Następnie zwijam je w pary, usuwając ze sznurków, gdy są suche.

Teraz może to nie wydawać się tak różne od „tworzenia stosów według koloru” sugerowanych przez najlepsze odpowiedzi, ale po pierwsze, nie wybierając oddzielnych stosów, ale zakresy, nie mam problemu z klasyfikacją, czy „fioletowy” przechodzi na stos „czerwony” czy „niebieski”; po prostu idzie pomiędzy. A następnie poprzez zintegrowanie dwóch operacji (odłożenie do wyschnięcia i posortowanie), narzut sortowania podczas zawieszenia wynosi około 10% tego, czym byłoby oddzielne sortowanie.

Właśnie skończyłem parowanie skarpet i stwierdziłem, że najlepszym sposobem na to jest:

• Wybierz jedną ze skarpet i odłóż ją (utwórz „wiadro” dla tej pary)
• Jeśli następny jest parą poprzedniego, umieść go w istniejącym wiadrze, w przeciwnym razie utwórz nowy.

W najgorszym przypadku oznacza to, że będziesz miał n / 2 różnych wiader i będziesz miał n-2 ustalenia, które wiadro zawiera parę bieżących skarpet. Oczywiście ten algorytm działa dobrze, jeśli masz tylko kilka par; Zrobiłem to z 12 parami.

Nie jest tak naukowy, ale działa dobrze :)

Moje rozwiązanie nie odpowiada dokładnie twoim wymaganiom, jak wymaga tego formalnie O(n) „dodatkowej” przestrzeni. Jednak biorąc pod uwagę moje warunki, jest bardzo wydajny w moim praktycznym zastosowaniu. Dlatego myślę, że powinno to być interesujące.

Połącz z innym zadaniem

Szczególnym warunkiem w moim przypadku jest to, że nie używam suszarki, po prostu powiesić swoje szmatki na zwykłej suszarce. Wieszanie tkanin wymaga O(n)operacji (przy okazji, zawsze rozważam pakowanie pojemników) tutaj problem ), a problem z natury wymaga liniowej „dodatkowej” przestrzeni. Kiedy wyjmuję nową skarpetę z wiadra, próbuję powiesić ją obok pary, jeśli para jest już zawieszona. Jeśli to skarpetka z nowej pary, zostawiam trochę miejsca obok niej.

Oracle Machine is Better ;-)

To oczywiście wymaga dodatkowej pracy, aby sprawdzić, czy gdzieś wisi już pasująca skarpeta, i to dałoby rozwiązanie O(n^2) ze współczynnikiem 1/2dla komputera. Ale w tym przypadku „czynnik ludzki” jest faktycznie zaletą - zazwyczaj bardzo szybko (prawie O(1)) mogę zidentyfikować pasującą skarpetę, jeśli już była zawieszona (prawdopodobnie wiąże się to z niedostrzegalnym buforowaniem w mózgu) - uważam to za rodzaj ograniczona „wyrocznia” jak w Oracle Machine ;-) My, ludzie, w niektórych przypadkach mamy te zalety w stosunku do maszyn cyfrowych ;-)

Zrób to prawie O(n)!

W ten sposób łącząc problem parowania skarpet z problemem wieszania ubrań, dostaję O(n)„dodatkową przestrzeń” za darmo i mam rozwiązanie, które jest O(n)na czas, wymaga tylko trochę więcej pracy niż zwykłe wieszanie ubrań i pozwala na natychmiastowy dostęp do pełnej pary skarpetki nawet w bardzo zły poniedziałkowy poranek ... ;-)

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ć

1. ludzie rzucają obu skarpetami mniej więcej w tym samym obszarze kosza,
2. bin nie jest losowy w żadnym momencie i dlatego
3. 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.

Podjąłem proste kroki, aby zmniejszyć wysiłek w proces zajmujący czas O (1).

Ograniczając wkład do jednego z dwóch rodzajów skarpet (białe skarpetki do rekreacji, czarne skarpetki do pracy), muszę jedynie określić, którą z dwóch skarpet mam w ręku. (Technicznie, ponieważ nigdy nie są myte razem, zredukowałem proces do czasu O (0)).

Konieczne są pewne wysiłki z góry, aby znaleźć pożądane skarpetki i kupić w wystarczającej ilości, aby wyeliminować potrzebę istniejących skarpet. Ponieważ robiłem to przed potrzebą czarnych skarpet, mój wysiłek był minimalny, ale przebieg może się różnić.

Taki wysiłek był wielokrotnie obserwowany w bardzo popularnym i skutecznym kodzie. Przykłady obejmują # DEFINE'ing pi do kilku miejsc po przecinku (istnieją inne przykłady, ale to ten, który teraz przychodzi na myśl).

Utwórz tabelę skrótów, która będzie używana dla niedopasowanych skarpet, używając wzoru jako skrótu. Iteruj po skarpetach jeden po drugim. Jeśli skarpeta ma wzór pasujący do tabeli mieszającej, wyjmij skarpetę ze stołu i ułóż parę. Jeśli skarpeta nie pasuje, połóż ją na stole.

Problem z sortowaniem n par skarpet to O (n) . Zanim wrzucisz je do kosza na pranie , przewlecz lewy do prawego. Po ich wyjęciu przecinasz nić i wkładasz każdą parę do szuflady - 2 operacje na n parach, więc O (n).

Teraz kolejnym pytaniem jest po prostu, czy robisz własne pranie, a twoja żona robi to samo. Jest to problem prawdopodobnie w zupełnie innej dziedzinie problemów . :)