Scanning multi threads

di Paolovox il
4 risposte
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

  • 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;
    		}
    		
    
  • 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 ...
  • 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.
  • 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