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

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

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

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 штук белого и m пакетов черного цвета. В повседневной жизни нет необходимости в других цветах.

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

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

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

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

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

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

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

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

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

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

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

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

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

Предполагая, что единственная операция для socks - это сравнение на равенство, этот алгоритм в основном по-прежнему является алгоритмом 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) с помощью радиальной сортировки. Вам просто нужно выбрать некоторые атрибуты для ведер.

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. Распространите работу. Вы хотите выполнить такой сложный процесс ЦП асинхронно, не блокируя пользовательский интерфейс. Возьми эту кучу носков и положи их в сумку. Ищите пару только тогда, когда она вам нужна. Таким образом, объем работы будет гораздо менее заметен.

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

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

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

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. "если s пары с носком t в 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 в следующей доступной позиции.

Делайте, пока A не станет пустым.

Для каждой строки 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). (В скобках доказательство твердости ED очень интересно, через топология.)

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

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

• Возьмите из кучи носок наугад.
• Для первого носка или если все ранее выбранные носки были парными, просто поместите носок в первый «слот» «массива» непарных носков перед собой.
• If you have one or more selected unpaired socks, check your current sock against all the unpaired socks in the array.
  • It is possible to separate socks into general classes or types (white/black, ankle/crew, athletic/dress) when building your array, and "drill-down" to only compare like-for-like.
  • Если вы найдете приемлемое совпадение, соедините оба носка и удалите их из массива.
  • Если вы этого не сделаете, поместите текущий носок в первый открытый слот в массиве.
• Повторите с каждым носком.

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

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

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

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

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

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

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

Машина

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

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

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

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

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

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

Алгоритм

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

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

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

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

В результате будет одна или две стопки: 1. "совпадают" и 2. "отсутствуют".

Эвристика:

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

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

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

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

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

Я делаю это:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Я обнаружил, что интеграция процесса сортировки в режим «развешивание для сушки» упрощает задачу. Мне все равно нужно подобрать каждый носок и повесить (переместить), и мне почти ничего не стоит повесить его в определенном месте на веревочках. Теперь, чтобы не принудительно перебирать весь буфер (строки), я предпочитаю размещать носки по цвету / оттенку. Более темный левый, более яркий правый, более красочный фронт и т. Д. Теперь, прежде чем вешать каждый носок, я смотрю в его «правую часть», есть ли уже подходящий - это ограничивает «сканирование» до 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) по времени, требует немного больше работы, чем простые подвесные ткани, и позволяет сразу получить доступ к полной пара носков даже в очень плохое утро понедельника ... ;-)

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

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

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

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

1. Выложите все носки на стол (1) и создайте хэш-карту {шаблон: позиция} (ε)
2. While there are remaining socks (n/2):
   1. Pick up one random sock (1)
   2. Найдите положение соответствующего носка (ε)
   3. Извлеките носок (1) и сохраните пару.

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

1. Все носки бросить на стол (1)
2. While there are remaining socks (n/2):
   1. Pick up one random sock (1)
   2. while it is not paired (1/P):
      1. Find sock with similar pattern
      2. Возьмите носок и сравните оба (1)
      3. Если все в порядке, сохраните пару

Теперь это зависит от нашей способности находить подходящие пары. Это особенно актуально, если у вас темно-серые пары или белые спортивные носки, которые часто имеют очень похожий узор! Допустим, у вас есть вероятность P найти соответствующий носок. В среднем вам понадобится 1 / P попыток, прежде чем найти соответствующий носок, чтобы сформировать пару. Общая сложность составляет 1 + (n / 2) * (1 + 1 / P) = O (n).

Оба варианта линейны по количеству носков и являются очень похожими решениями. Давайте немного изменим задачу и допустим, что у вас есть несколько пар одинаковых носков в наборе, и что легко сохранить несколько пар носков за один ход (1 + ε ). Для K различных шаблонов вы можете реализовать:

1. For each sock (n):
   1. Pick up one random sock (1)
   2. Поместите его в кластер своего шаблона
2. For each cluster (K):
   1. Take cluster and store pairs of socks (1+ε)

Общая сложность становится n + K = O (n). Он по-прежнему линейный, но выбор правильного алгоритма теперь может сильно зависеть от значений P и K! Но можно еще раз возразить, что у вас могут возникнуть трудности с поиском (или созданием) кластера для каждого носка.

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

На пути к эффективному алгоритму соединения носков из стопки

Предварительные условия

1. В стопке должен быть хотя бы один носок
2. Стол должен быть достаточно большим, чтобы вместить N / 2 носков (худший случай), где N - общее количество носков.

