Auf Leistung von `die Clojure first` Funktion

Question

sah ich das folgende Beispiel in Video Rich auf Sequenzen http://blip.tv/file/734409 etwa 33-36 Minuten hinein:

(first "abcd") => \a 

Nun er sagt, dass dies zu (Art erweitert):

(first "abcd") => (first (seq "abcd")) => (first '(\a \b \c \d)) 

So sieht es aus wie ein O(N) Betrieb, da die vollständige Kopie der Zeichenfolge gemacht wird. Vor allem, wenn ein String unveränderlich ist, warum wird es dann kopiert? (Edit: basierend auf einer Antwort, ist es wahrscheinlich nicht; sah einfach so, wenn gedruckt.) Zweitens angenommen first auf etwas anderes in Java, das veränderbar ist, sagen eine verknüpfte Liste von ganzen Zahlen. Sollte first auf eine faule Weise handeln (z. B. zuerst eine persistente Sequenz erstellen)? Wäre es nicht sinnvoll, es sofort zu bewerten und zu speichern? Es wäre eine Art Hack, der die nette Abstraktion durchbricht, aber die Arbeit schnell erledigt, denke ich. Wenn Sie (seq "abcd") anrufen, wissen Sie nicht, wie es verwendet wird. Wenn Sie eine first auf einer seq anrufen, wissen Sie, was zu tun ist. Aber wenn Sie first auf "abcd" anrufen, denke ich, dass die Durchführung einer hacky und schnell "greifen und speichern", Ansatz ist besser als eine Sequenz und dann rufen Sie first.

Fehle ich etwas? Hat Rich Hickey einige Schritte ausgelassen?

Lassen Sie mich wissen, wenn ich Fragen habe. Vielen Dank!

Answer 1

Die anderen Antworten sind korrekt, aber ich werde diese Gelegenheit nutzen, um auf einen interessanten Effekt von Clojures Philosophie der Unveränderlichkeit hinzuweisen.

So sieht es aus wie eine O (N) Operation, weil die vollständige Kopie der Zeichenfolge erstellt wird.

Strings, wie andere Datenstrukturen in Clojure, sind unveränderlich. (Sie sind ein Sonderfall, in der JVM anstelle von Clojure implementiert, aber das ist zu diesem Punkt unerheblich.)

Kopien von unveränderlichen Objekten sind frei. Das ist richtig, frei.Weil Sie überhaupt nicht kopieren müssen. Das gleiche zugewiesene Objekt im Speicher kann einfach im Großhandel wiederverwendet werden, da es garantiert immer dasselbe ist, als wenn es "kopiert" wurde.

Also eine Funktion wie seqnie muss eigentlich alles kopieren. Es funktioniert nur mit dem, was direkt übergeben wird, und gibt eine (möglicherweise faule) Sequenz zurück, die eine abstrakte Schnittstelle zu allem bereitstellt, was Sie seq aufgerufen haben.

Und so ist seq immer O (1).

Answer 2

Es folgt nicht, dass eine vollständige Kopie der Zeichenfolge erstellt wird. (Aber das ist eine gute Frage.)

In der Quelle für clojure.lang.RT Sie werden feststellen, dass die Laufzeit verwendet CharSequence die Sequenz zu erstellen:

static ISeq seqFrom(Object coll){ 
    if(coll instanceof Seqable) 
     return ((Seqable) coll).seq(); 
    else if(coll == null) 
     return null; 
    else if(coll instanceof Iterable) 
     return IteratorSeq.create(((Iterable) coll).iterator()); 
    else if(coll.getClass().isArray()) 
     return ArraySeq.createFromObject(coll); 
    else if(coll instanceof CharSequence) 
     return StringSeq.create((CharSequence) coll); 
      . 
      . 
      . 

wirklich Also, das ist eine Java-Frage, nicht ein clojure Frage. Ich habe das nicht überprüft, aber ich bin ziemlich sicher, dass CharSequence das "Richtige" macht.

Answer 3

Sie könnten die seq so betrachten, als ob sie eine Lazy-Sequenz basierend auf der Zeichenfolge erstellt.

Es erstellt eigentlich keine Lazy-Sequenz, es schließt tatsächlich die Java-Implementierung von CharSequence kurz, aber das ist ein Implementierungsdetail.

Aus Komplexität Sicht first ist O(1) auf einem seq, und Sie können eine seq in konstanter Zeit von irgendetwas ist iterable erstellen.