Ayer emparejé los calcetines de la ropa limpia y descubrí que no era muy eficiente. Estaba haciendo una búsqueda ingenua, escogiendo un calcetín y "iterando" la pila para encontrar su par. Esto requiere iterar sobre N / 2 * n / 4 = n ² /8 calcetines en promedio.

Como informático, estaba pensando en lo que podía hacer. Por supuesto, se me ocurrió ordenar (según tamaño / color / ...) para lograr una solución O (NlogN).

El hash u otras soluciones que no están en el lugar 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 npares de calcetines, que contienen 2nelementos (suponga que cada calcetín tiene exactamente un par coincidente), ¿cuál es la mejor manera de emparejarlos eficientemente con hasta un espacio extra logarítmico? (Creo que puedo recordar esa cantidad de información si es necesario).

Agradeceré una respuesta que aborde los siguientes aspectos:

• Una solución teórica general para una gran cantidad de calcetines.
• El número real de calcetines no es tan grande, no le creo a mi cónyuge y tengo más de 30 pares. (Y es bastante fácil distinguir entre mis calcetines y los de ella; ¿puede usarse esto también?)
• ¿Es equivalente al problema de distinción de elementos ?

Se han propuesto soluciones de clasificación , pero la clasificación es demasiado : no necesitamos orden; solo necesitamos grupos de igualdad .

Entonces el hashing sería suficiente (y más rápido).

1. Para cada color de medias, forme una pila . Itere sobre todos los calcetines en su cesta de entrada y distribúyalos en las pilas de colores .
2. Iterar sobre cada pila y distribuirla por alguna otra métrica (por ejemplo, patrón) en el segundo conjunto de pilas
3. Aplique recursivamente este esquema hasta que haya distribuido todos los calcetines en pilas muy pequeñas que pueda procesar visualmente de inmediato.

Este tipo de particionamiento hash recursivo en realidad lo está haciendo SQL Server cuando necesita unir hash o agregar hash en grandes conjuntos de datos. Distribuye su flujo de entrada de compilació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 (clave hash) que proporcione suficientes depósitos para que cada depósito sea lo suficientemente pequeño como para ser procesado muy rápidamente. Desafortunadamente, no creo que los calcetines tengan tal 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 del mundo real que se me ocurre es crear un rectángulo de pilas : una dimensión es el color, la otra es el patrón. ¿Por qué un rectángulo? Porque necesitamos O (1) acceso aleatorio a las pilas. (Un cuboide 3D también funcionaría, pero eso no es muy práctico).

Actualizar:

¿Qué pasa con el paralelismo ? ¿Pueden varios humanos combinar los calcetines más rápido?

1. La estrategia de paralelización más simple es hacer que varios trabajadores tomen de la cesta 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 (que se manifiestan como colisiones manuales y comunicación humana) destruyen la eficiencia y la velocidad (¡vea la Ley de escalabilidad universal !). ¿Es propenso a puntos muertos ? No, porque cada trabajador solo necesita acceder a una pila a la vez. Con solo un "bloqueo" no puede haber un punto muerto. Livelocks podría ser posible dependiendo de cómo los humanos coordinen el acceso a las pilas. Podrían simplemente usar retroceso aleatoriocomo las tarjetas de red hacen eso a nivel físico para determinar qué tarjeta puede acceder exclusivamente al cable de red. Si funciona para las NIC , también debería funcionar para los humanos.
2. Se escala casi indefinidamente si cada trabajador tiene su propio conjunto de pilas . Luego, los trabajadores pueden tomar grandes cantidades de calcetines de la cesta de entrada (muy poca discusión, ya que rara vez lo hacen) y no necesitan sincronizar al distribuir los calcetines (porque tienen pilas de hilos locales). Al final, todos los trabajadores necesitan unir sus conjuntos de pilas. Creo que se puede hacer en O (log (cuenta de trabajadores * pilas por trabajador)) si los trabajadores forman un árbol de agregación .

¿Qué pasa con el problema de distinción de elementos ? Como dice el artículo, el problema de distinción de elementos se puede resolver O(N). Esto es lo mismo para el problema de los calcetines (también O(N), si necesita solo un paso de distribución (propuse varios pasos solo porque los humanos son malos en los cálculos; un paso es suficiente si distribuye 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), por lo que hemos alcanzado el límite inferior óptimo .

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

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

Los humanos pueden ganar algoritmos de CPU usando 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. La desventaja es que requiere una superficie plana, pero generalmente es abundante.

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

Elige dos para formar un par. Tiempo constante.

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

Usa la clasificación por radix . Esto es solo 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 pares. 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 medias 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.

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

• paso 1) descarta todos tus calcetines existentes

• paso 2) ve a Walmart y cómpralos en paquetes de 10 n paquetes de blanco ym paquetes de negro. No hay necesidad de otros colores en la vida cotidiana.

Sin embargo, de vez en cuando, tengo que hacer esto nuevamente (calcetines perdidos, calcetines dañados, etc.), y odio descartar calcetines perfectamente buenos con demasiada frecuencia (¡y deseé que siguieran vendiendo la misma referencia de calcetines!), 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 recoge cinco de ellos al azar y memoriza su forma o su longitud.

