¿Debería un programador competente ser capaz de idear su propio algoritmo de ruta más corta?

58

Estoy sufriendo una crisis de confianza en mi habilidad como programador de computadoras.

Ayer intenté crear mi propio algoritmo de ruta más corta para un gráfico y después de algunas horas simplemente tiré la toalla y aprendí el algoritmo de Dijkstra.

¿Es este el tipo de cosas que un buen programador debería ser capaz de "reinventar" en un par de horas o no soy realista?

Bueno, al menos pude reinventar el tipo de burbuja: D

Programador novato
fuente
77
Alguien que haya realizado una IU durante 20 años probablemente tendrá dificultades para encontrar una solución a un problema desde otro dominio, en un corto período de tiempo.
Codificador
38
¡Pasar mucho tiempo en los sitios de SE da a todos una crisis de confianza, creo! (No es que sea algo malo). La felicidad en la vida es encontrar el equilibrio perfecto entre la aceptación de lo que es y el deseo de cambiarlo.
TrojanName
2
No pude reinventarlo yo mismo, pero trato de recordar cómo funciona. asegúrese de comprender esta animación: upload.wikimedia.org/wikipedia/commons/2/23/…
Trabajo
66
@Brian Tragedia del genio local. Ya casi nunca puedes ser el mejor en nada.
Rei Miyasaka
77
un ordenador buena científico debería, pero no necesariamente un programador informático o software ingeniero
Neil McGuigan

Respuestas:

118

Un buen programador debe darse cuenta de que ya se ha escrito un gran algoritmo para resolver un problema y no pierde el tiempo reinventando ruedas.

Dudo que a Dijkstra se le ocurra el algoritmo de ruta más corto en unas pocas horas, por lo que parece un estándar realmente alto para determinar si alguien es un "buen programador".

GSto
fuente
25
@Nakilon: los programadores que ignoran las soluciones existentes solo están perdiendo el tiempo, y si no lo están haciendo, están haciendo una solución peor. Ver: Todos los que crean su propio esquema de hash de contraseña vs bcrypt.
Restablece a Mónica el
10
@GSto: según wikipedia, Dijkstra ideó el algoritmo en menos de una hora: 20 minutos, según la primera nota en wikipedia: en.wikipedia.org/wiki/Dijkstra%27s_algorithm
woliveirajr
99
Es un algoritmo relativamente simple, pero Dijkstra era muy talentoso y había sido entrenado en física teórica y matemática avanzada. No hay nada como unos años escribiendo pruebas para mejorar la capacidad de diseñar algoritmos.
Kevin Cline
19
@woliveirajr - Bueno, estoy seguro de que Newton tomó la misma cantidad de tiempo para elaborar las leyes del movimiento. Después de pensarlo por 20 años primero.
Torre
66
@Nakilon: Sí, por eso todos escriben todo en C, porque de lo contrario solo eres un codificador y usas el lenguaje de alto nivel de otra persona. Oh, espera, me refiero a la asamblea, de lo contrario solo estás usando el lenguaje de bajo nivel de otra persona. Oh, espera, me refiero a encender interruptores para cambiar los circuitos eléctricos, de lo contrario solo estás usando el conjunto de instrucciones de otra persona. O bien, podría usar lo que ya está allí y trabajar para crear algo nuevo . ¿Por qué perder el tiempo reinventando el algoritmo de Dijkstra cuando puedes inventar algo nuevo, como un programa que lo usa?
Restablece a Mónica el
54

¿Es este el tipo de cosas que un buen programador debería ser capaz de "reinventar" en un par de horas o no soy realista?

Primero, quizás estás confundiendo la programación con la informática teórica. Un programador fantástico necesita un buen fundamento en informática pero no necesita ser fantástico. Dijkstra fue fantástico en informática.

En segundo lugar, esperaría que cualquiera con una buena comprensión de los gráficos desarrolle su propio recorrido de gráficos después de un poco de reflexión. Pero no es un algoritmo de ruta más corto. El algoritmo de Dijkstra en particular es altamente sofisticado. Una vez que lo entiendes, es cegadoramente obvio. Pero la mayoría de las cosas son así.

