Le moyen le plus rapide pour aplatir / onu-aplatir imbriquée objets JSON

Question

J'ai jeté un peu de code, ensemble, à s'aplatir et de l'onu-aplatir complexe/imbriquée objets JSON. Cela fonctionne, mais il est un peu lent (déclenche la "longue script' avertissement).

Pour le aplatie noms que je veux "." comme séparateur et [INDEX] pour les tableaux.

Exemples:

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}

J'ai créé un point de repère qui ~simule mon cas d'utilisation http://jsfiddle.net/WSzec/

• Obtenir un imbriquée objet JSON
• L'aplatir
• Regardez à travers et éventuellement de le modifier tout aplati
• Unflatten de retour à l'état initial imbriquée format à être expédié

Je voudrais plus rapide code: Pour clarifier, le code qui complète le JSFiddle de référence (http://jsfiddle.net/WSzec/) beaucoup plus rapide (~20%+ serait bien) dans IE 9+, FF 24+ et google Chrome 29+.

Voici pertinentes du code JavaScript: Courant plus Rapide: http://jsfiddle.net/WSzec/6/

JSON.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[""];
}
JSON.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 Modifié ci-dessus pour @Bergi mise en œuvre, qui est actuellement le plus rapide. En aparté, à l'aide ".indexOf" au lieu de "regex.exec" est environ 20% plus rapide dans les FF, mais 20% plus lent en Chrome; donc je vais rester avec les regex, car il est plus simple (voici ma tentative à l'aide indexOf pour remplacer les regex http://jsfiddle.net/WSzec/2/).

EDIT 2 Bâtiment sur @Bergi l'idée, j'ai réussi à créé un rapide non-regex version (3x plus rapide dans FF et ~10% plus rapide dans google Chrome). http://jsfiddle.net/WSzec/6/ Dans le présent (l'actuelle), la mise en œuvre des règles pour les noms de clés sont tout simplement, les clés ne peuvent pas commencer par un nombre entier ou contiennent une période.

Exemple:

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

EDIT 3 en Ajoutant @AaditMShah 'inline chemin de l'analyse de l'approche (plutôt que de la Chaîne.split) a contribué à améliorer la unflatten performance. Je suis très heureux avec l'ensemble de l'amélioration de la performance atteint.

La dernière jsfiddle et jsperf:

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

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

Answer 1

Voici ma beaucoup plus courte de mise en œuvre:

JSON.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;
};

JSON.flatten n'a pas trop changé (et je ne suis pas sûr de savoir si vous avez vraiment besoin de ceux - isEmpty des cas):

JSON.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;
}

Ensemble, ils exécuter votre référence dans environ la moitié du temps (Opera 12.16: ~900ms au lieu de ~ 1900ms, Chrome 29: ~800ms au lieu de ~1600ms).

Answer 2

J'ai écrit deux fonctions d' flatten et unflatten un objet JSON.

---

Aplatir un objet 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));

Performance:

1. Il est plus rapide que la solution actuelle dans l'Opéra. La solution actuelle est de 26% plus lent à l'Opéra.
2. Il est plus rapide que la solution actuelle dans Firefox. La solution actuelle est de 9% plus lent dans Firefox.
3. Il est plus rapide que la solution actuelle dans Chrome. La solution actuelle est de 29% plus lent dans google Chrome.

---

Unflatten un objet 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[""];
}

Performance:

1. Il est plus rapide que la solution actuelle dans l'Opéra. La solution actuelle est de 5% plus lent à l'Opéra.
2. Il est plus lent que la solution actuelle dans Firefox. Ma solution est de 26% plus lent dans Firefox.
3. Il est plus lent que la solution actuelle dans Chrome. Ma solution est de 6% plus lent dans google Chrome.

---

Les aplatir et les unflatten un objet JSON:

Dans l'ensemble, mon solution effectue soit aussi bien ou même mieux que la solution actuelle.

Performance:

1. Il est plus rapide que la solution actuelle dans l'Opéra. La solution actuelle est de 21% plus lent à l'Opéra.
2. C'est aussi rapide que la solution actuelle dans Firefox.
3. Il est plus rapide que la solution actuelle dans Firefox. La solution actuelle est de 20% plus lent dans google Chrome.

---

Format de sortie:

Aplatie objet utilise la notation de point pour les propriétés de l'objet et le support de notation pour les indices de tableau:

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}

À mon avis, ce format est mieux que de l'aide de la notation par points:

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}

---

Avantages:

1. L'aplatissement d'un objet est plus rapide que la solution actuelle.
2. L'aplatissement et de unflattening un objet est aussi vite ou plus vite que la solution actuelle.
3. Objets aplatis utiliser à la fois la notation par points et le support de la notation pour des raisons de lisibilité.

Inconvénients:

1. Unflattening un objet est plus lent que la solution actuelle dans la plupart (mais pas tous) des cas.

---

L'actuel JSFiddle demo a donné les valeurs suivantes en sortie:

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

Ma mise à jour JSFiddle demo a donné les valeurs suivantes en sortie:

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

Je ne suis pas vraiment sûr de ce que cela signifie, donc je vais rester avec le jsPerf résultats. Après tout jsPerf est une analyse comparative de la performance de l'utilitaire. JSFiddle ne l'est pas.

Answer 3

@Bergi du code que j'ai fait une simple page web pour aplatir // unflatten.

http://fiddle.jshell.net/blowsie/S2hsS/show/light/

Answer 4

Voici une autre approche qui s'exécute plus lentement (environ 1000ms) que la réponse ci-dessus, mais a une idée intéressante :-)

Au lieu d'itérer sur chaque propriété de la chaîne, il choisit juste la dernière propriété et utilise une look-up-table pour le reste de stocker les résultats intermédiaires. Ce look-up-table sera itéré jusqu'à ce qu'il n'y a pas de propriété chaînes de gauche et toutes les valeurs résider sur uncocatenated propriétés.

JSON.unflatten = function(data) {
    "use strict";
    if (Object(data) !== data || Array.isArray(data))
        return data;
    var regex = /\.?([^.\[\]]+)$|\[(\d+)\]$/,
        props = Object.keys(data),
        result, p;
    while(p = props.shift()) {
        var m = regex.exec(p),
            target;
        if (m.index) {
            var rest = p.slice(0, m.index);
            if (!(rest in data)) {
                data[rest] = m[2] ? [] : {};
                props.push(rest);
            }
            target = data[rest];
        } else {
            target = result || (result = (m[2] ? [] : {}));
        }
        target[m[2] || m[1]] = data[p];
    }
    return result;
};

Il utilise actuellement l' data paramètre d'entrée pour la table, et met beaucoup de propriétés - non-destructive, la version doit être possible. Peut-être un habile lastIndexOf d'utilisation fonctionne mieux que le regex (dépend du moteur d'expressions régulières).

Le voir en action ici.