¿Por que cinco? Por lo general, los humanos son buenos, recuerdan entre cinco y siete elementos diferentes en la memoria de trabajo, un poco como el equivalente humano de una pila RPN , 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.

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

Siéntase libre de escribir la fórmula para calcular cuántas muestras tiene que extraer para una probabilidad del 50% de una coincidencia. IIRC es una ley hipergeométrica.

Lo hago todas las mañanas y rara vez necesito más de tres sorteos, pero tengo npares similares (alrededor de 10, más o menos los perdidos) de mcalcetines blancos con forma. Ahora puede estimar el tamaño de mi pila de acciones :-)

Por cierto , descubrí que la suma de los costos de transacción de ordenar todos los calcetines cada vez que necesitaba un par era mucho menor que hacerlo una vez y atar los calcetines. Un just-in-time funciona mejor porque entonces no tienes que atar los calcetines, y también hay un retorno marginal decreciente (es decir, sigues buscando esos dos o tres calcetines que cuando estás en algún lugar de la lavandería y que necesitas para terminar de combinar tus calcetines y pierdes tiempo con eso).

Lo que hago es levantar el primer calcetín y ponerlo (por ejemplo, en el borde del lavadero). Luego tomo otro calcetín y compruebo si es igual al primer calcetín. Si es así, los elimino a ambos. Si no es así, lo puse 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" los calcetines es una opción. En realidad, ni siquiera necesita "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 los calcetines es comparar la igualdad, este algoritmo sigue siendo básicamente un algoritmo n ² , aunque no sé cuál es 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 computación, un árbol puede lograr lo mismo, pero eso es espacio extra. Y, por supuesto, estamos de vuelta en NlogN (o un poco más, si hay varios calcetines que son iguales por 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. :)

Esto es hacer la pregunta equivocada. La pregunta correcta es: ¿por qué paso tiempo clasificando calcetines? ¿Cuánto cuesta anualmente cuando valora su tiempo libre por X unidades monetarias de su elección?

Y la mayoría de las veces, este no es solo un tiempo libre, es el tiempo libre de la mañana , que podría pasar en la cama, tomar un café o salir 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 evitar el problema.

Y hay un camino!

Encuentra un calcetín que te guste. Tenga en cuenta todas las características relevantes: color en diferentes condiciones de iluminación, calidad general y durabilidad, 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 los tejidos naturales son buenos y deben 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 de izquierda a derecha, encontrar un par es una operación O (1), y clasificar los calcetines es una operación aproximada O (M), donde M es el número de lugares en su casa, que ha plagado de calcetines, idealmente algunos pequeño número constante

Si elige un par elegante con diferentes calcetines izquierdo y derecho, haciendo una clasificación completa de los cubos del pie izquierdo y derecho tome 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 para las iteraciones promedio de 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 un N. razonable. Esto puede acelerarse usando una imagen avanzada algoritmos de reconocimiento y heurística, al escanear la pila de calcetines sin clasificar con Mk1 Eyeball .

Entonces, un algoritmo para lograr la eficiencia del emparejamiento de calcetines O (1) (suponiendo un calcetín simétrico) es:

1. Necesita estimar cuántos pares de calcetines necesitará para el resto de su vida, o tal vez hasta que se retire y se mude a climas más cálidos sin necesidad de usar calcetines nunca más. Si eres joven, también podrías estimar 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 su calcetín seleccionado a granel, cuánto cuesta y cómo se entregan.

3. ¡Pide los calcetines!

4. Deshágase de sus viejos calcetines.

Un paso alternativo 3 implicaría comparar los costos de comprar la misma cantidad de calcetines quizás más baratos, algunos pares a la vez a lo largo de los años y agregar el costo de clasificar los calcetines, pero confíe en mi palabra: ¡comprar al por mayor es más barato! Además, los calcetines en almacenamiento aumentan su valor a la tasa de inflación del precio 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 realmente no ocupan mucho espacio en el estante superior de un armario.

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

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

Puede lograr O (n) con clasificación de radix . Solo necesita elegir algunos atributos para los cubos.

1. Primero puedes elegir (el suyo, el mío): 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 pilas por color (recuerde mantener el orden inicial del paso 1 para todos los calcetines en la misma pila),
3. luego la longitud del calcetín,
4. luego textura, ....

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

Como solución práctica:

1. Haga rápidamente montones de calcetines fácilmente distinguibles. (Decir por color)
2. Ordena rápidamente cada pila y usa la longitud del calcetín para comparar. Como humano, puede tomar una decisión bastante rápida sobre qué calcetín usar para dividir que evite el peor de los casos. (Puedes ver múltiples calcetines en paralelo, ¡úsalo para tu ventaja!)
3. Deje de clasificar las pilas cuando hayan alcanzado un umbral en el que se sienta cómodo para encontrar pares de puntos y medias no deseables al instante

Si tiene 1000 medias, con 8 colores y una distribución promedio, puede hacer 4 pilas de cada 125 medias en c * n tiempo. Con un umbral de 5 medias puede ordenar cada pila en 6 carreras. (Contando 2 segundos para lanzar un calcetín en la pila correcta, te tomará menos de 4 horas)

Si tiene solo 60 calcetines, 3 colores y 2 tipos de calcetines (los suyos o los de su esposa), puede ordenar cada pila de 10 calcetines en 1 corrida (nuevamente umbral = 5). (Contar 2 segundos te llevará 2 min).