Probablemente podría derivar algún tipo de algoritmo de ruta más corta después de probar algunas cosas y darle tiempo a la idea. Pero no se decepcione si eso lleva horas, o incluso unos días. Esto está completamente bien y es normal.

(Advertencia: bueno, deberías ser capaz de aplicar la fuerza bruta al problema en unas pocas horas como máximo, pero esto no daría un algoritmo de trabajo incluso en gráficos bastante pequeños).

Konrad Rudolph
fuente
56
No se preocupe, si la fuerza bruta no funciona, simplemente no está usando suficiente.
Robbie
2
+1 para resaltar la diferencia entre CS teórico y programación. La programación es la resolución de problemas del mundo real, y la CS teórica está ahí para apoyar la programación. Sin embargo, la CS teórica no es 100% esencial en la programación diaria de la mayoría de las personas.
Phil
17

¿Es este el tipo de cosas que un buen programador debería ser capaz de "reinventar" en un par de horas o no soy realista?

Definitivamente poco realista. Las personas no solo "inventan" algoritmos en unas pocas horas. Se necesita mucho esfuerzo y trabajo. Para citar este blog:

En Programming Pearls, Bentley, citando a Donald Knuth, dice: "Si bien la primera búsqueda binaria se publicó en 1946, la primera búsqueda binaria que funciona correctamente para todos los valores de n no apareció hasta 1962".

y la versión de Bentley también fue problemática cuando se implementó para conjuntos grandes.

Además, un buen programador sabe qué herramientas están a su disposición y cuándo usarlas. No obtienes puntos extra por originalidad o por hacer las cosas de manera diferente: quieres que funcione y funcione bien.

Veintiuna
fuente
1
BlackJack, tuve que unirme a este foro para señalar que Bentley no dijo lo que usted dijo que dijo: Knuth lo dijo y Bentley lo citó. Cuando leí tu comentario pensé que habías hecho un buen punto, pero me gusta verificar mis fuentes y nunca había oído hablar de Bentley. Sin embargo, he oído hablar de Knuth y puedo confiar en lo que dice. Por favor revise sus fuentes mejor la próxima vez.
Richard
8
@Richard - El comentario fue "En Programming Pearls, dice Bentley ..." Knuth fue el primero en decirlo, pero mi fuente es Programming Pearls, no TAoCP, así que escribí lo que escribió Bentley. No afirmé que Bentley es el creador, simplemente cité lo que se dice en el libro. Los autores no inventaron una gran cantidad de material en los libros, por lo que no entiendo por qué lo verías así.
BlackJack
Al atribuir la cotización únicamente a Bentley, usted no le debe el crédito a Knuth y, si la declaración de "Bentley" era incorrecta, coloca a Bentley en la posición de haber producido información incorrecta, en lugar de simplemente haberla difundido. Hablando estrictamente, no dijiste lo que dijo Bentley: si lo hubieras hecho, habrías dicho: "Bentley dijo que Knuth dijo eso ...". La cita se usa bien aquí, pero se saca del contexto en el que se dijo.
Richard
3
@ Richard - La cita que he enumerado es directamente del blog, que cita directamente del libro (literalmente, creo que es la página 57 de la primera edición). Si tiene tantos problemas con la declaración, póngase en contacto con el autor del blog y pídale que lo cambie.
BlackJack
1
@ Richard y BlackJack: Ambos tienen razón, pero la atribución al autor original agrega credibilidad y contexto a la declaración. Mi edición debería ser suficiente.
Steven Evers
9

Es muy poco probable que pueda encontrar una solución mejor que las que puede elegir.

Salir con un algoritmo mejor que uno considerado "el mejor" (en su caso, el más corto) no es algo que todos puedan hacer. Probablemente ni siquiera sea posible.

