¿Los desarrolladores de Google realmente usan conceptos como la notación O grande para determinar el tiempo de ejecución de un algoritmo en un proceso de codificación diario?

No puedo hablar con los desarrolladores de Google, pero pasé cinco años escribiendo software de enrutamiento en una empresa que fabricaba enrutadores IP. Les puedo asegurar que estábamos al tanto de la notación O grande en el día a día.

En la mayoría de los casos, la discusión de la notación O grande fue mayormente explícita durante la fase de diseño de un proyecto. La elección de las estructuras de datos para un protocolo de enrutamiento fue un producto de discusión sobre la notación O grande. Las diversas operaciones se analizaron por separado. ¿Qué tan rápido podemos buscar una ruta? ¿Qué tan rápido podemos cambiar una ruta? ¿Qué tan rápido podemos compilar una representación de software del estado de enrutamiento en la representación de hardware que empujamos hacia abajo en la estructura de red?

También utilizamos algoritmos conocidos como el algoritmo de Dijkstra y el algoritmo Bellman-Ford para el cálculo de la ruta más corta. Por supuesto, conocer las grandes características de O de esos algoritmos era importante, sobre todo para no arruinar algo agregando un bucle [math] O (n ^ 2) [/ math] en un [math] O (n log n ) [/ math] algoritmo.

Pero una vez que se realizó el diseño, la discusión de la notación O grande no fue realmente explícita. Su trabajo principal cuando codificaba era básicamente usar las estructuras de datos de la forma en que estaban destinadas. Por ejemplo, si termina en una situación en la que enumera los elementos de una tabla hash ordenados por valor, probablemente deba reconsiderar si la enumeración realmente necesita ser ordenada, y si lo hace, tal vez la tabla hash fue la elección incorrecta de la estructura de datos.

La mayoría de las veces, trabajas con algoritmos conocidos. El rendimiento big-O de los algoritmos que usa generalmente le informa si su código podría ser un cuello de botella en el rendimiento Cualquier cosa lineal o mejor generalmente no es un problema. n log n generalmente está bien, pero debe ser cauteloso, y cualquier cosa n al cuadrado o peor, debe tener mucho cuidado.

Con mucha menos frecuencia, debe desarrollar un algoritmo novedoso. Cuando hace esto, el comportamiento big-O es una pregunta que siempre le preguntan sus pares o en una revisión de código. Sus pares sospechan con razón sobre algoritmos novedosos, porque a menudo tienen problemas de rendimiento. A menudo se puede comparar con un algoritmo existente, utiliza una relación binaria para dividir y conquistar, por ejemplo, por lo que es log n. Si no puede discutir análogamente sobre el rendimiento, debe resolverlo mediante un análisis directo.

No trabajo en Google, pero puedo decir que el uso de la notación big-O suele ser una forma realmente útil de hablar sobre cómo se escala algo. Conocer la diferencia entre un algoritmo [matemático] O (N) [/ matemático] y un algoritmo [matemático] O (N ^ 2) [/ matemático] puede significar la diferencia entre algo que requiere diez servidores para ejecutarse y mil servidores para correr.

Dije “cómo algo escala” porque “tiempo de ejecución” es probablemente una mala forma de pensar en la notación big-O. Lo que Big-O te dice es esto: si te doy más información, ¿cuánto más procesamiento tomará para obtener una respuesta? Es decir, si le doy una entrada de tamaño N y tarda X en ejecutarse, ¿cuánto tiempo se tarda en procesar una entrada de 10N? ¿Va a ser 10X? 100X? 1000X? O tal vez solo X? Nadie está calculando el tiempo real que tomará, esto es puramente una herramienta para comprender el costo de lo que sea que esté construyendo.

Dicho esto, la complejidad del tiempo no es lo único para lo que puedes usar big-O. También puede considerar la complejidad del espacio. Eso significa que si le doy N entrada, usará X cantidad de memoria / almacenamiento. Si le doy una entrada de 10N, ¿usará memoria 10X? Memoria 100X? ¿O solo memoria X?

El uso de big-O como una forma de estimar cómo funcionará algo “en la vida real” le permite planificar la capacidad y asegurarse de no construir algo que no se caiga en la producción. También le permite identificar fácilmente partes de su sistema que podrían estar haciendo demasiado trabajo: un algoritmo [matemático] O (N ^ 2) [/ matemático] entre los algoritmos [matemático] O (N) [/ matemático] podría ser un cuello de botella .

No en Google, pero quiero señalar que es importante comprender la complejidad del algoritmo que está utilizando.

Ejemplo práctico: tiene un algoritmo que alimenta con filas de datos, agrupados en bloques. Hay un costo fijo en el procesamiento de un bloque de datos, más el costo de cada fila. Si sabe que la complejidad es lineal (O (n)), tiene sentido usar bloques grandes: la duración total dependerá de todos modos del número total de filas que tenga, pero si puede mantener el número de bloques pequeño (mediante el uso de bloques grandes) reduce el tiempo de procesamiento.

Por otro lado, si sabe que la complejidad del algoritmo es cuadrática (O ([matemática] n ^ 2 [/ matemática])) o peor, tiene sentido usar bloques más pequeños, ya que el tiempo de procesamiento es proporcional al cuadrado de El número de filas en un paquete. Si conoce los coeficientes exactos, puede calcular un tamaño de bloque óptimo.

Ninguna empresa en la que he trabajado lo hace. Ciertamente no en ninguna de las áreas a las que estuve expuesto. Nunca he tenido un trabajo en ningún lugar donde surgiera más que ocasionalmente.

Se espera que sepa cosas como “los bucles en bucles pueden no ser buenos”. Pero en su mayor parte, utiliza bibliotecas que se encargan de cualquier detalle algorítmico. De hecho, ni siquiera te molestas en cosas como verificar la concatenación de cadenas o nulas. Utiliza una biblioteca o una función de orden superior para hacerlo.

Ahora, si su trabajo es construir bibliotecas que implementen algoritmos, como si construye utilidades de programación dinámica, entonces probablemente le interese. Pero incluso entonces, probablemente no haría nada a mano, todo se mide y prueba a través de la automatización.

El tema es en gran parte académico. En la práctica del día a día no estás descubriendo el fuego, así que lo que sea que estés tratando de resolver probablemente esté en Stack Overflow.

Por supuesto lo hacemos. Simplemente no tendemos a hablar sobre ellos entre nosotros porque los usamos de pasada mientras escribimos nuestro código y revisamos el código de los demás.

La razón por la que estos conceptos surgen en las entrevistas es que hay muchos programadores profesionales que nunca antes han necesitado codificar a este nivel (lo estoy mirando a USTED, codificador que conoce API pero no CS).

Sí. No muy a menudo: con mayor frecuencia, si nos preocupamos por el rendimiento, nos preocupamos más por las constantes que por el rendimiento asintótico, pero ocasionalmente las entradas son lo suficientemente grandes como para tener en cuenta la notación O grande. Por supuesto, dada la diversidad de proyectos en los que trabajamos, lo que es cierto para mí no es necesariamente cierto para los ingenieros de otros grupos.