Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

JavaScript: Search and Don’t Replace (2008)

johnresig.com

Post reply on HN
Print view View original

41–46 of 46 posts

Re: JavaScript: Search and Don’t Replace (2008)

#41

Post by minitech »

Ciantic wrote: post #9

I would have come up with something like this: Object.entries(Array.from(new URLSearchParams("foo=1&foo=2&foo=3&blah=a&blah=b").entries()).reduce((a,[k,v]) => ({ ...a, [k]: [...a[k] ?? [], v] }), {})).map(([key, values]) => `${key}=${values.join(",")}`).join("&");

> .reduce((a,[k,v]) => ({ ...a, [k]: [...a[k] ?? [], v] }), {}))

Note that this unfortunately common pattern is quadratic, which is usually not a good idea, and can have conflicts between entries and properties of Object.prototype. A similar implementation without those problems:

  .reduce((a, [k, v]) => a.has(k) ? a.set(k, [v]) : (a.get(k).push(v), a), new Map())
And an alternate implementation:

  const input = new URLSearchParams("foo=1&foo=2&foo=3&blah=a&blah=b");
  const result = new URLSearchParams();

  for (const key of input.keys()) {
    if (!result.has(key)) {
      result.set(key, input.getAll(key).join(","));
    }
  }

  return String(result);

Re: JavaScript: Search and Don’t Replace (2008)

#42

Post by rezonant »

lucasmullens wrote: post #24

We probably should be cautious reading anything about JS optimization that's 12 years old. It might have been true at the time, but now with the highly-optimized V8 engine, and a set of native methods that didn't exist back then, there's a pretty good chance there's another way to do this that's even faster.

Truer words! I did a quick microbench of a few implementations of this and found that Resig's implementation is far from the best performance possible. PSA: Microbenchmarks are not indicative of real world performance

Find the code here: https://gist.github.com/rezonant/639c67db5bd6503e8f022291b91...

Results on my system (Core i7 7700, Node.js 10.15.3, Windows 10 2004):

---- Comparing 7 implementations, 1000000 repetitions each

  short input:
      resig: 2920ms
      resigModernized: 2369ms
      fullyFunctional: 2817ms
      functionalHybrid: 2352ms
      mapReduce: 5002ms
      splitmap: 1490ms
      compressURL: 6064ms
  long input, few keys:
      resig: 28664ms
      resigModernized: 23087ms
      fullyFunctional: 17509ms
      functionalHybrid: 18431ms
      mapReduce: 46959ms
      splitmap: 14791ms
      compressURL: 24485ms
  long input, many keys:
      resig: 17468ms
      resigModernized: 15049ms
      fullyFunctional: 15781ms
      functionalHybrid: 13768ms
      mapReduce: 30352ms
      splitmap: 12959ms
      compressURL: 34180ms
----

The winner (according to this crude benchmark) is this implementation:

  function splitmap(data){
      let q = new Map();
      for (let [key, value] of data.split(/&/g).map(x => x.split(/=/))) {
          q.set(key, `${q.has(key) ? q.get(key) + ',' : ''}${value}`);
      }
  
      let ret = "";
      for (let [ key, value ] of q)
          ret = `${ret ? ret + '&' : ''}${key}=${value}`;
      return ret;
  }
...but I'm sure folks can come up with something faster

EDIT: The splitmap() implementation will fail on key=value=foo, cutting off the extra "=foo", though if you are expecting valid URL-encoded params then this might be an acceptable limitation.

Re: JavaScript: Search and Don’t Replace (2008)

#43

Post by chmod775 »

recursive wrote: post #40
chmod775 wrote: post #31

He missed an opportunity to make that even shorter and even more of a clusterfuck. I present to you: function compress(data){ var s = {}, q = []; data.replace(/([^=&]+)=([^&]*)/g, function(m, k, v) { s[k] ? q[s[k] - 1] += "," + v : s[k] = q.push(m); }); return q.join("&"); }

Further fucked: function compress(data){ return data.replace(/(? I say: do replace after all! (Javascript didn't have zero-width look-behinds at the time)

That doesn't handle strings like

    foo=1&foo=2&foo=3&blah=a&blah=b&foo=4
correctly. You'd expect

    foo=1,2,3,4&blah=a,b
but get

    foo=1,2,3&blah=a,b&foo=4
I don't think it's possible to solve this just using a single search/replace.

Re: JavaScript: Search and Don’t Replace (2008)

#44

Post by recursive »

chmod775 wrote: post #43
recursive wrote: post #40

Earlier quoted context omitted.

Further fucked: function compress(data){ return data.replace(/(? I say: do replace after all! (Javascript didn't have zero-width look-behinds at the time)

That doesn't handle strings like foo=1&foo=2&foo=3&blah=a&blah=b&foo=4 correctly. You'd expect foo=1,2,3,4&blah=a,b but get foo=1,2,3&blah=a,b&foo=4 I don't think it's possible to solve this just using a single search/replace.

It wasn't clear from the post whether that was a valid input. If it is, some parts would need to be re-ordered, making it a very fancy search/replace indeed. But I still think it's possible. One or two replacements to switch the ordering, and then my original one to get the final output.

Re: JavaScript: Search and Don’t Replace (2008)

#45

Post by recursive »

chmod775 wrote: post #43
recursive wrote: post #40

Earlier quoted context omitted.

Further fucked: function compress(data){ return data.replace(/(? I say: do replace after all! (Javascript didn't have zero-width look-behinds at the time)

That doesn't handle strings like foo=1&foo=2&foo=3&blah=a&blah=b&foo=4 correctly. You'd expect foo=1,2,3,4&blah=a,b but get foo=1,2,3&blah=a,b&foo=4 I don't think it's possible to solve this just using a single search/replace.

I put some effort into trying to find a search/replace to do it. Without a high-powered replacement function, I couldn't do it. But I did do this instead.

        function compress(data){
            return data.split`&`.sort().join`&`.replace(/(?

Re: JavaScript: Search and Don’t Replace (2008)

#46

Post by chmod775 »

recursive wrote: post #45
chmod775 wrote: post #43

Earlier quoted context omitted.

That doesn't handle strings like foo=1&foo=2&foo=3&blah=a&blah=b&foo=4 correctly. You'd expect foo=1,2,3,4&blah=a,b but get foo=1,2,3&blah=a,b&foo=4 I don't think it's possible to solve this just using a single search/replace.

I put some effort into trying to find a search/replace to do it. Without a high-powered replacement function, I couldn't do it. But I did do this instead. function compress(data){ return data.split`&`.sort().join`&`.replace(/(?

That's a really creative way to do it!
Post reply on HN