La clasificación inicial de los cubos acelerará su proceso, ya que divide sus n calcetines en k cubos a c*ntiempo, de modo que solo tendrá que hacer el c*n*log(k)trabajo. (Sin tener en cuenta el umbral). En general, todo lo que haces sobre el n*c*(1 + log(k))trabajo, donde c es el momento de tirar un calcetín sobre una pila.

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

En informática, esto puede ser útil: tenemos una colección de n cosas , un orden en ellas (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. La asignación de una cosa a 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 ordenar 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 en longitud. Cualquier relación de equivalencia que cree una partición con más de 2 elementos que tengan un tamaño aproximado traerá una mejora de la velocidad sobre la clasificación (siempre que podamos asignar directamente un calcetín a su pila), y la clasificación puede ocurrir muy rápidamente en conjuntos de datos más pequeños.

Estás intentando resolver el problema equivocado.

Solución 1: cada vez que coloque calcetines sucios en la cesta de la ropa, átelos con un nudo pequeño De esa manera no tendrá que ordenar nada después del lavado. Piense en ello como registrar un índice en una base de datos Mongo. Un poco de trabajo por delante para algunos ahorros de CPU en el futuro.

Solución 2: si es invierno, no tiene que usar medias a juego. Somos programadores Nadie necesita saber, mientras funcione.

Solución 3: Difundir el trabajo. Desea realizar un proceso de CPU tan complejo de forma asincrónica, sin bloquear la interfaz de usuario. Toma esa pila de calcetines y mételos en una bolsa. Solo busque un par cuando lo necesite. De esa manera, la cantidad de trabajo que se necesita es mucho menos notable.

¡Espero que esto ayude!

Esta pregunta es realmente profundamente filosófica. En el fondo, se trata de si el poder de las personas para resolver problemas (el "software" de nuestros cerebros) es equivalente a lo que pueden lograr los 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 informática en este problema tiene que ver con 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 lograr esto. La memoria humana es asociativa , algo así como una tabla hash donde los conjuntos de características de valores almacenados se combinan con los valores correspondientes. Por ejemplo, el concepto de "auto rojo" se asigna a todos los autos rojos que una persona es capaz de recordar. Alguien con una memoria perfecta tiene un mapeo perfecto. La mayoría de las personas son imperfectas a este respecto (y la mayoría de los demás). El mapa asociativo tiene una capacidad limitada. Los mapeos pueden sonar fuera de existencia bajo varias circunstancias (una cerveza de más), se grabe por error ("aunque su nombre era Betty, no Nettie"), o nunca se sobrescriba aunque observemos que la verdad ha cambiado ("el auto de papá" evoca "pájaro de fuego naranja" cuando realmente sabíamos que había cambiado eso por el Camaro rojo).

En el caso de los calcetines, el recuerdo perfecto significa que mirar un calcetín ssiempre produce el recuerdo de su hermano t, incluida suficiente información (dónde está en la tabla de planchar) para ubicarlo ten tiempo constante. Una persona con memoria fotográfica logra tanto 1 como 2 en tiempo constante sin falta.

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

Alguien sin memoria o imaginación (perdón) solo mantendrá los calcetines en una pila y hará una búsqueda lineal de toda la pila.

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

Por lo tanto, el "mejor" algoritmo depende de las cualidades del software / hardware / software que lo ejecuta y nuestra voluntad de "engañar" imponiendo un orden total en pares. Ciertamente, un "mejor" meta- algoritmo es contratar al mejor clasificador de calcetines del mundo: una persona o máquina que pueda adquirir y almacenar rápidamente un gran conjunto N de conjuntos de atributos de calcetín en una memoria asociativa 1-1 con búsqueda constante de tiempo, insertar, y eliminar Se pueden adquirir tanto personas como máquinas como esta. Si tiene uno, puede emparejar todos los calcetines en tiempo O (N) para N pares, lo cual es óptimo. Las etiquetas de orden total le permiten usar el hash estándar para obtener el mismo resultado con una computadora humana o de hardware.

Costo: mover calcetines -> alto, buscar / buscar calcetines en línea -> pequeño

Lo que queremos hacer es reducir el número de movimientos y compensarlo con el número de búsquedas. Además, podemos utilizar el entorno multiproceso de los Homo Sapiens para guardar más cosas en el caché de decisión.

X = tuyo, Y = tus cónyuges

De la pila A de todos los calcetines:

Elija dos calcetines, coloque el calcetín X correspondiente en la línea X y el calcetín Y en la línea Y en la siguiente posición disponible.

Haz hasta que A esté vacío.

Para cada línea X e Y

1. Elija el primer calcetín en línea, busque a lo largo de la línea hasta que encuentre el calcetín correspondiente.

2. Poner en la línea final de calcetines correspondiente.

3. Opcional Mientras busca la línea y el calcetín actual que está viendo es idéntico al anterior, realice el paso 2 para estos calcetines.

Opcionalmente para el paso uno, toma dos calcetines de esa línea en lugar de dos, ya que la memoria de almacenamiento en caché es lo suficientemente grande, podemos identificar rápidamente si alguno de los calcetines coincide con el actual en la línea que está observando. Si tiene la suerte de tener tres brazos, podría analizar tres calcetines al mismo tiempo dado que el recuerdo del sujeto es lo suficientemente grande.

Haz hasta que tanto X como Y estén vacías.

Hecho

Sin embargo, como esto tiene una complejidad similar al tipo de selección, el tiempo que se tarda es mucho menor debido a las velocidades de E / S (calcetines en movimiento) y de búsqueda (buscando un calcetín en la línea).

Aquí hay un límite inferior Omega (n log n) en el modelo basado en comparación. (La única operación válida es comparar dos medias).

Suponga que sabe que sus 2n calcetines están dispuestos de esta manera:

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

donde f es una permutación desconocida del conjunto {1,2, ..., n}. Saber esto no puede hacer que el problema sea más difícil. ¡No hay! posibles salidas (coincidencias entre la primera y la segunda mitad), lo que significa que necesita log (n!) = Omega (n log n) comparaciones. Esto se puede obtener clasificando.

Dado que está interesado en las conexiones con el problema de la distinción de elementos: probar el límite Omega (n log n) para la distinción de elementos es más difícil, porque la salida es binaria sí / no. Aquí, la salida tiene que coincidir y la cantidad de salidas posibles es suficiente para obtener un límite decente. Sin embargo, hay una variante relacionada con la distinción de elementos. Suponga que le dan 2n calcetines y se pregunta si pueden combinarse de manera única. Puede obtener una reducción de ED enviando (a ₁ , a ₂ , ..., a _n ) a (a ₁ , a ₁ , a ₂ , a ₂ , ..., a _n , a _n ). (Entre paréntesis, la prueba de dureza de la disfunción eréctil es muy interesante, a través de la topología.)

Creo que debería haber un Omega (n ² ) vinculado al problema original si solo permite pruebas de igualdad. Mi intuición es: considere un gráfico donde agrega un borde después de una prueba, y argumenta que si el gráfico no es denso, la salida no se determina de manera única.

Así es como lo hago realmente, para p pares de medias ( n = 2p medias individuales):

• Agarra un calcetín al azar de la pila.
• Para el primer calcetín, o si se han emparejado todos los calcetines elegidos previamente, simplemente coloque el calcetín en la primera "ranura" de un "conjunto" de calcetines no emparejados frente a usted.
• Si tiene uno o más calcetines sin emparejar seleccionados, verifique su calcetín actual con todos los calcetines sin emparejar en la matriz.
  • Es posible separar los calcetines en clases o tipos generales (blanco / negro, tobillo / tripulación, atletismo / vestimenta) al construir su conjunto, y "profundizar" para comparar solo igual por igual.
  • Si encuentra una coincidencia aceptable, junte ambos calcetines y retírelos de la matriz.
  • Si no lo hace, coloque el calcetín actual en la primera ranura abierta de la matriz.
• Repita con cada calcetín.

El peor de los casos de este esquema es que cada par de calcetines es lo suficientemente diferente como para que coincida exactamente, y que los primeros n / 2 calcetines que elija sean todos diferentes. Este es su escenario O (n ² ), y es extremadamente improbable. Si el número de tipos únicos de calcetín t es menor que el número de pares p = n / 2 , y los calcetines en cada tipo son lo suficientemente parecidos (generalmente en términos relacionados con el desgaste) que cualquier calcetín de ese tipo se puede combinar con cualquier otra, entonces, como he deducido anteriormente, el número máximo de calcetines que nunca tendrá que comparar a es t , después de lo cual el siguiente que tire voluntadcoincide con uno de los calcetines sin emparejar. Este escenario es mucho más probable en el calcetín promedio que en el peor de los casos, y reduce la complejidad del peor de los casos a O (n * t) donde generalmente t << n .

Enfoque del mundo real:

Tan rápido como sea posible, retire los calcetines de la pila sin clasificar uno a la vez y colóquelos en pilas frente a usted. Las pilas deben estar dispuestas de manera eficiente en el espacio, con todos los calcetines apuntando en la misma dirección; El número de pilas está limitado por la distancia que puede alcanzar fácilmente. La selección de un montón sobre el cual colocar un calcetín debe hacerse, lo más rápido posible, colocando un calcetín sobre un montón de calcetines aparentemente similares; el tipo ocasional I (poner un calcetín en una pila a la que no pertenece) o el tipo II (poner un calcetín en su propia pila cuando hay una pila existente de calcetines similares) se puede tolerar: la consideración más importante es la velocidad .

Una vez que todos los calcetines estén en pilas, pase rápidamente por las pilas de múltiples calcetines creando pares y retirándolos (estos se dirigen al cajón). Si hay calcetines que no coinciden en la pila, vuelva a apilarlos a su mejor pila (dentro de la restricción lo más rápido posible). Cuando se hayan procesado todas las pilas de calcetines múltiples, combine los calcetines que se pueden emparejar restantes que no se emparejaron debido a errores de tipo II. Whoosh, ya terminaste, y tengo muchos calcetines y no los lavo hasta que una gran parte esté sucia. Otra nota práctica: volteo la parte superior de uno de un par de calcetines sobre el otro, aprovechando sus propiedades elásticas, para que permanezcan juntos mientras los transportan al cajón y mientras están en el cajón.

Según su pregunta, está claro que no tiene mucha experiencia real con la lavandería :). Necesita un algoritmo que funcione bien con una pequeña cantidad de calcetines no deseables.

Las respuestas hasta ahora no hacen un buen uso de nuestras capacidades de reconocimiento de patrones humanos. El juego de Set proporciona una pista de cómo hacerlo bien: coloque todos los calcetines en un espacio bidimensional para que ambos puedan reconocerlos bien y alcanzarlos fácilmente con las manos. Esto lo limita a un área de aproximadamente 120 * 80 cm más o menos. Desde allí, seleccione los pares que reconoce y elimínelos. Ponga medias extra en el espacio libre y repita. Si lava para personas con calcetines fácilmente reconocibles (me vienen a la mente niños pequeños), puede hacer una clasificación de radix seleccionando primero esos calcetines. Este algoritmo funciona bien solo cuando el número de calcetines individuales es bajo

Tome un primer calcetín y colóquelo sobre una mesa. Ahora elige otro calcetín; si coincide con el primero elegido, colóquelo encima del primero. Si no, colóquelo sobre la mesa a una pequeña distancia del primero. Elige un tercer calcetín; si coincide con alguno de los dos anteriores, colóquelo encima de ellos o colóquelo a una pequeña distancia del tercero. Repita hasta que haya recogido todos los calcetines.

Para decir qué tan eficiente es emparejar calcetines de una pila, primero tenemos que definir la máquina, porque el emparejamiento no se realiza ya sea por un turing ni por una máquina de acceso aleatorio, que normalmente se utilizan como base para un análisis algorítmico

