Conversione di una lista concatenata su una mappa

Question

Mi è stato assegnato un incarico di modifica per aggiornare uno esistente.

capire come ricodificare il problema prova di idoneità usando una mappa per ogni linea del terminale, sulla presupposto che la dimensione del problema è dominato dal numero di linee di ingresso, non i 500 linee terminali

Il programma contiene un file di testo che ha il numero, il nome. Il numero è il numero di PC e il nome è l'utente che ha effettuato l'accesso. Il programma restituisce l'utente per ciascun pc che ha effettuato l'accesso più spesso. Ecco il codice esistente

public class LineUsageData { 
    SinglyLinkedList<Usage> singly = new SinglyLinkedList<Usage>(); 


    //function to add a user to the linked list or to increment count by 1 
    public void addObservation(Usage usage){ 
     for(int i = 0; i < singly.size(); ++i){ 
      if(usage.getName().equals(singly.get(i).getName())){ 
       singly.get(i).incrementCount(1); 
       return; 
      } 
     } 

     singly.add(usage); 
    } 
    //returns the user with the most connections to the PC 
    public String getMaxUsage(){ 
     int tempHigh = 0; 
     int high = 0; 
     String userAndCount = ""; 
     for(int i = 0; i < singly.size(); ++i){//goes through list and keeps highest 
      tempHigh = singly.get(i).getCount(); 
      if(tempHigh > high){ 
       high = tempHigh; 
       userAndCount = singly.get(i).getName() + " " + singly.get(i).getCount(); 
      } 
     } 

     return userAndCount; 
    } 
} 

Ho problemi sul lato teorico. Possiamo usare una hashmap o una treemap. Sto cercando di pensare a come formerei una mappa che terrebbe la lista degli utenti per ciascun pc? Posso riutilizzare l'oggetto Usage che conterrà il nome e il conteggio dell'utente. Non dovrei modificare quell'oggetto però

Answer 1

Ho risolto questo in linea e non ho avuto la possibilità di vedere alcune delle risposte che sembravano essere entrambe molto utili. Mi dispiace per Nick e Aivean e grazie per le risposte. Ecco il codice che ho finito per scrivere per farlo funzionare.

public class LineUsageData { 

    Map<Integer, Usage> map = new HashMap<Integer, Usage>(); 
    int hash = 0; 
    public void addObservation(Usage usage){ 
     hash = usage.getName().hashCode(); 
     System.out.println(hash); 
     while((map.get(hash)) != null){ 
      if(map.get(hash).getName().equals(usage.name)){ 
       map.get(hash).count++; 
       return; 
      }else{ 
       hash++; 
      } 

     } 
     map.put(hash, usage); 
    } 






    public String getMaxUsage(){ 
     String str = ""; 
     int tempHigh = 0; 
     int high = 0; 

    //for loop 
     for(Integer key : map.keySet()){ 
      tempHigh = map.get(key).getCount(); 
      if(tempHigh > high){ 
       high = tempHigh; 
       str = map.get(key).getName() + " " + map.get(key).getCount(); 
      } 
     } 

     return str; 
    } 


} 

Answer 2

Quando si controlla se Usage è presente nell'elenco si esegue una ricerca lineare ogni volta (O(N)). Se si sostituisce l'elenco con lo Map<String,Usage>, sarà possibile cercare name in tempo sublineare. TreeMap ha il tempo di ricerca e aggiornamento O(log N), HashMap ha ammortizzato il tempo O(1) (costante).

Quindi, la struttura dati più efficace in questo caso è HashMap.

import java.util.*; 

public class LineUsageData { 
    Map<String, Usage> map = new HashMap<String, Usage>(); 

    //function to add a user to the map or to increment count by 1 
    public void addObservation(Usage usage) { 
     Usage existentUsage = map.get(usage.getName()); 
     if (existentUsage == null) { 
      map.put(usage.getName(), usage); 
     } else { 
      existentUsage.incrementCount(1); 
     } 
    } 

    //returns the user with the most connections to the PC 
    public String getMaxUsage() { 
     Usage maxUsage = null; 
     for (Usage usage : map.values()) { 
      if (maxUsage == null || usage.getCount() > maxUsage.getCount()) { 
       maxUsage = usage; 
      } 
     } 

     return maxUsage == null ? null : maxUsage.getName() + " " + maxUsage.getCount(); 
    } 

    // alternative version that uses Collections.max 
    public String getMaxUsageAlt() { 
     Usage maxUsage = map.isEmpty() ? null : 
       Collections.max(map.values(), new Comparator<Usage>() { 
        @Override 
        public int compare(Usage o1, Usage o2) { 
         return o1.getCount() - o2.getCount(); 
        } 
       }); 

     return maxUsage == null ? null : maxUsage.getName() + " " + maxUsage.getCount(); 
    } 

} 

Map può anche essere iterato nel tempo proporzionale alla sua dimensione, in modo da poter utilizzare la stessa procedura per trovare il massimo elemento in esso. Ti ho dato due opzioni, approccio manuale o utilizzo del metodo di utilità Collections.max.

Answer 3

Con parole semplici: Si utilizza un LinkedList (singolarmente o doppiamente) quando si dispone di un elenco di elementi, e di solito prevede di attraversare loro, e Map implementazione quando si dispone di voci "Dizionario-come", in cui un la chiave corrisponde a un valore e prevedi di accedere al valore utilizzando la chiave.

Al fine di convertire il vostro SinglyLinkedList a un HashMap o TreeMap, è necessario sapere quale proprietà del tuo articolo verrà utilizzato come chiave (deve essere un elemento con valori unici).

Supponendo che si sta utilizzando la proprietà nome dalla classe di utilizzo, si può fare questo (un semplice esempio):

//You could also use TreeMap, depending on your needs. 
Map<String, Usage> usageMap = new HashMap<String, Usage>(); 

//Iterate through your SinglyLinkedList. 
for(Usage usage : singly) { 
    //Add all items to the Map 
    usageMap.put(usage.getName(), usage); 
} 

//Access a value using its name as the key of the Map. 
Usage accessedUsage = usageMap.get("AUsageName"); 

Si noti inoltre che:

Map<string, Usage> usageMap = new HashMap<>(); 

è valido, a causa di diamond inference.