Comparando algoritmos en Java: Recortes de revista

Comparando algoritmos en Java: Recortes de revista

Cambiando un poco de temática, hoy os traigo un artículo práctico sobre cómo realizar la comparativa de varios algoritmos en Java. El tema surgió así, navegando por Internet me topé con un problema que decía lo siguiente:

Suponga que quiere escribir una nota realizando recortes de una revista y uniendo estos recortes. Antes de hacer esto, le gustaría saber si es posible escribir su nota usando una determinada revista.

Escriba una función que tenga como entrada dos cadenas de caracteres; la primera de ellas será la nota que deseamos escribir y la segunda cadena de caracteres será el texto completo de la revista que poseemos. La función debe determinar si la nota puede ser escrita con la revista dada.

Solución 1
Así a bote pronto, la solución más sencilla y la primera que se me ocurrió consistía básicamente en contabilizar el número de caracteres que teníamos en la nota y en la revista y comparar si todos los que teníamos en la nota se encontraban en la revista. En todo el ejercicio out será la variable que nos dirá si se puede implementar la nota usando la revista dada y la variable que devuelve el método es el tiempo que invierte, básico para luego contabilizar el tiempo de ejecución. Este primer algoritmo lo implementé así:

public double checkNote(String note, String magazine){
		//
		long start_time = System.nanoTime();
		out = true;
		
		//This vector saves the number of times that every letter appears in the magazine.
		int[] reps_magazine = new int[65535];
		
		//The same for the ransom note
		int[] reps_note = new int[65535];
		
		//If the number of letters of ransom note is higher than the number of letters of magazine can't write the note
		if (note.length() > magazine.length()){
			out = false;
		}else{
			//In another case
			//We go through the whole magazine and we write the number of times each letter in reps_magazine
			for (int i=0; i<magazine.length(); i++){
				reps_magazine[magazine.codePointAt(i)]++;
			}
			
			//The same for the ransom note
			for (int i=0; i<note.length(); i++){
				reps_note[note.codePointAt(i)]++;
			}
			//We compare the number of times for each letter in ransom note
			//and in magazine. If a letter appears more times in note than in magazine
			//break and out will be false. By that, we can't write the ransom note with the
			//letters of the magazine
			for (int i=0; i<65535; i++){ 				if (reps_note[i]>reps_magazine[i]){
					out = false;
					break;
				}
			}
		}
		long end_time = System.nanoTime();
		time= (end_time - start_time)/1e6;	
		return time;
	}

Sencillo, ¿verdad? Pero estaréis pensando que vaya método más poco eficiente. Es cierto, recorrer toda la revista, que suelen ser extensas para chequear una nota de unos cuantos caracteres, es poco inteligente.

Solución 2:
Para solucionar este problema, se me ocurre otro algoritmo. Ya no recorreríamos la revista entera en todo caso, sino que recorreríamos la nota entera, para obtener el número de veces que aparecía cada carácter.
A continuación, recorríamos la nota carácter a carácter (otra vez) e iríamos buscando en la revista los caracteres que necesitáramos. En caso de que un carácter de la nota no lo tuviésemos en la revista o lo tuviésemos menos veces, abandonaríamos nuestro algoritmo ya que no sería posible escribir la nota. Aquí tenéis la implementación:

 public double checkNote2 (String note, String magazine){
		//
		long start_time = System.nanoTime();
		out = true;
		int j = 0;
		
		//The same for the ransom note. 2^16 bits for Unicode 
		int[] reps_note = new int[65535];
		
		//If the number of letters of ransom note is higher than the number of letters of magazine can't write the note
		if (note.length() > magazine.length()){
			out = false;
		}else{
			//Other approximation more complex. 
			
			//This vector saves the number of times that every letter appears in the note.
			for (int i=0; i<note.length(); i++){
				reps_note[note.codePointAt(i)]++;
			}
			
			
			//Now, we go throught the note and by each letter, we check that it's appear the same number of times or more in the magazine.
			//If, we find a letter that appears more times in the note, we can't write the ransom note. 
			//This algorithm is more complex but it's better.
			int i=0;
			while (i<note.length() && out == true){  				int unicode = note.codePointAt(i); 				while(reps_note[unicode]>0 && out == true){
					while(j <magazine.length()){ 						if (note.charAt(i) == magazine.charAt(j)){ 							reps_note[unicode]--; 					        if (reps_note[unicode] == 0){ 					        	j=0; 					        	break; 					        } 						} 					    j++; 					} 					if (j> (magazine.length()-1) && reps_note[unicode]>0){
						out= false;
					}
				}
				i++;
			}
		}
		long end_time = System.nanoTime();
		time= (end_time - start_time)/1e6;	
		return time;
	}

Solución 3
Pero dándole vueltas al coco, quería pensar una solución especialmente diseñada para notas cortas o muy cortas que ni siquiera contase el número de caracteres de la nota sino que directamente fuera a compararla con la revista si el carácter dado aparecía. Este algoritmo es muy débil para notas largas ya que se basa en obtener el primer carácter de la nota e ir comparando con toda la revista hasta que lo encuentra. Os estaréis preguntando que si no vamos marcando en la revista las letras usadas, no tendríamos manera de averiguar si una letra ha sido usada antes o no, para ello he recurrido a un vector de booleanos. Aquí lo tenéis:

 public double checkNote3 (String note, String magazine){
		long start_time = System.nanoTime();
		out = true;
		boolean [] magletters = new boolean [magazine.length()];
			
		//I create a boolean array. It's all false but when you use a letter, the position of this 
		//changes a true and you can't use it again.
		int i=0;
		int j=0; 
			while (i<note.length() && j<magazine.length() && out ==true){; 				if (note.charAt(i) == magazine.charAt(j) && magletters[j]==false){ 					magletters[j]=true; 					i++; 					j=0; 				}else{ 					j++; 				}	 				if (j>=(magazine.length())){
					out = false;
				}
			}
			long end_time = System.nanoTime();
			time= (end_time - start_time)/1e6;
	
			return time;
	}

Finalmente, cómo habéis podido ver he ido colocando variables para medir el tiempo en ms que tarda cada uno de los algoritmos que he implementado. También para hacerlo más independiente de posibles picos de CPU he realizado 50 iteraciones. También os dejo el código tanto del método main como de un método creado para generar cadenas de caracteres aleatorias.

public static String generateSessionKey(int length){
		String alphabet = 
		        new String("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzºª!@·#$~%&¬?¿'¡^`[]*+¨´{}ÇçñÑ-_:.;,<>"); 
		int n = alphabet.length(); 

		String result = new String(); 
		Random r = new Random(); 

		for (int i=0; i<length; i++) 
		    result = result + alphabet.charAt(r.nextInt(n)); 

		return result;
		}
	
	public static void toCadena(Note note){
		String out;
		out = "The time has been of: " + note.time + " and the result has been:  " + note.out;
		System.out.println(out);
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		//An object for each algorithm
		final Note note1 = new Note();
		final Note note2 = new Note();
		final Note note3 = new Note();
		
		//Parameters
		int length_magazine = 4000;
		int num_iter = 50;
		int step = 20;
		
		//Aux Variables
		double time1 = 0, time2 = 0, time3 = 0;
		int cont1_false = 0;
		int cont1_true = 0;
		int cont2_false = 0;
		int cont2_true = 0;
		int cont3_false = 0;
		int cont3_true = 0;
		double time_iter1 = 0;
		double time_iter2 = 0;
		double time_iter3 = 0;
		
		double [][] times1 = new double [length_magazine/step-1][num_iter];
		double [][] times2 = new double [length_magazine/step-1][num_iter];
		double [][] times3 = new double [length_magazine/step-1][num_iter];
		
		double [] mean_times1 = new double [length_magazine/step-1];
		double [] mean_times2 = new double [length_magazine/step-1];
		double [] mean_times3 = new double [length_magazine/step-1];
		
		String random = generateSessionKey(length_magazine);
		
		for (int i=step; i<random.length(); i = step + i){
			random = generateSessionKey(length_magazine);
			String note_random = generateSessionKey(i);
			for (int j=0; j<num_iter; j++){	
				time1 = note1.checkNote(note_random, random);
				time_iter1 = time_iter1 + time1;
				times1[(i/step)-1][j]= time1;
				if (note1.out == false){
					cont1_false++;
				}else{
					cont1_true++;
				}
				time2= note2.checkNote2(note_random, random);
				time_iter2 = time_iter2 + time2;
				times2[(i/step)-1][j]= time2;
				if (note2.out == false){
					cont2_false++;
				}else{
					cont2_true++;
				}
				time3 =note3.checkNote3(note_random, random);
				time_iter3 = time_iter3 + time3;
				times3[(i/step)-1][j]= time3;
				if (note3.out == false){
					cont3_false++;
				}else{
					cont3_true++;
				}
				
				toCadena(note1);
				toCadena(note2);
				toCadena(note3);
				System.out.println("------------------------------------NEW ITERATION: " + j + "---------------------------------------");
			}
			mean_times1[(i/step)-1]= time_iter1/num_iter;
			time_iter1=0;
			mean_times2[(i/step)-1]= time_iter2/num_iter;
			time_iter2=0;
			mean_times3[(i/step)-1]= time_iter3/num_iter;
			time_iter3=0;
			System.out.println("------------------------------------NEW DIMENSION: " + i + "------------------------------------");
		}
		
		
		double time_med1 = time1/(num_iter*(random.length()/step - 1));
		double time_med2 = time2/(num_iter*(random.length()/step - 1));
		double time_med3 = time3/(num_iter*(random.length()/step - 1));
		
	    System.out.println("----------------------------------TRUE AND FALSE------------------------------------------");
	    System.out.println("First algorithm: " );
	    System.out.println("Number of true: " + cont1_true);
	    System.out.println("Number of false: " + cont1_false);
	    System.out.println("Second algorithm: " );
	    System.out.println("Number of true: " + cont2_true);
	    System.out.println("Number of false: " + cont2_false);
	    System.out.println("Third algorithm: " );
	    System.out.println("Number of true: " + cont3_true);
	    System.out.println("Number of false: " + cont3_false);
	
	    System.out.println("-------------------------FINAL CONCLUSIONS-----------------------------------------------");
	    for (int i= 0; i<(length_magazine/step-2); i++){
	    	int numcharacter = (i+1)*step;
	    	
	    	System.out.println("Num_characters_ransom_note: " + numcharacter);
	    	if (mean_times1[i]<mean_times2[i]){
	    		if (mean_times1[i]<mean_times3[i]){
	    			System.out.println("Winner is: Algorithm 1");
	    		}else{
	    			System.out.println("Winner is: Algorithm 3");
	    		}
	    	}else{
	    		if (mean_times2[i]<mean_times3[i]){
	    			System.out.println("Winner is: Algorithm 2");
	    		}
	    		else{
	    			System.out.println("Winner is: Algorithm 3");
	    		}
	    	}
	    	
	    }
	    
	    System.out.println((time_med1));
		System.out.println((time_med2));
		System.out.println((time_med3));
	
	}