La máquina

La máquina es una abstracción de un elemento del mundo real llamado ser humano. Es capaz de leer del entorno a través de un par de ojos. Y nuestro modelo de máquina puede manipular el medio ambiente mediante el uso de 2 brazos. Las operaciones lógicas y aritméticas se calculan utilizando nuestro cerebro (con suerte ;-)).

También tenemos que considerar el tiempo de ejecución intrínseco de las operaciones atómicas que se pueden llevar a cabo con estos instrumentos. Debido a restricciones físicas, las operaciones que se realizan con un brazo o un ojo tienen una complejidad temporal no constante. Esto se debe a que no podemos mover un montón de calcetines infinitamente grandes con un brazo ni un ojo puede ver el calcetín superior en un montón de calcetines infinitamente grande.

Sin embargo, la física mecánica también nos da algunos beneficios. No estamos limitados a mover como máximo un calcetín con un brazo. Podemos mover un par de ellos a la vez.

Entonces, dependiendo del análisis anterior, las siguientes operaciones deben usarse en orden descendente:

• operaciones lógicas y aritméticas
• lecturas ambientales
• modificaciones ambientales

También podemos aprovechar el hecho de que las personas solo tienen una cantidad muy limitada de calcetines. Entonces, una modificación ambiental puede involucrar a todos los calcetines en la pila.

El algoritmo

Así que aquí está mi sugerencia:

1. Extienda todos los calcetines en la pila sobre el piso.
2. Encuentra un par mirando los calcetines en el piso.
3. Repita desde 2 hasta que no se pueda hacer un par.
4. Repita desde 1 hasta que no haya medias en el piso.

La operación 4 es necesaria, porque al extender los calcetines sobre el piso, algunos pueden ocultar otros. Aquí está el análisis del algoritmo:

El analisis

El algoritmo termina con alta probabilidad. Esto se debe al hecho de que uno no puede encontrar pares de calcetines en el paso número 2.

Para el siguiente análisis de tiempo de ejecución de npares de pares de calcetines, suponemos que al menos la mitad de los 2ncalcetines no están ocultos después del paso 1. Por lo tanto, en el caso promedio podemos encontrar n/2pares. Esto significa que el bucle es el paso 4 se ejecuta O(log n)veces. El paso 2 se ejecuta O(n^2)veces. Entonces podemos concluir:

• El algoritmo involucra O(ln n + n)modificaciones ambientales (paso 1 O(ln n)más recoger cada par de calcetines del piso)
• El algoritmo involucra O(n^2)lecturas ambientales del paso 2
• El algoritmo involucra O(n^2)operaciones lógicas y aritméticas para comparar un calcetín con otro en el paso 2

Por lo tanto, tenemos una complejidad total de tiempo de ejecución de O(r*n^2 + w*(ln n + n))dónde ry wson los factores para las operaciones de lectura ambiental y escritura ambiental, respectivamente, para una cantidad razonable de calcetines. El costo de las operaciones lógicas y aritméticas se omite, porque suponemos que se necesita una cantidad constante de operaciones lógicas y aritméticas para decidir si 2 calcetines pertenecen al mismo par. Esto puede no ser factible en todos los escenarios.

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

Se me ocurrió otra solución que no prometía menos operaciones, ni menos consumo de tiempo, pero debería intentarse para ver si puede ser una heurística lo suficientemente buena como para proporcionar menos consumo de tiempo en una gran serie de pares de calcetines.

Condiciones previas: no hay garantía de que haya los mismos calcetines. Si son del mismo color, no significa que tengan el mismo tamaño o patrón. Los calcetines se barajan al azar. Puede haber un número impar de calcetines (faltan algunos, no sabemos cuántos). Prepárese para recordar una variable "índice" y configúrela en 0.

El resultado tendrá una o dos pilas: 1. "emparejado" y 2. "faltante"

Heurístico:

1. Encuentra el calcetín más distintivo.
2. Encuentra su pareja.
3. Si no hay coincidencia, colóquelo en la pila "faltante".
4. Repita desde 1. hasta que no haya más calcetines más distintivos.
5. Si hay menos de 6 calcetines, pase al 11.
6. Empareje ciegamente todos los calcetines a su vecino (no lo empaquete)
7. Encuentre todos los pares emparejados, empaquételos y muévalos a la pila "emparejada"; Si no hubo nuevas coincidencias, incremente el "índice" en 1
8. Si el "índice" es mayor que 2 (esto podría depender del valor del número de calcetines porque con un mayor número de calcetines hay menos posibilidades de emparejarlos a ciegas) pase a 11
9. Baraja el resto
10. Ir a 1
11. Olvídate del "índice"
12. Elige un calcetín
13. Encuentra su par
14. Si no hay un par para el calcetín, muévalo a la pila "faltante"
15. Si se encontró coincidencia, combínalo, empaca el par y muévelo a la pila "coincidente"
16. Si todavía hay más de un calcetín, vaya a 12
17. Si solo queda uno, vaya al 14
18. Sonríe satisfecho :)

Además, podría agregarse un cheque para los calcetines dañados también, como si se los quitara. Se podría insertar entre 2 y 3, y entre 13 y 14.

Espero con interés escuchar cualquier experiencia o corrección.

Cuando clasifico calcetines, hago una clasificación aproximada de radix , dejando caer calcetines cerca de otros calcetines del mismo tipo de color / patrón. Excepto en el caso en que puedo ver una coincidencia exacta en / cerca de la ubicación donde estoy a punto de soltar el calcetín, extraigo el par en ese punto.

Casi todos los demás algoritmos (incluida la respuesta de mayor puntuación por usr ) se ordenan y luego se eliminan los pares. Creo que, como humano, es mejor minimizar la cantidad de calcetines que se consideran al mismo tiempo.

Hago esto por:

1. Escoger un calcetín distintivo (lo que me llame la atención primero en la pila).
2. Comenzar una clasificación de radix desde esa ubicación conceptual tirando calcetines de la pila en función de su similitud.
3. Coloque el nuevo calcetín cerca de la pila actual, con una distancia basada en lo diferente que es. Si te encuentras poniendo el calcetín encima de otro porque es idéntico, forma el par allí y retíralos. Esto significa que las comparaciones futuras requieren menos esfuerzo para encontrar el lugar correcto.

Esto aprovecha la capacidad humana de emparejar difusamente en el tiempo O (1), que es algo equivalente al establecimiento de un mapa hash en un dispositivo informático.

Al tirar primero de los calcetines distintivos, deja espacio para "acercarse" a las características que son menos distintivas, para empezar.

Después de eliminar el color fluro, los calcetines con rayas y los tres pares de calcetines largos, puede terminar con calcetines en su mayoría blancos, ordenados por su desgaste.

En algún momento, las diferencias entre los calcetines son lo suficientemente pequeñas como para que otras personas no noten la diferencia, y no se necesita ningún esfuerzo adicional de combinación.

Cada vez que recoja un calcetín, colóquelo en un lugar. Luego, el próximo calcetín que recoja, si no coincide con el primer calcetín, colóquelo junto al primero. Si es así, hay un par. De esta manera, realmente no importa cuántas combinaciones haya, y solo hay dos posibilidades para cada calcetín que recojas: o tiene una combinación que ya está en tu conjunto de calcetines, o no, lo que significa que agréguelo a un lugar en la matriz.

Esto también significa que seguramente nunca tendrá todos sus calcetines en la matriz, porque los calcetines se eliminarán a medida que coincidan.

Considere una tabla hash de tamaño 'N'.

Si suponemos una distribución normal, entonces el número estimado de 'inserciones' para tener al menos un calcetín mapeado a un cubo es NlogN (es decir, todos los cubos están llenos)

Había derivado esto como parte de otro rompecabezas, pero estaría feliz de que me demuestren lo contrario. Aquí está mi artículo de blog sobre el mismo

Deje que 'N' corresponda a un límite superior aproximado en la cantidad de colores / patrones únicos de calcetines que tiene.

Una vez que tenga una colisión (también conocida como una coincidencia) simplemente quite ese par de calcetines. Repita el mismo experimento con el próximo lote de calcetines NlogN. Lo bueno de esto es que podrías estar haciendo NlogN comparaciones paralelas (resolución de colisión) debido a la forma en que funciona la mente humana. :-)

Los calcetines, ya sean reales o alguna estructura de datos análoga, se suministrarían en pares.

La respuesta más simple es antes de permitir que el par se separe, se debería haber inicializado una estructura de datos única para el par que contuviera un puntero hacia el calcetín izquierdo y derecho, permitiendo así que los calcetines sean referidos directamente o por medio de su par. También se puede extender un calcetín para contener un puntero a su compañero.

Esto resuelve cualquier problema de emparejamiento computacional al eliminarlo con una capa de abstracción.

