Copiar y pegar de Stack Overflow

(0 comentarios)

Si O’Reilly se animara alguna vez a publicar los títulos de Los 10 mejores libros de programación que NUNCA verás en las estanterías, probablemente “Copiando y pegando de Stack Overflow” se convertiría en un súper ventas.

[Pulsa para continuar]

Algoritmos y calcetines

(4 comentarios)

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.