Y para concluir os enseño las gráficas obtenidas con los siguientes parámetros:

  • Longitud revista: 4000
  • Longitud nota: 20 a 4000 de 20 en 20
  • Número de iteraciones por caso: 50

big_graphic

big_graphic

Esta gráfica por si sólo nos sirve para observar que el último algoritmo, como preveíamos, es un auténtico desastre conforme la longitud de la nota va creciendo. El algoritmo 1 y 2 son muy parejos durante todo el experimento. Ahora centrémonos en el escenario más típico, notas muy pequeñas comparada con la extensión de la revista. Tenemos la siguiente gráfica:

small_notes

Vemos que incluso el tercer algoritmo es más eficiente que ninguna para notas muy pequeñas (hasta 100 caracteres con respecto a 4000 de longitud de revista). Fijaros lo que da de sí un simple ejercicio y esto puede seguir creciendo, para ello, no dudéis en mandarme vuestras implementaciones para solucionar este sencillo problema.

Y por supuesto, para hacerlo todo más sencillo para vosotros, tenéis todo el código disponible en github ;)

Previous Los secretos del aprendizaje y la rápida memorización
Next Una revisión del negocio de la imprenta online

About author

Vicente
Vicente 88 posts

(Cofundador) Ingeniero Telecomunicación. Interesado en las últimas novedades tecnológicas por las que desde muy temprana edad, sentí una gran atracción. Dentro del inmenso mundo de las telecomunicaciones, siento predilección por la ingeniería de redes. Experimentado desarrollador Java.

You might also like

Tecnologia & Ciencia 1Comments

[Evento] Introducción a Appcelerator Titanium y conexión con un backend en PHP

El día 5 de setiembre de 2014 tendré la oportunidad de hablar en el grupo de PHP Valencia acerca de como  crear una app móvil con el entorno de desarrollo

Desarrollo 2 Comentarios

DART, ¿el fin de JavaScript?

Probablemente sí. Pero todavía muchos piensan que no. Hubo polémica al respecto la semana pasada en el Qcon 2012 de Londres. Dart es, de hecho, un nuevo lenguaje que ha venido para quedarse,

Desarrollo 1Comments

Cómo detectar un dispositivo móvil en Django con Mobi

Cuando estamos programando una aplicación web es probable que necesitemos distinguir si el usuario se conecta desde su dispositivo móvil (tablet, smartphone, iphone, etc) o desde un PC. En función

0 Comentarios

Ningún comentario... todavía ;)

Tú puedes ser el primero en comentar este artículo!

Deja un comentario