Aplicando la misma idea al problema práctico de emparejar calcetines, la respuesta aparente es: no permita que sus calcetines se desvinculan. Los calcetines se proporcionan como un par, se colocan en el cajón como un par (tal vez uniéndolos), se usan como un par. Pero el punto donde es posible desemparejar es en la lavadora, por lo que todo lo que se requiere es un mecanismo físico que permita que los calcetines permanezcan juntos y se laven eficientemente.

Hay dos posibilidades físicas:

Para un objeto 'par' que mantiene un puntero a cada calcetín, podríamos tener una bolsa de tela que usamos para mantener los calcetines juntos. Esto parece una sobrecarga masiva.

Pero para que cada calcetín mantenga una referencia al otro, hay una solución ordenada: un popper (o un 'botón a presión' si eres estadounidense), como estos:

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

Luego, todo lo que debe hacer es juntar los calcetines justo después de quitárselos y ponerlos en su canasta de lavado, y nuevamente ha eliminado el problema de la necesidad de combinar sus calcetines con una abstracción física del concepto de 'emparejar'.

Si la operación de "mover" es bastante costosa, y la operación de "comparar" es barata, y necesita mover todo el conjunto de todos modos, a un búfer donde la búsqueda es mucho más rápida que en el almacenamiento original ... simplemente integre la ordenación en la obligatoria moverse.

Descubrí que integrar el proceso de clasificación para colgar para secar es muy fácil. Necesito levantar cada calcetín de todos modos, y colgarlo (mover) y no me cuesta nada colgarlo en un lugar específico en las cuerdas. Ahora, simplemente para no forzar la búsqueda de todo el búfer (las cadenas), elijo colocar los calcetines por color / sombra. Más oscuro a la izquierda, más brillante a la derecha, frente más colorido, etc. Ahora, antes de colgar cada calcetín, miro en su "vecindad derecha" si ya hay una correspondiente, esto limita el "escaneo" a 2-3 otras medias, y si es , Cuelgo el otro justo al lado. Luego los enrollo en pares mientras los quito de las cuerdas, cuando están secos.

Ahora, esto puede no parecer tan diferente de "formar pilas por color" sugeridas por las respuestas principales, pero primero, al no elegir pilas discretas sino rangos, no tengo ningún problema para clasificar si "púrpura" va a la pila "roja" o "azul"; simplemente va en medio. Y luego, al integrar dos operaciones (colgar para secar y clasificar), la sobrecarga de la clasificación mientras se cuelga es como el 10% de lo que sería la clasificación por separado.

Terminé de emparejar mis calcetines justo ahora, y descubrí que la mejor manera de hacerlo es la siguiente:

• Elija uno de los calcetines y guárdelo (cree un 'cubo' para ese par)
• Si el siguiente es el par del anterior, colóquelo en el depósito existente, de lo contrario, cree uno nuevo.

En el peor de los casos, significa que tendrá n / 2 cubos diferentes, y tendrá determinaciones n-2 sobre el cubo que contiene el par del calcetín actual. Obviamente, este algoritmo funciona bien si solo tiene unos pocos pares; Lo hice con 12 pares.

No es tan científico, pero funciona bien :)

Mi solución no se corresponde exactamente con sus requisitos, ya que formalmente requiere O(n) espacio "extra". Sin embargo, teniendo en cuenta mis condiciones, es muy eficiente en mi aplicación práctica. Por lo tanto, creo que debería ser interesante.

Combinar con otra tarea

La condición especial en mi caso es que no uso secadora, solo cuelgo mis paños en una secadora de ropa común. Colgar telas requiere O(n)operaciones (por cierto, siempre considero el embalaje del contenedor problema del aquí) y el problema por su naturaleza requiere un espacio lineal "extra". Cuando saco un calcetín nuevo del cubo, trato de colgarlo junto a su par si el par ya está colgado. Si es un calcetín de un nuevo par, dejo un espacio al lado.

Oracle Machine es mejor ;-)

Obviamente, requiere un poco de trabajo adicional para verificar si el calcetín correspondiente ya está colgando en algún lugar y representaría una solución O(n^2)con un coeficiente aproximado 1/2para una computadora. Pero en este caso, el "factor humano" es en realidad una ventaja: por lo general, puedo O(1)identificar muy rápidamente (casi ) el calcetín a juego si ya estaba colgado (probablemente esté involucrado un almacenamiento en el cerebro imperceptible): considérelo como una especie de "oráculo" limitado como en Oracle Machine ;-) Nosotros, los humanos tenemos estas ventajas sobre las máquinas digitales en algunos casos ;-)

¡Casi lo tengo O(n)!

Por lo tanto, conectando el problema de emparejar calcetines con el problema de colgar paños, obtengo O(n)"espacio adicional" de forma gratuita, y tengo una solución que es casi O(n)a tiempo, requiere un poco más de trabajo que simples paños colgantes y permite acceder inmediatamente a un par completo de calcetines incluso en una muy mala mañana de lunes ... ;-)

Espero poder aportar algo nuevo a este problema. Noté que todas las respuestas descuidan el hecho de que hay dos puntos en los que puede realizar el preprocesamiento , sin ralentizar su rendimiento general de lavado.

Además, no necesitamos suponer una gran cantidad de calcetines, incluso para familias numerosas. Los calcetines se sacan del cajón y se usan, y luego se tiran en un lugar (tal vez un contenedor) donde permanecen antes de ser lavados. Si bien no llamaría a dicho bin una pila LIFO, diría que es seguro asumir que

