Búsqueda de sitios web

algoritmo - La forma más rápida de aplanar/des-aplanar objetos JavaScript anidados

Arme un código rápidamente para aplanar y desaplanar objetos complejos/anidados de JavaScript. Funciona, pero es un poco lento (activa la advertencia de 'script largo').

Para los nombres aplanados quiero "." como delimitador y [ÍNDICE] para arrays.

Ejemplos:

un-flattened | flattened
---------------------------
{foo:{bar:false}} => {"foo.bar":false}
{a:[{b:["c","d"]}]} => {"a[0].b[0]":"c","a[0].b[1]":"d"}
[1,[2,[3,4],5],6] => {"[0]":1,"[1].[0]":2,"[1].[1].[0]":3,"[1].[1].[1]":4,"[1].[2]":5,"[2]":6}

Creé un punto de referencia que ~simula mi caso de uso http://jsfiddle.net/WSzec/

  • Obtener un objeto anidado
  • Aplánalo
  • Revísalo y posiblemente modifícalo mientras está aplanado
  • Desenrúzgalo de nuevo a su formato anidado original para ser enviado

Me gustaría un código más rápido: Para aclarar, código que complete el benchmark de JSFiddle (http://jsfiddle.net/WSzec/) significativamente más rápido (~20%+ sería agradable) en IE 9+, FF 24+ y Chrome 29+.

Aquí está el código JavaScript relevante: El más rápido actual: http://jsfiddle.net/WSzec/6/

var unflatten = function(data) {
    "use strict";
    if (Object(data) !== data || Array.isArray(data))
        return data;
    var result = {}, cur, prop, idx, last, temp;
    for(var p in data) {
        cur = result, prop = "", last = 0;
        do {
            idx = p.indexOf(".", last);
            temp = p.substring(last, idx !== -1 ? idx : undefined);
            cur = cur[prop] || (cur[prop] = (!isNaN(parseInt(temp)) ? [] : {}));
            prop = temp;
            last = idx + 1;
        } while(idx >= 0);
        cur[prop] = data[p];
    }
    return result[""];
}
var flatten = function(data) {
    var result = {};
    function recurse (cur, prop) {
        if (Object(cur) !== cur) {
            result[prop] = cur;
        } else if (Array.isArray(cur)) {
             for(var i=0, l=cur.length; i<l; i++)
                 recurse(cur[i], prop ? prop+"."+i : ""+i);
            if (l == 0)
                result[prop] = [];
        } else {
            var isEmpty = true;
            for (var p in cur) {
                isEmpty = false;
                recurse(cur[p], prop ? prop+"."+p : p);
            }
            if (isEmpty)
                result[prop] = {};
        }
    }
    recurse(data, "");
    return result;
}

EDIT 1 Modifiqué lo anterior a la implementación de @Bergi, que actualmente es la más rápida. Como comentario, usar ".indexOf" en lugar de "regex.exec" es aproximadamente un 20% más rápido en FF pero un 20% más lento en Chrome; así que me quedaré con la expresión regular ya que es más simple (aquí está mi intento de usar indexOf para reemplazar la expresión regular http://jsfiddle.net/WSzec/2/).

EDIT 2 Basándome en la idea de @Bergi, logré crear una versión más rápida sin expresiones regulares (3 veces más rápida en FF y ~10% más rápida en Chrome). http://jsfiddle.net/WSzec/6/ En esta (la actual) implementación, las reglas para los nombres de las claves son simples: las claves no pueden comenzar con un número ni contener un punto.

Ejemplo :

  • {"foo":{"bar":[0]}} => {"foo.bar.0":0}

EDIT 3 Agregar el enfoque de análisis de rutas en línea de @AaditMShah (en lugar de String.split) ayudó a mejorar el rendimiento de unflatten. Estoy muy contento con la mejora general del rendimiento alcanzada.

El último jsfiddle y jsperf:

http://jsfiddle.net/WSzec/14/

http://jsperf.com/flatten-un-flatten/4

Respuesta #1

Aquí está mi implementación mucho más corta:

Object.unflatten = function(data) {
    "use strict";
    if (Object(data) !== data || Array.isArray(data))
        return data;
    var regex = /\.?([^.\[\]]+)|\[(\d+)\]/g,
        resultholder = {};
    for (var p in data) {
        var cur = resultholder,
            prop = "",
            m;
        while (m = regex.exec(p)) {
            cur = cur[prop] || (cur[prop] = (m[2] ? [] : {}));
            prop = m[2] || m[1];
        }
        cur[prop] = data[p];
    }
    return resultholder[""] || resultholder;
};

flatten no ha cambiado mucho (y no estoy seguro de si realmente necesitas esos casos de isEmpty):

Object.flatten = function(data) {
    var result = {};
    function recurse (cur, prop) {
        if (Object(cur) !== cur) {
            result[prop] = cur;
        } else if (Array.isArray(cur)) {
             for(var i=0, l=cur.length; i<l; i++)
                 recurse(cur[i], prop + "[" + i + "]");
            if (l == 0)
                result[prop] = [];
        } else {
            var isEmpty = true;
            for (var p in cur) {
                isEmpty = false;
                recurse(cur[p], prop ? prop+"."+p : p);
            }
            if (isEmpty && prop)
                result[prop] = {};
        }
    }
    recurse(data, "");
    return result;
}

Juntos, ejecutan su prueba de referencia en aproximadamente la mitad del tiempo (Opera 12.16: ~900 ms en lugar de ~1900 ms, Chrome 29: ~800 ms en lugar de ~1600 ms).

Nota: Esta y la mayoría de las otras soluciones respondidas aquí se centran en la velocidad y son susceptibles a la contaminación de prototipos y no deben usarse en objetos no confiables.

Respuesta #2

Escribí dos funciones para flatten y unflatten un objeto JSON.

Aplanar un objeto JSON:

var flatten = (function (isArray, wrapped) {
    return function (table) {
        return reduce("", {}, table);
    };

    function reduce(path, accumulator, table) {
        if (isArray(table)) {
            var length = table.length;

            if (length) {
                var index = 0;

                while (index < length) {
                    var property = path + "[" + index + "]", item = table[index++];
                    if (wrapped(item) !== item) accumulator[property] = item;
                    else reduce(property, accumulator, item);
                }
            } else accumulator[path] = table;
        } else {
            var empty = true;

            if (path) {
                for (var property in table) {
                    var item = table[property], property = path + "." + property, empty = false;
                    if (wrapped(item) !== item) accumulator[property] = item;
                    else reduce(property, accumulator, item);
                }
            } else {
                for (var property in table) {
                    var item = table[property], empty = false;
                    if (wrapped(item) !== item) accumulator[property] = item;
                    else reduce(property, accumulator, item);
                }
            }

            if (empty) accumulator[path] = table;
        }

        return accumulator;
    }
}(Array.isArray, Object));

Rendimiento:

  1. Es más rápido que la solución actual en Opera. La solución actual es un 26% más lenta en Opera.
  2. Es más rápido que la solución actual en Firefox. La solución actual es un 9% más lenta en Firefox.
  3. Es más rápido que la solución actual en Chrome. La solución actual es un 29% más lenta en Chrome.

Desaplanar un objeto JSON:

function unflatten(table) {
    var result = {};

    for (var path in table) {
        var cursor = result, length = path.length, property = "", index = 0;

        while (index < length) {
            var char = path.charAt(index);

            if (char === "[") {
                var start = index + 1,
                    end = path.indexOf("]", start),
                    cursor = cursor[property] = cursor[property] || [],
                    property = path.slice(start, end),
                    index = end + 1;
            } else {
                var cursor = cursor[property] = cursor[property] || {},
                    start = char === "." ? index + 1 : index,
                    bracket = path.indexOf("[", start),
                    dot = path.indexOf(".", start);

                if (bracket < 0 && dot < 0) var end = index = length;
                else if (bracket < 0) var end = index = dot;
                else if (dot < 0) var end = index = bracket;
                else var end = index = bracket < dot ? bracket : dot;

                var property = path.slice(start, end);
            }
        }

        cursor[property] = table[path];
    }

    return result[""];
}

Rendimiento:

  1. Es más rápido que la solución actual en Opera. La solución actual es un 5% más lenta en Opera.
  2. Es más lento que la solución actual en Firefox. Mi solución es un 26% más lenta en Firefox.
  3. Es más lento que la solución actual en Chrome. Mi solución es un 6% más lenta en Chrome.

Achatar y desachatar un objeto JSON:

En general, mi solución funciona igual de bien o incluso mejor que la solución actual.

Rendimiento:

  1. Es más rápido que la solución actual en Opera. La solución actual es un 21% más lenta en Opera.
  2. Es tan rápido como la solución actual en Firefox.
  3. Es más rápido que la solución actual en Firefox. La solución actual es un 20% más lenta en Chrome.

Formato de salida:

Un objeto aplanado utiliza la notación de puntos para las propiedades del objeto y la notación de corchetes para los índices de la matriz:

  1. {foo:{bar:false}} => {"foo.bar":false}
  2. {a:[{b:["c","d"]}]} => {"a[0].b[0]":"c","a[0].b[1]":"d"}
  3. [1,[2,[3,4],5],6] => {"[0]":1,"[1][0]":2,"[1][1][0]":3,"[1][1][1]":4,"[1][2]":5,"[2]":6}

En mi opinión, este formato es mejor que usar solo la notación de puntos:

  1. {foo:{bar:false}} => {"foo.bar":false}
  2. {a:[{b:["c","d"]}]} => {"a.0.b.0":"c","a.0.b.1":"d"}
  3. [1,[2,[3,4],5],6] => {"0":1,"1.0":2,"1.1.0":3,"1.1.1":4,"1.2":5,"2":6}

Ventajas:

  1. Aplanar un objeto es más rápido que la solución actual.
  2. Aplanar y desaplanar un objeto es tan rápido o más rápido que la solución actual.
  3. Los objetos aplanados utilizan tanto la notación de puntos como la notación de corchetes para mejorar la legibilidad.

Desventajas:

  1. Desaplanar un objeto es más lento que la solución actual en la mayoría (pero no en todos) los casos.

La demostración actual de JSFiddle dio los siguientes valores como salida:

Nested : 132175 : 63
Flattened : 132175 : 564
Nested : 132175 : 54
Flattened : 132175 : 508

Mi demostración actualizada de JSFiddle dio los siguientes valores como resultado:

Nested : 132175 : 59
Flattened : 132175 : 514
Nested : 132175 : 60
Flattened : 132175 : 451

No estoy muy seguro de lo que eso significa, así que me quedaré con los resultados de jsPerf. Después de todo, jsPerf es una utilidad de evaluación comparativa de rendimiento. JSFiddle no lo es.

Respuesta #3

Versión ES6:

const flatten = (obj, path = '') => {        
    if (!(obj instanceof Object)) return {[path.replace(/\.$/g, '')]:obj};

    return Object.keys(obj).reduce((output, key) => {
        return obj instanceof Array ? 
             {...output, ...flatten(obj[key], path +  '[' + key + '].')}:
             {...output, ...flatten(obj[key], path + key + '.')};
    }, {});
}

Ejemplo :

console.log(flatten({a:[{b:["c","d"]}]}));
console.log(flatten([1,[2,[3,4],5],6]));

Respuesta #4

3 ½ años después...

Para mi propio proyecto quería aplanar objetos JSON en notación de puntos de MongoDB y se me ocurrió una solución sencilla:

/**
 * Recursively flattens a JSON object using dot notation.
 *
 * NOTE: input must be an object as described by JSON spec. Arbitrary
 * JS objects (e.g. {a: () => 42}) may result in unexpected output.
 * MOREOVER, it removes keys with empty objects/arrays as value (see
 * examples bellow).
 *
 * @example
 * // returns {a:1, 'b.0.c': 2, 'b.0.d.e': 3, 'b.1': 4}
 * flatten({a: 1, b: [{c: 2, d: {e: 3}}, 4]})
 * // returns {a:1, 'b.0.c': 2, 'b.0.d.e.0': true, 'b.0.d.e.1': false, 'b.0.d.e.2.f': 1}
 * flatten({a: 1, b: [{c: 2, d: {e: [true, false, {f: 1}]}}]})
 * // return {a: 1}
 * flatten({a: 1, b: [], c: {}})
 *
 * @param obj item to be flattened
 * @param {Array.string} [prefix=[]] chain of prefix joined with a dot and prepended to key
 * @param {Object} [current={}] result of flatten during the recursion
 *
 * @see https://docs.mongodb.com/manual/core/document/#dot-notation
 */
function flatten (obj, prefix, current) {
  prefix = prefix || []
  current = current || {}

  // Remember kids, null is also an object!
  if (typeof (obj) === 'object' && obj !== null) {
    Object.keys(obj).forEach(key => {
      this.flatten(obj[key], prefix.concat(key), current)
    })
  } else {
    current[prefix.join('.')] = obj
  }

  return current
}

Características y/o advertencias

  • Solo acepta objetos JSON. Así que si pasas algo como {a:() => {}} ¡podrías no obtener lo que querías!
  • Elimina matrices y objetos vacíos. Así que esto {a: {}, b: []} se convierte en {}.

Respuesta #5

Usa esta biblioteca:

npm install flat

Uso (de https://www.npmjs.com/package/flat):

Aplanar :

    var flatten = require('flat')


    flatten({
        key1: {
            keyA: 'valueI'
        },
        key2: {
            keyB: 'valueII'
        },
        key3: { a: { b: { c: 2 } } }
    })

    // {
    //   'key1.keyA': 'valueI',
    //   'key2.keyB': 'valueII',
    //   'key3.a.b.c': 2
    // }

Desaplanar:

var unflatten = require('flat').unflatten

unflatten({
    'three.levels.deep': 42,
    'three.levels': {
        nested: true
    }
})

// {
//     three: {
//         levels: {
//             deep: 42,
//             nested: true
//         }
//     }
// }

Artículos relacionados