15
Wie hoch ist die Komplexität der Zählung in clojure?Was ist die zeitliche Komplexität der Zählfunktion in clojure?
Wie hoch ist die Komplexität der Zählung in clojure?Was ist die zeitliche Komplexität der Zählfunktion in clojure?
Hier ist die Umsetzung:
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());
}
So ist es O (1) für Arrays, Strings, Sammlungen, Karten und alles, was Gezählt implementiert. Es ist O (n) für alles, was IPersistentCollection implementiert, aber nicht gezählt.