1. la gente tira sus dos calcetines aproximadamente en la misma área del contenedor,
2. el contenedor no está aleatorizado en ningún punto, y por lo tanto
3. cualquier subconjunto tomado de la parte superior de este contenedor generalmente contiene los dos calcetines de un par.

Dado que todas las lavadoras que conozco tienen un tamaño limitado (independientemente de la cantidad de calcetines que tenga que lavar), y la aleatorización real ocurre en la lavadora, no importa cuántas medias tengamos, siempre tenemos pequeños subconjuntos que casi no contienen Singletons.

Nuestras dos etapas de preprocesamiento son "poner los calcetines en el tendedero" y "quitar los calcetines del tendedero", lo que tenemos que hacer para obtener calcetines que no solo estén limpios sino también secos. Al igual que con las lavadoras, los tendederos son finitos, y supongo que tenemos toda la línea donde ponemos nuestros calcetines a la vista.

Aquí está el algoritmo para 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 
 }
}

No pierdas tu tiempo moviendo calcetines o buscando la mejor combinación, todo esto debe hacerse en O (n), que también necesitaríamos para ponerlos en la línea sin clasificar. Los calcetines aún no están emparejados, solo tenemos varios grupos de similitud en la línea. Es útil que tengamos un conjunto limitado de calcetines aquí, ya que esto nos ayuda a crear grupos "buenos" (por ejemplo, si solo hay calcetines negros en el conjunto de calcetines, la agrupación por colores no sería el camino a seguir)

Aquí está el algoritmo para 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
 }

Debo señalar que para mejorar la velocidad de los pasos restantes, es aconsejable no elegir aleatoriamente el siguiente calcetín, sino tomar secuencialmente calcetín tras calce de cada grupo. Ambos pasos de preprocesamiento no toman más tiempo que simplemente poner los calcetines en la línea o en la canasta, lo que tenemos que hacer sin importar qué, por lo que esto debería mejorar en gran medida el rendimiento del lavado.

Después de esto, es fácil hacer el algoritmo de partición hash. Por lo general, aproximadamente el 75% de los calcetines ya están emparejados, dejándome con un subconjunto muy pequeño de calcetines, y este subconjunto ya está (algo) agrupado (no introduzco mucha entropía en mi cesta después de los pasos de preprocesamiento). Otra cosa es que los grupos restantes tienden a ser lo suficientemente pequeños como para ser manejados a la vez, por lo que es posible sacar un grupo completo de la cesta.

Aquí está el algoritmo para sort_remaining_clusters ():

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

Después de eso, solo quedan unos pocos calcetines. Aquí es donde introduzco los calcetines no emparejados previamente en el sistema y proceso los calcetines restantes sin ningún algoritmo especial: los calcetines restantes son muy pocos y se pueden procesar visualmente muy rápido.

Para todos los calcetines restantes, supongo que sus contrapartes todavía están sin lavar y los guardo para la próxima iteración. Si registra un crecimiento de calcetines no apareados con el tiempo (una "fuga de calcetines"), debe revisar su papelera; puede ser aleatorio (¿tiene gatos que duermen allí?)

Sé que estos algoritmos toman muchas suposiciones: un contenedor que actúa como una especie de pila LIFO, una lavadora normal limitada y un tendedero normal limitado, pero esto todavía funciona con una gran cantidad de calcetines.

Acerca del paralelismo: siempre que arroje ambos calcetines en el mismo contenedor, puede paralelizar fácilmente todos esos pasos.

He tomado medidas simples para reducir mi esfuerzo en un proceso que toma O (1) tiempo.

Al reducir mis entradas a uno de dos tipos de calcetines (calcetines blancos para recreación, calcetines negros para el trabajo), solo necesito determinar cuál de los dos calcetines tengo en la mano. (Técnicamente, dado que nunca se lavan juntos, he reducido el proceso al tiempo O (0)).

Se requiere un esfuerzo inicial para encontrar calcetines deseables y para comprar en cantidad suficiente como para eliminar la necesidad de sus calcetines existentes. Como había hecho esto antes de mi necesidad de medias negras, mi esfuerzo fue mínimo, pero el kilometraje puede variar.

Tal esfuerzo inicial se ha visto muchas veces en un código muy popular y efectivo. Los ejemplos incluyen # DEFINE'ing pi a varios decimales (existen otros ejemplos, pero ese es el que viene a la mente en este momento).

Cree una tabla hash que se utilizará para calcetines sin igual, utilizando el patrón como el hash. Iterar sobre los calcetines uno por uno. Si el calcetín tiene una coincidencia de patrón en la tabla hash, quítelo de la mesa y forme un par. Si el calcetín no tiene una coincidencia, colóquelo en la mesa.

El problema de ordenar tus n pares de calcetines es O (n) . Antes de tirarlos a la cesta de la ropa. , debe enroscar el izquierdo al derecho. Al sacarlos, cortas el hilo y pones cada par en tu cajón - 2 operaciones en n pares, entonces O (n).

Ahora la siguiente pregunta es simplemente si usted lava su propia ropa y si su esposa lava la suya. Ese es un problema probable en un dominio de problemas completamente diferente . :)