Algunas preguntas de clasificación

Question

Me han encontrado una manera que mejore (por lo que he probado) en el algoritmo quicksort más allá de lo que ya se ha hecho. Estoy trabajando en probarlo y luego quiero correr la voz sobre él. Sin embargo, le agradecería un poco de ayuda con algunas cosas. Asi que aqui están mis preguntas. Todo el código está en C ++ por cierto.

1. Uno de los géneros que he estado comparando a mi ordenación rápida es la std :: sort de la Biblioteca C ++ estándar. Sin embargo, parece ser extremadamente lento. Sólo estoy ordenar matrices de enteros y anhela, pero parece ser alrededor de 8-10 veces más lento que tanto mi ordenación rápida y una clasificación rápida estándar por Bentley y McIlroy (y tal vez Sedgewick). ¿Alguien tiene alguna idea de por qué es tan lenta? El uso de código I para la especie es sólo std :: sort (a, a + numelem); donde a es la matriz de largos o ints y numelem es el número de elementos de la matriz. Los números son muy aleatoria, y me han tratado diferentes tamaños, así como diferentes cantidades de elementos repetidos. También probé qsort, pero es aún peor, ya que esperaba. Editar:. Ignorar esta primera pregunta - que ha sido resuelto

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

3. ¿Cómo recomendaría salir la palabra acerca de mis adiciones a la ordenación rápida? Hasta ahora, mi clasificación rápida parece ser significativamente más rápido que todos los demás quicksorts que yo he probado en contra. La principal fuente de su velocidad es que se trata elementos repitió mucho más eficaz que otros métodos que he encontrado. Se elimina casi por completo el comportamiento peor caso sin añadir mucho tiempo en la comprobación de elementos repetidos. He publicado al respecto en los foros de Java, pero no obtuvo respuesta. También probé escrito a Jon Bentley porque estaba trabajando con Vladimir en su clasificación rápida de doble pivote y no conseguí respuesta (aunque yo no estaba terriblemente sorprendido por esto). Debería escribir un artículo sobre él y lo puso en arxiv.org? Debería publicar en algunos foros? ¿Hay algunas listas de correo a las que debo publicar? He estado trabajando en esto durante algún tiempo y mi método es de fiar. Tengo algo de experiencia con la publicación de investigaciones porque soy un estudiante de doctorado en física computacional. ¿Debo intentar acercarse a alguien en el departamento de Informática de mi universidad? Por cierto, también he desarrollado una clasificación rápida de doble pivote diferente, pero no es mejor que mi clasificación rápida de un solo pivote (aunque es mejor que la clasificación rápida de doble pivote de Vladimir con algunos conjuntos de datos).

Realmente aprecio su ayuda. Sólo quiero añadir lo que pueda para el mundo de la informática. No estoy interesado en patentar este o cualquier cosa absurda como esa.

Answer 1

Si usted tiene confianza en su trabajo, sin duda prueba a discutir con alguien con conocimientos en la universidad tan pronto como sea posible. No es suficiente para demostrar que su código se ejecuta más rápido que otro procedimiento en su máquina. Tienes que demostrar matemáticamente cualquiera que sea la ganancia de rendimiento que afirman que han logrado a través de análisis de su algoritmo. Yo diría que lo primero que debe hacer es asegurarse de ambos algoritmos se están comparando se implementan y se compila de manera óptima - es posible que sólo se engañando a sí mismo aquí. La probabilidad de que un logro de tales una marcada mejora individual sobre un método de clasificación tan importante sin tener ya un conocimiento profundo de sus variantes aceptadas sólo parece minúsculo. Sin embargo, no deja que te desanime. Debe ser de todos modos interesante. ¿Usted estaría dispuesto a publicar el código aquí? ... Además, dado que la clasificación rápida es especialmente vulnerable a los peores escenarios, las pruebas que decide plazo pueden tener un efecto enorme, al igual que la elección de los pivotes. En general, diría que cualquier conjunto de datos con un gran número de elementos equivalentes o uno que ya está altamente ordenados no es una opción buena para la clasificación rápida - y ya hay maneras conocidas de combatir esa situación, y los métodos de clasificación mejores alternativas .

Answer 2

Si realmente ha hecho un gran avance y tienen la matemáticas para demostrarlo, usted debe tratar de lograr que se publicó en el Diario de la ACM . Es, definitivamente, una de las revistas más prestigiosas de la informática.

El segundo mejor sería uno de los IEEE revistas como < a href = "http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=32" rel = "nofollow noreferrer"> Las transacciones en Ingeniería de Software .