¿Hay buenos métodos para hacer esto? Puedo encontrar documentos con algoritmos, pero generalmente no muestran sus resultados computacionales con los mismos conjuntos de problemas y el año de publicación de dos documentos suele ser diferente, por lo que lo más probable es que utilicen equipos diferentes para resolver los problemas.
Editar: por problema, me refiero también al tamaño específico del problema, el uso de memoria y otras características del problema.
Con respecto a la diferencia en la configuración, generalmente los documentos SOTA "bien aclamados" no tienen estos problemas. Al menos eso es lo que he notado mayormente en mi campo.
Si ese es el caso, sugiero hacer un pequeño estudio dentro del documento que cubra todos los resultados en los diferentes entornos. (Por favor, corríjame si me equivoco aquí).
Creo que tienes un malentendido sobre la eficiencia del algoritmo y su estudio. Un buen curso de algoritmos y estructuras de datos debería corregir eso.
Asumiré aquí que en realidad te refieres a un algoritmo y no solo a un programa de computadora útil. No són la misma cosa. Algunos programas útiles, si bien pueden contener algoritmos, tienen su desempeño dominado por otras preocupaciones no algorítmicas. De hecho, el rendimiento allí podría estar vinculado a un tipo particular de conjunto de datos para el cual las pequeñas desviaciones dan como resultado un rendimiento muy diferente.
Los algoritmos se juzgan buenos o malos según las preocupaciones teóricas, no ejecutándolos en datos de muestra. Las medidas teóricas los hacen independientes del hardware dentro de ciertos límites. Un algoritmo rápido se ejecutará más rápido que un algoritmo lento en diferentes computadoras que tengan una arquitectura similar (consulte las advertencias a continuación). Algunos algoritmos (clasificación de burbujas) siempre son malos. Otros siempre son mejores (clasificación por selección). Aún otros son "siempre" buenos (clasificar por fusión, pero vea las advertencias).
Entonces, la idea de "equipo diferente" es una pista falsa, siempre que el equipo tenga una arquitectura similar.
Advertencias, y hay bastantes.
Algunos algoritmos requieren mucha memoria (clasificación rápida en un conjunto grande) porque son altamente recursivos. Si una máquina no tiene suficiente memoria rápida , la clasificación rápida de un gran conjunto de datos estará limitada por la eficiencia independiente del sistema de memoria.
Algunos algoritmos "lentos" funcionan bien en conjuntos de datos pequeños y pueden preferirse a los algoritmos "rápidos" si se espera que el conjunto de datos sea pequeño. Pero estas cosas son conocidas y normalmente se incorporan al software de trabajo. Por ejemplo, en la ordenación rápida una vez que una "división" da como resultado un segmento de tamaño 10 aproximadamente, un algoritmo cuadrático se hará cargo de completar la ordenación. Pero eso es solo un buen diseño de software, y utiliza resultados teóricos conocidos para las diversas opciones.
Sin embargo, si la arquitectura de una máquina cambia drásticamente (como una GPU difiere de una CPU), entonces el juego cambia y algunos algoritmos que son rápidos en uno serán más lentos en el otro. Por ejemplo, aún clasificando cosas, si una arquitectura hace comparaciones "libres", entonces se preferirá en esa arquitectura un algoritmo que use muchas comparaciones, en lugar de reordenamientos . Pero, nuevamente, esto se basa en las consideraciones teóricas que miden los diversos tipos de operaciones requeridas por un algoritmo.
Entonces, para responder a su pregunta, debe observar las medidas teóricas, y estas normalmente las proporcionan los autores.
Otra advertencia. Hay algunos problemas aplicados que están bastante mal estructurados y no han cedido (todavía) al análisis teórico asumido anteriormente. Tal vez un poco de caos está involucrado. Para estos, algunas medidas empíricas podrían ser necesarias en este momento. Pero algunos de esos tipos de problemas también pueden llevar a las personas a inventar nuevas arquitecturas que puedan manejar los problemas de manera eficiente. Pero, el mismo tipo de problema también lleva a los teóricos a inventar nuevos algoritmos que sean susceptibles de un análisis general de eficiencia. Pero, lo más probable es que los resultados se informen en términos teóricos, no en tiempos en hardware específico. Esto es probablemente lo que estás viendo. Y, con suerte, parte de su análisis incluye límites sobre cuándo se puede esperar que el algoritmo se comporte bien.
GreyLiteratura
jon custer
usuario1271772
davidbak