News for hackers. Stuff that matters.
Re:Ruby `reject!` by ouid on Monday February 20, 2017 @05:37PM (#13691653)
I think that perhaps the most interesting part of this article is that it comes from a blog called 'accidentallyquadratic' with more than one entry.
Re:Ruby `reject!` by jameshart on Monday February 20, 2017 @07:43PM (#13692321)
I remember coming across it before when the left-pad incident happened, and marvelling at the fact there were already many entries there then. The problem is now, whenever a new entry on this blog gets linked, I find myself compelled to go back and read all the entries in it again. I can't help thinking that over time, that process is going to become prohibitively slow.
Re:Ruby `reject!` by ouid on Monday February 20, 2017 @09:02PM (#13692630)
It's probable that, as time goes on, the interestingness threshold for linking to a post on the blog will get higher, perhaps even exponentially.
Re:Ruby `reject!` by rikkus on Tuesday February 21, 2017 @03:47AM (#13694252)
This should be the highest voted comment on hackernews, or we're doing something wrong.
Re:Ruby `reject!` by ouid on Wednesday February 22, 2017 @01:29AM (#13703519)
it's pretty elegant.
Re:Ruby `reject!` by emfree on Monday February 20, 2017 @10:25PM (#13693011)
One of the older posts eloquently discusses why "accidentally quadratic" behavior is both so recurring and so insidious: http://accidentallyquadratic.tumblr.com/post/113840433022/wh...
Re:Ruby `reject!` by vanderZwan on Tuesday February 21, 2017 @06:43AM (#13694849)
Raise your hand if you have not only written accidentally quadratic code, but managed to compose said code in such a way that you ended up with something even worse!

raises hand

Imagine you have a React SPA where users can select a number of items for which they want more information (I can't give more details at this moment). Said information has to be fetched from the server upon selection.

I recently discovered that the website would fetch all selected items whenever a new item was selected, including previously selected items, regardless of whether it had already been fetched. So if I start with one selection and build up to n, that is 1 + 2 + .. + n-1 + n = (n²+n)/2[0]. Whoops.

To make it worse, I had also somehow had managed to set up my components in such a way that for each fetch being received, React would remount (that's right, re-mount) all of the selected items. Don't ask me how. I'll just say have only been doing web stuff since last year and leave it at that.

If we assume a user clicks fast enough to select every item before the fetches are received, that would be the previous equation multiplied by n selections, so.. (n³+n²)/2. Yikes!

So yeah... that was stupidly slow. Here's what I did to fix it; obvious but worth spelling out:

    - only fetch what hasn't been/isn't being fetched
    - only re-render the component that was updated
    - don't immediately do the above when the user 
      selects an item; let them make a selection first,
      then click a "show information" button, then
      fetch all the needed information in a *single* fetch
      and render it in a *single* update to the components.
[0] https://www.wolframalpha.com/input/?i=sum+one+to+n
Re:Ruby `reject!` by inopinatus on Monday February 20, 2017 @10:52PM (#13693149)
Looking forward to sister blog "Inadvertently Exponential" and the satirical "Maliciously Factorial".
Re:Ruby `reject!` by greenyoda on Tuesday February 21, 2017 @03:28AM (#13694198)
Many years ago, I got a bug report about a feature in an ex-coworker's code. The complaint was that the program would hang when you added the tenth item in a GUI. It turned out that it didn't really hang, but took a half hour to execute because the algorithm was inadvertently exponential. Further examination of the code revealed that the result of the exponential calculation wasn't even being used. So I didn't have to figure out how to make the algorithm linear - I just removed the useless code.
Re:Ruby `reject!` by thunderbong on Monday February 20, 2017 @05:45PM (#13691713)
Yes! And posts dealing with quadratic behavior in languages!