Pregunta Cómo emparejar calcetines de una pila de manera eficiente?


Ayer estaba emparejando los calcetines de la ropa limpia y descubrí que la forma en que lo estaba haciendo no es muy eficiente. Estaba haciendo una búsqueda ingenua, escogiendo un calcetín e "iterando" el montón para encontrar su pareja. Esto requiere iterar sobre n / 2 * n / 4 = n2/ 8 medias en promedio.

Como científico informático, ¿estaba pensando qué podría hacer? La clasificación (según tamaño / color / ...) por supuesto vino a la mente para lograr una solución O (NlogN).

Las soluciones hash u otras soluciones in situ no son una opción, porque no puedo duplicar mis calcetines (aunque podría ser bueno si pudiera).

Entonces, la pregunta es básicamente:

Dado un montón de n pares de calcetines, que contienen 2n elementos (suponiendo que cada calcetín tiene exactamente un par coincidente), ¿cuál es la mejor forma de emparejarlos de manera eficiente con un espacio extra logarítmico? (Creo que puedo recordar esa cantidad de información si es necesario).

Agradecería una respuesta que aborde los siguientes aspectos:

  • Un general teórico solución para una gran cantidad de calcetines.
  • La cantidad real de medias no es tan grande, no creo que mi pareja y yo tengamos más de 30 pares. (Y es bastante fácil distinguir entre mis calcetines y los de ella; ¿se puede usar también?)
  • Es equivalente a la problema de distinción de elementos?

3501
2018-01-19 15:34


origen


Respuestas:


Se han propuesto soluciones de clasificación, pero ordenar es un poco demasiado: No necesitamos orden; solo necesitamos grupos de igualdad.

Asi que hash sería suficiente (y más rápido).

  1. Para cada color de calcetines, formar una pila. Itera sobre todos los calcetines en su canasta de entrada y distribuirlos en las pilas de colores.
  2. Iteramos sobre cada pila y distribuirlo por alguna otra métrica (por ejemplo, patrón) en el segundo conjunto de pilas
  3. Aplicar recursivamente este esquema hasta que hayas distribuido todos los calcetines pilas muy pequeñas que puedes procesar visualmente de inmediato

Este tipo de partición hash recursiva en realidad está siendo realizada por servidor SQL cuando necesita combinar hash o hash en grandes conjuntos de datos. Distribuye su flujo de entrada de construcción en muchas particiones que son independientes. Este esquema escala a cantidades arbitrarias de datos y múltiples CPU linealmente.

No necesita particiones recursivas si puede encontrar una clave de distribución (tecla hash) que proporciona suficientes cubos que cada cubo sea lo suficientemente pequeño para ser procesado muy rápidamente. Desafortunadamente, no creo que los calcetines tengan esa propiedad.

Si cada calcetín tuviera un número entero llamado "PairID" uno podría distribuirlos fácilmente en 10 cubos de acuerdo con PairID % 10 (el último dígito).

La mejor partición en el mundo real en la que puedo pensar es crear un rectángulo de pilas: una dimensión es color, la otra es el patrón. ¿Por qué un rectángulo? Porque necesitamos O (1) acceso aleatorio a las pilas. (A 3D cuboides también funcionaría, pero eso no es muy práctico.)


Actualizar:

Qué pasa paralelismo? ¿Pueden varios humanos hacer coincidir los calcetines más rápido?

  1. La estrategia de paralelización más simple es hacer que varios trabajadores tomen de la canasta de entrada y coloquen los calcetines en las pilas. Esto solo aumenta mucho: imagina a 100 personas peleando por 10 montones. Los costos de sincronización (manifestándose como colisiones de manos y comunicación humana) destruir la eficiencia y la aceleración (ver el Ley de escalabilidad universal!). ¿Es esto propenso a puntos muertos? No, porque cada trabajador solo necesita acceder a un montón a la vez. Con solo un "candado" no puede haber un punto muerto. Livelocks podría ser posible dependiendo de cómo los humanos coordinan el acceso a las pilas. Podrían simplemente usar retroceso al azar como las tarjetas de red, hacen eso en un nivel físico para determinar qué tarjeta puede acceder exclusivamente al cable de la red. Si funciona para NICs, debería funcionar para los humanos también.
  2. Se escala casi indefinidamente si cada trabajador tiene su propio conjunto de pilas. Los trabajadores pueden tomar grandes trozos de calcetines de la canasta de entrada (muy poca contención ya que lo hacen con poca frecuencia) y no necesitan sincronizarse cuando distribuyen los calcetines (porque tienen montones locales). Al final, todos los trabajadores necesitan unir sus conjuntos de pilotes. Creo que se puede hacer en O (log (conteo de trabajadores * pilas por trabajador)) si los trabajadores forman un árbol de agregación.