Un buen programador debería ser capaz de comprender la lógica detrás del algoritmo y por qué es mejor o peor (o simplemente inadecuado para ese problema en particular) que otros algoritmos que intentan resolver el mismo problema.

(s) También debería poder saber si realmente es la mejor manera de resolver ese problema en particular.

De todos modos, si quieres practicar, aún puedes intentar escribir tu implementación personal de un algoritmo, tratando de resolver un problema usando tu mente. Puede que no sea el mejor, pero es una buena práctica para resolver problemas.

Jose Faeti
fuente
6

Esto me recuerda algo que leí sobre la diferencia entre "ingeniería de software" (lo que yo llamaría programación) y las otras disciplinas de ingeniería. Ahora que lo pienso, creo que fue el libro original de Design Patterns. Estoy seguro de que alguien aquí puede citarlo en la parte superior de su cabeza.

De todos modos, el punto (aunque no exactamente orientado al diseño de algoritmos) fue que las disciplinas de ingeniería están codificadas; No es probable que los ingenieros civiles pasen tiempo intentando reinventar la viga en I, pero los programadores lo hacen todo el tiempo. El problema (y me doy cuenta de que simplemente estoy haciendo eco de los sentimientos de muchos) es que este comportamiento es derrochador y propenso a errores, y sirve al ego más que la solución.

La informática me llevó a la programación, y me encantan los dos. Sin embargo, soy mucho mejor programador que informático. Nunca te acusaría de ser incompetente porque no podrías reinventar el algoritmo de Dijkstra en una tarde. Cuestionaría tu competencia como programador si no pudieras reconocer un problema que podría resolverse mediante un algoritmo de gráfico de ruta más corta.

Dicho esto, creo que pensar en algoritmos e intentar diseñar e implementar nuevos es (potencialmente) divertido y (casi) siempre instructivo. Solo trato de separar limpiamente mi tiempo CS de mi tiempo de programación. Para los programadores, nuestro tiempo (especialmente pagado) se gasta mejor en resolver problemas prácticos en lugar de los abstractos. Además, el tiempo CS casi siempre me aplasta la confianza.

Keith Layne
fuente
Oh, la ironía ... ahora que puedo comentar en cualquier lugar, ¿debería eliminar la respuesta que me valió ese privilegio? Debería haber una insignia para eso.
Keith Layne
Hay - Disciplinado sin embargo, si su reputación se recalcula, volverá a bajar a 1.
ChrisF
Sí, ese es exactamente mi punto ... Yo estaría yendo más allá de la disciplina en ese punto de la OMI. Si convertí mi respuesta a un comentario antes de eliminarlo, podría tenerlo todo ... Sugiero una nueva insignia llamada UberDisciplined para cualquier eliminación que haga que regrese al nuevo estado de usuario. :)
Keith Layne
3

No notarás las mismas cosas que todos los demás. Creo que es solo un hecho de la vida con el que tenemos que vivir. Gran parte se reduce a su aprendizaje pasivo y los modelos mentales que ha desarrollado como resultado de ellos.

Conozco a algunos programadores muy inteligentes y competentes a quienes se les tuvo que enseñar la ley de DeMorgan en la escuela antes de que pudieran hacerlo de manera consistente. Por casualidad descubrí el algoritmo de Dijkstra por mi cuenta (y tengo que admitir que estoy un poco orgulloso de ello), pero me llevó mucho tiempo hasta que pude entender el tipo de burbuja.

Más famoso, Einstein, quien crees que sería un experto en teoría de nudos, no pudo atar sus propios cordones de los zapatos hasta que tenía alrededor de diez años.

Es probable que haya reinventado, sin saberlo, muchas cosas que muchos otros nunca habrían descubierto si no hubiera sido por la enseñanza explícita.

Rei Miyasaka
fuente
3

Ruego diferir por lo que dicen la mayoría de las respuestas. Si bien no esperaría que un programador de cualquier nivel pudiera aparecer solo en el algoritmo de Dijkstra, definitivamente esperaría que él encontrara alguna forma (eficiente o no) para resolver el problema.

