javascript - react - redux immutable

¿Immutable.js o Lazy.js realizan una fusión de atajo?

Question

Primero, permítame definir qué es una fusión corta para aquellos de ustedes que no lo saben. Considere la siguiente transformación de matriz en JavaScript:

var a = [1,2,3,4,5].map(square).map(increment);

console.log(a);

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

Aquí tenemos una matriz, [1,2,3,4,5] , cuyos elementos son el primer cuadrado, [1,4,9,16,25] , y luego se incrementan [2,5,10,17,26] . Por lo tanto, aunque no necesitamos la matriz intermedia [1,4,9,16,25] , todavía la creamos.

La fusión de atajo es una técnica de optimización que puede deshacerse de las estructuras de datos intermedias al fusionar algunas llamadas de funciones en una. Por ejemplo, la fusión abreviada se puede aplicar al código anterior para producir:

var a = [1,2,3,4,5].map(compose(square, increment));

console.log(a);

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

function compose(g, f) {
    return function (x) {
        return f(g(x));
    };
}

Como puede ver, las dos llamadas de map separadas se han fusionado en una sola llamada de map al componer las funciones de square e increment . Por lo tanto, la matriz intermedia no se crea.

Ahora, entiendo que las bibliotecas como Lazy.js y Lazy.js emulan la evaluación perezosa en JavaScript. La evaluación perezosa significa que los resultados solo se calculan cuando es necesario.

Por ejemplo, considere el código anterior. Aunque square e increment cada elemento de la matriz, es posible que no necesitemos todos los resultados.

Supongamos que solo queremos los primeros 3 resultados. Usando Immutable.js o Lazy.js podemos obtener los primeros 3 resultados, [2,5,10] , sin calcular los 2 últimos resultados, [17,26] , porque no son necesarios.

Sin embargo, la evaluación perezosa solo retrasa el cálculo de los resultados hasta que se requiera. No elimina las estructuras de datos intermedias al fusionar funciones.

Para aclarar este punto, considere el siguiente código que emula una evaluación perezosa:

var List = defclass({
    constructor: function (head, tail) {
        if (typeof head !== "function" || head.length > 0)
            Object.defineProperty(this, "head", { value: head });
        else Object.defineProperty(this, "head", { get: head });

        if (typeof tail !== "function" || tail.length > 0)
            Object.defineProperty(this, "tail", { value: tail });
        else Object.defineProperty(this, "tail", { get: tail });
    },
    map: function (f) {
        var l = this;

        if (l === nil) return nil;

        return cons(function () {
            return f(l.head);
        }, function () {
            return l.tail.map(f);
        });
    },
    take: function (n) {
        var l = this;

        if (l === nil || n === 0) return nil;

        return cons(function () {
            return l.head;
        }, function () {
            return l.tail.take(n - 1);
        });
    },
    mapSeq: function (f) {
        var l = this;
        if (l === nil) return nil;
        return cons(f(l.head), l.tail.mapSeq(f));
    }
});

var nil = Object.create(List.prototype);

list([1,2,3,4,5])
    .map(trace(square))
    .map(trace(increment))
    .take(3)
    .mapSeq(log);

function cons(head, tail) {
    return new List(head, tail);
}

function list(a) {
    return toList(a, a.length, 0);
}

function toList(a, length, i) {
    if (i >= length) return nil;

    return cons(a[i], function () {
        return toList(a, length, i + 1);
    });
}

function square(x) {
    return x * x;
}

function increment(x) {
    return x + 1;
}

function log(a) {
    console.log(a);
}

function trace(f) {
    return function () {
        var result = f.apply(this, arguments);
        console.log(f.name, JSON.stringify([...arguments]), result);
        return result;
    };
}

function defclass(prototype) {
    var constructor = prototype.constructor;
    constructor.prototype = prototype;
    return constructor;
}

