(Dis) Demostrando que un algoritmo funciona más rápido que otro debido al lenguaje interno

Question

Para un proyecto en la universidad, tuvimos que implementar algunos algoritmos diferentes para calcular las clases de equivalencia cuando se les dio un conjunto de elementos y una colección de relaciones entre dichos elementos .

Fuimos instruidos para implementar, entre otros, el algoritmo Union-Find y sus optimizaciones (Union by Depth, Size). Por accidente (haciendo algo que pensé que era necesario para la corrección del algoritmo) descubrí otra forma de optimizar el algoritmo.

No es tan rápido como Union By Depth, pero está cerca. No pude entender por qué fue tan rápido como lo fue, así que consulté a uno de los asistentes de la docencia que tampoco pudo descifrarlo.

El proyecto fue en Java y las estructuras de datos que utilicé fueron basadas en matrices sencillas de números enteros (el objeto, no el int) Más tarde, en la evaluación del proyecto, me dijeron que es probable que tuviera algo que ver con 'Java almacenamiento en caché, pero no puedo encontrar nada en línea sobre cómo el almacenamiento en caché afectaría esto.

¿Cuál sería la mejor manera, sin calcular la complejidad del algoritmo, para demostrar o refutar que mi optimización es tan rápida debido a la forma de hacer las cosas de Java? Implementándolo en otro lenguaje (¿nivel inferior?) ¿Pero quién puede decir que el lenguaje no hará lo mismo?

espero sido claro,

gracias

Answer 1

La única manera es demostrar el peor de los casos (caso medio, etc) la complejidad del algoritmo.

Porque si no lo hace, que sólo podría ser consecuencia de una combinación de

• Los datos particulares
• El tamaño de los datos
• algún aspecto del hardware
• Algunos los aspectos de la implementación del lenguaje
• etc.

Answer 2

Si tiene acceso al código fuente, y el código fuente JDK está disponible, creo, puede navegar a través de él para encontrar los detalles de implementación relevantes.

Answer 3

¡En general es muy difícil realizar tal tarea en las máquinas virtuales modernas! Al igual que usted insinúa que realizan todo tipo de cosas a sus espaldas. Las llamadas a métodos se incorporan, los objetos se reutilizan. Etc. Un buen ejemplo es ver cómo los bucles triviales se compilan si obviamente no están realizando otra cosa que contar. O cómo una función de programación funcional está integrada o optimizada.

Además, tiene la dificultad de probar su punto en general en cualquier conjunto de datos. Un O (n^2) puede ser mucho más rápido que un algoritmo aparentemente más rápido, por ejemplo O (n). Dos ejemplos

1. El ordenamiento de burbuja es más rápido al ordenar una colección de datos casi ordenada que la clasificación rápida.
2. La clasificación rápida en el caso general, por supuesto, es más rápida.

En general, la notación de la gran O ignora deliberadamente las constantes que en una situación práctica pueden significar la vida o la muerte de su implementación. y esas constantes pueden haber sido lo que te golpeó. Por lo tanto, en la práctica 0.00001 * n ^ 2 (supongamos que el tiempo de ejecución de su algoritmo) es más rápido que 1000000 * n log n

Por lo tanto, el razonamiento es difícil dada la información limitada que proporciona.

Answer 4

Es probable que el compilador o la JVM hayan encontrado una optimización para su código. Puede intentar leer el bytecode generado por el compilador javac y deshabilitar la compilación JIT en tiempo de ejecución con la opción -Djava.compiler=NONE.