Pytanie Jak sprawnie sparować skarpetki ze stosu?


Wczoraj parowałem skarpetki z czystej bielizny i zorientowałem się, że robię to niezbyt wydajnie. Robiłem naiwne poszukiwania - wybierając jedną skarpetkę i "iterując" stos, aby znaleźć jego parę. Wymaga to iterowania powyżej n / 2 * n / 4 = n2/ 8 skarpetek średnio.

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

Hashing lub inne nie-w-miejscu rozwiązania nie są opcją, ponieważ nie jestem w stanie zduplikować skarpetek (chociaż mogłoby być miło, gdybym mógł).

Pytanie brzmi w zasadzie:

Biorąc pod uwagę stos n pary skarpet, zawierające 2n elementy (zakładając, że każda skarpetka ma dokładnie jedną pasującą parę), jaki jest najlepszy sposób na ich sparowanie z logarytmiczną dodatkową przestrzenią? (Wierzę, że pamiętam tę ilość informacji w razie potrzeby.)

Docenię odpowiedź, która dotyczy następujących aspektów:

  • Generał teoretyczny rozwiązanie dla ogromnej liczby skarpet.
  • Rzeczywista liczba skarpetek nie jest duża, nie wierzę mojemu małżonkowi i mam ponad 30 par. (I dość łatwo jest odróżnić moje skarpetki od jej, czy też można to wykorzystać?)
  • Czy to jest odpowiednik element odrębności problemu?

3507
2018-01-19 15:34


pochodzenie


Używam zasady dziurkacza, aby sparować dokładnie jeden ze stosu prania. Mam 3 różne kolory skarpet (czerwony, niebieski i zielony) i 2 pary każdego koloru. Podnoszę za każdym razem 4 numery skarpetek i zawsze tworzę parę i zabieram się do pracy. - Srinivas
Jeszcze jedna zasada dziury dla gołębi: jeśli weźmiesz podzbiór skarpet n + 2 + 1, tam musi być przynajmniej jedna para w tym podzbiorze. - wildplasser
Świetne pytanie! Być może zainteresowałeś się moim artykułem dotyczącym pokrewnego problemu, który jest omówieniem prawdopodobieństwa wyciągnięcia z kupki dwóch dopasowanych skarpet: blogs.msdn.com/b/ericlippert/archive/2010/03/22/... - Eric Lippert
Dlaczego nie odrodzić dziecko i waitpid więc jako rodzic nie sortujesz nawet skarpetek? - Mxyk
Rozwiązałem ten problem, mając tylko białe skarpetki sięgające kolan. Wszystkie pasują. Mogłem po prostu chwycić dowolne dwie skarpety ze stosu i pasowałyby do siebie. Ponadto upraszczam problem, NIE sparowując skarpet. Mam szufladę na skarpety, w której po prostu wrzucam wszystkie moje skarpetki, bez spodni. Każdego ranka wyciągam losowo dwie z szuflady. Uprościłem to do O (0). Nie można zrobić nic prostszego. :) - Lee


Odpowiedzi:


Zaproponowano rozwiązania sortowania, ale sortowanie to trochę za dużo: Nie potrzebujemy zamówienia; potrzebujemy tylko grup równościowych.

Więc mieszanie wystarczyłoby (i szybciej).

  1. Dla każdego koloru skarpet, uformować stos. Iteruj po wszystkich skarpetach w koszyku wejściowym i rozprowadzić je na stosach kolorów.
  2. Iteruj po każdym stosie i rozpowszechniać go według innych danych (na przykład wzór) do drugiego zestawu stosów
  3. Rekurencyjnie zastosuj ten schemat dopóki nie rozprowadzisz wszystkich skarpetek bardzo małe stosy, które możesz natychmiast wizualnie przetworzyć

Tego rodzaju rekursywne partycje hash są wykonywane przez SQL Server kiedy musi się mieszać lub agregować hash w ogromnych zbiorach danych. Rozdziela swój strumień wejściowy kompilacji na wiele niezależnych partycji. Ten schemat skaluje się liniowo do dowolnych ilości danych i wielu procesorów.

Nie potrzebujesz rekursywnego partycjonowania, jeśli znajdziesz klucz dystrybucyjny (klawisz skrótu) zapewnia wystarczającą ilość wiaderek że każde wiadro jest na tyle małe, że można je bardzo szybko przetworzyć. Niestety nie sądzę, aby skarpetki miały taką własność.

