elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: Guía rápida para descarga de herramientas gratuitas de seguridad y desinfección.


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java (Moderadores: Debci, Leyer)
| | | |-+  Duda a nivel de optimizacion, con página "acepta el reto"
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Duda a nivel de optimizacion, con página "acepta el reto"  (Leído 205 veces)
kraiked

Desconectado Desconectado

Mensajes: 22


Ver Perfil
Duda a nivel de optimizacion, con página "acepta el reto"
« en: 8 Diciembre 2017, 00:18 »

Hola, he hecho un reto de la página acepta el reto, exactamente este: https://www.aceptaelreto.com/problem/statement.php?id=364

Y entrego mi programa pero la duda a es a nivel de optimización, a mi me sale entorno a 0.3 segundos, y si miro las estadísticas de otras personas ves tiempos de 0.012s, 0.016s.... en torno a 25 veces más rápido, y yo por mucho que mire mi código no veo dónde se podría optimizar para acercarme algo a sus resultados.

Código:
public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String texto;
       
       
       
        do {

            texto = sc.nextLine();

            if (!texto.equals("FIN")) {
               
                int tamanio = texto.length();
                String cadenaSalida = "";
               
                for(int i = 0; i < tamanio; ++i)
                    cadenaSalida += cifrar(texto.charAt(i));
               
                System.out.println(cadenaSalida);
            }

        } while (!texto.equals("FIN"));

    }
   
    private static String cifrar(char letra){
       
        switch (letra) {
            case 'A':
                return "B";
            case 'B':
                return "C";
            case 'C':
                return "D";
            case 'D':
                return "E";
            case 'E':
                return "F";
            case 'F':
                return "G";
            case 'G':
                return "H";
            case 'H':
                return "I";
            case 'I':
                return "J";
            case 'J':
                return "K";
            case 'K':
                return "L";
            case 'L':
                return "M";
            case 'M':
                return "N";
            case 'N':
                return "O";
            case 'O':
                return "P";
            case 'P':
                return "Q";
            case 'Q':
                return "R";
            case 'R':
                return "S";
            case 'S':
                return "T";
            case 'T':
                return "U";
            case 'U':
                return "V";
            case 'V':
                return "W";
            case 'W':
                return "X";
            case 'X':
                return "Y";               
            case 'Y':
                return "Z";   
            case 'Z':
                return "A";
            default:
                return " ";

        }

    }

Entonces por eso os consultaba, ya que no se donde puede estar el punto para que haya tanta diferencia.

Un saludo


En línea

NEBIRE


Desconectado Desconectado

Mensajes: 748


Ver Perfil
Re: Duda a nivel de optimizacion, con página "acepta el reto"
« Respuesta #1 en: 8 Diciembre 2017, 19:21 »

Hay varios quids a los que atender...

De entrada el bucle priuncipal no está óptimamente planteado.
Verás si haces un bucle 'Mientras X', es una redundancia inútil, preguntar acto seguido lo mismo Si x luego...
Piensa en un condicional como un bucle de un solo ciclo, si se cumple se entra y se ejecuta 1 vez y si no, no... un bucle persé es lo mismo, solo que permite entrar muchas más veces retornando al origen.

Tu bucle debiera se rmejor así:

Código:
texto = sc.nextLine();
 Si  (!texto.equals("FIN")) luego
     Hacer
         ... todo el trabajo que realizas
         texto = sc.nextLine();
     Repetir mientras   (!texto.equals("FIN"))
Fin si
Y aún más ióptimo cuando un lenguaje admite en el bucle condcionarlo al comienzo:

Código:
texto = sc.nextLine();
 Hacer mientras  (!texto.equals("FIN"))
     ... todo el trabajo que realizas
     texto = sc.nextLine();
 Repetir

Luego, llamas múkltiples veces desde dentro del bucle a un rutina externa a la propia donde yace el bucle, cada llamada externa a otra función es una sobrecarga porque exige depositar en la pila el estado actual en dicha función, antes de llamar a la función (cifrar) y a su vez tras la llamada, volver a restablecer el estado en dicha función sacando los datos de la pila... y esto se hace por cada letra...
ergo... mete ese código dentro del bucle, no en una función aparte. Sólo con eso ganarás en velocidad.

Por último, aunque tu función "cifrar" es clara, no es nada óptima, esto no debe resolverse invocando a una función, desde el momento en que F=X, es deicr en que hay una asignación directa, lo correcto es meterlo en un array, ya que no requiere un cálculo complejo tal que con la misma entrada pudiera dar lugar a diferentes salidas...

Ergo genera una array, al inicio de tu aplicación donde se establezca la igualdad d ela asignación:

Array(0) = 65  /A
Array(1)= 66  /B
Array(2)= 67 /C
...
Array(25) = 90 //Z
Array(26) = 65 //A

Y ahora en tu código simplemente codificas para redirigir un valor a un índice correcto. Tu array podría llamarse Cifrar (para más inri)
   CadenaSalida += Cifrar(ValorASCII(Texto.CharEn(I))-65+dpz)
Esto es: debe tomarse el valor ASCII del caracter obtenido en: Texto.charEn(i)
Como "A", es el carácter 65º y nuestro array comienza en 0, le restamos 65 y como estmaos haciendo una codificación césar, el dpz, suma el valor a desplazar en este caso dpz=1, si en vez de 1, usas dpz la misma función te vale para codificar con diferentes valores.
Más eficaz aún sería si el array en vez de asignarse la "A" en el índice 0, se asignara en el propio indice 65, así se evitaría también la resta de -65 para cada carácter.
Así al inciio crea un array estático así:
Código:
Bucle para k desde 0 a 255
   ArrayCifrado(k) = k
Fin bucle
Que es una tabla ASCII, es decir cada índice contiene el código de cáracter de la tabla ASCII, ArrayCifrado(65) = 65, qeu es el código de la letra "A".
Todavía queda ajustar cuando excede la suma del desplazamiento. en el previo yo he provisto un índice 26 par ala "A" cuando la letra a codfificar fuera la "Z", pero si el desplazamiento fuera mayor de 1, necesitaría un indice 27 y contener la "B", etc... mejor que eso es ver si el ídnice supera el límite y en tal caso 'modular'...
indice = ASCII(Texto.CharEn(i)) + dpz
Si indice> 90 luego
   indice = ((indice modulo 90) + 65)
Fin si
Cadenasalida += CharFromASCII(ArrayCifrado(indice)) //CVharFromASCII, sería la función opuesta a ASCII, es decir le das un código ASCII y te devuelve el carácter correspondiente.

Y por último tu código peca de ineficiencia en la concatenación de la cadena que vas generando...
CadenaSalida += ...
Cada vez que concatenas un carácter o un texto a otro, requiere construir otra cadena del tamaño adecuado (del tamaño exacto que se reclama tendrá), y copiar allí el texto original y luego el otro que se concatena, y luego destruir la cadena previa, esto es, supone buscar espacio libre en la memoria, reservarlo, copiar y luego apuntar la dirección de esa memoria a la variable cuyo nombre se usa...
El modo óptimo es que si se puede precalcular el tamaño que tendrá el texto al final, se genere de una sola vez una cadena de texto de ese tamaño (aunque sea repleto de espacios) y luego en vez de concatenar se va alterando el contenido del carácter en la posición x...

Con todos estos consejos llevados a cabo, ten por seguro que incluso vas a superar los valores que tu señalas como más rápidos que el tuyo...


En línea

kraiked

Desconectado Desconectado

Mensajes: 22


Ver Perfil
Re: Duda a nivel de optimizacion, con página "acepta el reto"
« Respuesta #2 en: 13 Diciembre 2017, 23:49 »

Muchas gracias por responder, he estado jugando con algunos consejos y la verdad que ha merojado :).

Y yo que pensaba que mi codigo era aceptable, pero vamos aun me queda mucho por aprender :)
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines