StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>As a practical solution:</p> <ol> <li>Quickly make piles of easily distinguishable socks. (Say by color)</li> <li>Quicksort every pile and use the length of the sock for comparison. As a human you can make a fairly quick decision which sock to use to partition that avoids worst case. (You can see multiple socks in parallel, use that to your advantage!)</li> <li>Stop sorting piles when they reached a threshold at which you are comfortable to find spot pairs and unpairable socks instantly</li> </ol> <p>If you have 1000 socks, with 8 colors and an average distribution, you can make 4 piles of each 125 socks in c*n time. With a threshold of 5 socks you can sort every pile in 6 runs. (Counting 2 seconds to throw a sock on the right pile it will take you little under 4 hours.)</p> <p>If you have just 60 socks, 3 colors and 2 sort of socks (yours / your wife's) you can sort every pile of 10 socks in 1 runs (Again threshold = 5). (Counting 2 seconds it will take you 2 min).</p> <p>The initial bucket sorting will speed up your process, because it divides your n socks into k buckets in <code>c*n</code> time so than you will only have to do <code>c*n*log(k)</code> work. (Not taking into account the threshold). So all in all you do about <code>n*c*(1 + log(k))</code> work, where c is the time to throw a sock on a pile.</p> <p>This approach will be favourable compared to any <code>c*x*n + O(1)</code> method roughly as long as <code>log(k) < x - 1</code>.</p> <hr> <p>In computer science this can be helpful: We have a collection of n <em>things</em>, an order on them (length) and also an equivalence relation (extra information, for example the color of socks). The equivalence relation allows us to make a partition of the original collection, and in every equivalence class our order is still maintained. The mapping of a <em>thing</em> to it's equivalence class can be done in O(1), so only O(n) is needed to assign each item to a class. Now we have used our extra information and can proceed in any manner to sort every class. The advantage is that the data sets are already significantly smaller.</p> <p>The method can also be nested, if we have multiple equivalence relations -> make colour piles, than within every pile partition on texture, than sort on length. Any equivalence relation that creates a partition with more than 2 elements that have about even size will bring a speed improvement over sorting (provided we can directly assign a sock to its pile), and the sorting can happen very quickly on smaller data sets.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload