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

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

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

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

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

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

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

Решения для сортировки были предложены, но сортировка - это слишком много : нам не нужен порядок; нам просто нужны группы равенства .

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

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

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

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

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

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

Обновить:

А как насчет параллелизма ? Могут ли несколько человек подобрать носки быстрее?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Заказать носки!

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

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

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

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

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

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

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

В качестве практического решения:

1. Быстро сделайте груды легко различимых носков. (Скажем по цвету)
2. Быстрая сортировка каждой кучи и использование длины носка для сравнения. Как человек, вы можете довольно быстро принять решение, какой носок использовать для разбиения, чтобы избежать наихудшего случая. (Вы можете видеть несколько носков параллельно, используйте это в ваших интересах!)
3. Прекратите сортировку свай, когда они достигнут порога, при котором вам удобно мгновенно находить спот пары и негодные носки

Если у вас 1000 носков, с 8 цветами и средним распределением, вы можете сделать 4 стопки из каждых 125 носков за c * n время. С порогом в 5 носков вы можете сортировать каждую кучу за 6 прогонов. (Считая 2 секунды, чтобы бросить носок в нужную кучу, вам понадобится чуть меньше 4 часов.)

Если у вас всего 60 носков, 3 цвета и 2 вида носков (ваши / вашей жены), вы можете отсортировать каждую стопку из 10 носков за 1 прогон (снова порог = 5). (Подсчет 2 секунд займет у вас 2 минуты).

Первоначальная сортировка сегментов ускорит ваш процесс, потому что он делит ваши n носков на k сегментов во c*nвремени, так что вам остается только выполнять c*n*log(k)работу. (Без учета порога). Так что в целом вы делаетеn*c*(1 + log(k)) работе, где c - это время, чтобы бросить носок в кучу.

Этот подход будет выгодным по сравнению с любым c*x*n + O(1)методом примерно столько же, сколько и log(k) < x - 1.

В информатике это может быть полезно: у нас есть коллекция из n вещей , порядок их (длина), а также отношение эквивалентности (дополнительная информация, например, цвет носков). Отношение эквивалентности позволяет нам сделать разбиение исходной коллекции, и в каждом классе эквивалентности наш порядок все еще сохраняется. Сопоставление вещи с ее классом эквивалентности может быть выполнено в O (1), поэтому для присвоения каждого элемента классу требуется только O (n). Теперь мы использовали нашу дополнительную информацию и можем сортировать каждый класс любым способом. Преимущество состоит в том, что наборы данных уже значительно меньше.

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

Вы пытаетесь решить не ту проблему.

Решение 1. Каждый раз, когда вы кладете грязные носки в корзину для белья, завязывайте их в маленький узел. Таким образом, вам не придется делать какую-либо сортировку после стирки. Думайте об этом как о регистрации индекса в базе данных Mongo. Впереди немного работы для некоторой экономии процессора.

Решение 2: Если зима, вам не нужно носить соответствующие носки. Мы программисты. Никто не должен знать, пока это работает.

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

Надеюсь это поможет!

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

Очевидный алгоритм сортировки носков:

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

Теперь информатика в этой проблеме - все о шагах

1. msgstr "если пары с носком т в N". Как быстро мы можем «вспомнить», что мы видели до сих пор?
2. «удалить t из N» и «добавить s к N». Насколько дорого отслеживать то, что мы видели до сих пор?

Люди будут использовать различные стратегии для достижения этих целей. Человеческая память является ассоциативной , что-то вроде хеш-таблицы, в которой наборы функций сохраненных значений связаны с соответствующими значениями. Например, понятие «красная машина» отображает все красные машины, которые человек способен запомнить. У кого-то с прекрасной памятью есть прекрасное отображение. Большинство людей несовершенны в этом отношении (и большинство других). Ассоциативная карта имеет ограниченную емкость. Отображения могут петь не существовать при различных обстоятельствах (одно пиво слишком много), могут быть записаны по ошибке («хотя ее звали Бетти, а не Нетти») или никогда не будут перезаписаны, даже если мы увидим, что правда изменилась («машина отца») "вызывает" оранжевую Жар-птицу ", когда мы действительно знали, что он

В случае носков, идеальный отзыв означает, что взгляд на носок sвсегда производит память его брата t, включая достаточно информации (где она находится на гладильной доске), чтобы найти tв постоянном времени. Человек с фотографической памятью обязательно выполняет и 1, и 2 за постоянное время.

