Dans mon code, l'itération Java TreeSet est le facteur temps dominant. En regardant le système, je crois que c'est la complexité O (n). Quelqu'un peut-il vérifier cela?Quelle est la complexité temporelle de l'itération de TreeSet?
Je pense qu'en fournissant des liens vers l'arrière depuis le nœud enfant vers le nœud parent, je pourrais améliorer les performances.
TreeSet l'itération est bien sûr O (n), comme on peut l'attendre de n'importe quel algorithme de marche en arbre sensible.
Je pense que en fournissant des liens vers l'arrière du nœud enfant au nœud parent je pourrais améliorer les performances.
TreeMap (sur laquelle TreeSet est basé) a déjà de telles références parentes. Ceci est la méthode tout se résume à:
private Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
Je pense que le point clé est que ce ne sont pas seulement les nœuds feuilles qui ont des valeurs attachées. Pour les 'n' leafs, vous avez des noeuds' O (n log n) 'mais aussi des valeurs' O (n log n) '. Dans les cas réels, je m'attendrais à ce que les opérations 'O (n)' dominent les opérations 'O (n log n)' de toute façon. –
Je pensais que ce serait O (n) + O (logn) parce que si vous itérez dans l'ordre, vous devez d'abord utiliser les traversées log (n) pour trouver la feuille de gauche ou de droite, et vous avez n traversées pour marcher dans l'arbre en arrière. Ainsi vous avez O (n)? Est-ce que mes maths ont un sens? –
@john: O (n) + O (log n) est la même chose que O (n) par définition. –
Avez-vous envisagé de prendre une copie de la TreeSet lorsque vous le modifier? Si le temps dominant est passé dans l'itération de TreeSet (plutôt que de la modifier), copier le TreeSet dans un tableau ou ArrayList (seulement quand il est altéré) et seulement itérer sur ce tableau/ArrayList pourrait presque éliminer le coût de l'itération de TreeSet.
Ou 'ImmutableSortedSet' de Guava, qui est soutenu par un tableau. –
Cette question n'a pas de sens. On dirait que vous dites que l'itération sur votre arbre est O (n). C'est le meilleur que vous pouvez faire pour l'itération - regarder n éléments nécessite O (n) temps. Si vous voulez accélérer le code qui est dominé par l'itération, vous devez changer l'algorithme afin qu'il ne fasse pas d'itération - par exemple, en faisant des recherches dans l'arbre par clé (ce qui serait O (log n)) au lieu. – babbageclunk