Como puede ver, las llamadas de función se intercalan y solo se procesan los primeros tres elementos de la matriz, lo que demuestra que los resultados se computan de forma perezosa:

square [1] 1
increment [1] 2
2
square [2] 4
increment [4] 5
5
square [3] 9
increment [9] 10
10

Si no se utiliza la evaluación perezosa, el resultado sería:

square [1] 1
square [2] 4
square [3] 9
square [4] 16
square [5] 25
increment [1] 2
increment [4] 5
increment [9] 10
increment [16] 17
increment [25] 26
2
5
10

Sin embargo, si ve el código fuente, entonces cada list funciones, map , take y mapSeq devuelve una estructura de datos de List intermedia. No se realiza fusión corta.

Esto me lleva a mi pregunta principal: ¿bibliotecas como Immutable.js y Lazy.js realizan una fusión corta?

La razón por la que pregunto es porque según la documentación, "aparentemente" lo hacen. Sin embargo, soy escéptico. Tengo mis dudas de si realmente realizan una fusión corta.

Por ejemplo, esto se toma del archivo README.md de README.md :

Immutable también proporciona un Seq perezoso, lo que permite un encadenamiento eficiente de los métodos de recolección como el map y el filter sin crear representaciones intermedias. Crear algunos Seq con Range y Repeat .

Así que los desarrolladores de Immutable.js afirman que su estructura de datos Seq permite un encadenamiento eficiente de los métodos de recopilación como el map y el filter sin crear representaciones intermedias (es decir, realizan una fusión de atajos).

Sin embargo, no los veo hacerlo en su code ninguna parte. Quizás no pueda encontrarlo porque están usando ES6 y mis ojos no están muy familiarizados con la sintaxis de ES6.

Además, en su documentación para Lazy Seq mencionan:

Seq describe una operación perezosa, lo que les permite encadenar de manera eficiente el uso de todos los métodos de Iterable (como el map y el filter ).

Seq es inmutable : una vez que se crea un Seq, no se puede cambiar, anexar, reorganizar ni modificar de otra manera. En su lugar, cualquier método mutativo llamado en una Seq devolverá una nueva Seq.

Seq es perezoso : Seq hace el menor trabajo necesario para responder a cualquier llamada de método.

Así se establece que Seq es efectivamente perezoso. Sin embargo, no hay ejemplos que muestren que las representaciones intermedias no se crean (lo que dicen estar haciendo).

Pasando a Lazy.js tenemos la misma situación. Afortunadamente, Daniel Tao escribió una Lazy.js el Lazy.js sobre cómo funciona Lazy.js, en la que menciona que, en el fondo, Lazy.js simplemente hace la función de la composición. Da el siguiente ejemplo:

Lazy.range(1, 1000)
    .map(square)
    .filter(multipleOf3)
    .take(10)
    .each(log);

function square(x) {
    return x * x;
}

function multipleOf3(x) {
    return x % 3 === 0;
}

function log(a) {
    console.log(a);
}

<script src="https://rawgit.com/dtao/lazy.js/master/lazy.min.js"></script>

Aquí, las funciones map , filter y take producen MappedSequence , FilteredSequence y TakeSequence . Estos objetos de Sequence son esencialmente iteradores, que eliminan la necesidad de matrices intermedias.

Sin embargo, por lo que entiendo, todavía no se está produciendo una fusión corta. Las estructuras de la matriz intermedia simplemente se reemplazan con estructuras de Sequence intermedia que no están fusionadas.

Podría estar equivocado, pero creo que expresiones como Lazy(array).map(f).map(g) producen dos objetos MappedSequence separados en los que el primer objeto MappedSequence alimenta sus valores al segundo, en lugar de que el segundo reemplace el primero haciendo el trabajo de ambos (a través de la composición de la función).

TLDR: ¿Immutable.js y Lazy.js de hecho realizan una fusión corta? Por lo que sé, se deshacen de matrices intermedias al emular la evaluación perezosa a través de objetos de secuencia (es decir, iteradores). Sin embargo, creo que estos iteradores están encadenados: un iterador alimenta sus valores perezosamente al siguiente. No se fusionan en un solo iterador. De ahí que no "eliminen representaciones intermedias". Solo transforman matrices en objetos de secuencia de espacio constante.

Answer 1

Soy el autor de Immutable.js (y un fan de Lazy.js).

¿Se utilizan Lazy.js y Immutable.js''s Seq en la fusión de atajo? No, no exactamente. Pero sí eliminan la representación intermedia de los resultados de la operación.

La fusión corta es una técnica de compilación / transpilación de código. Tu ejemplo es bueno:

var a = [1,2,3,4,5].map(square).map(increment);

Transpilado:

var a = [1,2,3,4,5].map(compose(square, increment));

Lazy.js e Immutable.js no son transpilers y no volverán a escribir el código. Son bibliotecas de tiempo de ejecución. Así que en lugar de la fusión de atajo (una técnica de compilación) usan una composición iterable (una técnica de tiempo de ejecución).

Usted responde esto en su TLDR:

Por lo que sé, se deshacen de matrices intermedias al emular la evaluación perezosa a través de objetos de secuencia (es decir, iteradores). Sin embargo, creo que estos iteradores están encadenados: un iterador alimenta sus valores perezosamente al siguiente. No se fusionan en un solo iterador. De ahí que no "eliminen representaciones intermedias". Solo transforman matrices en objetos de secuencia de espacio constante.

Eso es exactamente correcto.

Vamos a desempacar:

Las matrices almacenan resultados intermedios al encadenar:

var a = [1,2,3,4,5];
var b = a.map(square); // b: [1,4,6,8,10] created in O(n)
var c = b.map(increment); // c: [2,5,7,9,11] created in O(n)

La transpilación de fusión abreviada crea funciones intermedias:

var a = [1,2,3,4,5];
var f = compose(square, increment); // f: Function created in O(1)
var c = a.map(f); // c: [2,5,7,9,11] created in O(n)

La composición iterable crea iterables intermedios:

var a = [1,2,3,4,5];
var i = lazyMap(a, square); // i: Iterable created in O(1)
var j = lazyMap(i, increment); // j: Iterable created in O(1)
var c = Array.from(j); // c: [2,5,7,9,11] created in O(n)

Tenga en cuenta que utilizando una composición iterable, no hemos creado una tienda de resultados intermedios. Cuando estas bibliotecas dicen que no crean representaciones intermedias, lo que quieren decir es exactamente lo que se describe en este ejemplo. No se crea ninguna estructura de datos que [1,4,6,8,10] los valores [1,4,6,8,10] .

Sin embargo, por supuesto se hace alguna representación intermedia. Cada operación "perezosa" debe devolver algo. Vuelven un iterable. Crearlos es extremadamente barato y no está relacionado con el tamaño de los datos que se operan. Tenga en cuenta que en la transpilación de fusión corta, también se hace una representación intermedia. El resultado de compose es una nueva función. La composición funcional (escrita a mano o el resultado de un compilador de fusión de atajo) está muy relacionada con la composición iterable.

El objetivo de eliminar representaciones intermedias es el rendimiento, especialmente con respecto a la memoria. La composición iterable es una forma poderosa de implementar esto y no requiere la sobrecarga que supone analizar y reescribir el código de un compilador de optimización que estaría fuera de lugar en una biblioteca de tiempo de ejecución.

Appx:

Esto es lo que podría parecer una implementación simple de lazyMap :

function lazyMap(iterable, mapper) {
  return {
    "@@iterator": function() {
      var iterator = iterable["@@iterator"]();
      return {
        next: function() {
          var step = iterator.next();
          return step.done ? step : { done: false, value: mapper(step.value) }
        }
      };
    }
  };
}