migliore struttura dati per memorizzare i marchi e le fila degli studenti

Question

ho le seguenti informazioni di studenti con segni corrispondenti e si colloca

Name Marks Rank 
A  30  1 
B  20  2 
C  10  3 

Il rango dello studente è inversamente proporzionale ai segni dello studente. Devo trovare la migliore struttura dati per memorizzare le informazioni di cui sopra in modo che le seguenti operazioni vengano eseguite nel modo più ottimale (Migliore complessità temporale). Si può presumere che il nome dello studente sia unico.

1. nome dello studente Dato, trovare segni e di rango
2. rango Dato, trovare marchi e nome dello studente
3. Aggiornamento segni di uno studente.

Sto pensando di utilizzare due hashmap una per lo studente e la mappatura dei contrassegni e un'altra per il nome dello studente e la mappatura del rango. C'è una struttura dati migliore per questo? C'è un modo in cui posso fare uso del fatto che il grado è inversamente proporzionale ai voti.

Answer 1

Questo può essere fatto con le strutture di due dati:

1. Una mappa hash che mappa da nome dello studente al suo grado.
2. order statistic tree di studenti, dove la chiave per i confronti è il voto.

---

Questo permette di fare tutte le seguenti operazioni in O(logn):

1. Scopri rango di uno studente: trovate nella mappa di hash, e quindi trovare la sua statistica d'ordine (rango) in l'albero.
2. Aggiorna un voto studente: trova il suo vecchio voto sulla mappa, rimuovilo sia dalla mappa che dall'albero e reinseriscilo con i nuovi valori.
3. Dato un rango, utilizzare l'albero delle statistiche degli ordini per trovare lo studente pertinente e il suo grado.

Inoltre, la ricerca del voto di uno studente viene effettuata in O(1) (caso medio) utilizzando la mappa di hash.

---

Nota:

È possibile passare all'attuazione dello studente nome-> mappa di grado a una mappa ad albero piuttosto che mappa hash senza influenzare la complessità troppo, e garantendo una migliore comportamento peggiore dei casi. (La ricerca di un voto sarà anche O (logn) e non O (1) con questo cambiamento).

Answer 2

Il mio suggerimento è anche quello di utilizzare due HashMap, ma uno di essi viene riempito gradualmente invece di aggiungere la sua complessità di ordinamento per aggiornare il tempo. Ciò fornirebbe le seguenti proprietà:

• lettura veloce byStudent
• più lento aggiornamenti O (n).Se si aggiorna molto, si potrebbe prendere in considerazione l'estrazione del reorder dal metodo addOrUpdate, l'aggiornamento in lotti e il riordino delle chiamate dopo ogni batch dall'esterno.
• alla fine veloce byRank lettura.

---

class MyClass { 
    Comparator<RankedStudent> comp = Comparator.comparingInt(e -> e.marks); 
    private Map<String, RankedStudent> repo = new HashMap<>(); 
    private Map<Integer, RankedStudent> rankCache = new HashMap<>(); 

    public RankedStudent getByStudent(String student) { 
     return repo.get(student); 
    } 

    public RankedStudent getByRank(Integer rank) { 
     return Optional.ofNullable(rankCache.get(rank)).orElseGet(() -> { 
      rankCache.putIfAbsent(rank, repo.values().stream().sorted((s1, s2) -> rank == s1.rank ? 1 : 0) 
        .findFirst().orElse(null)); 
      return rankCache.get(rank); 
     }); 
    } 

    public void addOrUpdate(String student, Integer marks) { 
     repo.put(student, new RankedStudent(student, marks, -1)); 
     reorder(); 
    } 

    public void reorder() { 
     final Iterator<RankedStudent> it = repo.values().stream().sorted(comp.reversed()).iterator(); 
     IntStream.range(0, repo.size()).boxed().forEach(i -> it.next().rank = i + 1); 
     rankCache.clear(); 
    } 
} 

class RankedStudent { 

    public String name; 
    public int marks; 
    public int rank; 

    public RankedStudent(String name, int marks, int rank) { 
     this.name = name; 
     this.marks = marks; 
     this.rank = rank; 
    } 
}