Алгоритм

Пытаться:

1. Выбери первый носок
2. Положи это на стол
3. Выберите следующий носок и посмотрите на него (может возникнуть исключение «нет больше носков в стопке»)
4. Теперь просканируйте носки на столе (выдает исключение, если на столе не осталось носков)
5. Есть ли совпадение? a) yes = ›удалите соответствующий носок из таблицы b) no =› положите носок на стол (может возникнуть исключение «таблица недостаточно велика»)

Кроме:

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

• На столе не осталось носков:
  бросок (последний неспаренный носок)

• В куче не осталось носков:
  выйдите из прачечной.

Наконец-то:

• Если в стопке еще остались носки:
  goto 3

Известные проблемы

Алгоритм войдет в бесконечный цикл, если вокруг нет стола или на нем недостаточно места для размещения хотя бы одного носка.

Возможное улучшение

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

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

Отсортируйте носки на столе по указанному признаку. Назовем этот атрибут «цвет». Расположите носки в ряд и поместите носки более темного цвета справа (например, .push_back ()) и носки более светлого цвета слева (например, .push_front ()).

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

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

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

PoC в соответствии с рекомендациями MCVE:

#include <iostream>
#include <vector>
#include <string>
#include <time.h>

using namespace std;

struct pileOfsocks {
    pileOfsocks(int pairCount = 42) :
        elemCount(pairCount<<1) {
        srand(time(NULL));
        socks.resize(elemCount);

        vector<int> used_colors;
        vector<int> used_indices;

        auto getOne = [](vector<int>& v, int c) {
            int r;
            do {
                r = rand() % c;
            } while (find(v.begin(), v.end(), r) != v.end());
            v.push_back(r);
            return r;
        };

        for (auto i = 0; i < pairCount; i++) {
            auto sock_color = getOne(used_colors, INT_MAX);
            socks[getOne(used_indices, elemCount)] = sock_color;
            socks[getOne(used_indices, elemCount)] = sock_color;
        }
    }

    void show(const string& prompt) {
        cout << prompt << ":" << endl;
        for (auto i = 0; i < socks.size(); i++){
            cout << socks[i] << " ";
        }
        cout << endl;
    }

    void pair() {
        for (auto i = 0; i < socks.size(); i++) {
            std::vector<int>::iterator it = find(unpaired_socks.begin(), unpaired_socks.end(), socks[i]);
            if (it != unpaired_socks.end()) {
                unpaired_socks.erase(it);
                paired_socks.push_back(socks[i]);
                paired_socks.push_back(socks[i]);
            }
            else
                unpaired_socks.push_back(socks[i]);
        }

        socks = paired_socks;
        paired_socks.clear();
    }

private:
    int elemCount;
    vector<int> socks;
    vector<int> unpaired_socks;
    vector<int> paired_socks;
};

int main() {
    pileOfsocks socks;

    socks.show("unpaired socks");
    socks.pair();
    socks.show("paired socks");

    system("pause");
    return 0;
}

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

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

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

At time i:

Blue  read  Pile[i]    : If Blue  then Blue.Count++  ; B=TRUE  ; sync

Red   read  Pile[i+1]  : If Red   then Red.Count++   ; R=TRUE  ; sync

Green read  Pile [i+2] : If Green then Green.Count++ ; G=TRUE  ; sync

С процессом синхронизации:

Sync i:

i++

If R is TRUE:
    i++
    If G is TRUE:
        i++

Для этого требуется инициализация:

Init:

If Pile[0] != Blue:
    If      Pile[0] = Red   : Red.Count++
    Else if Pile[0] = Green : Green.Count++

If Pile[1] != Red:
    If Pile[0] = Green : Green.Count++

Где

Best Case: B, R, G, B, R, G, .., B, R, G

Worst Case: B, B, B, .., B

Time(Worst-Case) = C * n ~ O(n)

Time(Best-Case) = C * (n/k) ~ O(n/k)

n: number of sock pairs
k: number of colors
C: sync overhead

Две линии мышления: скорость, необходимая для поиска любого совпадения, по сравнению со скоростью, необходимой для поиска всех совпадений, по сравнению с хранилищем.

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

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

//test.cu
#include <thrust/device_vector.h>
#include <thrust/sequence.h>
#include <thrust/copy.h>
#include <thrust/count.h>
#include <thrust/remove.h>
#include <thrust/random.h>
#include <iostream>
#include <iterator>
#include <string>

// Define some types for pseudo code readability
typedef thrust::device_vector<int> GpuList;
typedef GpuList::iterator          GpuListIterator;

