¿Cuál es el mejor algoritmo de programación que hayas creado?

Tengo dos algoritmos de los que estoy muy orgulloso:

1) Cuando estaba en LinkedIn, se me ocurrió un algoritmo más rápido para encontrar rutas entre los miembros. Finalmente descubrí que este algoritmo se llama búsqueda bidireccional de amplitud, pero no lo sabía cuando se me ocurrió. En esos días, LinkedIn apoyaba ver perfiles de personas que estaban a 4 grados de distancia, y hacer una búsqueda amplia de 4 grados tomó aproximadamente [matemática] O (n ^ 4) [/ matemática] tiempo (donde ‘n’ era el promedio número de conexiones por usuario). En lugar de hacer un BFS al 4º grado, modifiqué nuestro código para hacer un BFS al 2º grado tanto para el espectador de un perfil como para el miembro que se está viendo. Luego ordenaría a los miembros en cada una de esas dos redes de segundo grado y verificaría si hubo alguna superposición. Los dos miembros estaban separados <= 4 grados si y solo si había superposición en sus redes de segundo grado. El resultado fue un algoritmo que era [matemático] O (n ^ 2 * log n) [/ matemático] en teoría, y aproximadamente 200 veces más rápido en la práctica.

2) En Google, tenía una tarea en la que tenía un diccionario de cadenas, y tenía que encontrar una manera de ver si una nueva cadena estaba dentro de una distancia de distancia de Levenshtein dada a cualquier cadena en el diccionario. (Ejemplo de caso de uso: digamos que tiene 1 millón de contraseñas y desea ver si la nueva contraseña de un usuario está dentro de una distancia de edición de <= 2 a al menos una de las contraseñas en su diccionario).

La distancia de Levenshtein es un algoritmo O (longitud de cadena más larga * longitud de cadena más corta), por lo que ejecutarlo contra cada cadena en un diccionario grande no es divertido. Se me ocurrió un enfoque que computaba un histograma de distribución de caracteres para cada cadena: toma un campo de 64 bits, lo divide en 16 conjuntos de 4 bits y luego calcula el número de caracteres que son X módulo 16 para X = 0 …15. Por ejemplo, en la cadena “hola”, los valores ASCII de los caracteres son 104, 101, 108, 108, 111, que son 8, 5, 12, 12, 15 módulo 16. En un campo de 64 bits, “hola” correspondería así a un 0001 en el 9º, 6º y 16º conjunto de 4 bits, un 0010 en el 13º conjunto y un 0000 en cualquier otro conjunto de 4 bits. Al final, cada cadena que había reducido a un solo histograma de 64 bits.

Después de calcular estos histogramas para cada cadena del diccionario, podría compararlos con el histograma de la cadena de búsqueda y usar aritmética de bits para determinar rápidamente un límite inferior en la distancia de edición. Por ejemplo, si una cadena tiene 5 letras que son 3 mod 16 y 0 letras que son 4 mod 16, y otra cadena tiene 0 letras que son 3 mod 16 y 5 letras que son 4 mod 16, entonces su distancia de edición será de menos 5 (es decir, se requieren 5 operaciones de edición de edición si reemplaza ‘aaaaa’ con ‘bbbbb’). Debido a que el límite inferior casi siempre era mucho más alto que el umbral de distancia que me interesaba, pude evitar el cálculo de la distancia completa de Levenshtein aproximadamente el 99.99% del tiempo. Como resultado, pude hacer mi verificación de distancia de edición contra un diccionario completo de elementos de 1m en milisegundos, lo cual fue muy aceptable para el caso de uso en el que estaba trabajando.

Como VC (y anteriormente como PM), no he codificado mucho recientemente. Pero estos son mis tres trucos favoritos que he hecho en los últimos 5-6 años:

1.) Algoritmo de consumo de electricidad en tiempo real:

En mi último año de escuela desarrollé un algoritmo para estimar el consumo de energía en tiempo real en una computadora en función de la potencia de diseño térmico o TDP de sus procesadores.

La idea era que si conoces información sobre la arquitectura del procesador de la computadora, TDP y su utilización actual, podrías estimar el consumo de energía de las aplicaciones en tiempo real.

Si bien esto no hace nada si su máquina consume constantemente la misma cantidad de energía (consulte: HowStuffWorks “Cómo funciona la energía del vampiro”), el algoritmo podría proporcionar una cierta introspección sobre cómo los diferentes tipos de aplicaciones y cargas de trabajo afectaron el consumo de energía de una computadora, algo muy interesante a escala en un centro de datos.

Usé este algoritmo dentro de algo llamado The Tesla Project, que un amigo mío y yo enviamos para la competencia Imagine Cup de Microsoft. Terminamos siendo finalistas nacionales para la competencia en 2010, y desde entonces hemos estudiado patentarla.

Más información sobre Tesla: Página sobre Sjsu

2.) Gráfico de arbitraje teórico de divisas:

En mi tercer año de escuela intenté usar las matemáticas para el lado oscuro más oscuro: las finanzas. Mi mejor amiga acababa de hacer su pasantía de verano en banca de inversión en el Bank of America Merryl Lynch, y quería encontrar una manera de unirme a ella en el verano siguiente.

Desafortunadamente, como estudiante en una escuela de segundo nivel, la banca de inversión estaba fuera de discusión. Así que aproveché mi currículum y mi experiencia en programación competitiva (y no hice una pequeña cantidad de ingeniería social dado que mi experiencia en programación competitiva era bastante inexacta) para obtener una entrevista para un papel tecnológico centrado en el comercio.

Cuando aparecieron mis entrevistas, realmente no me importaba mucho el papel. Había recibido una oferta de devolución para una pasantía de administración de productos en NetApp, y mi amigo iba a estar encerrado en una parte bastante aburrida de la compañía, de modo que incluso si obtuviera el papel no la vería ese verano. En comparación con Facebook y Google, sentí que las dos primeras entrevistas que tuve fueron una especie de broma, y ​​debido a mi estupidez / arrogancia nerd de la universidad, incluso hice una de ellas borracho por el altavoz en el club de informática de mi escuela.

Sin embargo, el tercero fue bastante duro y divertido. Tuve que diseñar un sistema para navegar en divisas extranjeras dados los precios de cambio. Estaba profundizando en la teoría de gráficos en ese momento, y se me ocurrieron dos enfoques:

• Punto único a punto de comercio de divisas óptimo utilizando http://en.wikipedia.org/wiki/Dij … en una estructura de costos de la relación de cambio de divisas entre monedas. Esta parecía ser la respuesta básica, pero bajo la presión de reproducirlo se sentía bastante bien.
• Construcción de un sistema de actualización constante de “redes monetarias óptimas” utilizando un árbol de expansión mínimo y un enfoque similar. La idea era que BAML pudiera mantener un MST actualizado constantemente para ciertas monedas altamente negociadas y usar dicho árbol para podar búsquedas punto a punto, posiblemente para la memorización (por ejemplo: recordar algunas rutas no directas decentes entre el USD y los Pesos cubanos).
• Empleando el agrupamiento de K-Means (ver: http://en.wikipedia.org/wiki/Km …) sobre la progresión de la serie temporal de los precios de cambio para “reconocer” ciertos tipos de condiciones de mercado y el comercio de acuerdo con las rutas memorizadas de los dos anteriores enfoques. Por ejemplo, si sé que financieramente hoy está progresando como hace seis días, me gustaría podar aún más mis operaciones punto a punto utilizando un subgráfico óptimo que desarrollé a partir de un cálculo anterior.

Los dos últimos enfoques fueron aparentemente bastante novedosos, y me dieron una oferta para unirme a BAML durante el verano (así como una solicitud al final de la escuela para entrar en el comercio algorítmico cuando mi entrevistador buscó un fondo de cobertura). Decidí oponerme a ese curso de acción y fui por mi verdadera pasión de ser un primer ministro, que creo que fue una mejor opción a largo plazo.

4.) Jane Austen Sort (JAS):

En mi primer año como VC, me uní a una de las varias ligas de fútbol de fantasía asociadas entre empresas con algunos de mis amigos. Me gusta el fútbol, ​​pero no estaba tan al tanto del cable de exención y las noticias actualizadas como mis amigos, así que decidí codificar un sistema que eligió un equipo ridículo para mí.

Escribí un sistema al que llamé Jane Austen Sort (o JAS) que seleccionaba a un jugador para una posición abierta dada la distancia de Levenshtein entre el nombre de cada jugador disponible y una subcadena elegida al azar de igual longitud derivada de la conversación entre el Sr. Darcy y Elizabeth en Orgullo y Perjudicar. El jugador con la distancia más corta fue elegido.

Mi equipo fue, suficiente para decir, realmente muy malo . Pero el Equipo Jane Austen (más tarde llamado Equipo Stark porque usé un enfoque similar con respecto a los intercambios en la temporada usando la conversación de Game of Thrones) fue lo suficientemente bueno como para vencer a otra persona esa temporada.

Escribí un algoritmo de almacenamiento en caché que le ahorra a mi empresa $ 3 millones por año en costos al identificar y almacenar en caché mensajes repetitivos sobre la marcha y evita que se envíen. El algoritmo también reconoce los mensajes relacionados y puede alterar o purgar mensajes “sucios” que otros cambiarían y sabrían cuándo y cuándo no almacenar en caché según los requisitos de procesamiento de la hora del día. Nuestros costos de mensajería se basan en el uso, por lo que cuanto menos enviemos, menos pagaremos.

Es el mejor algoritmo que he creado porque es transparente para los usuarios de la API que se encuentra arriba, es autocurativo, se controla a sí mismo y funciona en toda nuestra organización. Se tardó alrededor de un mes en desarrollarse y tiene un impacto real, tangible y medible.

