Algoritmos y calcetines

Además de ayudar a resolver dudas sobre programación, a veces Stackoverflow también sirve para echar unas risas. Pero sólo si tienes un sentido del humor un tanto especial, y te hacen gracia las discusiones prácticas sobre la eficiencia de los algoritmos para el emparejamiento de calcetines.

Algoritmos para emparejar calcetines

Y es que, como bien explica el usuario Amit Gross en su pregunta, usar una búsqueda simple, seleccionando un calcetín e iterando sobre la pila de calcetines restantes en busca de su pareja, es una operación muy costosa, que requeriría iterar sobre n/2 * n/4 = n2/8 calcetines de media.

La respuesta más votada sugiere utilizar un particionado recursivo basándose en un hash, como hace, por ejemplo, SQL Server cuando trabaja con grandes volúmenes de datos. Con este algoritmo clasificaríamos los calcetines en distintas pilas según su color, y distribuiríamos estos calcetines en pilas más pequeñas basándonos en otros criterios, como el dibujo, hasta tener pilas lo suficientemente pequeñas para poder procesarlas visualmente rápidamente.

Comentarios
  1. Dos cosas:

    – El enlace está roto, básicamente porque se antepone la URL del artículo a la URL de destino.

    – Yo ya trabajé en un programa así para clasificar mi ropa en una base de datos, pero era un poco más sencillo. Igualmente… maldito Stackoverflow xD

    Responder

    • Dos cosas:

      – Ups! Gracias Juanjo.

      – ¿No será open source? 😛

      Responder

  2. Jajaja creo que es la pregunta con más respuestas que he visto en Stackoverflow.

    Responder

Deja un comentario