Ответ 1

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

Значит хеширование достаточно (и быстрее).

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

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

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

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

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

Update:

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

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

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

• Подберите один из стека 2n-5.

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

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

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 7

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

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

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

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

Ответ 8

Как практическое решение:

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

Если у вас 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). Теперь мы использовали нашу дополнительную информацию и можем всячески сортировать каждый класс. Преимущество в том, что наборы данных уже значительно меньше.

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

Ответ 9

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

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

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

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

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

Ответ 10

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

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

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

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

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

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

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

Кто-то с менее совершенной памятью может использовать несколько классов эквивалентности эквивалентности, основанных на особенностях его способности отслеживать: размер (папа, мама, ребенок), цвет (зеленоватый, красноватый и т.д.), узор (аргил, и т.д.), стиль (footie, knee-high и т.д.). Таким образом, гладильная доска будет разделена на разделы для категорий. Обычно это позволяет размещать категорию по постоянному времени по памяти, но тогда необходим линейный поиск по категории "ведро".

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

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

Таким образом, "лучший" алгоритм зависит от качества используемого wetware/hardware/программного обеспечения и нашей готовности "обманывать", накладывая общий порядок на пары. Разумеется, "лучший" мета-алгоритм - нанять лучшего в мире сортировщика-носка: человека или машины, которые могут приобретать и быстро хранить огромный набор наборов атрибутов Nock в 1-1 ассоциативной памяти с постоянным поиском времени, вставкой, и удалить. Можно приобрести как людей, так и машины. Если он у вас есть, вы можете соединить все носки в O (N) время для N пар, что является оптимальным. Общие тэги заказов позволяют использовать стандартное хеширование, чтобы получить тот же результат с помощью человеческого или аппаратного компьютера.

Ответ 11

Стоимость: Перемещение носков → высокий, поиск/поиск носков в строке → маленький

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

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

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

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

Сделайте до тех пор, пока не будет пусто.

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

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

• Поместите в соответствующую законченную линию носков.

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

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

Сделайте до тех пор, пока не будут пустыми и X, и Y.

Готово

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

Ответ 12

Здесь нижняя граница Omega (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), связанная с отличием элемента, сложнее, потому что вывод двоичный yes/no. Здесь результат должен быть совпадением, а количество возможных выходов достаточно для получения приличной привязки. Однако существует вариант, связанный с отличием элемента. Предположим, вам даны 2n носки и интересно, могут ли они быть однозначно спарены. Вы можете получить сокращение от ED, отправив (a ₁, a ₂,..., a _n) в (a ₁, ₁, a ₂, a ₂,..., a _n, а <суб > псуб > ). (В сущности, доказательство твердости ED очень интересно, через топологию.)

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

Ответ 13

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

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

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

Ответ 14

Реальный мир:

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

Ответ 15

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

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

Ответ 16

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

Ответ 17

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

Ответ 18

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

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

Результат будет иметь одну или две сваи: 1. "согласован" и 2. "отсутствует"

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

• Найдите наиболее отличительный носок.
• Найти его соответствие.
• Если нет совпадения, поместите его в "пропавшую" кучу.
• Повторяйте с 1. до тех пор, пока нет более отличительных носков.
• Если есть меньше шести носков, перейдите к 11.
• Сопрячь все следы с соседом (не упаковывайте его).
• Найдите все согласованные пары, упакуйте их и переместите упакованные пары в "сопоставленную" кучу;  Если новых совпадений не было - инкремент "index" на 1
• Если "индекс" больше, чем 2 (это может быть значение зависит от носка  потому что с большим количеством носков меньше шансов пара их вслепую) перейти к 11
• Перемешать остальные
• Перейдите к 1
• Забудьте "index"
• Выберите носок
• Найти свою пару
• Если для носка нет пары, переместите ее в "пропавшую" кучу
• Если совпадение найдено в паре, пакуйте пару и переместите ее в "согласованную" кучу
• Если есть еще несколько носков, перейдите к 12
• Если есть только один левый, перейдите к 14
• Улыбка удовлетворена:)

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

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

Ответ 19

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

Машина

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

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

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

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

• логические и арифметические операции
• экологические чтения
• изменения окружающей среды

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

Алгоритм

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

• Разложите все носки в кучу над полом.
• Найдите пару, глядя на носки на полу.
• Повторяйте с 2 до тех пор, пока не будет создана пара.
• Повторяйте с 1 до тех пор, пока на полу не будет носков.

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

Анализ

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

Для следующего анализа времени спаривания парных носков n мы предполагаем, что после шага 1 не будет скрыта половина носков 2n. Таким образом, в среднем случае мы можем найти пары 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 носка к одной и той же паре, требуется определенное количество логических и арифметических операций. Это может быть невыполнимо в каждом сценарии.

Ответ 20

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

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

Я делаю это:

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

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

Сначала вытаскивая отличительные носки, вы оставляете пространство для "увеличения" функций, которые менее характерны для начала.

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

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

Ответ 21

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

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

Ответ 22

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

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

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

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

Существуют две физические возможности:

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

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

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

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

Ответ 23

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

Если мы предполагаем нормальное распределение, то оценочное число "вставок", имеющих по крайней мере один носок, сопоставленный с одним ведром, равно NlogN (т.е. все ковши заполнены)

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

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

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

Ответ 24

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

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

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

Такие предварительные усилия были замечены много раз в очень популярном и эффективном коде. Примеры включают # ОПРЕДЕЛЕНИЕ pi к нескольким десятичным знакам (существуют другие примеры, но тот, который приходит на ум прямо сейчас).

Ответ 25

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

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

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

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

Ответ 26

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

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

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

Ответ 27

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

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

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

Ответ 28

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

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

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

Oracle Machine лучше, -)

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

У него почти O(n)!

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

Ответ 29

Как сделать предварительную обработку? Я бы прошивал отметку или номер идентификатора в каждом носке таким образом, чтобы каждая пара имела одинаковый номер метки/идентификатора. Этот процесс может быть сделан каждый раз, когда вы покупаете новую пару носков. Затем вы можете сделать сортировку radix, чтобы получить общую стоимость O (n). Найдите место для каждого знака/идентификационного номера и просто выберите все носки один за другим и поместите их в нужное место.

Ответ 30

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