Este algoritmo redujo nuestros costos anuales para estos datos en un 40%. Soy muy popular con nuestra organización interna que paga las facturas de datos. Soy el enemigo público n. ° 1 del vendedor que ya no recibe este dinero y esta cantidad de dinero ha aparecido en su balance público. Les he hecho perder los objetivos del presupuesto interno y si alguna vez juntan 2 + 2 y calculan quién soy yo y para cuál de sus clientes trabajo, los escuadrones de éxitos pueden no estar muy lejos.

Las lágrimas de los contadores vendedores llorones son las más dulces que existen.

Las 1500 líneas de código que consisten en el algoritmo son algunas de las piezas de software más valiosas que he escrito. Muy pocas piezas de software empresarial utilizadas para uso interno tienen flujos de efectivo positivos adjuntos para el retorno directo de la inversión. La mayoría ahorra dinero indirectamente al ahorrar tiempo o costos asociados con un proceso en otro lugar. Este código no lo hace. Incluso tenemos un tablero que rastrea y calcula el rendimiento del almacenamiento en caché en dólares reales ahorrados en tiempo real.

Baste decir que también soy muy popular entre nuestra gerencia ejecutiva que puede ver ese tablero. La mayoría de los entornos no tienen soluciones de monitoreo para los procesos de negocios que le informan a medida que pasan el día dónde, cuándo y cuánto dinero está ahorrando y gastando.

La implementación del algoritmo específico que no puedo compartir, ya que mi empleador la posee, pero cualquiera que use este proveedor en particular para obtener datos financieros ciertamente puede pagarme para decirles cómo transferir dinero a su bolsillo mediante técnicas similares. La idea es simple, pero lograr la ejecución correcta es un desafío. Los datos asociativos incorporados son particularmente inteligentes ya que la mayoría de los algoritmos de almacenamiento en caché no entienden cómo otras operaciones los afectan y, por lo general, son soluciones puntuales por aplicación. Esta solución es general para este tipo de datos y podemos ajustarla libremente.

Una imagen vale mas que mil palabras.

El algoritmo es una combinación de ‘búsqueda aleatoria’ y ‘descenso más pronunciado’. Esto me hace sentir orgulloso ya que soy un ingeniero de materiales por experiencia, no un programador profesional. Las imágenes a unir (en la captura de pantalla) son imágenes de microscopio electrónico de barrido. (Microestructuras en otras palabras)

El algoritmo que usé para convertir la música en precios de acciones ficticias para mi juego de Android, MoonStocks. Es algo así como Dance-Dance Revolution para las acciones. Los precios suben y bajan de acuerdo con las porciones de alta o baja frecuencia de una canción.

Usé el siguiente método:

Tome la forma de onda de una canción y conviértala en una serie de puntos de datos utilizando una transformación de Fourier, donde cada punto de datos representa la frecuencia dominante en un segmento de tiempo dado. Escale los puntos de datos para que caigan en algún rango de enteros positivos que podrían representar una cantidad realista en dólares de una acción.

Una vez que se han generado los puntos de datos, se pueden usar para que los gráficos de acciones muestren líneas interpoladas entre ellos al ritmo de la música. Si quieres verlo en acción, MoonStocks está disponible en las aplicaciones de Android en Google Play.

Fue hace mucho tiempo, y recuerdo vagamente cómo se implementó, pero fue algo como esto: fusión de datos temporales y conversión a lenguaje natural .

Cuando trabajaba en Ask.com, formaba parte del equipo que lanzó AskCity; en el momento de su lanzamiento, fue revisado como el mejor producto de búsqueda local, ya que agregaba datos de Yelp, OpenTable, CitySearch, StubHub y más, eso proporcionó una interfaz integrada con mapas + resultados de búsqueda para eventos y lugares.

Esencialmente, escribí una función que tomaba un montón de datos temporales (una lista de pares de tiempo de fecha de inicio y finalización) y escupía la cadena más corta posible que resumía con precisión todas las fechas , por ejemplo, “Días de la semana de 9 am a 9 pm, fines de semana de 10 am a medianoche “o” De lunes a viernes de 9 a. m. a 5 p. m., los sábados de 10 a. m. a 6 p. m., domingos cerrados “o” Todos los días de 10 a. m. a 10 p. m., cerrado el Día de Acción de Gracias “para que aparezcan los fragmentos de resultados de búsqueda.

Eventos como conciertos que se presentaron en varios días, o películas con varios horarios y lugares con varias horas de funcionamiento (por ejemplo, restaurantes que cierran 1 día a la semana, horario extendido o reducido en ciertos días).

Hubo muchos casos de esquina con los que tratar (por ejemplo, un espectáculo de Broadway que duró varios días, pero con un día libre en el medio debido a un feriado), pero para proporcionar la secuencia más concisa y precisa, cada par de fecha y hora en la lista tuvo que ser examinado, y una excepción podría descartar todo; no solo eso, sino que también tenía que ver qué elementos no estaban en la lista. Los metadatos generados para calcular el resumen más corto en lenguaje natural eran varias veces más grandes que los datos originales.