Qué pasa con la problema de distinción de elementos? Como dice el artículo, el problema de distinción de elementos se puede resolver en O(N). Esto es lo mismo para el problema de los calcetines (también O(N), si solo necesita un paso de distribución (propuse varios pasos solo porque los humanos son malos en los cálculos; un paso es suficiente si distribuye en md5(color, length, pattern, ...), es decir, un hash perfecto de todos los atributos)).

Claramente, uno no puede ir más rápido que O(N), así que hemos llegado al límite inferior óptimo.

Aunque las salidas no son exactamente las mismas (en un caso, solo un booleano. En el otro caso, los pares de calcetines), las complejidades asintóticas son las mismas.


2176
2017-10-19 20:47



Como la arquitectura del cerebro humano es completamente diferente de una CPU moderna, esta pregunta no tiene sentido práctico.

Los seres humanos pueden ganar los algoritmos de CPU utilizando el hecho de que "encontrar un par coincidente" puede ser una operación para un conjunto que no es demasiado grande.

Mi algoritmo

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

Al menos esto es lo que estoy usando en la vida real, y lo encuentro muy eficiente. El inconveniente es que requiere una superficie plana, pero por lo general es abundante.


522
2018-05-27 19:13



Caso 1: Todos los calcetines son idénticos (esto es lo que hago en la vida real por cierto).

Elige a dos de ellos para hacer un par. Tiempo constante.

Caso 2: Hay un número constante de combinaciones (propiedad, color, tamaño, textura, etc.).

Utilizar clase de radix. Este es solo el tiempo lineal ya que no se requiere comparación.

Caso 3: El número de combinaciones no se conoce de antemano (caso general).

Tenemos que hacer una comparación para verificar si dos calcetines vienen en pareja. Elija uno de los O(n log n) algoritmos de clasificación basados ​​en la comparación.

Sin embargo, en la vida real, cuando el número de calcetines es relativamente pequeño (constante), estos algoritmos teóricamente óptimos no funcionarían bien. Puede llevar incluso más tiempo que la búsqueda secuencial, que teóricamente requiere tiempo cuadrático.


231



Respuesta no algorítmica, pero "eficiente" cuando lo hago:

  • paso 1) descarta todos tus calcetines existentes

  • paso 2) ve a Walmart y comprarlos por paquetes de 10 - n paquete de blanco y m paquetes de negro. No necesita otros colores en el día a día vida.

Sin embargo, en ocasiones, tengo que hacer esto otra vez (calcetines perdidos, medias dañadas, etc.), y odio tirar calcetines perfectamente buenos con demasiada frecuencia (y ¡ojalá siguieran vendiendo los mismos calcetines de referencia!), Así que recientemente tomé un enfoque diferente.

Respuesta algorítmica:

Considere que si dibuja solo un calcetín para la segunda pila de calcetines, como lo está haciendo, sus probabilidades de encontrar el calcetín coincidente en una búsqueda ingenua son bastante bajas.

  • Así que escoja cinco de ellos al azar y memorice su forma o su longitud.

¿Por que cinco? Por lo general, los humanos somos buenos recordando entre cinco y siete elementos diferentes en la memoria de trabajo, un poco como el equivalente humano de un RPN pila - cinco es un valor predeterminado seguro.

  • Recoge uno de la pila de 2n-5.

  • Ahora busque una coincidencia (coincidencia de patrones visuales - los humanos son buenos en eso con una pequeña pila) dentro de los cinco que dibujó, si no encuentra uno, luego agréguelo a sus cinco.

  • Mantenga los calcetines al azar de la pila y compárelos con los calcetines 5 + 1 para un partido. A medida que su stack crezca, reducirá su rendimiento pero aumentará sus probabilidades. Mucho mas rápido.

