Jak efektywnie sparować skarpetki ze stosu?

3911

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 2 /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 ?
amit
źródło
448
Używam zasady gołębia, aby sparować dokładnie jeden ze stosu prania. Mam 3 różne kolory skarpet (czerwony, niebieski i zielony) i 2 pary każdego koloru. Za każdym razem wybieram 4 skarpetki i zawsze tworzę parę i zabieram się do pracy.
Srinivas,
59
Jeszcze jedna zasada gołębia: jeśli weźmiesz podzbiór skarpet n / 2 +1, w tym podzbiorze musi być co najmniej jedna para.
wildplasser,
40
Świetne pytanie! Być może zainteresuje cię mój artykuł na pokrewny problem, którym jest dyskusja na temat prawdopodobieństwa wyciągnięcia dwóch pasujących skarpet ze stosu: blogs.msdn.com/b/ericlippert/archive/2010/03/22/...
Eric Lippert,
335
Dlaczego nie odrodzić dziecka, waitpidaby jako rodzic sam nie sortowałeś skarpet?
Mxyk,
137
Rozwiązałem ten problem, mając tylko białe skarpetki do kolan. Wszystkie pasują do siebie. Mógłbym po prostu losowo pobrać dowolne dwie skarpetki ze stosu i pasowałyby do siebie. Dodatkowo upraszczam problem, NIE parując skarpet. Mam szufladę skarpet, do której po prostu wrzucam wszystkie skarpetki niesparowane. Każdego ranka biorę dwie losowo z szuflady. Upraszczam to do O (0). Nie może być prostsze. :)
Lee

Odpowiedzi:

2448

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.

usr
źródło
72
Właśnie to robię! Uzależniam stosy od stylu otwierania skarpety (mam tylko biały), co daje mi wystarczająco dużo „wiader”, aby szybko dopasować każdą z nich.
Scott Chamberlain
29
Próbowałem tego z moimi skarpetkami (mam z łatwością ponad 30 par) i stary, jest SZYBKO. Jednym z problemów, które znalazłem, jest to, że nie mogę mieć wystarczająco dobrego algorytmu skrótu (mam dużo białych skarpet bez żadnego wzoru), więc staje się trudny. W takim przypadku jaki byłby to optymalny sposób?
NothingsImpossible
56
@NotingsImpossible Tak wyglądają ataki typu hash na kolizję dla słabego serwera WWW! Czy białe skarpetki wyróżniają się jakimś atrybutem? Musi być coś, na czym możesz je rozpowszechniać. W przeciwnym razie możesz po prostu dowolnie tworzyć pary.
usr
37
To jest sortowanie Radix, które zgadzam się, że jest właściwą odpowiedzią. @MarkPeters Nie sądzę, że potrzebujesz tabeli odnośników. Pojedyncze przejście liniowe nad skarpetami może przekształcić skarpetki w wektory liczbowe, dzięki czemu mapowanie „segmentu skarpety” do wiadra jest banalne. Skarpety można przywiązać do wektorów za pomocą sznurka, aby nie trzeba było kolejnego przejścia liniowego na końcu.
Pointy,
49
Facet, z którym chodziłem na studia, faktycznie miał PairIDs. Został przyszyty do każdej pary skarpet z nitką: 1, 2, 3, 4 ...
Ryan Lundy
579

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.

dpc.ucore.info
źródło
228
wraz ze wzrostem liczby skarpet ludzki SIMD nie staje się lepszy niż procesor.
Lie Ryan,
25
Najlepsza odpowiedź, IMO. Chociaż redukowanie codziennego problemu do algorytmu komputerowego jest zabawne i sprytne (i odpowiednie dla SO), o wiele bardziej sensowne jest użycie mocy rozdzielczej oka / mózgu człowieka dla zestawu tak małego jak ~ 60 skarpet.
drug_user841417,
13
@LieRyan Jeśli skarpetki są równomiernie rozmieszczone, w końcu dostrzeżesz parę w odpowiednio małym zestawie skarpet ze względu na paradoks urodzinowy (chyba że rozróżnisz kolory z dowolną precyzją, w co wątpię), więc wąskim gardłem tutaj nie będzie algorytm dopasowywania kolorów ludzkich, ale krok rozprzestrzeniania.
Thomas
13
@ dpc.ucore.info Nie, ponieważ mają różne tkane wzory mankietów, długości mankietów, długości całkowite i odcienie czerni (moja żona prawdopodobnie zraniłaby mnie fizycznie za ten ostatni).
Christian
199
Lepiej mieć nadzieję, że masz parzystą liczbę skarpet, w przeciwnym razie będziesz składać skarpetki przez długi czas ...
Patrick James McDougle
258

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.