Hay 2 algoritmos delante de mi nombre

1. Algoritmo de clasificación ingenuo
2. Cifrado y descifrado de mensajes.

Algoritmo de clasificación ingenuo

En mi segundo año de universidad, estaba trabajando en los algoritmos de clasificación. Entonces encontré algo interesante. Mi algo parece una burbuja normal o un tipo de selección, pero cuando lo analizo ejecutándolo en el sistema, me sorprendió que mientras juego con una gran cantidad de datos, el tiempo que toma este algoritmo es menos de la mitad del tiempo que toma la burbuja o selección de selección.

  Una clase ingenua (A [n])
 {

 // Datos de entrada establecidos en la matriz A [n]
 // Loop1
 para i = 1 a n 
 {
 m = (n + 1-i) / 2
 para j = i a m + i
 {
 Compare if (a [j]> a [n + ij])
 Cambie a [j] y a [n + ij]
 }
 }

 // Loop2:
 para i = n a 1
 {m = i / 2
 para j = 1 a m
 {
 compare if (a [j]> a [i-j + 1])
 Cambie a [j] y a [i-j + 1]
 }
 }
 } 

Cifrado y descifrado de mensajes.

En mi tercer año trabajo para un nuevo algoritmo de cifrado y descifrado. En esto cifré la clave también con el mensaje. Entonces, con este enfoque, el usuario puede cifrar la clave con el mensaje. Si alguien hackeó el masaje, entonces no es posible hackearlo ya que la clave ya está encriptada.

Para descifrar el usuario tiene que pasar la clave original. Si el usuario proporciona la clave falsa, el mensaje se descifrará, pero el usuario no accederá al código correcto.

P.ej. Saurabh tiene 7 char. En él y la tecla tiene 5 letras, por lo que las primeras cinco letras del mensaje cambiarán de acuerdo con la tecla, pero al final solo nos quedan dos letras, por lo que rellenamos la letra p (x o y o z) para que el relleno forme pares de longitud exacta .

Saurabh Saurabh xxx A [20] = {19,1,21,1,18,2,8,24,24,24}

m = longitud del algoritmo de cifrado de clave:

a. tome dos matrices flagtxt y flagkey del tamaño de la longitud del texto y la clave y llénelas con ceros.

si. Haga este proceso hasta la longitud de la clave

