algoritm - Snabbaste sättet att platta till/återställa nästlade JavaScript-objekt

Jag satte ihop lite kod för att platta ut och avplatta komplexa/nestade JavaScript-objekt. Det fungerar, men det är lite långsamt (utlöser varningen 'långt skript').

För de platta namnen vill jag ha "." som avgränsare och [INDEX] för arrayer.

Exempel:

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}

Jag skapade ett riktmärke som ~simulerar mitt användningsfall http://jsfiddle.net/WSzec/

  • Hämta ett nästlat objekt
  • Platta till det
  • Titta igenom det och eventuellt ändra det medan det är utplattat
  • Gör den oplattad tillbaka till sitt ursprungliga nästlade format för att skickas iväg

Jag skulle vilja ha snabbare kod: För tydlighetens skull, kod som klarar JSFiddle-benchmarken (http://jsfiddle.net/WSzec/) betydligt snabbare (~20%+ vore trevligt) i IE 9+, FF 24+ och Chrome 29+.

Här är den relevanta JavaScript-koden: Nuvarande snabbaste: 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;
}

REDIGERA 1 Ändrade ovanstående till @Bergis implementation som för närvarande är den snabbaste. Som en parentes, att använda ".indexOf" istället för "regex.exec" är cirka 20% snabbare i FF men 20% långsammare i Chrome; så jag kommer att hålla mig till regex eftersom det är enklare (här är mitt försök att använda indexOf för att ersätta regex http://jsfiddle.net/WSzec/2/).

REDIGERA 2 Byggt vidare på @Bergi:s idé lyckades jag skapa en snabbare version utan regex (3x snabbare i FF och ~10% snabbare i Chrome). http://jsfiddle.net/WSzec/6/ I den här (den nuvarande) implementationen är reglerna för nyckelnamn helt enkelt att nycklar inte kan börja med ett heltal eller innehålla en punkt.

Exempel :

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

REDIGERA 3 Att lägga till @AaditMShah:s inline-path-parsningsmetod (istället för String.split) hjälpte till att förbättra prestandan vid unflatten. Jag är mycket nöjd med den övergripande prestandaförbättringen som uppnåtts.

Den senaste jsfiddle och jsperf:

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

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

Svar #1

Här är min mycket kortare implementation:

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 har inte förändrats mycket (och jag är inte säker på om du verkligen behöver de där isEmpty-fallen):

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

Tillsammans kör de din benchmarking på ungefär halva tiden (Opera 12.16: ~900 ms istället för ~1900 ms, Chrome 29: ~800 ms istället för ~1600 ms).

Notera: Denna och de flesta andra lösningar som besvaras här fokuserar på hastighet och är känsliga för prototype- förorening och bör inte användas på opålitliga objekt.

Svar #2

Jag skrev två funktioner för att flatten och unflatten ett JSON-objekt.

Platta till ett JSON-objekt:

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

Prestanda:

  1. Det är snabbare än den nuvarande lösningen i Opera. Den nuvarande lösningen är 26% långsammare i Opera.
  2. Det är snabbare än den nuvarande lösningen i Firefox. Den nuvarande lösningen är 9% långsammare i Firefox.
  3. Det är snabbare än den nuvarande lösningen i Chrome. Den nuvarande lösningen är 29% långsammare i Chrome.

Avplatta ett JSON-objekt:

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

Prestanda:

  1. Det är snabbare än den nuvarande lösningen i Opera. Den nuvarande lösningen är 5% långsammare i Opera.
  2. Det är långsammare än den nuvarande lösningen i Firefox. Min lösning är 26 % långsammare i Firefox.
  3. Det är långsammare än den nuvarande lösningen i Chrome. Min lösning är 6 % långsammare i Chrome.

Platta till och återställa ett JSON-objekt:

Överlag presterar min lösning antingen lika bra eller till och med bättre än den nuvarande lösningen.

Prestanda:

  1. Det är snabbare än den nuvarande lösningen i Opera. Den nuvarande lösningen är 21% långsammare i Opera.
  2. Det är lika snabbt som den nuvarande lösningen i Firefox.
  3. Det är snabbare än den nuvarande lösningen i Firefox. Den nuvarande lösningen är 20% långsammare i Chrome.

Utdataformat:

Ett platt objekt använder punktnotation för objektets egenskaper och hakparentesnotation för arrayindex:

  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}

Enligt min åsikt är detta format bättre än att enbart använda punktnotation:

  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}

Fördelar:

  1. Att platta till ett objekt är snabbare än den nuvarande lösningen.
  2. Att platta till och återställa ett objekt är lika snabbt eller snabbare än den nuvarande lösningen.
  3. Avplattade objekt använder både punktnotation och hakparentesnotation för läsbarhet.

Nackdelar:

  1. Att återställa ett objekt är långsammare än den nuvarande lösningen i de flesta (men inte alla) fall.

Den nuvarande JSFiddle-demonstrationen gav följande värden som utdata:

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

Min uppdaterade JSFiddle-demo gav följande värden som output:

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

Jag är inte riktigt säker på vad det betyder, så jag håller mig till jsPerf-resultaten. Trots allt är jsPerf ett verktyg för prestandamätning. JSFiddle är det inte.

Svar #3

ES6-version:

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 + '.')};
    }, {});
}

Exempel :

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

Svar #4

3 ½ år senare...

För mitt eget projekt ville jag platta till JSON-objekt i MongoDB dot-notation och kom på en enkel lösning:

/**
 * 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
}

Egenskaper och/eller varningar

  • Det accepterar bara JSON-objekt. Så om du skickar något som {a:() => {}} kanske du inte får vad du ville ha!
  • Det tar bort tomma arrayer och objekt. Så detta {a: {}, b: []} plattas till {}.

Svar #5

Använd detta bibliotek:

npm install flat

Användning (från https://www.npmjs.com/package/flat):

Platta till :

    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
    // }

Avplatta:

var unflatten = require('flat').unflatten

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

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

Relaterade artiklar