Scanning multi threads

di il
4 risposte

Scanning multi threads

Ho una lista di circa 100.000 stringhe e voglio inserirle in una Map<Integer,List<String> che mi permette in O(1) di accedere a tutte le parole della stessa dimensione. Per ottimizzare i tempi sto cercando di implementare una versione multithreading dato che con gli stream di java 8 non ci sono riuscito.
La mia idea è quella di utilizzare due threads, il primo che comincia a scannerizzare dall'inizio fino alla metà della lista, e l'altro dalla fine fino alla metà più uno.
Come dal main thread posso capire quando l'esecuzione di entrambi i threads si è conclusa??

Il codice è il seguente: (lista è la lista delle stringhe)

Map<Integer, List<String>> mappa = new HashMap<>();
		
		
		Runnable r1 = () -> {
			for(int i = lista.size()-1 ; i>(lista.size()/2)+1 ; i--){
				if(mappa.get(lista.get(i).length()) == null){
					mappa.put(lista.get(i).length(), new ArrayList<>(Arrays.asList(lista.get(i))));
				}
				else{
					mappa.get(lista.get(i).length()).add(lista.get(i));
				}
			}
		};
		
		Runnable r2 = () -> {
			for(int i = 0 ; i<=(lista.size()/2) ; i++){
				if(mappa.get(lista.get(i).length()) == null){
					mappa.put(lista.get(i).length(), new ArrayList<>(Arrays.asList(lista.get(i))));
				}
				else{
					mappa.get(lista.get(i).length()).add(lista.get(i));
				}
			}
			
		};
		
		new Thread(r1).start(); new Thread(r2).start();
	
Grazie e buon primo maggio

4 Risposte

  • Re: Scanning multi threads

    Forse con una piccola modifica ci sono riuscito, ovvero dopo la partenza dei threads, faccio si che il main thread cicli fin quando non terminano nel seguente modo:
    
          Thread t1 = new Thread(r1); 
    		Thread t2 = new Thread(r2);
    		
    		t1.start();
    		t2.start();
    		
    		while(true){
    			if(t1.getState() == State.TERMINATED && t2.getState() == State.TERMINATED) break;
    		}
    
    Da qui continuo la normale esecuzione del main thread.




    CODICE COMPLETO
    
    Map<Integer, List<String>> mappa = new HashMap<>();
    		
    		
    		Runnable r1 = () -> {
    			for(int i = lista.size()-1 ; i>(lista.size()/2) ; i--){
    				if(mappa.get(lista.get(i).length()) == null){
    					mappa.put(lista.get(i).length(), new ArrayList<>(Arrays.asList(lista.get(i))));
    				}
    				else{
    					mappa.get(lista.get(i).length()).add(lista.get(i));
    				}
    			}
    		};
    		
    		Runnable r2 = () -> {
    			for(int i = 0 ; i<=(lista.size()/2) ; i++){
    				if(mappa.get(lista.get(i).length()) == null){
    					mappa.put(lista.get(i).length(), new ArrayList<>(Arrays.asList(lista.get(i))));
    				}
    				else{
    					mappa.get(lista.get(i).length()).add(lista.get(i));
    				}
    			}
    			
    		};
    		
    		
    		Thread t1 = new Thread(r1); 
    		Thread t2 = new Thread(r2);
    		
    		t1.start();
    		t2.start();
    		
    		while(true){
    			if(t1.getState() == State.TERMINATED && t2.getState() == State.TERMINATED) break;
    		}
    		
    
  • Re: Scanning multi threads

    Paolovox ha scritto:


    		while(true){
    			if(t1.getState() == State.TERMINATED && t2.getState() == State.TERMINATED) break;
    		}
    
    Non serve, è inutile e "pesante" (è un loop continuo che consuma CPU). Per attendere la terminazione di un thread c'è il join()

    Paolovox ha scritto:


    
    Map<Integer, List<String>> mappa = new HashMap<>();
    		
    		
    		Runnable r1 = () -> {
    			for(int i = lista.size()-1 ; i>(lista.size()/2) ; i--){
    				if(mappa.get(lista.get(i).length()) == null){
    					mappa.put(lista.get(i).length(), new ArrayList<>(Arrays.asList(lista.get(i))));
    				}
    				else{
    					mappa.get(lista.get(i).length()).add(lista.get(i));
    				}
    			}
    		};
    		
    		Runnable r2 = () -> {
    			for(int i = 0 ; i<=(lista.size()/2) ; i++){
    				if(mappa.get(lista.get(i).length()) == null){
    					mappa.put(lista.get(i).length(), new ArrayList<>(Arrays.asList(lista.get(i))));
    				}
    				else{
    					mappa.get(lista.get(i).length()).add(lista.get(i));
    				}
    			}
    			
    		};
    È tutto parecchio inappropriato. HashMap NON è thread-safe, quindi NON puoi usarlo banalmente da più thread. E non è solo quello il punto. Anche la lista (per ciascuna lunghezza) va trattata nell'ottica "concorrente" (e ArrayList NON è thread-safe).

    E inoltre se una lista va aggiunta, perché la lunghezza non c'è ancora come chiave nella mappa, serve una "serializzazione" degli accessi, una mutua-esclusione insomma, perché altrimenti potresti avere una race condition in cui i due thread cercano di fare il put di nuova lista per la stessa lunghezza.

    Quindi, mi spiace, ma stai "ignorando" troppe cose sulla concorrenza e sul multi-threading.

    Paolovox ha scritto:


    Grazie e buon primo maggio
    Eh sì ... con tutti i problemi che ci sono nel lavoro in Italia (e che anche io sto avendo ultimamente sul lavoro) ... buon Primo Maggio ... speriamo ...
  • Re: Scanning multi threads

    Capito mi toccherà studiarlo per bene a settembre quando comincerò il corso di programmazione di sistemi multicore in java e openCL.

    Con le competenze che hai faccio fatica a crederci. Penso che l'importante sia pensare positivamente e non abbattersi per rispettare soprattutto la salute che viene prima di tutto.

    PS: con 100000 stringhe è più veloce la versione iterativa che quella sgarrata che ho fatto con i due threads.
  • Re: Scanning multi threads

    Paolovox ha scritto:


    PS: con 100000 stringhe è più veloce la versione iterativa che quella sgarrata che ho fatto con i due threads.
    E oltretutto, senza le dovute attenzioni sulla sincronizzazione, cosa succeda non è nemmeno chiaro né garantito. Potrebbe funzionare per puro c**o, potrebbe non funzionare (sì o no anche a seconda della piattaforma/s.o.), potresti corrompere le strutture dati interne alla mappa/lista, potresti anche perdere dati.
    Proprio per via della race condition nell'inserimento di una nuova lista, se la lunghezza 5 non c'è ancora nella mappa, se contemporaneamente il thread1 cerca di inserire una nuova lista con ["pluto"] e il thread2 cerca di inserire una nuova lista con ["pippo"], cosa succeda non è garantito ma è molto probabile (nel caso migliore) che una delle due la "perdi" perché sovrascritta dall'altra (appunto perché questa logica non è atomica).
Devi accedere o registrarti per scrivere nel forum
4 risposte