Jeśli każda skarpetka ma liczbę całkowitą o nazwie "PairID", z łatwością można je rozdzielić na 10 segmentów zgodnie z PairID % 10 (ostatnia cyfra).

Najlepszym partycjonowaniem w świecie rzeczywistym jest tworzenie prostokąt stosów: jeden wymiar to kolor, a drugi to wzór. Dlaczego prostokąt? Ponieważ potrzebujemy O (1) losowego dostępu do stosów. (3D prostopadłościan też by działało, ale to nie jest bardzo praktyczne.)


Aktualizacja:

Co powiesz na równoległość? Czy wielu ludzi może szybciej dopasować skarpetki?

  1. Najprostsza strategia zrównoleglania polega na tym, że wielu pracowników bierze z koszyka wejściowego i kładzie skarpetki na stosach. To tylko tyle się skaluje - wyobraź sobie 100 osób walczących z ponad 10 stosami. Koszty synchronizacji (przejawiające się jako zderzenie rąk i komunikacja międzyludzka) niszczyć wydajność i przyspieszenie (patrz Uniwersalne prawo dotyczące skalowalności!). Czy to jest podatne na to zakleszczenia? Nie, ponieważ każdy pracownik musi mieć dostęp tylko do jednego stosu na raz. Z tylko jednym "zamkiem" nie może być impasu. Livelocks może być możliwe w zależności od tego, w jaki sposób ludzie koordynują dostęp do stosów. Mogą po prostu użyć losowy backoff podobnie jak karty sieciowe, wykonaj to na poziomie fizycznym, aby określić, która karta ma dostęp wyłącznie do przewodu sieciowego. Jeśli to działa Karty sieciowe, powinno to również działać dla ludzi.
  2. Skaluje się niemal w nieskończoność, jeśli każdy pracownik ma własny zestaw stosów. Pracownicy mogą wtedy zabierać duże kawałki skarpet z koszyka wejściowego (bardzo mało rywalizacji, ponieważ robią to rzadko) i nie potrzebują synchronizować podczas dystrybucji skarpetek (ponieważ mają stosy miejscowe). 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 robotnicy tworzą drzewo agregacji.

A co z element odrębności problemu? Zgodnie z tym artykułem można rozwiązać problem odmienności elementu O(N). To samo dotyczy problemu skarpet (również O(N), jeśli potrzebujesz tylko jednego kroku dystrybucji (zaproponowałem wiele kroków tylko dlatego, że ludzie są źli w obliczeniach - wystarczy jeden krok, jeśli rozpowszechniasz md5(color, length, pattern, ...), tj doskonałe hash wszystkich atrybutów)).

Oczywiście, nie można iść szybciej niż O(N), więc dotarliśmy do optymalna dolna granica.

Chociaż wyjścia nie są dokładnie takie same (w jednym przypadku, po prostu boolean, w innym przypadku pary skarpet), asymptotyczne zawiłości są takie same.


2180
2017-10-19 20:47



Dokładnie to robię! Sprawię, że stosy zależą od stylu otwierania skarpety (mam tylko biały), co daje mi wystarczająco dużo "kubełków", aby szybko dopasować każdą z nich. - Scott Chamberlain
Próbowałem tego z moimi skarpetkami (mam łatwo 30+ par) i człowiek jest SZYBKO. Jednym z problemów, które znalazłem, jest to, że nie mogę mieć wystarczająco dobrego algorytmu mieszania (mam dużo białych skarpet bez żadnego wzoru), więc staje się trudny. W takim razie jaki byłby optymalny sposób na zrobienie tego? - NothingsImpossible
@NothingsImpossible, w jaki sposób ataki kolizji hash są dla słabego serwera WWW! Czy białe skarpety są rozróżnialne według jakiegoś atrybutu? Musi być coś, na czym możesz je rozpowszechniać. W przeciwnym razie możesz utworzyć pary dowolnie. - usr
To jest rodzaj radix, który, jak uważam, jest właściwą odpowiedzią. @MarkPeters Nie potrzebuję tabeli odnośników. Pojedyncze liniowe przejście przez skarpetki może przekształcić skarpetki w liczby wektorowe, dzięki czemu odwzorowanie "segmentu skarpety" na wiadro jest banalne. Skarpety można powiązać z wektorami za pomocą sznurka, aby na końcu nie potrzebować kolejnego przejścia liniowego. - Pointy
Facet, którego uczęszczałem do college'u, miał faktycznie parę PairIDów. Był on wszyta na każdej parze skarpet z nitką: 1, 2, 3, 4 ... - Ryan Lundy


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

