Amélioration des performances de la fusion de plusieurs cartes triées en une seule carte triée - java

Question

J'ai une méthode qui reçoit une SortedMap en entrée, cette carte contient plusieurs objets SortedMap, la sortie de cette méthode doit être une SortedMap contenant tous les éléments des maps maintenu dans la carte d'entrée. la méthode ressemble à ceci:

private SortedMap mergeSamples(SortedMap map){ 
    SortedMap mergedMap = new TreeMap(); 
    Iterator sampleIt = map.values().iterator(); 
    while(sampleIt.hasNext()) 
    { 
    SortedMap currMap = (SortedMap) sampleIt.next(); 
    mergedMap.putAll(currMap); 
    } 
    return mergedMap; 
} 

Ceci est un tueur de performance, que puis-je améliorer ici?

Answer 1

Je ne vois rien de mal avec votre code; tout ce que vous pouvez vraiment faire est d'essayer des implémentations alternatives de SortedMap. Le premier serait ConcurrentSkipListMap et ensuite regarder Commons Collections, Google Collections et GNU Trove. Ce dernier peut donner de très bons résultats, surtout si les clés et les valeurs de vos cartes sont des types primitifs.

Answer 2

Est-il nécessaire que l'entrée soit une SortedMap? Pour moi, il semblerait plus facile si l'entrée était juste une collection ou une liste. Cela pourrait accélérer la création de l'entrée et accélérer l'itération sur toutes les cartes contenues. À part cela, je crois que la source la plus probable d'amélioration de la performance de ce code est l'amélioration de la vitesse de l'implémentation compareTo() des valeurs dans les cartes triées qui sont fusionnées.

Answer 3

Votre code est bon. Cependant, il me semble que la conception globale de la structure de données a besoin d'une révision: Vous utilisez SortedMap<?, SortedMap<?, ?>, mais les clés de la carte parent ne sont pas utilisées. Voulez-vous exprimer un arbre avec des éléments imbriqués avec cela et votre tâche est-il d'aplatir l'arbre? Dans ce cas, soit créer une classe d'arbres qui prend en charge votre approche, ou d'une manière intelligente de fusionner les clés:

public class NestedKey implements Comparable<NestedKey> { 

    private Comparable[] entries; 

    public NestedKey(Comparable... entries) { 
    assert entries != null; 
    this.entries = entries; 
    } 

    public int compareTo(NestedKey other) { 
    for(int i = 0; i < other.entries.length; i++) { 
     if (i == entries.length) 
     return -1; // other is longer then self <=> self is smaller than other 
     int cmp = entries[i].compareTo(other.entries[i]); 
     if (cmp != 0) 
     return cmp; 
    } 
    if (entries.length > other.entries.length) 
     return 1; // self is longer than others <=> self is larger than other 
    else 
     return 0; 
    } 

} 

L'entrée NestedKey utilisé comme une clé pour un SortedMap compare à d'autres NestedKey objets en comparant chacun de ses Entrées Les NestedKeys présents dans tous les éléments présents mais comportant plus d'entrées sont supposés être plus grands. Ainsi, vous avez une relation comme ceci:

• NestedKey (1, 2, 3) < NestedKey (1, 2, 4)
• NestedKey (1, 3, 3) < NestedKey (2, 1, 1)
• NestedKey (1, 2, 3) < NestedKey (2)

Si vous utilisez une seule SortedMap qui utilise NestedKey comme ses clés, sa .values() revient automatiquement régler toutes les entrées, aplatit. Toutefois, si vous souhaitez utiliser uniquement des parties de SortedMap, vous devez utiliser .subMap. Par exemple, si vous voulez toutes les entrées avec NestedKeys entre 2 et 3, utilisez .subMap(new NestedKey(2), new NestedKey(3))