No dude en escribir la fórmula para calcular cuántas muestras debe dibujar para obtener un 50% de probabilidades de una coincidencia. IIRC es una ley hipergeométrica.

Hago eso todas las mañanas y rara vez necesito más de tres sorteos, pero tengo n pares similares (alrededor de 10, dar o tomar los perdidos) de m calcetines blancos en forma. Ahora puedes estimar el tamaño de mi pila de acciones :-)

Por cierto, Descubrí que la suma de los costos de transacción de clasificar todos los calcetines cada vez que necesitaba un par era mucho menor que hacerlo una sola vez y unir los calcetines. Un just-in-time funciona mejor porque entonces no tiene que atar los calcetines, y también hay un retorno marginal decreciente (es decir, sigue buscando esos dos o tres calcetines que cuando en algún lugar de la lavandería y que necesita) para terminar de hacer coincidir tus calcetines y pierdes tiempo con eso).


144



Lo que hago es levantar el primer calcetín y dejarlo (por ejemplo, en el borde del recipiente para lavar la ropa). Luego tomo otro calcetín y compruebo si es igual al primer calcetín. Si es así, los elimino a los dos. Si no es así, lo coloco al lado del primer calcetín. Luego tomo el tercer calcetín y lo comparo con los dos primeros (si todavía están allí). Etc.

Este enfoque se puede implementar con bastante facilidad en una matriz, suponiendo que "quitar" calcetines es una opción. En realidad, ni siquiera necesitas "quitar" los calcetines. Si no necesita ordenar los calcetines (ver a continuación), puede moverlos y terminar con una matriz que tiene todos los calcetines dispuestos en pares en la matriz.

Suponiendo que la única operación para calcetines es comparar por igualdad, este algoritmo es básicamente todavía un n2 Algoritmo, aunque no sé sobre el caso promedio (nunca aprendí a calcular eso).

La clasificación, por supuesto, mejora la eficiencia, especialmente en la vida real, donde puede "insertar" fácilmente un calcetín entre otros dos calcetines. En informática, un árbol puede lograr lo mismo, pero eso es espacio extra. Y, por supuesto, estamos de regreso en NlogN (o un poco más, si hay varios calcetines que son iguales según los criterios de clasificación, pero no del mismo par).

Aparte de eso, no puedo pensar en nada, pero este método parece ser bastante eficiente en la vida real. :)


92



Esto es hacer la pregunta incorrecta. La pregunta correcta es, ¿por qué gasto tiempo ordenando calcetines? ¿Cuánto cuesta anualmente, cuando valora su tiempo libre para X unidades monetarias de su elección?

Y la mayoría de las veces, esto no es solo alguna tiempo libre, es Mañana tiempo libre, que podría estar pasando en la cama, o bebiendo su café, o saliendo un poco temprano y no quedar atrapado en el tráfico.

A menudo es bueno dar un paso atrás y pensar una forma de resolver el problema.

¡Y hay una manera!

Encuentra un calcetín que te guste. Tenga en cuenta todas las características relevantes: color en diferentes condiciones de iluminación, calidad y durabilidad generales, comodidad en diferentes condiciones climáticas y absorción de olores. También es importante que no pierdan elasticidad en el almacenamiento, por lo que las telas naturales son buenas y deberían estar disponibles en una envoltura de plástico.

Es mejor si no hay diferencia entre los calcetines del pie izquierdo y derecho, pero no es crítico. Si los calcetines son simétricos entre la izquierda y la derecha, encontrar un par es O (1) operación, y ordenar los calcetines es O (M) operación aproximada, donde M es el número de lugares en su casa, que ha ensuciado con calcetines, idealmente algunos pequeño número constante.

Si eliges un par elegante con diferente calcetín izquierdo y derecho, haciendo una clasificación completa del cubo a los cubos izquierdo y derecho del pie, toma O (N + M), donde N es el número de calcetines y M es el mismo que el anterior. Alguien más puede dar la fórmula de iteraciones promedio para encontrar el primer par, pero el peor caso para encontrar un par con búsqueda ciega es N / 2 + 1, lo que se convierte en un caso astronómicamente improbable para N. razonable. Esto se puede acelerar utilizando una imagen avanzada algoritmos de reconocimiento y heurística, al escanear el montón de calcetines sin clasificar con Mk1 Eyeball.