Proceso para el cifrado de datos por la clave:

  para k = 1 a m
  J = 1
  para i = 1 a n (n es la longitud del texto rellenado)
  {
  si (j> m)
  {
  j = 1 a [i] = a [i] + b [j] j ++
  }
  más
 {
  a [i] = a [i] + b [j] j ++ 
 }
 Fin para

Proceso de ocultamiento de clave:

  Hacer
  para j = 1 a m-1 
 b [j] = b [j] + b [j + 1]
 fin para
 b [m] = b [m] + b [1]
 Fin para

Cambie la matriz A y B a la forma de caracteres:

P.ej.

  Para i = 1 a n
 mientras que a [i]> 256a [i] = a [i] -256
 flagtxt [i] + = 1
 terminar mientras 
 fin para
 para i = 1 a m
 mientras 
 b [i]> 256b [i] = b [i] -256
 tecla de bandera [i] + = 1
 terminara si
 fin para

Algoritham de descifrado: –

este es el proceso inverso de encriptación

Cambie los datos cifrados en formato ASCII:

P.ej

A [20] = {20,143,29,231,256}

B [20] = {10,2,230,19,23}

Descifrado de datos y clave:

  para i = 1 a n (n es la longitud del texto rellenado)
 mientras flagtxt [i]! = 0
 a [i] = a [i] +256
 flagtxt [i] -
 terminar mientras
 fin para
 para i = 1 a m
 mientras flagkey [i]! = 0
 b [i] = b [i] +256
 tecla de bandera [i] -
 terminar mientras
 fin para
 para k = 1 a m
 b [m] = b [m] -b [1]
 para j = m-1 a 1
 b [j] = b [j] -b [j + 1]
 fin para
 j = 1
 para i = 1 a n
 si (j> m)
 j = 1
 a [i] = a [i] -b [j]
 terminara si
 fin para
 fin para

Este no es mi algoritmo, sino algo que se le ocurrió a mi alumno Michael Otte:

Permite que los algoritmos de planificación de rutas aleatorias se aceleren de forma súper lineal en máquinas de múltiples núcleos, es decir, 10 núcleos no son 10 veces, sino 20, 30 o 50 veces más rápido.

Así es como funciona: cuando se busca una ruta más corta con un planificador aleatorio, y una vez que se encuentra una ruta desde el inicio hasta el objetivo, no hay una ruta más corta fuera del elipsoide que se pueda crear usando una banda elástica del mejor longitud entre inicio y gol como restricción para un bolígrafo. Compartir este elipsoide con cualquier otra persona que también trabaje en este problema, permitirá que esas computadoras reduzcan drásticamente su espacio de búsqueda, aumentando la eficiencia de la búsqueda. Además de reducir el espacio de búsqueda, compartir la mejor ruta posible aumentará la probabilidad de que otras computadoras realmente encuentren un punto que conduzca a una ruta más corta.

El algoritmo se describe con más detalle en este documento C-FOREST: Planificación paralela del camino más corto con aceleración superlineal

Escribí un programa para encontrar el conjunto de potencia de un conjunto dado utilizando el concepto de números binarios. Aunque no es extraordinario, estaba feliz de hacerlo.

Algoritmo

Supongamos que el conjunto es – {1,2,3}

Entonces aquí n es 3 ya que tenemos 3 elementos.

Ejecuto un bucle de 0 a 2 ^ n -1 y obtengo el equivalente binario, es decir, 000 a 111 en este
caso.

Ahora asigna cada número binario al índice de los elementos en el conjunto anterior,
Recojo el elemento si el índice correspondiente es 1, descarto lo contrario.

Aquí está el código:

  #include 
 #include 
 #include 

 int * bin (int n, int x)    
 {
 int * a;
 a = (int *) malloc (n * sizeof (int));

   mientras que (x! = 0)
   {
       if (x> = (pow (2, n-1)))
       {
       a [n-1] = 1;
       x = x- (pow (2, n-1));
       }
       más
       {
       a [n-1] -0;
       }

 norte--;
   }
 devolver a;
 }

 vacío principal()
 {
 int n, j, k = 0, b [1500];
 largo i;
 int * a;
 int * c;
 printf ("Ingrese n \ n");
 scanf ("% d", & n);
 a = (int *) malloc (n * sizeof (int));
 c = (int *) malloc (n * sizeof (int));
 
 
 printf ("Ingrese los elementos \ n");
 
   para (i = 0; i 

    

Se me ocurrieron algunos que puedo recordar.

1. El algoritmo de isosuperficie de corte de esquinas. Esto funcionó para cualquier estructura de cuadrícula. Desafortunadamente, en ese momento, las personas de los Cubos Marchantes estaban arrojando su peso. Aunque mi algoritmo produjo mejores resultados para hexahedra (manejando cuidadosamente los problemas del sillín y el tubo / tapa), no los quería en mi hocico, por lo que cada vez que comenzó el programa almacené en caché todas las soluciones hexaédricas en lugar de ponerlas en lógica.
2. El algoritmo Circle Spline. Hacer trazados para la animación usa splines, pero en la visualización científica el arco circular es algo deseable. Así que lo mezclé entre splines cartesianos y splines cilíndricos en un cilindro giratorio. Desafortunadamente, a veces se puso rizado, por lo que no ahorró tanto trabajo como esperaba.
3. Mi algoritmo de cosido de textura de cristalización simulada. Había visto el papel del algoritmo de corte mínimo y pensé, ¿por qué pensar en términos de un corte en primer lugar cuando tienes que ir a un algoritmo celular de todos modos? Así que acabo de hacer cristales que crecieron alrededor de sitios de nucleación de bajo error. Se puede hacer mucho en un procesador de gráficos, aunque hay una reducción que es molesta.
4. Es más un modelo de programación que un solo algoritmo, pero Makevar fue increíble y todavía lo es. Se basa en la vieja idea de un demonio en LISP y la utilidad Make en Unix. Tiene algunas similitudes con la programación funcional y las propiedades. Básicamente, el sistema sabe qué enlaces dependen de qué otros enlaces y hará el valor de un enlace si y solo si depende de los enlaces que han cambiado desde la última vez que se hizo. Tiene algunas características interesantes, como la paralelización automática, incluso entre máquinas. La mejor e inesperada ventaja fue que me ayudó a crear un problema de 500,000 líneas porque cada nueva característica se podía agregar en el tiempo O (1). Se puede incorporar a los idiomas, y lo he hecho varias veces, pero a nadie le importa lo que hago.

Hay muchos otros, pero estos son los que se me ocurren.

No sé si alguien había usado este algoritmo antes que yo, pero creo que este es uno de los mejores algoritmos que he creado durante mi carrera como programador competitivo.

El problema es encontrar componentes fuertemente conectados en un gráfico. Este es un problema bien conocido, pero estaba usando un enfoque que no figura en la wikipedia. Mi algoritmo fue encontrar componentes fuertemente conectados mediante el uso de una estructura de datos de conjunto disjunto:

  // Representante de un subconjunto disjunto.
 Representante int (const int node) {
	 if (padre [nodo]! = nodo)
		 padre [nodo] = Representante (padre [nodo]);
	 return parent [nodo];
 }

 // Encuentra componentes fuertemente conectados a través de la búsqueda de profundidad primero.
 // Devuelve el representante de un @nodo.
 int Dfs (const int node, int & step) {
	 cuando [nodo] = paso ++;
	 is_visited [nodo] = ENTRADO;
	 para (const int vecino: vecinos [nodo]) {
		 const int neighbour_representative =
			 (es_visitado [vecino] == NO_VISITADO)
				 ?  Dfs (vecino, paso)
				 : Representante (vecino);
		 if (es_visitado [vecino] == ENTRADO &&
			 when [neighbour_representative] 
  La complejidad de este algoritmo es peor que la complejidad de los algoritmos tradicionales, pero no es mucho más lenta que los algoritmos tradicionales, y es mucho más conciso, por lo que fue útil durante las competencias de programación. 

    

Lo mejor depende de la perspectiva.

La compresión y descompresión dinámicas de subsecciones locales de mapa de bits / framebuffer permitieron un rendimiento relativamente alto de alta resolución Postscript y otras representaciones de descripción de página en cantidades relativamente pequeñas de RAM y fue un gran problema, cuando RAM era una porción más significativa de los costos totales del producto. Incluso más recientemente, continúa mejorando el rendimiento al reducir la pérdida de memoria. Sin embargo, optimizar las compresiones fue tedioso. Aunque no fue terriblemente elegante, esta puede haber sido mi innovación más impactante económicamente.

Por otro lado, uno que encontré más elegante (pero no logré convencer a otros para implementar comercialmente) fue el medio tono hexagonal. En su libro, considerado autoritario en ese momento, Robert Ulichney aconsejó en su contra. Estaba demasiado impaciente para apreciar su análisis, y me pareció que simplificar y reducir las interacciones con los vecinos más cercanos podría mejorar la calidad percibida al reducir los artefactos con otros puntos que no sean los formados idealmente. Posteriormente, el Dr. Daniel Lau se enteró de este trabajo, que había sido publicado como documento de conferencia, y obtuvo un análisis para su reemplazo del libro de Ulichney.

Otro que considero que tiene un gran potencial y una amplia aplicabilidad es la interpolación de interpolación binaria multidimensional, donde los valores de precisión relativamente altos se conservan cuando se convierten mediante la búsqueda de tabla con sobremuestreo con una precisión más baja, donde los valores del espacio muestral nuevo más cercano son proporcionales en frecuencia de ocurrencia al significado de la muestra original de bits truncados. Significativamente más barato que las interpolaciones lineales para implementar en hardware, este algoritmo puede generar artefactos que evocan las juntas de Sierpinski Triángulo de Sierpinski – Wikipedia , que pueden mitigarse mediante el posterior filtrado FIR o equivalente.

No puedo decir cuál fue el mejor, pero sí puedo contar el que siempre me enorgulleció más.

Fue una de mis primeras sesiones en una computadora, un Commodore 64 nuevo. En la primera semana tuvimos lo que no teníamos una unidad de cassette, así que todo lo que hicimos en él, desapareció después del trabajo en el momento en que apagamos máquina apagada

Tuve que cambiar de asiento con mi hermano, que también quería divertirse con eso, así que solo tuve 2 horas con él. Después de escribir la pequeña lista al final del libro y trabajar en este “juego” de sprites, probé algo nuevo: ¡criptografía!

Entonces, solo tenía 2 horas de tiempo.

INICIO DE LA SESIÓN

Codifiqué un pequeño texto y agregué un número. Y un interruptor para ese código. No sabía nada sobre criptografía en ese momento, así que puse el nombre de las cifras entre paréntesis (cifra César). Comencé a agregarle la posición, pero también fue muy rápido romperlo. (Cesar + codificación de posición). Escaneé rápidamente el manual y encontré algo mejor que agregar. Modulo! No sé si tenían una función de módulo allí o si tuve que pensar en eso usando AND y NOT (álgebra booleana aplicada, nunca había oído hablar de eso antes). Creo que no tenían módulo e hice una subrutina para eso.

Todavía no lo estaba poniendo en funcionamiento, tenía que encontrar una manera de usar esta increíble herramienta. Así que codifiqué otro cifrado, donde codifiqué el texto con un índice de contraseña (cifrado Vigenère). Agregué mi subrutina de módulo (cifrado Vernam). Escribí un crack para eso (un poco de este criptoanálisis diferencial y ese criptoanálisis lineal y un poco de suerte y fuerza bruta, pero no muy profunda, sobre todo fuerza bruta. Trabajé con análisis de tuplas. Sin embargo, sentí que de alguna manera tenía alcanzó un límite de mis habilidades). No estaba satisfecho

Realmente me estaba poniendo caliente. Encontré el generador aleatorio, que para mí era desconocido en ese momento, implementado por un registro de desplazamiento de retroalimentación lineal en el C64. Lo usé con mi nueva subrutina de módulo para fortalecer mi encriptación. (Cifrado de Lorenz) y usó una contraseña como semilla (función Hash).

Escribí una subrutina para descifrar eso, porque la semilla / contraseña era demasiado corta.

Combiné 3 de los cifrados aleatorios de mi secuencia de código y los superpuse 1 + 2 y el tercero en el medio, con esto alargué la contraseña. (Estándar de cifrado de datos-> Triple DES). Tuve que POKE y PEEK el registro de comentarios en ejecución y restaurarlo para que tenga fuentes pseudoaleatorias independientes. Lo descubrí de la manera difícil (¡pirateando las notas al final del libro, con todos los valores de página cero!).

Perdí algo de tiempo para tratar de romper eso, sin mucho éxito, luego vino mi hermano, ya estaba a la mitad de su horario, nos metimos en una pelea, él desconectó la computadora.

FIN DE LA SESION

Por cierto, no intenté una transposición del código. Esto no vino a mi mente en ese momento.

No hice cifrado durante algún tiempo después de eso hasta que aprendí más sobre eso y reconocí lo que había logrado en las primeras tres horas de computación. Al parecer me especialicé en la universidad por un tiempo, porque tenía algunas habilidades naturales para eso.

Siempre estuve muy orgulloso de esta primera reunión con una computadora y considero que este es mi momento más glorioso. Todo lo demás se basó en el conocimiento de muchas otras personas y realmente no puedo decir si fue realmente mío o no. Pero esta primera sesión, sin ningún conocimiento sobre nada, fue completamente mía.

Y es por eso que lo considero mi mejor algoritmo.

Y debido a que la gente podría hacer cosas así con BASIC, nunca pensé mal de BASIC. Sí, es un lenguaje muy antiguo y tiene un mal nombre, principalmente porque solo teníamos estos editores de línea y muchos GOTO. Y fue muy lento para la Asamblea. Pero realmente tenía su fuerza.

En memoria de estas primeras tres horas de gloria mía, que me unieron para siempre a esta maravillosa máquina, reescribí algunas de las ideas que estaba codificando en ese momento en la Asamblea. Puedes descargar las cosas en mi github: silizium / cypherbasic. Necesitarías un emulador C64 para eso, yo uso “VICE”, el Versatile Commodore Emulator para eso, que también es parte de cada repositorio de Linux que conozco. También disponible en Android.

La lección que puede aprender de esta primera sesión, y lo que siempre creí, es: aquellos que piensan que son realmente inteligentes como adultos a menudo no son mejores que un niño en sus primeras horas. Cuando no se interrumpe, es inteligente y tiene ganas de conquistar algo nuevo.

Equipos enteros de informáticos necesitaban mucho tiempo de desarrollo para encontrar algo que protegiera el débil algoritmo DES mediante algo, que un niño pudiera cocinar en su primera sesión, literalmente, en una computadora.

Las cosas en informática no son la mitad de difíciles de alcanzar de lo que piensas.

Una buena idea aún puede mover el mundo. Solo tienes que probarlo. Y cree en ti mismo. Todos simplemente cocinan con agua y cubren sus cosas con palabras importantes. Pero las ideas, en su mayoría, no son tan grandes. Todavía. (¡Con algunas excepciones inteligentes notables, no todo es simple! Nunca dije eso).

Solo ve y prueba tu suerte tú mismo.

Tengo un hilo interesante para agregar. En 1972 (!) Era estudiante universitario y tenía un trabajo secundario ayudando a un laboratorio de bioquímica a resolver ecuaciones de velocidad de unión no lineal para acetilcolina y su receptor. Había estado usando métodos no lineales para el descenso más pronunciado en el mainframe de la época, un IBM 370, pero las ecuaciones más recientes no convergieron, y el tiempo en el grandote era costoso.

Tuve acceso a esta nueva cosa llamada una minicomputadora, una PDP-8. Podía usarlo durante la noche y los fines de semana, así que tenía mucho tiempo de computación. Ahora, esa máquina quedaría impresionada por tu Fitbit. Hizo menos de un millón de instrucciones por segundo, tenía 16K de palabras de 12 bits de memoria y cargó un programa de cinta de papel perforada. Después de codificar la rutina de arranque desde los interruptores binarios. No hay mucho allí.

Mirando hacia atrás, ahora veo que inventé el algoritmo genético para hacer el trabajo. Adapte la idea analítica no lineal de descenso más pronunciado (aproxima la pendiente multidimensional del espacio de error de parámetro y viaja por el camino más empinado), mediante un muestreo aleatorio de los parámetros locales, eligiendo algunos buenos candidatos e iterando por los mejores caminos. Así que esto tiene 1) mutación aleatoria, 2) la población o el acervo genético, y 3) la aptitud incorporada. También es muy simple: unas pocas líneas de código. Oh, el idioma era FOCAL, que está muerto y olvidado hace mucho tiempo. Una dulce calculadora rápida de lenguaje estructurado en bloques.

Después de muchas noches y fines de semana pude demostrar que la reacción requería energía, no fue pasiva, ¡mi primera ciencia!

Lecciones aprendidas, después de una larga carrera desde microcódigo a escribir un sistema operativo en tiempo real a hash distribuido en la nube (si ha tenido una conversación natural sobre la atención médica en los últimos 10 años, ha hablado con mi reconocedor de voz):

Este enfoque simple es sorprendentemente efectivo. Evita suposiciones, no requiere tanta mano como muchos algoritmos de optimización, y es rápido, pequeño y, por lo tanto, fácil de hacer. Estas son cosas buenas. Además, sin que yo lo supiera, otros ya estaban pensando en ese sentido. Por lo tanto, es fascinante cómo los tiempos generan innovaciones similares, y creemos que estamos siendo originales.

Nota final: la computadora estaba en el antiguo edificio de zoología, y era bastante espeluznante deambular en la penumbra entre las cabezas de animales salvajes en medio de la noche.

Mi mejor algoritmo fue creado para mi investigación de EM. Era un algoritmo de resumen automático. Lo llamo TextTeaser. Al principio, realmente dudo de la calidad de los resúmenes que produce. Pero después de recibir algunos comentarios con la gente, ahora creo que fue realmente tan bueno. Y recibo una solicitud de código abierto … ¡pronto!

Puede probar TextTeaser a través de este enlace: TextTeaser: una aplicación de resumen automático y API

He creado un algoritmo que calcula el relleno óptimo de una superficie rectangular dada con formas más pequeñas. El problema típico en la industria textil o de la madera, donde le gustaría optimizar la materia prima y reducir el desperdicio. Dado un conjunto de superficies con diferentes formas, deben instalarse en una superficie más grande (la materia prima) para minimizar el resto.
Los algos de fuerza bruta son O (n!) (Donde n es el número de formas) y son prohibitivos para calcular n’s más grandes. Se me ocurrió algo basado en una simple observación: si uno pone todas las formas en una caja (2d) y la sacude, se organizarán de la mejor manera (algo funcionaría exactamente igual en dimensiones más altas también) . El algo en sí mismo utilizó programación dinámica, agregando una pequeña inclinación de desplazamiento aleatoria a una pieza y calculando el movimiento del resto, teniendo en cuenta un pequeño vector de fuerza que actúa sobre cada pieza (gravedad). Esto asegurará que el algo converja. Para el cálculo de los puntos de contacto, utilicé una biblioteca externa basada en diagramas de Voronoi.
Esto fue hace unos 12 años, pero afaik el algo todavía se usa en la industria.
El cómputo fue todo en la CPU; porque en ese momento no había PhysX, y los sistemas de simulación patentados eran caros. Hoy, lo reescribiría para usar PhysX, eso lo aceleraría enormemente.

Un guión que crea el esqueleto de mis cursos que enseña varios sistemas de escritura:

Dada una gran cantidad de palabras y nombres internacionales (como “taxi”, “pizza”, “Perú”, “Tom”) en el sistema de escritura que desea aprender, el guión determinará el mejor orden de introducción de las letras / símbolos, donde mejor significa que puede leer la mayoría de las palabras dadas lo antes posible (para que pueda practicar la lectura sin tener que aprender el alfabeto completo primero). El resultado del script es una nueva letra, nuevas palabras que puede leer, una nueva letra, nuevas palabras que puede leer, etc. Independiente del lenguaje y funciona para sílabas y sistemas de escritura ideográfica, así como alfabetos.

También he creado un código interesante al desarrollar el prototipo del sistema de traducción automática para UNIKOM, pero no debo hablar de eso en este momento.

Un algoritmo para determinar las letras de las canciones en función de una búsqueda web.
Si realiza una búsqueda en la web de “letras cómodamente adormecidas”, obtendrá muchos resultados. En realidad, puede extraer la letra real porque la parte común del texto en cada página de resultados será la letra real.

Me gustaría extender esto a las imágenes algún día. Por ejemplo, si busca trabajos en la Búsqueda de imágenes de Google, obtiene un montón de imágenes, pero la entidad que está buscando aparece en un montón de imágenes, y puede extraerlas localizando los bits comunes de cada imagen.

Hace veinte años, estaba escribiendo una simulación de blackjack. Fui autodidacta, con poca o ninguna escolaridad, programando de forma aislada, por lo que mi único conocimiento de lógica o matemáticas provino de mi codificación.

Ataqué todos los problemas a través de la fuerza bruta, ejecuté cada posibilidad 10,000 veces y almacené los resultados en matrices.

La primera vez que creé una fórmula breve que reemplazó 84 líneas de código fue el momento en que sentí una alegría y un asombro completos por las matemáticas. Me dejó sin aliento.

Esa pequeña línea de código siempre será mi favorita, comenzó una historia de amor de toda la vida con las matemáticas, el lenguaje elegante y lírico del universo.