¿Cuál es el algoritmo más difícil que has implementado? ¿Por qué fue difícil? ¿Cuánto tiempo te llevó?

En mi último año de secundaria, implementé con éxito el algoritmo de Ukkonen para construir un árbol de sufijos en tiempo lineal. Hice esto como preparación para IOI 2010, aunque el árbol de sufijos no se incluyó en el programa de estudios. Mi motivación fue resolver algunos problemas de campos de entrenamiento nacionales que resultaron ser solo solucionables usando árboles / matrices de sufijos. (Esos problemas fueron elegidos por el usuario de Quora en ese entonces).

Imprimí una copia del papel para poder llevarlo a todas partes. A veces incluso lo leo mientras almorzo (de verdad). El algoritmo es bastante difícil y complicado; Al principio, incluso no tenía sentido para mí. Me tomó varias semanas finalmente entender cada una de las anotaciones, los pseudocódigos y las ideas detrás de esto. Finalmente, pude implementarlo en C ++. Luego lo probé para construir el árbol de sufijos para una cadena que contiene 1 millón de caracteres, y tardé menos de 3 segundos si recuerdo correctamente.

¡Estaba muy, muy orgulloso esa vez! Desafortunadamente, en el primer año de la universidad, alguien robó mi computadora portátil 🙁 Por lo tanto, también perdí mi código Ukkonen. Han pasado 3 años; Si leo el periódico nuevamente, no creo que todavía recuerde todos los detalles. Todavía lo lamento, hasta ahora. ¡Adiós, uno de los códigos más bellos que he escrito en mi vida!

El código del que estoy más orgulloso es una estructura de datos que inventé para un problema del Proyecto Euler. Más tarde descubrí al leer los comentarios que era esencialmente lo mismo que un árbol indexado binario.

Para una matriz de longitud n, solo se necesitan operaciones O (log n) para incrementar cualquier intervalo de entradas dado. La desventaja es que se necesitan operaciones O (log n) para recuperar un valor. Pero para este problema específico que convirtió mi solución O (n ^ 2) en una solución O (n log n), lo que redujo el tiempo de ejecución de semanas a minutos.

Me tomó un par de días pensar en el problema para finalmente descubrir esa solución. Lo recuerdo con cariño, porque generalmente si no puedo obtener la solución dentro de la primera hora, no la obtendré en absoluto. Por una vez, perseveré, y valió la pena.

(Y por favor no pregunte qué problema fue. El objetivo del Proyecto Euler es resolverlo usted mismo).

En la escuela de posgrado, elaboré una nueva teoría para la transformación de similitud de los operadores de campo de 3 y 4 electrones que surgen en la física nuclear cuántica de capa abierta y la química cuántica.

Pude resolver el problema de crear una transformación unitaria pura, mientras que la teoría existente requería el uso de integrales espurias que violaban las restricciones de espín conocidas en los electrones y no tenían una verdadera interpretación física. De hecho, me parecía imposible que se requiriera un enfoque tan poco físico, y solo pude completar este trabajo al estar completamente aislado de mi asesor o cualquier tipo de microgestión que sospecho que otros estudiantes se ven obligados a soportar. También puedo señalar que no seguí ningún tipo de “proceso científico” o metodología ágil aquí, eso habría hecho imposible la idea. No puedo enfatizar esto lo suficiente. Puedo describirlo más parecido a que un chef pruebe una receta y diga, esto simplemente no sabe bien, y luego trabaje a través de varias especias y hierbas hasta obtener la mezcla correcta. entonces comenzó el verdadero trabajo.

Resolví la mayoría de las ideas conceptuales en mi cabeza corriendo en la pista a las 6 de la mañana, y pasé varias semanas resolviendo los detalles matemáticos. Luego me tomó algunas semanas implementar el código y probarlo en casos del mundo real.

(Basado en este trabajo, y en un conjunto mucho más grande de problemas de codificación, como escribir un compilador funcional para implementar la teoría, y combinado con su aplicación, obtuve una beca NSF en química teórica (1 de solo 2 en todo el país))

En la escuela secundaria, maxflow codes, una versión de descomposición de Heavy-light con un seg-tree, que pensé que era el primero en encontrar.
En la universidad: un algoritmo mejorado para calcular particiones sólidas, que se publicó en este documento, el algoritmo iTEBD para obtener el estado fundamental del modelo Ising.

Hace dos días, completé la implementación del algoritmo de optimización de enjambre de partículas en mi proyecto de prueba de software. Los algoritmos de IA son simples a la vista, cómodos de implementar pero difíciles de perfeccionar, especialmente si está trabajando en un gran conjunto de datos.

Los más difíciles son los algoritmos descritos en todos los libros de texto y tutoriales en línea que dan descripciones deficientes de implementaciones que no manejan casos especiales que se encuentran a menudo en el mundo real. Uno sería el algoritmo de interacción de Bentley-Ottmann. La mala dirección, la descripción incompleta e inadecuada le dará una implementación que no funciona mucho mejor que la fuerza bruta.

Prueba este Inconvergente – Inicio

línea convergente / diferencial

y este Inconvergente – Inicio

y similar se puede encontrar aquí Página en chromeexperiments.com

Feliz dolor de cabeza !!!