Por ejemplo, dijiste como comentario adicional que eras capaz de crear burbujas por tu cuenta. Sé que es el algoritmo de clasificación más desagradable, pero encontraste una manera de resolver un problema, y ​​eso es lo que espero que los programadores puedan: encontrar una forma de resolver problemas.

Por supuesto, investigar y encontrar soluciones hechas por otros también funciona, pero el extremo de ese punto es un tipo que no piensa en sí mismo y cuyos programas son un compendio de búsquedas de Google.

Creo que estoy sonando más duro de lo que realmente quiero, pero mi punto es: esperaría que un programador sea lo suficientemente creativo como para encontrar una solución a un problema, incluso si la solución es defectuosa o desordenada.


Entonces, volviendo a su caso, no creo que deba tener que idear el algoritmo de Dijkstra, pero si tiene la capacidad de escribir un algoritmo para probar varias posibilidades y encontrar el camino más corto sin terminar en un bucle infinito, entonces tienes mi aprobación.

(Por cierto, mi aprobación cuenta en el mismo orden de importancia que un cupón de lavado de autos gratis).

Alfa
fuente
3
Estoy de acuerdo en que sí, un programador competente debería ser capaz de idear burbujas o su equivalente. Incluso podría ser un uso productivo del tiempo implementarlo y probarlo, tal vez solo para comprender mejor el problema. Pero creo que hay que decir que ningún programador competente continuaría y realmente lo usaría en el código de producción. Hacer eso es lo que hace que sus clientes regresen el próximo año y se quejen de que, ahora que tienen más datos para procesar, su algoritmo O (n!) Tardará el doble de la edad del universo en completarse ...
Thomas Padron-McCarthy
¿A quién le importa si puedes inventar algoritmos, si ni siquiera puedes reconocer cuándo apesta? La autocrítica es tan importante para un programador como la creatividad. Prefiero trabajar con un programador que admite rápidamente cuando saben que su propia solución está tardando demasiado o es poco probable que sea la mejor, que con un programador que quiere reinventar cada rueda porque lastima su ego de lo contrario.
Rei Miyasaka
Estoy de acuerdo en ambos puntos, pero creo que estamos midiendo dos cosas diferentes. Una es la capacidad del programador para resolver problemas (algo que considero esencial). Otro es la autocrítica (lo considero esencial pero no para la programación: de por vida) y la capacidad de juzgar el código (muy deseable). También diría que las soluciones que toman para siempre no son realmente soluciones, ¿verdad? ;)
Alfa el
2

Sí, él / ella debería.

Puede ser el equivalente moral del tipo burbuja, pero creo que un buen programador debería ser capaz de encontrar al menos algo que funcione, por ineficiente que sea.

Huelga decir que si ese problema en particular surgiera, un buen programador primero buscaría si hay una biblioteca que lo haga por él, o qué algoritmos publicados lo hacen y son fáciles de implementar.

Por supuesto, muchas tareas de programación son mucho menos difíciles y no todos necesitan ser capaces de abordar problemas tan difíciles. Pero querrá tener a alguien con una mente así en su equipo, porque podría tener algunos problemas específicos de proyectos complicados en los que no puede confiar en un montón de investigaciones científicas previas.

Hans-Peter Störr
fuente
1

No te preocupes

Como programador de Perl, mi objetivo es nunca reinventar la rueda. Ese es el trabajo de CPAN. Si hay un algoritmo o módulo simple y bien soportado, lo usamos. Si no hay un buen módulo, a continuación, nos inventamos la rueda. Esa es una de las mejores cosas de Perl.

Entonces, lo que digo es esto:

  1. No recomiendo reinventar la rueda pero cuando lo haces ...
  2. Intenta no reinventarlo por completo y ...
  3. No te preocupes si no puedes hacerlo. Por eso tenemos una comunidad de programación :-).
Dinámica
fuente
No se trata de reinventar, se trata de resolver problemas en general. Si no intentas inventar cosas por tu cuenta, nunca mejorarás.
Nils
0

