Вопрос: Как эффективно сочетать носки с кучей?


Вчера я спаривал носки с чистого белья и выяснил, как я это делаю, это не очень эффективно. Я делал наивный поиск - собирал один носок и «итерировал» кучу, чтобы найти свою пару. Это требует итерации по n / 2 * n / 4 = n 2 / 8 носков в среднем.

Как компьютерный ученый, я думал, что я могу сделать? Сортировка (в зависимости от размера / цвета / ...), конечно, приходила на ум для решения O (NlogN).

Хеширование или другие решения не на месте - это не вариант, потому что я не могу дублировать свои носки (хотя было бы неплохо, если бы я мог).

Итак, вопрос в основном:

Учитывая кучу nпары носков, содержащих 2nэлементы (предположим, что каждый носок имеет ровно одну совпадающую пару), каков наилучший способ их эффективного соединения с помощью логарифмического дополнительного пространства? (По-моему, я могу запомнить этот объем информации в случае необходимости.)

Я буду признателен за ответ, который касается следующих аспектов:

  • Генерал теоретический решение для огромного количества носков.
  • Фактическое количество носков не так велико, я не верю моему супругу, и у меня более 30 пар. (И довольно легко различить мои носки и ее, можно ли это использовать и?)
  • Это эквивалентно проблема отличимости элемента ?

3473


источник


Ответы:


Были предложены варианты сортировки, но сортировка немного : Нам не нужен заказ; нам нужны группы равенства ,

Так хэширования было бы достаточно (и быстрее).

  1. Для каждого цвета носков, формировать кучу , Итерируйте все носки в корзине ввода и распределить их на цветные свая ,
  2. Итерации по каждой куче и распространять его по какой-либо другой метрике (например, рисунок) во второй набор свай
  3. Рекурсивно применить эту схему пока вы не распространили все носки на очень маленькие сваи, которые вы можете визуально обрабатывать немедленно

Такое рекурсивное хэш-разбиение фактически выполняется SQL Server когда ему нужно объединить хэш-соединение или хеш-агрегат над огромными наборами данных. Он распределяет входной поток сборки во множество разделов, которые являются независимыми. Эта схема масштабируется до произвольного количества данных и нескольких процессоров линейно.

Вам не нужно рекурсивное разделение, если вы можете найти ключ распространения (хэш-ключ), который обеспечивает достаточное количество ведер что каждый ковш достаточно мал, чтобы обрабатываться очень быстро. К сожалению, я не думаю, что у носков такая собственность.

Если у каждого носка было целое число, называемое «PairID», можно было бы легко распределить их на 10 ведер в соответствии с PairID % 10(последняя цифра).

Лучшее реальное разбиение, о котором я могу думать, - это создать прямоугольник свай : одно измерение - цветное, другое - шаблон. Почему прямоугольник? Потому что нам нужен O (1) случайный доступ к сваям. (3D-изображение кубоид также будет работать, но это не очень практично.)


Обновить:

Как насчет параллелизм ? Может ли несколько людей быстрее соответствовать носкам?

  1. Простейшая стратегия распараллеливания состоит в том, чтобы несколько работников взяли из корзины ввода и положили носки на свай. Это только масштабы - воображайте 100 человек, сражающихся более 10 свай. Стоимость синхронизации (проявляющиеся как ручные столкновения и человеческое общение) разрушить эффективность и ускорить (см. Универсальный закон о масштабируемости !). Является ли это склонным к тупики ? Нет, потому что каждому работнику нужно только один раз получить доступ к одной куче. С одним «замком» не может быть тупика. Livelocks может быть возможно в зависимости от того, как люди координируют доступ к сваи. Они могут просто использовать случайное отсрочка как сетевые карты, делают это на физическом уровне, чтобы определить, какая карта может иметь исключительно доступ к сетевому проводу. Если это работает сетевые адаптеры , он должен работать и для людей.
  2. Он масштабируется почти бесконечно, если у каждого работника есть своя свая , Затем рабочие могут брать большие куски носков из корзины ввода (очень редко, поскольку они редко делают это), и им не нужно синхронизировать при распространении носков вообще (потому что у них есть нитки-локальные сваи). В конце концов, всем работникам необходимо объединить свои сваи. Я считаю, что это можно сделать в O (log (количество работника * свая на одного работника)), если рабочие образуют дерево агрегации ,

Что насчет проблема отличимости элемента ? Как указывается в статье, проблема отличимости элемента может быть решена в O(N), Это то же самое для проблемы с носками (также O(N), если вам нужен только один шаг распределения (я предложил несколько шагов только потому, что люди плохи при расчетах - достаточно одного шага, если вы распространяете md5(color, length, pattern, ...), т.е. идеальный хэш всех атрибутов)).