Por lo tanto, un algoritmo para lograr la eficiencia de apareamiento de calcetines O (1) (asumiendo calcetín simétrico) es:

  1. Debe estimar cuántos pares de calcetines necesitará para el resto de su vida, o tal vez hasta que se retire y se mueva a climas más cálidos sin necesidad de usar calcetines nunca más. Si eres joven, también puedes calcular cuánto tiempo pasará antes de que todos tengamos robots de clasificación de calcetines en nuestros hogares, y todo el problema se vuelve irrelevante.

  2. Debe averiguar cómo puede pedir el calcetín seleccionado a granel, cuánto cuesta y entregan.

  3. Ordene los calcetines!

  4. Deshazte de tus viejos calcetines.

Un paso 3 alternativo implicaría comparar los costos de comprar la misma cantidad de calcetines quizás más baratos con algunos pares a la vez a lo largo de los años y agregar el costo de clasificar los calcetines, pero tome mi palabra: ¡comprar a granel es más barato! Además, los calcetines en almacenamiento aumentan en valor a la tasa de inflación de los precios de las acciones, que es más de lo que obtendría en muchas inversiones. Por otra parte, también hay un costo de almacenamiento, pero los calcetines no ocupan mucho espacio en el estante superior de un armario.

Problema resuelto. Por lo tanto, solo consigue calcetines nuevos, tira / dona tus viejos y vive feliz para siempre sabiendo que estás ahorrando dinero y tiempo todos los días para el resto de tu vida.


50



El límite teórico es O (n) porque necesita tocar cada calcetín (a menos que algunos ya estén emparejados de alguna manera).

Puedes lograr O (n) con clase de radix. Solo necesita elegir algunos atributos para los cubos.

  1. Primero puedes elegir (la suya, la mía) dividirlos en 2 montones,
  2. luego use colores (puede tener cualquier orden para los colores, por ejemplo, alfabéticamente por nombre de color) - divídalos en montones por color (recuerde mantener el orden inicial del paso 1 para todos los calcetines en el mismo montón),
  3. luego la longitud del calcetín,
  4. luego textura, ....

Si puede elegir un número limitado de atributos, pero suficientes atributos que puedan identificar de forma única cada par, debe hacerlo en O (k * n), que es O (n) si podemos considerar que k es limitado.


47



Como una solución práctica:

  1. Haga rápidamente montones de calcetines fácilmente distinguibles. (Decir por color)
  2. Coloca rápidamente cada montón y usa la longitud del calcetín para comparar. Como ser humano, puede tomar una decisión bastante rápida que utilizar para particionar y evitar el peor de los casos. (Puedes ver varios calcetines en paralelo, ¡utiliza eso para tu ventaja!)
  3. Deje de clasificar las pilas cuando alcanzan un umbral en el que se siente cómodo para encontrar pares de puntos y calcetines no deseables al instante

Si tiene 1000 calcetines, con 8 colores y una distribución promedio, puede hacer 4 pilas de 125 calcetines en c * n de tiempo. Con un umbral de 5 calcetines, puedes ordenar cada montón en 6 carreras. (Contar 2 segundos para tirar un calcetín en el montón correcto le tomará poco menos de 4 horas).

Si solo tienes 60 calcetines, 3 colores y 2 tipos de calcetines (el tuyo o el de tu esposa) puedes clasificar cada pila de 10 calcetines en 1 carrera (Umbral de nuevo = 5). (Contar 2 segundos le tomará 2 minutos).

La clasificación inicial de los depósitos acelerará su proceso, ya que divide sus n calcetines en k cubetas en c*n tiempo, así que solo tendrás que hacer c*n*log(k) trabajo. (No teniendo en cuenta el umbral). Entonces todo en todo lo que haces n*c*(1 + log(k)) trabajo, donde c es el momento de tirar un calcetín en una pila.

Este enfoque será favorable en comparación con cualquier c*x*n + O(1) método aproximadamente el tiempo que log(k) < x - 1.


En informática esto puede ser útil: Tenemos una colección de n cosas, un orden en ellos (longitud) y también una relación de equivalencia (información adicional, por ejemplo, el color de los calcetines). La relación de equivalencia nos permite hacer una partición de la colección original, y en cada clase de equivalencia, nuestro orden aún se mantiene. El mapeo de un cosa su clase de equivalencia se puede hacer en O (1), por lo que solo se necesita O (n) para asignar cada elemento a una clase. Ahora hemos utilizado nuestra información adicional y podemos proceder de cualquier manera para clasificar cada clase. La ventaja es que los conjuntos de datos ya son significativamente más pequeños.