Кто-то с неидеальной памятью может использовать несколько классов эквивалентности здравого смысла, основанных на особенностях его способности отслеживать: размер (папа, мама, ребенок), цвет (зеленоватый, красноватый и т. Д.), Рисунок (аргайл, обычный и т. Д.) , стиль (футбол, по колено и т. д.). Так что гладильная доска будет разделена на разделы по категориям. Это обычно позволяет расположить категорию в постоянном времени по памяти, но тогда необходим линейный поиск по категории «сегмент».

Кто-то без памяти или воображения вообще (извините) просто хранит носки в одной стопке и выполняет линейный поиск всей стопки.

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

Таким образом, «лучший» алгоритм зависит от качества работающего на нем программного обеспечения / аппаратного / программного обеспечения, а также от нашей готовности «обманывать» путем наложения общего порядка на пары. Безусловно, «лучшим» мета- алгоритмом является найм лучшего в мире сортировщика носков: человека или машины, которые могут найти и быстро сохранить огромный набор N наборов атрибутов носка в ассоциативной памяти 1-1 с постоянным поиском по времени, вставкой, и удалить. И люди, и машины, подобные этой, могут быть закуплены. Если у вас есть, вы можете соединить все носки за O (N) времени для N пар, что является оптимальным. Теги общего заказа позволяют вам использовать стандартное хеширование, чтобы получить тот же результат на человеческом или аппаратном компьютере.

Стоимость: перемещение носков -> высокая, поиск / поиск носков в ряд -> маленькая

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

X = Ваш, Y = Ваши супруги

Из кучи А всех носков:

Выберите два носка, поместите соответствующий носок X в линию X, и носок Y в линию Y в следующую доступную позицию.

Делай, пока А не опустеет.

Для каждой строки X и Y

1. Выберите первый носок в строке, ищите вдоль линии, пока не найдете соответствующий носок.

2. Положите в соответствующую готовую линию носки.

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

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

Делайте, пока X и Y не опустеют.

Выполнено

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

Вот нижняя граница Омега (n log n) в модели, основанной на сравнении. (Единственная допустимая операция - сравнение двух носков.)

Предположим, вы знаете, что ваши 2n носки расположены следующим образом:

p ₁ p ₂ p ₃ ... p _n p _{f (1)} p _{f (2)} ... p _{f (n)}

где f - неизвестная перестановка множества {1,2, ..., n}. Знание этого не может усложнить проблему. Нет! возможные результаты (совпадения между первой и второй половиной), что означает, что вам нужно сравнение log (n!) = Omega (n log n). Это можно получить путем сортировки.

Поскольку вас интересуют связи с проблемой отличимости элементов: доказать, что Omega (n log n) ограничен для отличимости элементов, сложнее, потому что выходные данные являются двоичными да / нет. Здесь выходные данные должны совпадать, а количество возможных выходных сигналов достаточно для получения достойной границы. Тем не менее, есть вариант, связанный с различимостью элементов. Предположим, вы получили 2n носков и задаетесь вопросом, могут ли они быть уникально спарены. Вы можете получить сокращение от ED, отправив (a ₁ , a ₂ , ..., a _n ) в (a ₁ , a ₁ , a ₂ , a ₂ , ..., a _n , a _n ). (В скобках доказательство твердости ЭД очень интересно через топологию.)

Я думаю, что для исходной задачи должна быть оценка Omega (n ² ), если вы разрешаете только тесты на равенство. Моя интуиция такова: рассмотрите график, в который вы добавляете ребро после теста, и утверждайте, что если график не плотный, выходной результат не определяется однозначно.

Вот как я на самом деле это делаю для p пар носков ( n = 2p отдельных носков):

• Возьмите носок наугад из кучи.
• Для первого носка или, если все ранее выбранные носки были спарены, просто поместите носок в первый «слот» «массива» непарных носков перед вами.
• Если у вас есть один или несколько выбранных непарных носков, проверьте текущий носок на наличие всех непарных носков в массиве.
  • Можно разделить носки на общие классы или типы (белый / черный, лодыжка / бригада, спортивная одежда / платье) при построении массива и «детализация», чтобы сравнить только одно и то же.
  • Если вы найдете приемлемое совпадение, соедините оба носка и удалите их из массива.
  • Если вы этого не сделаете, поместите текущий носок в первый открытый слот в массиве.
• Повторите с каждым носком.