Ludzie mogą wygrać 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 to jest to, czego używam w prawdziwym życiu i uważam, że jest bardzo wydajny. Minusem jest to, że wymaga płaskiej powierzchni, ale zwykle jest obfita.


523
2018-05-27 19:13



gdy wzrasta liczba skarpet, ludzka karta SIM nie jest lepsza od procesora. - Lie Ryan
Najlepsza odpowiedź, IMO. Chociaż jest to zabawne i sprytne (i odpowiednie dla SO), aby zredukować codzienny problem z algorytmem komputerowym, rozsądniej jest użyć mocy rozdzielczej ludzkiego oka / mózgu dla zestawu tak małego jak ~60 skarpet. - drug_user841417
@LieRyan Jeśli skarpetki są równomiernie rozmieszczone, zauważysz parę w jakimkolwiek wystarczająco małym zestawie skarpetek ze względu na urodzinowy paradoks (chyba że możesz odróżnić kolory od arbitralnej precyzji, którą wątpię), więc wąskie gardło tutaj nie byłoby ludzki algorytm dopasowywania kolorów, ale etap rozprzestrzeniania. - Thomas
@ dpc.ucore.info Nie, ponieważ mają one różne wzory splotów mankietu, długości mankietów, długości całkowitej i odcieni czerni (moja żona prawdopodobnie fizycznie zraniłaby mnie za tę ostatnią). - Christian
Lepiej mieć nadzieję, że masz parzystą liczbę skarpet, bo inaczej będziesz składać skarpetki przez długi czas ... - Patrick James McDougle


Przypadek 1: Wszystkie skarpetki są identyczne (tak właśnie robię w prawdziwym życiu).

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

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

Posługiwać się sortowanie radix. Jest to tylko czas liniowy, ponieważ porównanie nie jest wymagane.

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

Musimy zrobić porównanie, aby sprawdzić, czy dwie skarpetki są w parze. Wybierz jeden z O(n log n) oparte na porównywaniu algorytmy sortowania.

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


231



> Może to zająć więcej czasu niż wyszukiwanie sekwencyjne, które teoretycznie wymaga czasu. Tak, dlatego nienawidzę tego robić, może powinienem wyrzucić wszystkie moje skarpetki i zacząć od przypadku 1. - Nils
Łatwiej też mieć te same skarpetki. Co kilka lat kupuję 10 takich 6 paczek skarpetek, gdy są one w sprzedaży i wyrzucają wszystkie moje stare skarpetki. Po prostu łatwiej dopasować identyczne skarpetki i wyglądają lepiej niż stare święte skarpetki. Dzięki temu, najprostsze dla mnie jest po prostu pierwsze z góry stosu. - Michael D. Kirkpatrick
wadą wszystkich identycznych skarpet jest to, że mają tendencję do starzenia się w różnym tempie. Więc wciąż próbujesz dopasować je w zależności od tego, jak bardzo są zużyte. (co jest trudniejsze niż zwykłe dopasowanie według wzoru) - SDC
Problem z posiadaniem 60 par identycznych skarpet "ponieważ ułatwia parowanie" jest taki, że daje ludziom wrażenie, że pracujesz z komputerami. - Steve Ives
Przypadek 1 nie jest stały czas, kiedy jest wykonywana operacja, na przykład składanie par razem. W tym przypadku jest to czas liniowy z najmniejszym stałym współczynnikiem (dowód, który został pozostawiony jako ćwiczenie dla czytelnika). Jeden nie można w tym samym czasie złożyć jednej pary i wiadra pełnego skarpet. Jednak skaluje się liniowo. Według prawa Amdahla ma on nieograniczone przyspieszenie, ignorując koszty ogólne. Zgodnie z prawem Gustafsona, możesz złożyć tyle par, ile potrzeba, aby spasować jedną parę, biorąc pod uwagę wystarczającą liczbę pracowników (których ilość jest pozostawiona jako ćwiczenie dla czytelnika), ignorując obciążenie. - acelent