Terry Li
źródło
8
> Może to zająć nawet więcej czasu niż wyszukiwanie sekwencyjne, co teoretycznie wymaga czasu kwadratowego. Tak, dlatego nie lubię tego robić, może powinienem wyrzucić wszystkie skarpetki i zacząć od przypadku 1.
Nils
57
wadą wszystkich identycznych skarpet jest to, że mają tendencję do starzenia się w różnym tempie. Więc nadal próbujesz dopasować je na podstawie ich zużycia. (co jest trudniejsze niż zwykłe dopasowanie według wzorca)
SDC
118
Problem z posiadaniem 60 par identycznych skarpet „ponieważ ułatwia parowanie” polega na tym, że daje się wrażenie, że pracujesz z komputerem.
Steve Ives
13
Przypadek 1 nie jest stałym czasem, gdy występuje operacja, taka jak składanie par razem. W tym przypadku jest to czas liniowy z najmniejszym stałym współczynnikiem (czego dowodem jest ćwiczenie dla czytelnika). One nie mogą ewentualnie mieć taką samą czas składany jedną parę i wiadro pełne skarpetek. Jednak skaluje się liniowo. Zgodnie z prawem Amdahla ma nieograniczone przyspieszenie, ignorując koszty ogólne. Zgodnie z prawem Gustafsona możesz spasować tyle par, ile potrzeba, aby spasować jedną parę, biorąc pod uwagę wystarczającą liczbę pracowników (których ilość pozostaje na ćwiczeniu dla czytelnika), ignorując koszty ogólne.
acelent
7
@PauloMadeira Sortowanie odbywa się w sposób ciągły - wystarczy wziąć stos i włożyć go do szuflady. Jedyną operacją w tym przypadku jest postawienie skarpet na stopach, co również jest stałe. Wydajność uzyskuje się dzięki odroczonemu wykonaniu noszenia skarpety, być może przy pewnym poświęceniu w przestrzeni (zajęta przestrzeń nieskładanych skarpet jest większa niż złożona). Twierdzę, że warto; Zwykle przegrywam ten spór z żoną.
Travis,
157

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

Guylhem
źródło
25
Głosuj za odpowiedzią „nie algorytmiczną”. To jest dokładnie to, co robię i działa cudownie. Problem wymiany nie stanowi problemu, jeśli „obrócisz” skarpetę wkładając umyte skarpetki z tyłu i wyciągając rano z przodu szuflady. Wszystkie skarpetki noszą się równomiernie. Kiedy zaczynam zauważać pewne zużycie jednego, umieszczam na liście zakupów, aby całkowicie zastąpić całą klasę skarpet. W przypadku starych skarpet daję najlepsze 20% wartości firmy (związanej w woreczku spożywczym, aby się nie pomieszały), a resztę wyrzucam. Nie marnujesz skarpet, w tym momencie 80% i tak ma tylko 6 miesięcy.
FastAl
2
BTW (1) Wiązanie skarpet powoduje, że jedna elastyczna jest rozciągnięta i szybciej ulegnie awarii. Ograniczenie rodzajów unikalnych skarpet sprawia, że ​​wiązanie jest niepotrzebne. (2) Wadą ograniczenia unikatowych skarpet jest to, że dla osób mających pewne obawy związane z modą metoda ta może być nieodpowiednia.
FastAl
3
Przybyłem tutaj, aby opublikować odpowiedź „nie algorytmiczną”. Podobnie jak w prawdziwej informatyce, większość ludzi nigdy nie zwraca wystarczającej uwagi na dane i ich strukturę.
bkconrad
Używam tego algorytmicznego podejścia każdego ranka i działa jak urok! Dodatkowo nakładam zużyte skarpetki na inny stos, aby później go wyrzucić (niestety udaje im się ponownie dotrzeć do oryginalnego stosu, zanim znajdę czas, aby go wyrzucić).
Donatas Olsevičius
3
«N pakiet białych i m pakietów czarnych. Nie potrzebujesz innych kolorów w życiu codziennym »Dobrą standardową zasadą łatwego wyboru skarpetek jest to, że powinny one pasować albo do koloru twoich spodni, albo koloru paska. Z tego powodu najczęściej używanymi kolorami będą prawdopodobnie czarny, niebieski, szary i nieco brązowy. Trudno uwierzyć, że potrzeba wielu białych skarpet.
Andrea Lazzarotto,
106

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 2 , 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. :)