Наихудший сценарий этой схемы состоит в том, что каждая пара носков достаточно различна, что должно точно соответствовать ей, и что первые выбранные вами носки n / 2 различны. Это ваш сценарий O (n ² ), и он крайне маловероятен. Если число уникальных типов носков t меньше, чем количество пар p = n / 2 , и носки в каждом типе достаточно похожи (обычно в терминах износа), то любой носок этого типа можно соединить с любым В остальном, как я и предполагал выше, максимальное количество носков, с которыми вам когда-либо придется сравнивать, - это t , после чего следующий, который вы потянете, будетсопоставьте один из непарных носков. Этот сценарий гораздо более вероятен в среднем ящике с носками, чем в худшем случае, и снижает сложность в худшем случае до O (n * t), где обычно t << n .

Реальный подход:

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

После того, как все носки сложены в кучу, быстро пройдите через несколько носков, создавая пары и удаляя их (они направляются к ящику). Если в куче есть несоответствующие носки, соберите их в лучшую (в пределах максимально возможного ограничения) кучу. Когда все кучи с несколькими носками были обработаны, сопоставьте оставшиеся пригодные для носки носки, которые не были спарены из-за ошибок типа II. Ух ты, все готово - и у меня много носков, и я не стираю их, пока большая часть не станет грязной. Еще одно практическое замечание: я переворачиваю верх одной из пары носков поверх другой, используя их упругие свойства, чтобы они оставались вместе при транспортировке в ящик и в ящике.

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

Ответы до сих пор не используют наши возможности распознавания образов человека. Игра Set дает ключ к пониманию того, как сделать это хорошо: поместите все носки в двухмерное пространство, чтобы вы могли хорошо их распознать и легко достать до них руками. Это ограничивает вас площадью около 120 * 80 см или около того. Оттуда выберите пары, которые вы узнаете, и удалите их. Положите дополнительные носки в свободное место и повторите. Если вы стираете для людей с легко узнаваемыми носками (на ум приходят маленькие дети), вы можете сделать радикальную сортировку, сначала выбрав эти носки. Этот алгоритм хорошо работает только тогда, когда количество одиночных носков мало

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

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

Машина

Машина - это абстракция элемента реального мира, называемого человеком. Он способен читать из окружающей среды через пару глаз. И наша модель машины способна манипулировать окружающей средой, используя 2 руки. Логические и арифметические операции рассчитываются с использованием нашего мозга (надеюсь ;-)).

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

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

Таким образом, в зависимости от предыдущего анализа следующие операции должны использоваться в порядке убывания:

• логические и арифметические операции
• экологические чтения
• экологические изменения

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

Алгоритм

Итак, вот мое предложение:

1. Расстелите все носки в куче по полу.
2. Найдите пару, посмотрев на носки на полу.
3. Повторяйте от 2 до тех пор, пока не получится ни одна пара
4. Повторите с 1 до тех пор, пока на полу нет носков.

Операция 4 необходима, потому что при расправлении носков по полу некоторые носки могут скрывать другие. Вот анализ алгоритма:

Анализ

Алгоритм заканчивается с большой вероятностью. Это связано с тем, что на шаге № 2 невозможно найти пары носков.

Для следующего анализа времени выполнения пар nпар носков мы предполагаем, что по крайней мере половина 2nносков не скрыта после шага 1. Так что в среднем случае мы можем найти n/2пары. Это означает, что цикл 4 этапа выполняется O(log n)раз. Шаг 2 выполняется O(n^2)раз. Итак, мы можем сделать вывод:

• Алгоритм включает в себя O(ln n + n)модификации среды (шаг 1 O(ln n)плюс сбор каждой пары носков с пола)
• Алгоритм включает в себя O(n^2)считывание окружения с шага 2
• Алгоритм включает в себя O(n^2)логические и арифметические операции для сравнения носка с другим на шаге 2

Таким образом, мы имеем общую сложность во время выполнения, O(r*n^2 + w*(ln n + n))где rи wявляются факторами для операций чтения среды и записи среды соответственно для разумного количества носков. Стоимость логических и арифметических операций опущена, потому что мы предполагаем, что требуется постоянное количество логических и арифметических операций, чтобы решить, принадлежат ли 2 носка к одной паре. Это может быть неосуществимо в каждом сценарии.

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

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

Предварительные условия: нет гарантии, что носки одинаковые. Если они одного цвета, это не значит, что они имеют одинаковый размер или рисунок. Носки в случайном порядке. Там может быть нечетное количество носков (некоторые отсутствуют, мы не знаем, сколько). Подготовьтесь запомнить переменную «index» и установите ее в 0.

Результат будет иметь одну или две стопки: 1. «совпадает» и 2. «отсутствует»

Эвристический:

1. Найдите самый характерный носок.
2. Найди свой матч.
3. Если совпадения нет, положите его на «пропущенную» кучу.
4. Повторите с 1. до тех пор, пока не останется больше отличительных носков.
5. Если носков меньше 6, переходите к 11.
6. Соедините вслепую все носки с соседом (не упаковывайте его)
7. Найдите все подходящие пары, соберите их и переместите упакованные пары в «согласованную» кучу; Если новых совпадений не было - увеличьте «index» на 1
8. Если «index» больше 2 (это может быть значение, зависящее от номера носка, потому что при большем количестве носков меньше шансов соединить их вслепую) переходите к 11
9. Перемешать остальное
10. Перейти к 1
11. Забудьте "индекс"
12. Выбрать носок
13. Найди свою пару
14. Если для носка нет пары, переместите его в «пропавшую» кучу
15. Если совпадение найдено в паре, упакуйте пару и переместите его в «подходящую» кучу
16. Если есть еще несколько носков, переходите к 12
17. Если осталось только одно, перейдите к 14
18. Улыбка устраивает :)

Также может быть добавлена ​​проверка на наличие поврежденных носков, как будто их удаление. Его можно вставить между 2 и 3 и между 13 и 14.

Я с нетерпением жду, чтобы услышать о любых событиях или исправлениях.

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

Почти все другие алгоритмы (включая самый лучший ответ от usr ) сортируют, а затем удаляют пары. Я считаю, что, как человек, лучше минимизировать количество носков, рассматриваемых одновременно.

Я делаю это путем:

1. Выбор отличительного носка (все, что бросается в глаза первым в куче).
2. Начинаем сортировку по кругу с этого концептуального места, вытягивая носки из кучи, основываясь на сходстве с этим.
3. Поместите новый носок рядом с текущей кучкой, с расстоянием, основанным на том, насколько он отличается. Если вы обнаружите, что надеваете носок поверх другого, потому что он идентичен, сформируйте там пару и удалите их. Это означает, что будущие сравнения потребуют меньше усилий, чтобы найти правильное место.

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

Сначала потянув за характерные носки, вы оставляете место для «увеличения» возможностей, которые менее характерны, для начала.

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

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

Всякий раз, когда вы берете носок, положите его в одном месте. Затем следующий носок, который вы берете, если он не соответствует первому носку, установите его рядом с первым. Если это так, есть пара. Таким образом, на самом деле не имеет значения, сколько комбинаций существует, и есть только две возможности для каждого подобранного носка - либо у него есть совпадение, которое уже есть в вашем массиве носков, либо нет, что означает, что вы добавить его в место в массиве.

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

Рассмотрим хэш-таблицу размера «N».

Если мы предполагаем нормальное распределение, то предполагаемое количество «вставок», чтобы хотя бы один носок был сопоставлен с одним сегментом, равно NlogN (т. Е. Все сегменты заполнены).

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

Пусть 'N' соответствует приблизительной верхней границе количества имеющихся у вас уникальных цветов / рисунка носков.

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

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

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

Это решает любую вычислительную проблему сопряжения, удаляя ее со слоем абстракции.

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

Есть две физические возможности:

Для «парного» объекта, который держит указатель на каждый носок, у нас может быть тканевый мешок, который мы используем, чтобы держать носки вместе. Это похоже на огромные накладные расходы.

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

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

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

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

Я обнаружил, что интеграция процесса сортировки в подвешивание к сушке делает его легким. В любом случае мне нужно подобрать каждый носок и повесить его (переместить), и мне ничего не стоит повесить его в определенном месте на веревочке. Теперь, чтобы не заставлять искать весь буфер (строки), я решил разместить носки по цвету / оттенку. Темнее влево, ярче вправо, более пестрый фронт и т. Д. Теперь, прежде чем повесить каждый носок, я смотрю в его «правильной окрестности», если уже есть соответствующий - это ограничивает «сканирование» до 2-3 других носков - и если это так Я вешаю другой прямо рядом с ним. Затем я скручиваю их попарно, снимая с струн, когда высыхаю.

Теперь это может показаться не таким уж и отличным от «формирования куч по цвету», предложенного верхними ответами, но, во-первых, не выбирая дискретные груды, а диапазоны, у меня нет проблем с классификацией, идет ли «фиолетовый» в «красную» или «синюю» кучу; это просто идет между. И затем при объединении двух операций («повесить, чтобы высушить» и «отсортировать») затраты на сортировку во время «подвешивания» составляют примерно 10% от того, что будет отдельной сортировкой.

Я только что закончил сопряжение своих носков и обнаружил, что лучший способ сделать это - это следующее:

• Выберите один из носков и уберите его (создайте «ведро» для этой пары)
• Если следующий является парой предыдущего, поместите его в существующее ведро, в противном случае создайте новое.

В худшем случае это означает, что у вас будет n / 2 разных сегментов, и у вас будет n-2 определения того, какой сегмент содержит пару текущего носка. Очевидно, что этот алгоритм хорошо работает, если у вас всего несколько пар; Я сделал это с 12 парами.

Это не так научно, но работает хорошо :)

Мое решение не совсем соответствует вашим требованиям, так как формально требует O(n)«лишнего» пространства. Однако, учитывая мои условия, это очень эффективно в моем практическом применении. Таким образом, я думаю, что это должно быть интересно.

Объединить с другой задачей

Особое условие в моем случае заключается в том, что я не пользуюсь сушильной машиной, а просто вешаю одежду на обычную сушилку для белья. Подвешивание тканей требует O(n)операций (кстати, я всегда рассматриваю здесь проблему упаковки бина ), а проблема по своей природе требует линейного «дополнительного» пространства. Когда я беру новый носок из ведра, я пытаюсь повесить его рядом с его парой, если пара уже повешена. Если это носок из новой пары, я оставляю немного места рядом с ним.

Oracle Machine лучше ;-)

Очевидно, что требуется дополнительная работа, чтобы проверить, есть ли уже где-нибудь подходящий носок, и это даст решение O(n^2)с коэффициентом 1/2для компьютера. Но в этом случае «человеческий фактор» на самом деле является преимуществом - я обычно могу очень быстро (почти O(1)) идентифицировать соответствующий носок, если он уже был подвешен (возможно, это связано с незаметным кэшированием в мозге) - считаю это своего рода ограниченный «оракул», как в Oracle Machine ;-) Мы, люди, в некоторых случаях имеем эти преимущества перед цифровыми машинами ;-)

Имейте это почти O(n)!

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

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

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

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

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

Наши две стадии предварительной обработки - это «положить носки на веревку для белья» и «снять носки с веревки для белья», что мы должны сделать, чтобы получить носки, которые не только чистые, но и сухие. Как и в случае со стиральными машинами, бельевые веревки ограничены, и я предполагаю, что у нас есть целая часть линии, где мы видим наши носки.

Вот алгоритм для 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 
 }
}

Не тратьте свое время на перемещение носков или поиск лучшего соответствия, все это должно быть сделано в O (n), который нам также понадобится для того, чтобы просто поставить их на несортированную линию. Носки еще не спарены, у нас есть только несколько кластеров сходства на линии. Полезно, чтобы у нас был ограниченный набор носков, поскольку это помогает нам создавать «хорошие» кластеры (например, если в наборе носков есть только черные носки, кластеризация по цветам не будет подходящим способом)

Вот алгоритм для 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
 }

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

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

Вот алгоритм для sort_remaining_clusters ():

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

После этого осталось всего несколько носков. Здесь я ввожу ранее непарные носки в систему и обрабатываю оставшиеся носки без какого-либо специального алгоритма - оставшихся носков очень мало и их можно обрабатывать визуально очень быстро.

Для всех оставшихся носков, я предполагаю, что их аналоги все еще не вымыты, и отложу их для следующей итерации. Если вы регистрируете рост непарных носков с течением времени («утечка носков»), вы должны проверить свою корзину - она ​​может быть рандомизирована (есть ли у вас кошки, которые там спят?)

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

О параллелизме: пока вы добавляете оба носка в одну корзину, вы можете легко распараллелить все эти шаги.

Я предпринял простые шаги, чтобы уменьшить мои усилия в процессе, требующем O (1) времени.

Сокращая мои затраты на один из двух типов носков (белые носки для отдыха, черные носки для работы), мне нужно только определить, какой из двух носков у меня в руке. (Технически, поскольку они никогда не моются вместе, я сократил время процесса до O (0).)

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

Такое искреннее усилие было много раз замечено в очень популярном и эффективном коде. Примеры включают в себя # DEFINE'ing до нескольких десятичных знаков (существуют другие примеры, но это тот, который приходит на ум прямо сейчас).

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

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

Теперь следующий вопрос - просто ли вы стираете самостоятельно, а ваша жена занимается стиркой? Это проблема, вероятно, в совершенно другой области проблем . :)