Odpowiedź nieautoryzująca, ale "wydajna", gdy to robię:

  • krok 1) odrzuć wszystkie swoje skarpetki

  • krok 2) przejdź do Walmart i kup je pakietami po 10 - n pakietu białe i m pakiety czarnego. Nie potrzeba innych kolorów w codzienności życie.

Od czasu do czasu muszę to robić ponownie (utracone skarpetki, uszkodzone skarpetki itp.) I nie chcę zbyt często wyrzucać doskonałych skarpet (i żałuję, że nie sprzedają tych samych skarpetek!), Więc ostatnio wziąłem inne podejście.

Odpowiedź algorytmiczna:

Zastanów się, że jeśli narysujesz tylko jedną skarpetkę dla drugiej skarpetki, to twoje szanse na znalezienie pasującej skarpetki 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 RPN stack - pięć to bezpieczna wartość domyślna.

  • Podnieś jeden ze stosu 2n-5.

  • Teraz szukaj dopasowania (dopasowanie wzoru wizualnego - ludzie są dobrzy w tym z małym stosem) wewnątrz piątki, którą narysowałeś, jeśli jej nie znajdziesz, a następnie dodaj to do piątki.

  • Trzymaj losowo skarpetki ze stosu i porównuj ze skarpetkami 5 + 1 na mecz. Wraz ze wzrostem twojego stosu zmniejszysz wydajność, ale zwiększysz swoje szanse. O wiele szybciej.

Zapamiętaj wzór, aby obliczyć, ile próbek musisz dobrać, aby uzyskać 50% prawdopodobieństwa meczu. IIRC to prawo hipergeometryczne.

Robię to każdego ranka i rzadko potrzebuję więcej niż trzech losowań - ale mam n podobne pary (około 10, dawaj lub zabijaj) z m w kształcie białych skarpet. Teraz możesz oszacować wielkość mojego stada zapasów :-)

BTW, Stwierdziłem, że suma kosztów transakcyjnych sortowania wszystkich skarpet za każdym razem, gdy potrzebowałem pary, była o wiele mniejsza niż jednorazowa i wiążąca skarpetki. Funkcja "just-in-time" działa lepiej, ponieważ wtedy nie musisz wiązać skarpetek, a także maleje marginalna stopa zwrotu (to znaczy, wciąż szukasz tych dwóch lub trzech skarpet, które gdzieś w praniu i które potrzebujesz aby dopasować skarpetki i stracić na tym czas).


144



Awans do odpowiedzi "nie-algorytmicznej". Dokładnie to robię i działa wspaniale. Problem wymiany nie stanowi problemu, jeśli "obrócisz" skarpetkę, umieszczając umyte skarpetki na plecach i ciągnąc od przodu szuflady rano. Wszystkie skarpetki noszą się równomiernie. Kiedy zaczynam zauważać pewne zużycie, zakładam listę zakupów, aby całkowicie zastąpić całą klasę skarpet. W przypadku starych skarpet dam najlepsze 20% do wartości firmy (przywiązane w worku na zakupy, żeby się nie mieszały) i rozbij resztę. Nie marnujesz skarpetek, w tym momencie 80% pozostało tylko 6 miesięcy. - FastAl
BTW (1) Wiązanie skarpet powoduje, że elastyczna jedna z nich jest naciągnięta, a obleje szybciej. Ograniczenie rodzajów unikalnych skarpet, które posiadasz, unieruchamia. (2) Wadą ograniczania unikalnych skarpet jest to, że dla osób mających pewne obawy związane z modą, metoda może być nieodpowiednia. - FastAl
Przyszedłem tutaj specjalnie po to, aby opublikować swoją "nieautoryzującą się" odpowiedź. Jak w prawdziwej informatyce, większość ludzi nigdy nie zwraca uwagi na dane i ich strukturę. - bkconrad
Używam tego podejścia algorytmicznego każdego ranka i działa jak urok! Dodatkowo nakładam zużyte skarpetki na inny stos, który później wyrzucę (niestety uda im się ponownie dotrzeć do oryginalnego stosu, zanim znajdę czas, żeby je wyrzucić). - Donatas Olsevičius
«N pakiet białych i m pakietów czarnych. Nie ma potrzeby stosowania innych kolorów w życiu codziennym »Dobrą normą dla łatwego doboru skarpet jest fakt, że powinny one pasować zarówno do koloru twoich spodni, jak i koloru paska. Z tego powodu najpowszechniej stosowanymi kolorami będą prawdopodobnie czarny, niebieski, szary i brązowy. Trudno uwierzyć, że trzeba mieć wiele białych skarpet. - Andrea Lazzarotto