Vilx-
źródło
7
To też robię (zauważ, że jeśli po prostu zostawisz spacje, wstawki są również O (1)), ale źle skaluje się z teoretycznie dużą liczbą skarpet.
Mooing Duck,
15
słabo skaluje się z teoretycznie dużą liczbą rodzajów skarpet
Steven Lu 20'13
@StevenLu - jak powiedziałem - jest to n * n lub nLogn, w zależności od tego, czy je posortujesz, czy nie. Skaluje się więc tak słabo, jak każdy algorytm sortowania. Jeśli chcesz szybciej, ponumeruj je i użyj sortowania radix.
Vilx-
Jest to zasadniczo przechowywanie skarpet znalezionych, ale niepasujących w wyszukiwaniu opartym na haszowaniu. W przypadku idealnego skrótu jest to O (n), ale jeśli masz wystarczającą ilość przechowywanych skarpet, że skrót zaczyna się degenerować, staje się odpowiednio bardziej złożony.
Jon Hanna,
3
jaką wartość wkładanie skarpety między dwiema innymi skarpetami zapewnia celowi parowania skarpet? nie ma liczności skarpet. : -x
JoeBrockhaus
60

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.

hyde
źródło
Dożywotnia (przy założeniu 75 lat) dostawa skarpet (zakładając, że wyczerpujesz 4 pary miesięcznie, co daje 3600 par) zajęłaby (zakładając, że nowa para skarpet zajmuje 20 cali sześciennych) łącznie 1 1/2 jarda sześciennego. To ogromna ilość miejsca. Zakładając, że dostarczą ci go w pudełku, które jest w przybliżeniu sześcianem, skrzynia będzie miała około 3 stóp 4 cali z boku.
AJMansfield,
2
@AJMansfield ważne obawy. Nie zgadzam się jednak z kilkoma twoimi liczbami. Zajmie mi to tylko 40 lat (25 ... 65) (czas między nie zamieszkaniem u rodziców / akademika / etc a przejściem na emeryturę, patrz wyżej). Myślę też, że jedna para zajmuje więcej niż 0,5 x 4 x 6 cali w oryginalnym opakowaniu. Te liczby znacznie obniżają twoją przestrzeń kosmiczną!
hyde
Krok 4 jest niepotrzebnie marnotrawiony, -1.
Dan Bechard
2
Przewodnik dla innych, którzy mogą być zdezorientowani pomiarami AJMansfield, tłumaczenie na metrykę: »wziąłby (zakładając, że nowa para skarpet zajmuje 327 cm³) łącznie 1,14 m³. To ogromna ilość miejsca. Zakładając, że dostarczą ci je w pudełku, które jest w przybliżeniu sześcianem, skrzynia ta będzie miała około 1,04 m na boku. «
Joey
Jak pytanie oparte na ciekawości może być „niewłaściwym pytaniem”? Classic StackOverflow ...
Timmmm
52

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.

andredor
źródło
3
Skarpetki często występują w 4-pakach i większych, ponieważ jest to tańsze, ale także czyni je nierozróżnialnymi. Aby temu przeciwdziałać, moja żona przyszywa drobny ślad do każdej nowej pary skarpet, które kupuję. Znak ma inny kolor dla każdej pary lub inny kształt, jeśli zabraknie kolorów. Dzięki takiemu podejściu nie potrzebujesz nawet ograniczonego zestawu atrybutów. Po prostu uszyj unikalny numer na każdej parze. :) Aby uzyskać dodatkowe punkty, użyj pliku binarnego.
Vilx-
29
@ Vilx- DLACZEGO?!? Czy nie chodzi o to, że są nierozróżnialne?
flup
2
@flup - Myślę, że cała sprawa polega na sprzedaży w większych pakietach. :) Jeśli chodzi o mnie, to pomaga je nosić w parach. W przeciwnym razie mogę skończyć z trzema bardzo znoszonymi skarpetami i jedną nowiutką. Trochę głupie.
Vilx-
13
Nie zgadzam się z obliczeniem O (n). Co to jest $ k $? $ k $ to liczba atrybutów. Argumentowałbym, że $ k $ to $ O (log n) $, ponieważ musi wystarczyć do jednoznacznej identyfikacji każdej pary. Jeśli masz 2 pary (czarno-biały), wystarczy kolor ($ k = 1, n = 2 $). Jeśli masz jedną parę czarnych, krótkich; jedna para czerni, długa; jedna para białych, krótkich; i jedna para białych, długich - wtedy $ k = 2, n = 4 $. Następnie, jeśli ograniczymy $ k $, jednocześnie ograniczymy $ n $. Jeśli zamierzamy ograniczyć $ n $, wówczas obliczanie zamówień nie ma już sensu.
emory
3
@ Emory, myślę, że szukasz znaku wstecznego, a nie $postaci, aby twoje rzeczy wyglądały jak kod.
Xymostech
33

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.