Ясно, что нельзя идти быстрее, чем O(N), поэтому мы достигли оптимальная нижняя граница ,

Хотя выходы не совсем одинаковы (в одном случае, только булевы. В другом случае, пары носков), асимптотические сложности одинаковы.


2167



Поскольку архитектура человеческого мозга полностью отличается от современного процессора, этот вопрос не имеет практического смысла.

Люди могут побеждать алгоритмы процессора, используя тот факт, что «поиск совпадающей пары» может быть одной операцией для набора, который не слишком велик.

Мой алгоритм:

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

По крайней мере, это то, что я использую в реальной жизни, и считаю это очень эффективным. Недостатком является то, что для этого требуется плоская поверхность, но она обычно изобилует.


522



Дело 1 : Все носки идентичны (кстати, это то, что я делаю в реальной жизни).

Выберите любые два из них, чтобы сделать пару. Постоянное время.

Случай 2 : Существует постоянное количество комбинаций (собственность, цвет, размер, текстура и т. Д.).

использование сортировка radix , Это только линейное время, так как сравнение не требуется.

Случай 3 : Количество комбинаций неизвестно заранее (общий случай).

Мы должны сделать сравнение, чтобы проверить, входят ли два носка в пару. Выберите один из O(n log n)алгоритмы сортировки на основе сравнения.

Однако в реальной жизни, когда количество носков относительно невелико (постоянное), эти теоретически оптимальные алгоритмы не будут работать хорошо. Это может занять еще больше времени, чем последовательный поиск, что теоретически требует квадратичного времени.


231



Не алгоритмический ответ, но «эффективный», когда я это делаю:

  • шаг 1) отбросить все существующие носки

  • шаг 2) перейти к Walmart и купите их по пакетам 10 - n пакетов белый и m пакетов черного цвета. Нет необходимости в других цветах в повседневной жизнь.

Но раз в разы, я должен сделать это снова (потерянные носки, поврежденные носки и т. Д.), И я ненавижу слишком часто отбрасывать совершенно хорошие носки (и я хотел, чтобы они продолжали продавать одни и те же ссылки на носки!), Поэтому я недавно принял другой подход.

Алгоритмический ответ:

Подумайте, чем если вы нарисуете только один носок для второго стека носков, как вы это делаете, ваши шансы найти подходящий носок в наивном поиске довольно низки.

  • Так что возьмите пять из них наугад, и запомните их форму или их длину.

Почему пять? Обычно люди хорошие, помнят от пяти до семи различных элементов в рабочей памяти - немного похоже на человеческий эквивалент RPN stack - пять является безопасным по умолчанию.

  • Возьмите один из стека 2n-5.

  • Теперь найдите совпадение (сопоставление визуальных шаблонов - люди хороши в этом с небольшим стеком) внутри пяти вы нарисовали, если вы его не найдете, а затем добавьте это в свои пять.

  • Держите случайным образом сбор носков из стека и сравните с вашими носками 5 + 1 для матча. По мере роста вашего стека он снизит вашу производительность, но повысит ваши шансы. Намного быстрее.

Не стесняйтесь записывать формулу, чтобы рассчитать, сколько образцов вы должны нарисовать для 50% шансов на матч. IIRC - это гипергеометрический закон.

Я делаю это каждое утро и редко нуждаюсь в более чем трех розыгрышах - но у меня есть nаналогичные пары (около 10, давать или брать потерянные) mобразные белые носки. Теперь вы можете оценить размер моего пакета акций :-)

КСТАТИ , Я обнаружил, что сумма транзакционных издержек при сортировке всех носков каждый раз, когда мне нужна была пара, была намного меньше, чем когда-либо, и привязывала носки. Лучшее время работает лучше, потому что вам не нужно связывать носки, а также уменьшает маргинальный доход (т. Е. Вы продолжаете искать эти два или три носка, которые когда-то в прачечной и что вам нужно чтобы закончить совпадение с вашими носками, и вы теряете время на этом).


144



Что я делаю, так это то, что я забираю первый носок и кладу его (скажем, на край чаши для белья). Затем я забираю еще один носок и проверяю, не совпадает ли он с первым носком. Если это так, я удаляю их обоих. Если это не так, я положил его рядом с первым носком. Затем я подбираю третий носок и сравниваю это с первыми двумя (если они все еще там). И т.п.

Этот подход можно довольно легко реализовать в массиве, предполагая, что «удаление» носков является опцией. На самом деле вам даже не нужно «удалять» носки. Если вам не нужна сортировка носков (см. Ниже), вы можете просто переместить их и получить массив, в котором все носки расположены в парах в массиве.

