15
Quelle est la complexité temporelle de count dans clojure?Quelle est la complexité temporelle de la fonction count dans clojure?
Quelle est la complexité temporelle de count dans clojure?Quelle est la complexité temporelle de la fonction count dans clojure?
est ici la mise en œuvre:
public static int count(Object o){
if(o == null)
return 0;
else if(o instanceof Counted)
return ((Counted) o).count();
else if(o instanceof IPersistentCollection) {
ISeq s = seq(o);
o = null;
int i = 0;
for(; s != null; s = s.next()) {
if(s instanceof Counted)
return i + s.count();
i++;
}
return i;
}
else if(o instanceof String)
return ((String) o).length();
else if(o instanceof Collection)
return ((Collection) o).size();
else if(o instanceof Map)
return ((Map) o).size();
else if(o.getClass().isArray())
return Array.getLength(o);
throw new UnsupportedOperationException("count not supported on this type: " + o.getClass().getSimpleName());
}
Il est donc O (1) pour les tableaux, les chaînes, les collections, les cartes et tout ce qui met en œuvre DISPOSONS. C'est O (n) pour tout ce qui implémente IPersistentCollection, mais pas Counted.