El método también se puede anidar, si tenemos múltiples relaciones de equivalencia -> hacer pilas de colores, que dentro de cada partición de pila en la textura, que ordenar por la longitud. Cualquier relación de equivalencia que cree una partición con más de 2 elementos que tengan un tamaño par traerá una mejora de velocidad sobre la clasificación (siempre que podamos asignar directamente un calcetín a su pila), y la clasificación puede suceder muy rápidamente en conjuntos de datos más pequeños.


31



Esta pregunta es realmente profundamente filosófica. En esencia se trata de si el poder de las personas para resolver problemas (el "wetware" de nuestros cerebros) es equivalente a lo que se puede lograr mediante algoritmos.

Un algoritmo obvio para la clasificación de calcetines es:

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

Ahora la ciencia de la computación en este problema es todo acerca de los pasos

  1. "si s se empareja con un calcetín t en N". ¿Qué tan rápido podemos "recordar" lo que hemos visto hasta ahora?
  2. "eliminar t de N" y "agregar s a N". ¿Qué tan caro es hacer un seguimiento de lo que hemos visto hasta ahora?

Los seres humanos usarán varias estrategias para efectuar esto. Memoria humana es de asociación, algo así como una tabla hash donde los conjuntos de características de los valores almacenados se emparejan con los valores correspondientes. Por ejemplo, el concepto de "coche rojo" se asigna a todos los autos rojos que una persona es capaz de recordar. Alguien con una memoria perfecta tiene una asignación perfecta. La mayoría de las personas son imperfectas a este respecto (y la mayoría de las demás). El mapa asociativo tiene una capacidad limitada. Asignaciones pueden emitir pitidos fuera de existencia en varias circunstancias (una cerveza demasiada), se registrará por error ("Creo que su nombre era Betty, no Nettie"), o nunca se sobrescribirá a pesar de que observamos que la verdad ha cambiado ("coche de papá" evoca "Orange Firebird" cuando en realidad sabíamos que había cambiado eso por el Camaro rojo).

En el caso de los calcetines, la recuperación perfecta significa mirar un calcetín s siempre produce la memoria de su hermano t, incluyendo suficiente información (donde está en la tabla de planchar) para ubicar t en tiempo constante. Una persona con memoria fotográfica logra tanto 1 como 2 en tiempo constante sin falta.

Alguien con memoria menos que perfecta podría usar algunas clases de equivalencia de sentido común basadas en las características dentro de su capacidad para rastrear: tamaño (papá, mamá, bebé), color (verdoso, rojizo, etc.), patrón (argyle, liso, etc.) , estilo (footie, hasta la rodilla, etc.). Entonces, la tabla de planchar se dividiría en secciones para las categorías. Esto generalmente permite que la categoría se ubique en un tiempo constante por memoria, pero luego se necesita una búsqueda lineal a través de la categoría "cubo".

Alguien sin memoria o imaginación (lo siento) simplemente mantendrá los calcetines en una pila y hará una búsqueda lineal de la pila completa.

Un monstruo aseado podría usar etiquetas numéricas para los pares como alguien sugirió. Esto abre la puerta a un ordenamiento total, que permite al humano usar exactamente los mismos algoritmos que con una CPU: búsqueda binaria, árboles, hashes, etc.

Entonces, el "mejor" algoritmo depende de las cualidades del wetware / hardware / software que lo está ejecutando y de nuestra disposición a "hacer trampa" al imponer un orden total en pares. Sin duda, un "mejor" meta-algorithm es contratar el mejor clasificador de calcetines del mundo: una persona o máquina que puede adquirir y almacenar rápidamente un conjunto grande de conjuntos de atributos de calcetines en una memoria asociativa 1-1 con búsqueda, inserción y eliminación de tiempo constante. Se pueden conseguir personas y máquinas como esta. Si tiene uno, puede emparejar todos los calcetines en el tiempo O (N) para N pares, lo cual es óptimo. Las etiquetas de orden total le permiten usar el hashing estándar para obtener el mismo resultado con una computadora humana o de hardware.


25