Предполагая, что единственная операция для носков - это сравнение для равенства, этот алгоритм в основном по-прежнему равен n 2 алгоритм, хотя я не знаю о среднем случае (никогда не научился его вычислять).

Сортировка, конечно, повышает эффективность, особенно в реальной жизни, когда вы можете легко «вставить» носок между двумя другими носками. При вычислении же может быть достигнуто дерево, но это дополнительное пространство. И, конечно же, мы вернулись в NlogN (или немного больше, если есть несколько носков, которые совпадают по критериям сортировки, но не из одной пары).

Помимо этого, я ничего не могу придумать, но этот метод кажется довольно эффективным в реальной жизни. :)


92



Это задает неправильный вопрос. Правильный вопрос: почему я трачу время на сортировку носков? Сколько это стоит на ежегодной основе, когда вы цените свое свободное время для Х денежных единиц по вашему выбору?

И чаще всего это не просто Любые свободное время, это утро свободное время, которое вы могли бы провести в постели, или потягивая кофе, или немного пораньше, и не попадаете в трафик.

Часто бывает полезно сделать шаг назад и подумать над проблемой.

И есть способ!

Найдите носок, который вам нравится. Учитывайте все соответствующие особенности: цвет в разных условиях освещения, общее качество и долговечность, комфорт в разных климатических условиях и поглощение запахов. Также важно, чтобы они не теряли эластичность при хранении, поэтому натуральные ткани хороши, и они должны быть доступны в пластиковой упаковке.

Лучше, если нет никакой разницы между ногами и ногами правой ноги, но это не критично. Если носки слева-справа симметричны, поиск пары - это операция O (1), а сортировка носков - приблизительная операция O (M), где M - количество мест в вашем доме, которое вы засорило носками, в идеале небольшое постоянное число.

Если вы выбрали необычную пару с разными левыми и правыми носками, то для полного сортировки ковша в левую и правую стопы возьмите O (N + M), где N - количество носков, а M - такое же, как указано выше. Кто-то еще может дать формулу для средних итераций для поиска первой пары, но наихудший случай для поиска пары со слепым поиском - N / 2 + 1, что становится астрономически маловероятным случаем для разумного N. Этого можно ускорить, используя расширенное изображение алгоритмов распознавания и эвристики при сканировании кучи несортированных носков с помощью Глазное яблоко Mk1 ,

Таким образом, алгоритм достижения эффективности спаривания носков O (1) (при условии симметричного носка) заключается в следующем:

  1. Вы должны оценить, сколько пар носков вам понадобится на всю оставшуюся жизнь, или, возможно, до тех пор, пока вы не уйдете на пенсию и не перейдете в более теплый климат, и вам больше не придется носить носки. Если вы молоды, вы также можете оценить, сколько времени потребуется, прежде чем мы все будем иметь сортировочные роботы в наших домах, и вся проблема станет неактуальной.

  2. Вам нужно узнать, как вы можете заказать свой выбранный носок оптом, и сколько это стоит, и они доставляют.

  3. Закажите носки!

  4. Избавьтесь от своих старых носков.

Альтернативный шаг 3 предполагает сравнение затрат на покупку одного и того же количества, возможно, более дешевых носков, по несколько пар за один раз за год и добавление стоимости сортировки носков, но, честное слово, покупка навалом дешевле! Кроме того, носки на складе растут в цене по курсу инфляции цен на акции, что больше, чем вы могли бы получить во многих инвестициях. Опять же, есть также стоимость хранения, но носки действительно не занимают много места на верхней полке шкафа.

Задача решена. Итак, просто получите новые носки, бросьте / пожертвуйте своих старых, и живите счастливо, когда узнаете, что вы каждый день сберегаете деньги и время на всю оставшуюся жизнь.


50



Теоретический предел - O (n), потому что вам нужно прикоснуться к каждому носку (если только некоторые из них уже не связаны как-то).

Вы можете достичь O (n) с помощью сортировка radix , Вам просто нужно выбрать некоторые атрибуты для ведер.

  1. Сначала вы можете выбрать (ее, мою) - разделить на две сваи,
  2. затем используйте цвета (может иметь любой порядок цветов, например, в алфавитном порядке по имени цвета) - разделить их на сваях по цвету (не забудьте сохранить начальный порядок с шага 1 для всех носков в той же куче),
  3. затем длина носка,
  4. затем текстуры, ....

Если вы можете выбрать ограниченное количество атрибутов, но достаточно атрибутов, которые могут однозначно идентифицировать каждую пару, вы должны быть сделаны в O (k * n), который является O (n), если мы можем считать k ограниченным.


47



As a practical solution:

  1. Quickly make piles of easily distinguishable socks. (Say by color)
  2. 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!)
  3. Stop sorting piles when they reached a threshold at which you are comfortable to find spot pairs and unpairable socks instantly

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

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