Robię tylko pierwszą skarpetkę i kładę ją (powiedzmy na krawędzi miski). Następnie wybieram kolejną skarpetkę i sprawdzam, czy jest taka sama jak pierwsza skarpetka. Jeśli tak, usuwam oba. Jeśli nie, odkładam go obok pierwszej skarpety. Następnie podnoszę trzecią skarpetkę i porównuję ją z pierwszymi dwoma (jeśli nadal tam są). Itp.

To podejście można dość łatwo wdrożyć w tablicy, zakładając, że "usunięcie" skarpet jest opcją. Właściwie nie musisz nawet "usuwać" skarpet. Jeśli nie potrzebujesz sortowania skarpet (patrz niżej), możesz po prostu je przenieść i skończyć z tablicą, w której wszystkie skarpetki ułożone są w pary w tablicy.

Zakładając, że jedyną operacją dla skarpet jest porównanie dla równości, ten algorytm jest w zasadzie wciąż równy n2 algorytm, choć nie wiem o przeciętnym przypadku (nigdy nie nauczyłem się tego obliczyć).

Sortowanie poprawia oczywiście wydajność, szczególnie w prawdziwym życiu, w którym można łatwo włożyć skarpetę między dwie inne skarpetki. W obliczeniach można to osiągnąć za pomocą drzewa, ale to dodatkowa przestrzeń. I oczywiście wracamy do NlogN (lub nieco więcej, jeśli istnieje kilka takich samych skarpetek według kryteriów sortowania, ale nie z tej samej pary).

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


92



To też robię (zauważ, że jeśli po prostu zostawisz spacje, to wstawki też będą O (1)), ale skalą się kiepsko z teoretycznie dużą liczbą skarpet. - Mooing Duck
skaluje się słabo z teoretycznie dużą liczbą rodzaje skarpety - Steven Lu
@StevenLu - tak jak powiedziałem - to n * n lub nLogn, w zależności od tego, czy je sortujesz, czy nie. Więc skaluje się tak źle, jak każdy algorytm sortowania. Jeśli chcesz szybciej, policz je i użyj sortowania radix. - Vilx-
W zasadzie polega to na przechowywaniu znalezionych skarpet, ale niezrównanych w wyszukiwaniu hash. W przypadku idealnego skrótu jest to O (n), ale jeśli masz wystarczająco dużo skarpet przechowywanych, że skrót zaczyna się degenerować, staje się on bardziej złożony. - Jon Hanna
jaką wartość wkładanie skarpety między 2 inne skarpetki zapewnia cel parowania skarpetek? nie ma liczności skarpet. : -x - JoeBrockhaus


Zadaje to niewłaściwe pytanie. Właściwym pytaniem jest, dlaczego spędzam czas sortując skarpetki? Ile kosztuje rocznie, gdy cenisz swój wolny czas na X jednostek monetarnych do wyboru?

I częściej niż nie, to nie tylko każdy czas wolny ranek czas wolny, który można spędzać w łóżku, popijać kawę lub wychodzić trochę wcześniej i nie dać się złapać w korku.

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

I jest sposób!

Znajdź skarpetę, którą lubisz. Uwzględnij wszystkie istotne cechy: kolor w różnych warunkach oświetleniowych, ogólna jakość i trwałość, komfort w różnych warunkach klimatycznych i pochłanianie zapachów. 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 opakowaniu z tworzywa sztucznego.

Lepiej, jeśli nie ma różnicy między skarpetkami lewą i prawą, ale nie jest to krytyczne. Jeśli skarpetki są symetryczne w lewo-prawo, znalezienie pary jest operacją O (1), a sortowanie skarpet jest przybliżoną operacją O (M), gdzie M to liczba miejsc w twoim domu, które zasypałeś skarpetkami, najlepiej niektóre mała stała liczba.

Jeśli wybrałeś fantazyjną parę z inną lewą i prawą skarpetą, wykonanie pełnego sortowania kubełków do lewej i prawej łyżki dla stóp bierze O (N + M), gdzie N jest liczbą skarpet, a M jest takie samo jak powyżej. Ktoś inny może podać formułę dla średnich iteracji znalezienia pierwszej pary, ale najgorszym przypadkiem znalezienia pary z ślepym wyszukiwaniem jest N / 2 + 1, co staje się astronomicznie mało prawdopodobne w przypadku uzasadnionego N. To może być przyspieszone przy użyciu zaawansowanego obrazu algorytmy rozpoznawania i heurystyki podczas skanowania stosu niesortowanych skarpet Mk1 gałka oczna.

