najlepszą strukturę danych do przechowywania znaków i szeregi studentów

Question

Mam następujące informacje uczniów z odpowiednimi znakami i plasuje

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

Rangę studenta jest odwrotnie proporcjonalna do cech studenta. Muszę znaleźć najlepszą strukturę danych do przechowywania powyższych informacji, aby następujące operacje były wykonywane w sposób najbardziej optymalny (najlepsza złożoność czasu). Można założyć, że nazwisko ucznia jest unikalne.

1. Imię student, odnaleźć ślady i pozycjonowanie
2. Biorąc pod uwagę rangę, odnaleźć ślady i nazwisko studenta
3. znaków Aktualizacja studenta.

Mam na myśli wykorzystanie dwóch mapek na mapowanie uczniów i znaczników, a na mapowanie nazwisk i rang. Czy istnieje lepsza struktura danych dla tego ?. Czy istnieje sposób, w jaki mogę wykorzystać fakt, że pozycja jest odwrotnie proporcjonalna do ocen.

Answer 1

Można to zrobić z dwóch struktur danych:

1. hash mapa który mapuje nazwy od studenta do jego klasy.
2. An uczniów, gdzie kluczem do porównań jest ocena.

---

ta pozwala wykonać wszystkie poniższe czynności w O(logn):

1. Znajdź rangę studenta: znaleźć go na mapie hash, a następnie znaleźć swoją statystykę zamówienia (pozycja) w drzewo.
2. Zaktualizuj ocenę ucznia: odszukaj jego starszą ocenę na mapie, usuń ją zarówno z mapy, jak i drzewa, a następnie wstaw ponownie z nowymi wartościami.
3. Podając rangę, użyj drzewa statystyk zamówień, aby znaleźć odpowiedniego ucznia i jego ocenę.

Ponadto znalezienie oceny ucznia odbywa się w O(1) (średnia wielkość liter) za pomocą samej mapy skrótu.

---

Uwaga:

Można przełączać wdrażanie ucznia klasy mapie nazwa-> do drzewa mapie zamiast hash mapie bez wpływania na złożoność zbyt dużo, i gwarantujących zachowanie lepszej najgorszy przypadek. (Znalezienie oceny będzie również O (logn), a nie O (1) z tą zmianą).

Answer 2

Moja sugestia jest również użycie dwóch HashMap, ale jeden z nich jest wypełniany stopniowo zamiast dodawać złożoność sortowania do czasu aktualizacji. Zapewniłoby to następujące właściwości:

• szybki odczyt byStudent
• wolniej aktualizacji O (n).Jeśli często aktualizujesz, możesz rozważyć wyjęcie reorder z metody addOrUpdate, aktualizowanie w partiach i wywoływanie zmian po każdej partii z zewnątrz.
• ostatecznie szybki odczyt byRank.

---

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