Algunas preguntas de clasificación

Question

He encontrado una manera que mejora (según lo que he probado) en el algoritmo de la solución rápida más allá de lo que ya se ha hecho. Estoy trabajando en probarlo y luego quiero correr la voz sobre eso. Sin embargo, agradecería algo de ayuda con algunas cosas. Asi que aqui están mis preguntas. Todo mi código está en C++ por cierto.

1. Uno de los géneros que he estado comparando con mi quicksort es el std :: sort de C++ Standard Library. Sin embargo, parece ser extremadamente lento. Solo estoy ordenando matrices de enteros y largos, pero parece ser alrededor de 8-10 veces más lento que mi quicksort y una solución estándar de Bentley y McIlroy (y tal vez Sedgewick). ¿Alguien tiene alguna idea de por qué es tan lento? El código que uso para el género es solo std :: sort (a, a + numelem); donde a es la matriz de longs o ints y numelem es la cantidad de elementos en la matriz. Los números son muy aleatorios, y he probado diferentes tamaños y diferentes cantidades de elementos repetidos. También probé qsort, pero es aún peor, como esperaba. Editar: Ignora esta primera pregunta: se ha resuelto.

2. Me gustaría encontrar más buenas implementaciones de solución rápida para comparar con mi solución rápida. Hasta ahora tengo una Bentley-McIlroy y también he comparado con la primera versión publicada de la conexión rápida de doble pivote de Vladimir Yaroslavskiy. Además, planeo portar timsort (que es un tipo de combinación, creo) y el quicksort optimizado de doble pivote de la fuente jdk 7. ¿Qué otras implementaciones de quicksorts buenas conoces? Si no están en C o C++, podría estar bien, porque soy bastante bueno en portar, pero preferiría C o C++ si los conoces.

3. ¿Cómo recomendarías saber más sobre mis adiciones al quicksort? Hasta ahora, mi solución rápida parece ser significativamente más rápida que todas las demás soluciones rápidas contra las que la probé. La principal fuente de su velocidad es que maneja los elementos repetidos de manera mucho más eficiente que otros métodos que he encontrado. Erradica casi por completo el comportamiento del peor de los casos sin agregar mucho tiempo en la comprobación de elementos repetidos. Lo publiqué sobre los foros de Java, pero no obtuve respuesta. También intenté escribirle a Jon Bentley porque estaba trabajando con Vladimir en su conexión rápida de doble pivote y no obtuve respuesta (aunque no me sorprendió demasiado). ¿Debo escribir un artículo al respecto y ponerlo en arxiv.org? ¿Debo publicar en algunos foros? ¿Hay algunas listas de correo a las que debo publicar? He estado trabajando en esto desde hace un tiempo y mi método es legítimo. Tengo cierta experiencia con la publicación de investigaciones porque soy un candidato a doctorado en física computacional. ¿Debo intentar acercarme a alguien en el departamento de Ciencias de la Computación de mi universidad? Por cierto, también he desarrollado una conexión rápida de doble pivote diferente, pero no es mejor que mi quicksort de un solo pivote (aunque es mejor que la serie de doble pivote de Vladimir con algunos conjuntos de datos).

Realmente aprecio su ayuda. Solo quiero agregar lo que pueda al mundo de la informática. No estoy interesado en patentar esto o algo absurdo como ese.

Answer 1

Si tiene confianza en su trabajo, definitivamente trate de discutirlo con alguien que sepa de su universidad lo antes posible. No es suficiente mostrar que su código se ejecuta más rápido que otro procedimiento en su máquina. Tienes que demostrar matemáticamente cualquier ganancia de rendimiento que asegures haber logrado mediante el análisis de tu algoritmo. Yo diría que lo primero que debe hacer es asegurarse de que los dos algoritmos que está comparando se implementen y compilen de manera óptima; es posible que se esté engañando a sí mismo aquí. La probabilidad de que un individuo logre una mejora tan marcada en un método de clasificación tan importante sin tener un conocimiento completo de sus variantes aceptadas simplemente parece minúscula. Sin embargo, no dejes que te desanime. Debería ser interesante de todos modos. ¿Estaría dispuesto a publicar el código aquí? ...Además, dado que el quicksort es especialmente vulnerable a los escenarios del peor de los casos, las pruebas que elija ejecutar pueden tener un gran efecto, al igual que la elección de los pivots. En general, diría que cualquier conjunto de datos con una gran cantidad de elementos equivalentes o uno que ya esté altamente clasificado nunca es una buena opción para el servicio rápido, y ya existen formas bien conocidas de combatir esa situación y mejores métodos de clasificación alternativos. .

Answer 2

Si realmente ha hecho un gran avance y tiene las matemáticas para demostrarlo, intente publicarlo en el Journal of the ACM. Definitivamente es una de las revistas más prestigiosas para la informática.

El segundo mejor sería uno de los IEEE journals como Transactions on Software Engineering.