La teoría de grafos, y los algoritmos que se aplican a ella, parecen simples en la superficie, pero generalmente están lejos de serlo. Se podría pensar que la formación de gráficos no cruzados (planos) es simple, por ejemplo, a primera vista. El año pasado examiné ampliamente este problema (planaridad mediante la eliminación de los subgrafos de Kuratowski). Puedo decirle, por esa experiencia, que las personas que escriben estos algoritmos generalmente pasan la duración de sus estudios de doctorado haciéndolo, y a veces esa investigación se realiza en equipos. Y como investigadores , ese es su único enfoque de trabajo durante ese período de tiempo. No es sensato pensar que nosotros, los ingenieros en el terreno, podemos esperar lo mismo. Como alguien más aquí dijo correctamente, es cegadoramente obvio una vez que la solución está frente a usted. ¡Ese siempre parece ser el caso!

Ingeniero
fuente
0

¿Es este el tipo de cosas que un buen programador debería ser capaz de "reinventar" en un par de horas o no soy realista?

Diría que si eres capaz de inventar un algoritmo para un problema conocido como Shortest Path por tu cuenta, estás siendo un mal programador.

Significaría que está ignorando toda una historia sobre el problema de la ruta más corta , pasando de un algoritmo O (| V | ^ 4) publicado en 1955 al algoritmo O (E + V log V) publicado en 1984 (que es el de Dijkstra algoritmo con árboles de Fibonacci). Es casi seguro que lo harás peor que los algoritmos ya ideados. Peor aún, hay una buena posibilidad de que su algoritmo tenga huecos o errores que lo hacen incorrecto. Además, seguramente pasará mucho más tiempo pensando en su algoritmo, implementándolo y probándolo que el tiempo que llevaría reutilizar un algoritmo existente.

Deje el diseño de algoritmos a los diseñadores de algoritmos. Los programadores son consumidores de sus resultados. Los programadores combinan algoritmos y los ponen a trabajar en tareas del mundo real. Un oficial de policía no necesita poder reinventar la ley para poder trabajar o ser un buen oficial.

Incluso le recomiendo que use implementaciones hechas por expertos en lugar de implementar los algoritmos usted mismo para cualquier algoritmo moderadamente complicado. Es más probable que sea correcto, lo más probable es que lo hayan hecho más rápido de lo que nunca lo hará y le ahorrará mucho tiempo. Esto es particularmente cierto para los algoritmos criptográficos, porque obtiene la demanda adicional de seguridad, que generalmente solo los expertos pueden proporcionarle.

Alex ten Brink
fuente
Los algoritmos criptográficos son fáciles de verificar una implementación de; los vectores de prueba correctos conocidos son una moneda de diez centavos por docena para cualquier algoritmo especificado públicamente, y es correcto o no. (Puede obtener un rendimiento subóptimo con una implementación personalizada, pero si es correcto, se puede trabajar en eso). La parte difícil en la criptografía es cosas como la generación de números aleatorios, el manejo adecuado de claves sin formato y tablas de expansión de claves en memoria, adecuado manejo de las entradas del usuario (salazón, etc.), almacenando algo que le permita determinar si los datos descifrados son válidos, y así sucesivamente.
un CVn
Estaba pensando más en la línea de ataques de tiempo, etc., cosas que casi ningún programador sabe. No siempre es un problema, pero importante. Además, la combinación de primitivas criptográficas generalmente no funciona como uno espera, esto también es una parte difícil de la seguridad.
Alex ten Brink
Si bien los ataques cronometrados, etc., son ciertamente una preocupación válida (y no solo en criptografía), diría que la susceptibilidad de una implementación a estos no tiene impacto en su corrección . Y hay muchas, muchas maneras de cometer errores en la criptografía, mucho más que habilitar ataques de tiempo. Bruce Schneier solía dirigir su serie Doghouse ; No he visto nada en él recientemente, pero hay muchos ejemplos de advertencia allí. google.com/search?q=site%3Aschneier.com+%22the+doghouse%22
un CVn