¿Por qué tanta diferencia de tiempo de ejecución para el mismo algoritmo?

Hice la entrevista problema callejero similitud de cadena . Inicialmente hice esto en Python. Esto me dio un error de límite de tiempo excedido para los últimos 5 casos de prueba. Luego probé el mismo en Java y la solución fue aceptada. La diferencia horaria entre las versiones de Java y Python para los últimos 5 casos de prueba fue muy alta, pero Python supera a Java para los primeros 5 casos de prueba. ¿Por qué es así?

La longitud de la cuerda puede llegar hasta 100000.

stringsim.py

N=int(raw_input())
while N!=0:
    rootstr=[i for i in raw_input()]
    solution=0
    for i in xrange(len(rootstr)):
        for j in xrange(i,len(rootstr)):
            if(rootstr[j-i]==rootstr[j]):solution+=1
            else:break
    print solution
    N-=1

Solution.java:

class Solution{
    public static void main(String[] args) {
    java.util.Scanner sc=new java.util.Scanner(System.in);
    int N=sc.nextInt(),sol;
    while(N--!=0){
        sol=0;
        char[] s=sc.next().toCharArray();
        for(int i=0;i<s.length;i++){
            for(int j=i;j<s.length;j++){
                if(s[j]==s[j-i]) sol++;
                else break;
            }
        }
        System.out.println(sol);
    }
    }
}
Tiempo de ejecución para java:
1 Éxito 0.172387
2 Éxito 0.172177
3 Éxito 0.172185
4 Éxito 0.172178
5 Éxito 0.263904
6 Éxito 2.82661
7 Éxito 4.66869
8 Éxito 4.83201
9 Éxito 1.36585
10 Éxito 1.02123

Para python:
1 Éxito 0.081229
2 Éxito 0.081047
3 Éxito 0.081032
4 Éxito 0.081015
5 Éxito 0.910672
6 Límite de tiempo excedido. 16.1818
7 Límite de tiempo excedido. 16.2357
8 Límite de tiempo excedido. 16.2001
9 Límite de tiempo excedido. 16.2408
10 Límite de tiempo excedido. 16.1831
Respuesta 1

Estoy de acuerdo con el comentario de iccthedral: el Java JIT puede ser una posible razón por la cual Python es más rápido para las primeras entradas pequeñas. Para verificar esto, invierta el orden de entrada (para que las entradas grandes sean lo primero), ejecútelo para todas las entradas en el mismo proceso y mida el tiempo nuevamente para cada entrada individual. Si Python es lento en ese caso para las últimas entradas (pequeñas), se confirma la presunción.

Otra forma de verificarlo es agregar las entradas pequeñas al final también (manteniéndolas también al principio), y ver cuánto tiempo le lleva a Java ejecutar todo. Si el delta es mucho mayor que el tiempo de ejecución solo para las entradas pequeñas, se confirma la presunción.

El JIT de Java compila el código de bytes de Java al código de máquina (que la CPU puede ejecutar directamente y muy rápidamente). Pero solo se convierten esos métodos Java en los que Java pasa mucho tiempo ejecutándolos. (Esto se debe a que la conversión de todos los métodos a código de máquina sería lenta y el código de máquina resultante necesitaría demasiada memoria). Entonces, cuando se inicia el proceso de Java, comienza a ejecutar todos los métodos como código de bytes, mide cuánto tiempo se gasta en cada y una vez que se alcanza un umbral para un método, utiliza el JIT para compilar ese método en el código de máquina. Después de eso, el método se ejecuta mucho más rápido. Sin embargo, al comienzo de la ejecución del proceso, todos los métodos son lentos y, durante un corto período de tiempo, el proceso Java se vuelve aún más lento, porque está ocupado ejecutando el JIT.

Es probable que esto esté sucediendo en su caso: cuando Python haya terminado de encontrar la respuesta a los problemas simples, Java todavía está ejecutando los códigos de bytes o el JIT para compilar los códigos de bytes en el código de máquina. Pero eventualmente Java se pondrá al día, porque el código de la máquina es mucho más rápido.

Respuesta: 2

Estoy comenzando una clase de programación Java en UCSD la próxima semana y estoy tratando de prepararme durante el fin de semana. Hay una biblioteca llamada objectdraw.jar que viene con el libro que usaremos para nuestra clase ...

Estoy comenzando el desarrollo web con JSP, y he estado trabajando en mi aplicación por un tiempo. Tengo una clase de registro personalizada, que está en mi biblioteca personal. No quiero exportar la biblioteca a un ...

He escrito un programa que "compra" y "vende" bitcoin, aunque mi función de compra está dando resultados matemáticos incorrectos. En mi programa, tengo $ 20000 (doble USD) y bitcoin (que vale $ 4000. Todos ...

Supongo que no hay absolutamente ninguna manera de hacer algo como: Clase c = Class.forName ("Procesador <Entero, Cadena>"); en Java (donde definí el procesador previamente, por supuesto).