Tak więc algorytm uzyskiwania efektywności parowania O (1) (zakładając symetryczne skarpety) to:

  1. Musisz oszacować, ile par skarpet będziesz potrzebować do końca swojego życia, a może do momentu przejścia na emeryturę i przejścia do cieplejszych klimatów bez konieczności noszenia skarpet. Jeśli jesteś młody, możesz również oszacować, ile czasu zajmie, zanim wszyscy będziemy mieli 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ć swoją wybraną skarpetę luzem i ile kosztuje ona i ile ona dostarcza.

  3. Zamów skarpetki!

  4. Pozbądź się starych skarpetek.

Alternatywny krok 3 wiązałby się z porównywaniem kosztów kupowania takiej samej ilości tańszych skarpetek kilka par na raz przez lata i dodawania kosztu sortowania skarpet, ale wierz mi na słowo: kupowanie luzem jest tańsze! Również skarpetki w magazynie zwiększają wartość w tempie inflacji cen akcji, czyli więcej niż można uzyskać w przypadku wielu inwestycji. Z drugiej strony jest jeszcze koszt przechowywania, ale skarpetki naprawdę nie zajmują dużo miejsca na górnej półce szafy.

Problem rozwiązany. Więc po prostu weź nowe skarpety, rzuć / oddaj stare i żyj długo i szczęśliwie, wiedząc, że każdego dnia oszczędzasz pieniądze i czas do końca życia.


50



Dożywotnia (przy założeniu, że 75 lat) dostawa skarpet (zakładając, że zużyjesz 4 pary na miesiąc, czyli 3600 par), zajmie (zakładając, że nowa para skarpet zajmuje 20 cali sześciennych) łącznie 1 1/2 jardów sześciennych. To ogromna ilość miejsca. Zakładając, że dostarczą ci ją w pudełku, który jest w przybliżeniu sześcianem, skrzynia ta będzie miała około 3 stopy 4 cale na boku. - AJMansfield
@AJMansfield ważny problem. Jednak nie zgadzam się z kilkoma z twoich numerów. Zajęłbym przedział czasowy zaledwie 40 lat (25 ... 65) (czas między zamieszkaniem u rodziców / akademika / etc i przejściem na emeryturę, patrz wyżej). Sądzę 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 nieekonomiczny, -1. - Dan Bechard
Przewodnik dla osób, które mogą być pomylone z pomiarami AJMansfield, tłumaczenie na metryczne: »zajmie (zakładając, że nowa para skarpet zajmuje 327 cm³) w sumie 1,14 m³. To ogromna ilość miejsca. Zakładając, że dostarczą ci ją w pudełku, który jest w przybliżeniu sześcianem, skrzynia ta będzie miała około 1,04 m na boku. « - Joey


Teoretyczna granica to 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) z sortowanie radix. Musisz tylko wybrać atrybuty dla wiader.

  1. Najpierw możesz wybrać (jej, moje) - podzielić je na 2 stosy,
  2. następnie użyj kolorów (może mieć dowolną kolejność dla kolorów, np. alfabetycznie według nazwy koloru) - podziel je na stosy według kolorów (pamiętaj, aby zachować początkową kolejność od kroku 1 dla wszystkich skarpet na tym samym 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 mogą jednoznacznie zidentyfikować każdą parę, powinieneś zrobić to w O (k * n), czyli O (n), jeśli uważamy, że k jest ograniczone.


47



Skarpetki często są w 4-paczkach i większych, ponieważ jest to tańsze, ale także powoduje, że są one nie do odróżnienia. Aby temu przeciwdziałać, moja żona szyje maleńką markę na każdej nowej skarpetce, którą kupuję. Znak ma inny kolor dla każdej pary lub inny kształt, jeśli zabraknie jej kolorów. Dzięki takiemu podejściu nie potrzebujesz nawet ograniczonego zestawu atrybutów. Wystarczy uszyć unikalny numer na każdej parze. :) Aby uzyskać dodatkowe punkty, użyj binarnego. - Vilx-
@ Vilx- DLACZEGO?!? Czy nie chodzi o to, że są one nie do odróżnienia? - flup
@flup - Myślę, że chodzi o sprzedaż w większych pakietach. :) Jeśli chodzi o mnie, pomaga to je nosić w parach. W przeciwnym razie mogę skończyć na trzech bardzo zużytych skarpetach i jednej zupełnie nowej. Trochę głupie. - Vilx-
Nie zgadzam się z obliczeniem O (n). Co to jest $ k $? $ k $ to liczba atrybutów. Twierdzę, że $ k $ to $ O (log n) $, ponieważ musi wystarczyć, aby jednoznacznie zidentyfikować każdą parę. Jeśli masz dwie pary (czarno-białe), wystarczy kolor ($ k = 1, n = 2 $). Jeśli masz jedną parę czarną, krótką; jedna para czarnych, długich; jedna para białych, krótkich; i jedna para białych, długich - potem $ k = 2, n = 4 $. Następnie, jeśli ograniczymy $ k $, jednocześnie ograniczymy $ n $. Jeśli mamy zamiar ograniczyć $ n $, to kalkulacja zlecenia nie ma już sensu. - emory
@emory, myślę, że szukasz backtick, a nie the $ znak, aby twoje rzeczy wyglądały jak kod-y. - Xymostech