Samuel
źródło
3
Optymalizacja człowieka: argumentowałbym, że jako człowiek, w kroku 2 powinieneś spłaszczać skarpety w przybliżeniu rosnącej kolejności, a następnie powtarzać z drobniejszą i drobniejszą ziarnistością aż do posortowania, trochę jak sortowanie w skorupkach. Byłoby to znacznie szybsze dla człowieka (ocena wizualna) niż podejście oparte na zamianie.
AndrewC,
28

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!

Nikołaj Dyankow
źródło
5
Wiązanie skarpet (lub dowolnych ubrań) w węzeł zmniejsza zdolność pralki do prania ubrań i sprawia, że ​​odwiązanie ich w celu noszenia jest znacznie trudniejsze. Rozwiązanie 2 utrudnia utrzymanie, im dłuższy jest stan rzeczy; po 6 miesiącach, kiedy potrzebujesz dwóch czarnych skarpet do kostek do noszenia z szortami i trampkami, 6 miesięcy robienia wszelkich prac sprawi, że znalezienie tej pary w tym samym stanie (brudne / czyste, podobne zużycie) będzie znacznie mniej prawdopodobne. Rozwiązanie 3 jest mniej „asynchroniczne”, a bardziej „leniwe”; wykonuj minimalną pracę, której potrzebujesz dokładnie wtedy, kiedy jest to konieczne.
KeithS
Re: rozwiązanie 2: Ludzie dowiedzą się, że nie mam na sobie pasujących skarpet, ponieważ zobaczą je w moich Birks :)
Bob Probst
@BobProbst Tak, ale twoi koledzy programiści będą również nosić niedopasowane skarpetki z Birks i dlatego z przyjemnością zauważą, że nie są jedynymi.
Francesco Pasa
27

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.

Gen
źródło
Ok, to lepiej, chociaż nadal jest to całkiem złe ... to pytanie nie dotyczy tego. Bez względu na to, czy teza Turinga jest poprawna, zarówno ludzie, jak i nasze komputery mogą sortować skarpetki. (Rzeczywistość jest taka, że ​​ludzie, będąc istotami bardzo skończonymi, mają znacznie mniej mocy obliczeniowej niż Maszyny Turinga ... i to samo dotyczy naszych komputerów, ale ograniczenia są różne.)
Jim Balter
Nie zgadzam się. Oczywiście, każdy z naszych obecnych komputerów jest zasadniczo i ogromnym DFA (różnicami we / wy modulo), a nie TM. Jednak każde urządzenie analogowe, takie jak nasze ciała, może emulować nieskończoną taśmę. Nie mamy jeszcze użytecznej charakterystyki sposobu obliczania naszych umysłów.
Gen
Nie ma nieskończonej taśmy dla ludzi lub innych urządzeń fizycznych, ponieważ nic w ludzkim mózgu nie ma nieskończonej rozdzielczości, podobnie jak i nie może. Pomogłoby to również w nauce neurologii. W każdym razie nie było tu głębokiego filozoficznego pytania, niezależnie od tego, czy chcesz je zadać. Ale wierzcie w to, co chcecie ... To nie jest miejsce na tego rodzaju debatę, a ja miałem to już za wiele razy. Ale zawsze bawią mnie ludzie, którzy ledwo potrafią rozwiązać najprostsze problemy (wszyscy jesteśmy), wyobrażając sobie, że są one odpowiednikami TM.
Jim Balter,
22

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

1 ----- 1
źródło
22

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 1 p 2 p 3 ... 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 ( 1 , 2 , ..., n ) do ( 1 , 1 , 2 , 2 , ..., n , n ). (Nawiasowo dowód twardości zaburzeń erekcji jest bardzo interesujący z punktu widzenia topologii.)

