replace multiple values in json/jsObject/string

Question

I have a response from a web service and want to replace some values in the response with my custom values.

One way is to write a tree traverser and then check for the value and replace with my custom value

so the response is some what like this:

[
  {
    "name": "n1",
    "value": "v1",
    "children": [
      {
        "name": "n2",
        "value": "v2"
      }
    ]
  },
  {
    "name": "n3",
    "value": "v3"
  }
]

now my custom map is like this

const map = {
  "v1": "v11",
  "v2": "v22",
  "v3": "v33"
};

All I want is

[
  {
    "name": "n1",
    "value": "v11",
    "children": [
      {
        "name": "n2",
        "value": "v22"
      }
    ]
  },
  {
    "name": "n3",
    "value": "v33"
  }
]

I was thinking if I could stringify my response and then replace values using a custom build regex from my map of values.

Will it be faster as compared to tree traverser?
If yes, how should I do that?

somewhat like this

originalString.replace(regexp, function (replacement))

If there's a bunch of results you'll want a loop.

StackSlave
– StackSlave

2017-03-30 05:14:20 +00:00
Commented Mar 30, 2017 at 5:14 — StackSlave
– StackSlave, Commented Mar 30, 2017 at 5:14

Rico Kahler · Accepted Answer · 2017-03-30 06:46:45Z

3

The tree traversal is faster

Note that some things could be done more efficiently in the regex implementation but I still think there are some more bottlenecks to explain.

Why the regex is slow:

There are probably many more reasons why the regex is slower but I'll explain at least one significant reason:

When you're using regex to find and replace, you're using creating new strings every time and performing your matches every time. Regex expressions can be very expensive and my implementation isn't particularly cheap.

Why is the tree traversal faster:

In the tree traversal, I'm mutating the object directly. This doesn't require creating new string objects or any new objects at all. We're also not performing a full search on the whole string every time as well.

RESULTS

run the performance test below. The test using console.time to record how long it takes. See the the tree traversal is much faster.

function usingRegex(obj, map) {
  return JSON.parse(Object.keys(map).map(oldValue => ({
    oldValue,
    newValue: map[oldValue]
  })).reduce((json, {
    oldValue,
    newValue
  }) => {
    return json.replace(
      new RegExp(`"value":"(${oldValue})"`),
      () => `"value":"${newValue}"`
    );
  }, JSON.stringify(obj)));
}

function usingTree(obj, map) {
  function traverse(children) {
    for (let item of children) {
      if (item && item.value) {
        // get a value from a JS object is O(1)!
        item.value = map[item.value];
      }
      if (item && item.children) {
        traverse(item.children)
      }
    }
  }
  
  traverse(obj);
  return obj; // mutates
}

const obj = JSON.parse(`[
  {
    "name": "n1",
    "value": "v1",
    "children": [
      {
        "name": "n2",
        "value": "v2"
      }
    ]
  },
  {
    "name": "n3",
    "value": "v3"
  }
]`);

const map = {
  "v1": "v11",
  "v2": "v22",
  "v3": "v33"
};

// show that each function is working first
console.log('== TEST THE FUNCTIONS ==');
console.log('usingRegex', usingRegex(obj, map));
console.log('usingTree', usingTree(obj, map));

const iterations = 10000; // ten thousand
console.log('== DO 10000 ITERATIONS ==');
console.time('regex implementation');
for (let i = 0; i < iterations; i += 1) {
  usingRegex(obj, map);
}
console.timeEnd('regex implementation');

console.time('tree implementation');
for (let i = 0; i < iterations; i += 1) {
  usingTree(obj, map);
}
console.timeEnd('tree implementation');

edited Mar 30, 2017 at 6:46

answered Mar 30, 2017 at 5:41

Rico Kahler

19.6k14 gold badges67 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Abhijeet Ahuja Over a year ago

ask and you shall receive the check

Rico Kahler Over a year ago

but for the record, @nnnnnn's regex implementation is faster than mine

nnnnnn Over a year ago

My implementation is easier to understand, too, though that's subjective. But obviously your answer is more complete and should be the accepted one.

nnnnnn Over a year ago

"ask and you shall receive the check" - May I have the check please?

nnnnnn · Accepted Answer · 2017-03-30 05:37:10Z

2

Will it be faster as compared to tree traverser?

I don't know. I think it would depend on the size of the input, and the size of the replacement map. You could run some tests at JSPerf.com.

If yes, how should I do that?

It's fairly easy to do with a regex-based string replacement if the values you are replacing don't need any special escaping or whatever. Something like this:

const input = [
  {
    "name": "n1",
    "value": "v1",
    "children": [
      {
        "name": "n2",
        "value": "v2"
      }
    ]
  },
  {
    "name": "n3",
    "value": "v3"
  }
];

const map = {
  "v1": "v11",
  "v2": "v22",
  "v3": "v33"
};

// create a regex that matches any of the map keys, adding ':' and quotes
// to be sure to match whole property values and not property names
const regex = new RegExp(':\\s*"(' + Object.keys(map).join('|') + ')"', 'g');

// NOTE: if you've received this data as JSON then do the replacement
// *before* parsing it, don't parse it then restringify it then reparse it.
const json = JSON.stringify(input);
const result = JSON.parse(
  json.replace(regex, function(m, key) { return ': "' + map[key] + '"'; })
);

console.log(result);

edited Mar 30, 2017 at 5:37

answered Mar 30, 2017 at 5:30

nnnnnn

150k30 gold badges210 silver badges247 bronze badges

2 Comments

Abhijeet Ahuja Over a year ago

Thanks for the nice answer

Rico Kahler Over a year ago

@Abhijeet I hate to disagree with the acceptance, but I implemented both the tree traversal and the regex and showed that the tree traversal is faster yet I still don't get the check. sigh... what i do for rep lol you guys have a nice day haha

nullqube · Accepted Answer · 2017-03-30 05:18:15Z

0

definitely traverser go faster as string replace means travels against each characters in the final string as opposed to iterator that can skips no necessarily item.

answered Mar 30, 2017 at 5:18

nullqube

3,02921 silver badges20 bronze badges

2 Comments

nnnnnn Over a year ago

I'm not saying it would be slower, but an iterator would still have to test the value of every property in the (nested) object.

nullqube Over a year ago

and string regex have to test against each characters in the final string that would be larger than each individual items. comparing "ABC" with "DEF" when the first character are not the same stops comparing and return false but in string contains "ABC" then each character will check against the "ABC" ordering characters.

Collectives™ on Stack Overflow

replace multiple values in json/jsObject/string

3 Answers 3

4 Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related