Jako praktyczne rozwiązanie:

  1. Szybko rób stosy łatwych do odróżnienia skarpet. (Powiedz według koloru)
  2. Quicksortuj każdy stos i użyj długości skarpety dla porównania. Jako człowiek możesz podjąć dość szybką decyzję, która będzie używana do podziału, aby uniknąć najgorszego przypadku. (Możesz zobaczyć wiele skarpetek równolegle, wykorzystaj to na swoją korzyść!)
  3. Zatrzymaj sortowanie stosów, gdy osiągną próg, w którym możesz od razu znaleźć pary punktów i niesparowane skarpetki

Jeśli masz 1000 skarpetek, 8 kolorów i średnią dystrybucję, możesz zrobić 4 stosy po 125 skarpet w c * n czasie. Przy progu 5 skarpet możesz sortować każdy stos w 6 seriach. (Licząc 2 sekundy, aby rzucić skarpetkę na prawy stos, zajmie ci to trochę mniej niż 4 godziny.)

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

Początkowe sortowanie kubełków przyspieszy proces, ponieważ dzieli n skarpety na k wiadra c*n czas, więc będziesz musiał tylko zrobić c*n*log(k) praca. (Nie biorąc pod uwagę progu). Więc w sumie wszystko co robisz n*c*(1 + log(k)) praca, gdzie c to czas rzucania skarpet na stos.

Takie podejście będzie korzystne w porównaniu z każdym c*x*n + O(1) metoda z grubsza tak długo jak log(k) < x - 1.


W informatyce może to być pomocne: Mamy kolekcję n rzeczy, zamówienie 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ę oryginalnego zbioru, aw każdej klasie równoważności nasze zamówienie jest nadal zachowane. Mapowanie a rzecz do jego klasy równoważności można zrobić w O (1), więc tylko O ​​(n) jest potrzebne, aby przypisać każdy element do klasy. Teraz wykorzystaliśmy nasze dodatkowe informacje i możemy postępować w dowolny sposób, aby posortować każdą klasę. Zaletą jest to, że zestawy danych są już znacznie mniejsze.

Metoda może być również zagnieżdżona, jeśli mamy wiele relacji równoważności -> tworzyć stosy kolorów, niż w każdej partycji stosu na teksturach, niż sortować na długości. Każda relacja równoważności, która tworzy partycję z więcej niż 2 elementami, które mają mniej więcej rozmiar, przyniesie poprawę szybkości w porównaniu z sortowaniem (pod warunkiem, że możemy bezpośrednio przypisać skarpetkę do stosu), a sortowanie może odbywać się bardzo szybko na mniejszych zestawach danych.


31



Optymalizacja ludzka: argumentowałbym, że jako człowiek, w kroku 2, powinieneś plonować skarpetki w przybliżeniu w porządku rosnącym, a następnie powtarzać z drobniejszą i drobniejszą ziarnistością aż do posortowania, trochę jak sortowanie skorupowe. Byłoby to znacznie szybsze dla człowieka (ocena wizualna) niż podejście oparte na zamianie opartej na porównaniu. - AndrewC