Myślę, że powinna istnieć Omega (n 2 ) 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.

sdcvvc
źródło
19

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 2 ) 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 .

KeithS
źródło
1
Prawdopodobnie jest to bardzo zbliżone do mojego procesu mentalnego. Mam dodatkową warstwę optymalizacji wstępnego sortowania. Moje sportowe skarpetki są prane białkami, a moje skarpetki do sukienki - prane kolorami. Oznacza to, że dopóki nie zrzucę razem dwóch ładunków prania, moje skarpetki są już pogrupowane według rodzaju. Białe obciążenie przebiega naprawdę szybko (wiele identycznych skarpet), ale skarpetki na sukienki wymagają więcej czasu. Inne końcówki klucz - Make więcej dostępnej pamięci do sortowania (rozkładana i usunąć wszystkie nie-skarpetki pierwszy, a następnie uruchomić algorytm parowania)
ORH
17

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.

Peter Mortensen
źródło
15

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

Stephan Eggermont
źródło
Tak zazwyczaj to robię. Działa znacznie lepiej niż powtarzanie wszystkich pozostałych skarpet za każdym razem.
yu_ominae
Ładne podejście i myślę, że można je również zastosować do niektórych prawdziwych problemów z CS. Czy możesz podać przykład takiego problemu (problem CS, w którym możemy zastosować podobne podejście do rozwiązania problemów)? Jak skaluje się to rozwiązanie dla milionów skarpet?
dniu
Myślę, że jest to w zasadzie taka sama jak inna odpowiedź tutaj, stackoverflow.com/a/14423956 , od 20 stycznia. Obie +1. System widzenia człowieka jest masywnie równoległy.
Czy Ness
15

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.

justinfay
źródło
1
To jedyna poprawna odpowiedź. Wszyscy inni nie zwracają uwagi na fakt, że najwięcej czasu spędza się na rozróżnianiu podobnych skarpet (więc zebranie ich wszystkich pod względem wyglądu fizycznego jeszcze gorzej).
entonio
Dla zabawy napisałem tę metodę układania skarpet w mały program python gist.github.com/justinfay/53b574cf0a492f6795ef
Justin Fay
12

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.

SpaceTrucker
źródło
1
to jest to samo co stackoverflow.com/a/14423956 i stackoverflow.com/a/14468913 Myślę, że.
Czy Ness
@WillNess Tak, z nieco więcej wyjaśnień
SpaceTrucker
12
List<Sock> UnSearchedSocks = getAllSocks();
List<Sock> UnMatchedSocks = new list<Sock>();
List<PairOfSocks> PairedSocks = new list<PairOfSocks>();

foreach (Sock newSock in UnsearchedSocks)
{
  Sock MatchedSock = null;
  foreach(Sock UnmatchedSock in UnmatchedSocks)
  {
    if (UnmatchedSock.isPairOf(newSock))
    {
      MatchedSock = UnmatchedSock;
      break;
    }
  }
  if (MatchedSock != null)
  {
    UnmatchedSocks.remove(MatchedSock);
    PairedSocks.Add(new PairOfSocks(MatchedSock, NewSock));
  }
  else
  {
    UnmatchedSocks.Add(NewSock);
  }
}
Czad
źródło
12

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.

Sasa
źródło
Po napisaniu tego używam go za każdym razem. Pomogło mi to stać się nieco bardziej wydajnym, a praca jest teraz mniej nudna.
Sasa,
11

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.

Andrew Hill
źródło
10

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.

trpt4him
źródło
To właśnie robię ... O (n)
Pykler
2
@Pykler - To O (n) w najlepszym przypadku i O (n * n) w najgorszym przypadku.
Vilx-
2
To zakładając, że nie możesz stworzyć w pełni unikalnego skrótu w myślach wszystkich skarpet, które już widziałeś, co dla mnie jest O (1), aby dopasować skarpetę, którą widziałem i poprzednio i umieściłem w oczekiwaniu na pasujący skrót
Pykler
10

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ł. :-)

Arvind
źródło
10

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

mozboz
źródło
Nie odpowiada na pytanie, ponieważ obsługa już sparowanych danych jest łatwa, pytanie brzmi, co zrobić, gdy dane są NIEPAROWANE i chcesz je sparować.
amit
8

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.

