15
Jaka jest złożoność czasu liczenia w clojure?Jaka jest złożoność czasu funkcji liczenia w clojure?
Jaka jest złożoność czasu liczenia w clojure?Jaka jest złożoność czasu funkcji liczenia w clojure?
Oto realizacja:
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());
}
Więc to O (1) dla tablic, ciągi, kolekcje, mapy i cokolwiek który implementuje policzone. To O (n) dla wszystkiego, co implementuje IPersistentCollection, ale nie jest policzone.