Creo que en Habré hay fanáticos de la serie Silicon Valley . Esta semana, por primera vez en las seis temporadas, mostraron un código grande, por supuesto, quiero discutirlo aquí de inmediato.
Queriendo humillar al personaje principal Richard Hendrix, su antiguo jefe muestra en una reunión un fragmento de su antiguo código. Allí, se aplica una búsqueda lineal a los datos ya ordenados, por lo que la tarea se completará, pero parece muy ineficiente.
El propio Richard no argumenta que el código es malo. Sin embargo, entre los espectadores de la serie, su decisión de repente encontró defensores, y ahora me pregunto qué piensa Habr sobre su posición.
El fragmento de código conocido de Richard se ve así:
int index = 0; while (!element.equals(sortedList.get(index)) && sortedList.size() > ++index); return index < sortedList.size() ? index : -1;
Aquí, una búsqueda lineal gira a su vez a cada elemento de una lista ordenada, hasta llegar al correcto. Como regla, prefieren la búsqueda binaria en datos ordenados, que cada vez divide el conjunto a la mitad, descartando la mitad inadecuada en su conjunto (porque con un aumento en el volumen de datos, el número de iteraciones en el lineal aumenta mucho más rápido que en el binario). Pero en el subreddit / r / SiliconValleyHBO apareció el siguiente comentario :
"Quiero estudiar un poco y señalar que el" error "de Richard al usar la búsqueda lineal en lugar de la búsqueda binaria en datos ordenados en realidad resulta ser más productivo en muchos casos. Con conjuntos de datos gigantes (creo que el umbral está en millones de elementos) la búsqueda binaria es más rápida. Pero, en general, si su conjunto de datos no es gigantesco, el procesador almacenará mejor en una búsqueda lineal, será más adecuado para el predictor de ramificación, y su algoritmo también se puede vectorizar. Las búsquedas lineales requieren más iteraciones, pero cada una es increíblemente más rápida que una iteración de búsqueda binaria. Esto es contradictorio y contradice todo lo que le enseñaron en la universidad, pero lo es.
Este informe es muy interesante y muestra algunos resultados sorprendentes de mediciones de rendimiento real ".
Y otros miembros del hilo apoyaron al comentarista: sí, en teoría, todas las iteraciones son equivalentes, pero en hardware real con optimizaciones reales, todo es completamente diferente. Al igual que el creador de la serie, Mike Judge, trabajó en el Valle en los años 80, cuando todas estas memorias caché L1 y la predicción de ramificaciones aún no eran particularmente pronunciadas, por lo que el comportamiento de la CPU estaba mucho más cerca del modelo ideal: este es el ejemplo de la serie.
Para mí, como dice el comentario, todo suena contradictorio, pero se volvió interesante descubrir si Richard podría tener razón. Por supuesto, interfiere con el hecho de que no se da todo el contexto en la serie: por ejemplo, no tenemos idea de cuántos datos iteraron. Por un lado, Richard trabajó para el gigante de Internet Hooli, donde probablemente tuvo que lidiar con millones de registros, pero por otro, era su primer día de trabajo y no podía ser arrojado de inmediato a millones. Planteamos la pregunta de esta manera: incluso si la búsqueda binaria es claramente mejor para la mayoría de las tareas en Hooli, ¿es probable que Richard haya tomado la decisión correcta para sus condiciones y que otros personajes se rían de él en vano, sin conocer el contexto?
Para entender, abrí un informe citado por Reddit. Según lo prometido, resultó ser interesante (no sorprendente, dado que este es un informe de Andrei Alexandrescu ), pero después de mirar una parte y hacer clic en el resto, no vi mediciones comparativas de búsqueda binaria y lineal allí.
Pero recordé que en nuestra conferencia DotNext, el mismo Alexandrescu también habló sobre el rendimiento. Abrí la versión de texto de su informe, que hicimos para Habr, y busqué la palabra "lineal". Resultó, entre otras cosas, que solo dio un ejemplo de un escenario curioso en el que esta búsqueda sería mucho más efectiva que una binaria (buscando elementos coincidentes de dos conjuntos en el caso de que estos conjuntos sean idénticos), pero este es un caso muy específico, para el cual no hay una conclusión general " la búsqueda lineal se subestima ".
Busqué en Google lo que dice Internet moderno sobre esto, pero básicamente encontró respuestas a Stack Overflow, donde simplemente escriben "usar binario, menos iteraciones". También hubo casos en los que intentaron comparar, pero tampoco me parecieron muy convincentes.
Aquí, por supuesto, la opción pide "tienes que hacerte un punto de referencia para ver todo tú mismo en un hardware real".
Pero si, durante todas mis visitas a DotNext, aprendí algo de dos Andreevs (Alexandrescu y Akinshina ) conscientes del rendimiento, es una comprensión de la frecuencia con la que las personas evalúan incorrectamente y cuánto no tienen en cuenta. Por lo tanto, tengo poca confianza en las publicaciones aleatorias de Internet con puntos de referencia, pero para mí aún más bajo.
Afortunadamente, hay personas en Habr que entienden mucho más que yo (por ejemplo, el mismo Andrey DreamWalker Akinshin, quien escribió un libro completo sobre benchmarking). Por lo tanto, si comprende el tema, cuéntenos en los comentarios cómo es realmente todo. ¿A qué tamaño de datos puede un enfoque lineal seguir siendo una buena opción? ¿Qué tan probable es que Richard haya hecho todo bien, incluso si él mismo no está listo para defenderlo?
Y si no hay comentaristas conocedores, tendré que conectar Akinshin a la batería en el próximo DotNext y hacer el punto de referencia.