template <typename T>
struct ColoredSockQuery : public thrust::unary_function<T,bool>
{
    ColoredSockQuery( int colorToSearch )
    { SockColor = colorToSearch; }

    int SockColor;

    __host__ __device__
    bool operator()(T x)
    {
        return x == SockColor;
    }
};


struct GenerateRandomSockColor
{
    float lowBounds, highBounds;

    __host__ __device__
    GenerateRandomSockColor(int _a= 0, int _b= 1) : lowBounds(_a), highBounds(_b) {};

    __host__ __device__
    int operator()(const unsigned int n) const
    {
        thrust::default_random_engine rng;
        thrust::uniform_real_distribution<float> dist(lowBounds, highBounds);
        rng.discard(n);
        return dist(rng);
    }
};

template <typename GpuListIterator>
void PrintSocks(const std::string& name, GpuListIterator first, GpuListIterator last)
{
    typedef typename std::iterator_traits<GpuListIterator>::value_type T;

    std::cout << name << ": ";
    thrust::copy(first, last, std::ostream_iterator<T>(std::cout, " "));
    std::cout << "\n";
}

int main()
{
    int numberOfSocks = 10000000;
    GpuList socks(numberOfSocks);
    thrust::transform(thrust::make_counting_iterator(0),
                      thrust::make_counting_iterator(numberOfSocks),
                      socks.begin(),
                      GenerateRandomSockColor(0, 200));

    clock_t start = clock();

    GpuList sortedSocks(socks.size());
    GpuListIterator lastSortedSock = thrust::copy_if(socks.begin(),
                                                     socks.end(),
                                                     sortedSocks.begin(),
                                                     ColoredSockQuery<int>(2));
    clock_t stop = clock();

    PrintSocks("Sorted Socks: ", sortedSocks.begin(), lastSortedSock);

    double elapsed = (double)(stop - start) * 1000.0 / CLOCKS_PER_SEC;
    std::cout << "Time elapsed in ms: " << elapsed << "\n";

    return 0;
}

    //nvcc -std=c++11 -o test test.cu

Время работы для 10 миллионов носков: 9 мс

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

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

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

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

2. Возьмите одну из стопки носков.

3. Теперь положите носки на пол по очереди, следуя приведенному ниже правилу.

   • Определите, что это ваши носки, и посмотрите на соответствующую секцию на полу.

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

   • Поместите его в соответствующий раздел.

4. Повторяйте 3, пока все носки не снимутся со стопки.

Хеширование и абстракция

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

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

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

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

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

Как определить наш хеш-ключ?

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

Допустим, любой носок можно однозначно идентифицировать по

Attribute[Gender] + Attribute[Colour] + Attribute[Material] + Attribute[Type1] + Attribute[Type2] + Attribute[Left_or_Right]

Это наша первая хеш-функция. Давайте использовать короткие обозначения для этого h1(G_C_M_T1_T2_LR). h1 (x) - это не наш ключ местоположения.

Другой хеш-функцией, исключающей атрибут Left_or_Right, будет h2(G_C_M_T1_T2). Вторая функция h2 (x) - это ключ нашего местоположения! (для пространства на полу позади вас).

• Чтобы найти слот, используйте h2 (G_C_M_T1_T2).
• Как только слот будет найден, используйте h1 (x), чтобы проверить их хэши. Если они не совпадают, у вас есть пара. Иначе бросьте носок в тот же слот.

ПРИМЕЧАНИЕ. Поскольку мы удаляем пару, как только находим ее, можно с уверенностью предположить, что будет только один слот с уникальным значением h2 (x) или h1 (x).

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

Почему так важно класть носки на пол

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

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

Почему важно снимать пару с пола?

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

Анализ

1. Case 1: Worst case when Derpina cannot remember or spot the socks on the floor directly using the hashing technique. Derp does a linear search through the items on the floor. This is not worse than the iterating through the pile to find the pair.
   • Upper bound for comparison: O(n^2).
   • Нижняя граница для сравнения: (n / 2). (когда каждый второй носок, который подбирает Дерпина, оказывается парой предыдущего).
2. Case 2: Derp remembers each the location of every sock that he placed on the floor and each sock has exactly one pair.
   • Upper bound for comparison: O(n/2).
   • Нижняя граница для сравнения: O (n / 2).

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

Ускорение работы

Чтобы получить высший балл, чтобы Дерп получил O (n / 2) сравнений, я бы порекомендовал Дерпину,

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

Это эквивалентно проблеме отличимости элементов?

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

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

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