En el desempeño de la función `first` de Clojure

vi el siguiente ejemplo en el vídeo de Rich en las secuencias http://blip.tv/file/734409 unos 33-36 minutos en ella:En el desempeño de la función `first` de Clojure

(first "abcd") => \a

Ahora, ha dicho que este se expande a (tipo de):

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

Por lo tanto, parece que una operación O(N) porque se está realizando la copia completa de la cadena. En primer lugar, si un String es inmutable, ¿por qué se copia? (Editar: basado en una respuesta, probablemente no lo es, solo se veía de esa manera cuando se imprimía). En segundo lugar, suponga que first operaba en otra cosa en Java que es mutable, digamos una lista de enteros enlazados. ¿Debería first actuar de manera perezosa (por ejemplo, crear primero una secuencia persistente)? ¿No tendría sentido evaluarlo de inmediato y guardarlo? Sería una especie de truco que rompería la bonita abstracción, pero creo que hacer el trabajo rápido. Cuando llama al (seq "abcd"), no sabe cómo se usará. Cuando llama a first en un seq, sabe qué hacer. Pero, cuando llame al first en "abcd", creo que es mejor realizar un enfoque "agarrar y guardarlo" rápido y hacky que tomar una secuencia y llamar al first.

¿Echo de menos algo? Hizo Rich Hickey saltarse algunos pasos?

Deseo saber si tengo preguntas. ¡Gracias!

Fuente

2010-10-03 Hamish Grubijan

Las otras respuestas son correctas, pero aprovecharé esta oportunidad para señalar un efecto interesante de la filosofía de inmutabilidad de Clojure.

Por lo tanto, parece una operación O (N) porque se está realizando la copia completa de la cadena.

Las cadenas, al igual que otras estructuras de datos en Clojure, son inmutables. (Son un caso especial, llevando a cabo en la JVM en lugar de Clojure, pero eso es irrelevante a este punto.)

copias de objetos inmutables son libre. Así es, gratis.Porque no necesitas copiar nada. El mismo objeto asignado en la memoria simplemente puede reutilizarse al por mayor, ya que se garantiza que siempre será el mismo que cuando se "copió".

Así que una función como seqnunca tiene que copiar realmente cualquier cosa. Simplemente funciona en lo que sea que pase, directamente, y devuelve una secuencia (posiblemente perezosa) que proporciona una interfaz abstracta para lo que sea que haya llamado seq.

Y así, seq es siempre O (1).

Fuente

2010-10-04 16:31:06 levand

Gracias, ¿alguna otra entrada sobre el trabajo con objetos Java mutables que se pueden convertir en una secuencia? –

IIRC, seq de llamada devuelve una secuencia de Clojure perezosa respaldada por un iterador de Java sobre la colección. Entonces, a medida que se realiza la secuencia floja, necesita seguir todas las reglas que pertenecen a los iteradores (en lo que respecta a la mutación del objeto subyacente) Una vez que se ha realizado, sin embargo, es una secuencia de Clojure inmutable. – levand

@Hamish: si quisiera convertir un objeto Java mutable en una secuencia, entonces necesitaría hacer una copia defensiva con un costo de O (n) o arriesgarse a que los datos subyacentes pudieran ser cambiados (lo que violaría las expectativas normales de seq) comportamiento y tal vez causar errores sutiles). El enfoque anterior (copia) es probablemente preferible, este último es muy peligroso a menos que esté absolutamente seguro de que nada cambiará en el momento equivocado. – mikera

No se sigue que se está haciendo una copia completa de la cadena. (Pero esta es una buena pregunta.)

En la fuente de clojure.lang.RT se dará cuenta de que el tiempo de ejecución utiliza CharSequence para crear la secuencia:

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); 
      . 
      . 
      .

Así que en realidad, se trata de una cuestión de Java, no una pregunta clojure. No lo he comprobado, pero estoy bastante seguro de que CharSequence hace lo "correcto".

Fuente

2010-10-03 17:31:56

Gracias por la respuesta, Rob. Supongamos que 'CharSequence' hace lo correcto, porque puede, porque' String' es inmutable. Ahora, ¿qué pasaría si tuviera una lista enlazada mutable de 999 enteros definidos en código Java, y quisiera obtener solo el primer elemento? ¿Puedo hacerlo mejor que copiar 999 ítems primero, o es esta la penalidad que tendría que pagar por hacer las cosas de la manera "sin acoso"? P.ej. Debería haber hecho una clase que contenga esos inmutables quizás? Me parece que habría casos en los que se necesite usar una lib de Java imperfecta desde dentro de Clojure. Entiendo que el primer elemento puede ser grande. –

(continuación), por lo que llamar a 'first' puede llevar un tiempo; digamos, por ejemplo, que primero llamamos a una lista enlazada mutable de listas enlazadas mutables. Entiendo por qué querríamos convertir la primera lista vinculada interna mutable en una secuencia persistente mediante copia, pero ¿por qué hacer lo mismo con el 'resto 'de ella, con cosas que nunca se analizarán en este caso particular? ? –

No es necesario copiar 999 elementos en un seq, ya que el seq solo usa la estructura de datos subyacente según sea necesario, y por razones de rendimiento e inmutabilidad, almacena en caché lo que encuentra. Si llama 'first' en alguna colección (por ejemplo, su lista vinculada), entonces el único elemento de esa colección que el seq necesita mirar es el primero. Los elementos aún no observados de la colección subyacente pueden estar mutando sin previo aviso. Solo cuando el seq realmente lea un elemento, ese elemento será "persistente" dentro del seq. –

Puede mirar el seq como si creara una secuencia diferida basada en la cadena.

En realidad, no crea una secuencia perezosa, en realidad está en cortocircuito con la implementación java de CharSequence, pero eso es un detalle de implementación.

Desde el punto de vista de la complejidad, es firstO(1) en un seq, y se puede crear un seq en tiempo constante de cualquier cosa es iterable.

Fuente

2010-10-04 00:46:19 ithkuil

En el desempeño de la función `first` de Clojure

Respuesta

Cuestiones relacionadas