SF.
źródło
Takie podejście ma dwie inne zalety: suszenie na linii traci wiele mniej skarpet IME niż w suszarce, a proces sortowania można rozszerzyć na resztę prania, więc (np.) Wszystkie ręczniki są blisko siebie, aby je złożyć linii i binned i zabrane prosto do ich przechowywania. Działa również w dwóch przebiegach bez wysiłku, zakładając ubrania i ponownie je zdejmując.
cphlewis,
8

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 :)

maestro
źródło
Jest to nadal algorytm O (n ^ 2), ponieważ musisz iterować po każdym segmencie za każdym razem, gdy wyciągniesz nową skarpetę. Biorąc jednak pod uwagę fakt, że nawet skarpetki zakupione w tej samej partii mają niewielkie różnice, które czynią je efektywnymi unikalnymi parami (lub nawet pojedynczymi unikatami), i tak nie ma lepszego sposobu
Semisonic
Zgadzam się, ale mój algorytm zakłada, że ​​człowiek wykonuje parowanie. Dlatego podczas wyszukiwania pasującego wiadra będziesz mieć w pamięci coś w rodzaju pamięci podręcznej, więc tak naprawdę nie musisz iterować po wiadrach. Nie jestem pewien, jaka struktura danych jest zbudowana dla tego mechanizmu buforowania w mojej głowie podczas parowania.
maestro
8

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

wrzasa
źródło
8

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.

Philipp Flenker
źródło
Skarpety są jedynie metaforą do parowania dowolnych obiektów w niektórych bazach danych.
amit
1
Rozumiem, nie widziałem, że jesteś autorem. Jeśli chciałeś ogólnego rozwiązania, powinieneś tak powiedzieć. W każdym razie nie ma nic złego w braniu pod uwagę wszelkich posiadanych informacji, chyba że musisz wymyślić ogólne rozwiązanie - rezygnacja z ponownego użycia rozwiązania może spowodować znacznie lepszą wydajność. W takim przypadku rozważenie przypadku użycia i dostępnej bazy danych jako całości jest korzystne. Jednak ta specjalna odpowiedź na twoje specjalne pytanie ma problemy z podobnie wyglądającymi skarpetami, np. Czarnymi skarpetkami w różnych rozmiarach, więc nie ma zastosowania w niektórych przypadkach.
Philipp Flenker
1
Nie otrzymałeś także> 2k głosów pozytywnych, ponieważ zadałeś pytanie dotyczące parowania dowolnych obiektów w bazie danych. W szczególności ograniczyłeś to pytanie ze względu na samą naturę skarpet (których nie możesz powielić, w przeciwieństwie do danych), nawet zachęcałeś do korzystania z faktu, że możesz łatwo odróżnić skarpetki od skarpet małżonka. Jeśli zadajesz pytanie dotyczące skarpet, nie oczekuj, że odpowiedzi będą dotyczyć baz danych ;-)
Philipp Flenker
1
Istnieje kilka założeń: normalna pralka, normalna linia bielizny i fakt, że wrzucasz obie skarpetki do kosza w tym samym czasie, co oznacza, że ​​w większości przypadków obie skarpetki są w tej samej maszynie, a liczba resztki skarpet do sortowania są zatem niewielkie. Ale skoro tak naprawdę chcesz odpowiedzi na temat przechowywania dowolnych obiektów w bazie danych, czy naprawdę warto omawiać moje rozwiązanie w przyszłości?
Philipp Flenker
1
Jak powiedziałem, myślę, że zająłem się wszystkim, o co prosiłeś, z wyjątkiem problemu odróżnienia elementu, na który odpowiedzieli inni ludzie. Nie staram się być tutaj dupkiem, ale włożyłem wiele wysiłku w tę odpowiedź już dawno i jestem lekko rozczarowany, że teraz przejrzysz niektóre z odpowiedzi i twierdzisz, że nie odpowiedzieli na pierwotne pytanie . Dlaczego nie zostawisz całego wątku w spokoju - to wciąż ciekawa lektura, ponad 2 lata po tym, jak go zapytałeś?
Philipp Flenker
8

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

Scott Brickey
źródło
7

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.

viper110110
źródło
Jak to zrobić w miejscu, jak konkretnie wspomniano w pytaniu?
amit
7

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 . :)

Fred Mitchell
źródło
To nie odpowiada na pytanie, gdzie skarpetki są tylko metaforą.
amit
Pytanie brzmiało, jak sparować skarpetki z niesparowanego stosu, a nie jak uniknąć konieczności parowania.
amit