The initial bucket sorting will speed up your process, because it divides your n socks into k buckets in c*n time so than you will only have to do c*n*log(k) work. (Not taking into account the threshold). So all in all you do about n*c*(1 + log(k)) work, where c is the time to throw a sock on a pile.

This approach will be favourable compared to any c*x*n + O(1) method roughly as long as log(k) < x - 1.


In computer science this can be helpful: We have a collection of n things, 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 thing 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.

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.


31



This question is actually deeply philosophical. At heart it's about whether the power of people to solve problems (the "wetware" of our brains) is equivalent to what can be accomplished by algorithms.

An obvious algorithm for sock sorting is:

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

Now the computer science in this problem is all about the steps

  1. "if s pairs with a sock t in N". How quickly can we "remember" what we've seen so far?
  2. "remove t from N" and "add s to N". How expensive is keeping track of what we've seen so far?

Human beings will use various strategies to effect these. Human memory is associative, something like a hash table where feature sets of stored values are paired with the corresponding values themselves. For example, the concept of "red car" maps to all the red cars a person is capable of remembering. Someone with a perfect memory has a perfect mapping. Most people are imperfect in this regard (and most others). The associative map has a limited capacity. Mappings may bleep out of existence under various circumstances (one beer too many), be recorded in error ("I though her name was Betty, not Nettie"), or never be overwritten even though we observe that the truth has changed ("dad's car" evokes "orange Firebird" when we actually knew he'd traded that in for the red Camaro).

In the case of socks, perfect recall means looking at a sock s always produces the memory of its sibling t, including enough information (where it is on the ironing board) to locate t in constant time. A person with photographic memory accomplishes both 1 and 2 in constant time without fail.

Someone with less than perfect memory might use a few commonsense equivalence classes based on features within his capability to track: size (papa, mama, baby), color (greenish, redish, etc.), pattern (argyle, plain, etc.), style (footie, knee-high, etc.). So the ironing board would be divided into sections for the categories. This usually allows the category to be located in constant time by memory, but then a linear search through the category "bucket" is needed.

Someone with no memory or imagination at all (sorry) will just keep the socks in one pile and do a linear search of the whole pile.

A neat freak might use numeric labels for pairs as someone suggested. This opens the door to a total ordering, which allows the human to use exactly the same algorithms we might with a CPU: binary search, trees, hashes, etc.

So the "best" algorithm depends on the qualities of the wetware/hardware/software that is running it and our willingness to "cheat" by imposing a total order on pairs. Certainly a "best" meta-algorithm is to hire the worlds best sock-sorter: a person or machine that can aquire and quickly store a huge set N of sock attribute sets in a 1-1 associative memory with constant time lookup, insert, and delete. Both people and machines like this can be procured. If you have one, you can pair all the socks in O(N) time for N pairs, which is optimal. The total order tags allow you to use standard hashing to get the same result with either a human or hardware computer.


25



You are trying to solve the wrong problem.

Solution 1: Each time you put dirty socks in your laundry basket, tie them in a little knot. That way you will not have to do any sorting after the washing. Think of it like registering an index in a Mongo database. A little work ahead for some CPU savings in the future.

Solution 2: If it's winter, you don't have to wear matching socks. We are programmers. Nobody needs to know, as long as it works.

Solution 3: Spread the work. You want to perform such a complex CPU process asynchronously, without blocking the UI. Take that pile of socks and stuff them in a bag. Only look for a pair when you need it. That way the amount of work it takes is much less noticeable.

Hope this helps!


23



Here's an Omega(n log n) lower bound in comparison based model. (The only valid operation is comparing two socks.)

Suppose that you know that your 2n socks are arranged this way:

p1 p2 p3 ... pn pf(1) pf(2) ... pf(n)

where f is an unknown permutation of the set {1,2,...,n}. Knowing this cannot make the problem harder. There are n! possible outputs (matchings between first and second half), which means you need log(n!) = Omega(n log n) comparisons. This is obtainable by sorting.

Since you are interested in connections to element distinctness problem: proving the Omega(n log n) bound for element distinctness is harder, because the output is binary yes/no. Here, the output has to be a matching and the number of possible outputs suffices to get a decent bound. However, there's a variant connected to element distinctness. Suppose you are given 2n socks and wonder if they can be uniquely paired. You can get a reduction from ED by sending (a1, a2, ..., an) to (a1, a1, a2, a2, ..., an, an). (Parenthetically, the proof of hardness of ED is very interesting, via topology.)

I think that there should be an Omega(n2) bound for the original problem if you allow equality tests only. My intuition is: Consider a graph where you add an edge after a test, and argue that if the graph is not dense the output is not uniquely determined.


20