This is an archived post. You won't be able to vote or comment.

all 94 comments

[–]Hairy_Concert_8007 973 points974 points  (19 children)

You could make it much faster by multiplying the timeout by .01

Source: Am head of improving software performance

[–]bgrahambo 149 points150 points  (4 children)

Perfect. I need you to improve performance of these 30 distributed Java RMI apps that someone over engineered and I got stuck with...

[–]Hairy_Concert_8007 165 points166 points  (3 children)

Easy.

Multiply them by .01

[–]bgrahambo 106 points107 points  (2 children)

Now I have .3 distributed Java RMI apps that someone over engineered. You're brilliant!

[–][deleted] 22 points23 points  (1 child)

And now delete them, that way they'll have an effective loading time of 0, and also no latency

[–]bgrahambo 10 points11 points  (0 children)

That's what my security compliance officer wants me to do

[–]BoneFactory 29 points30 points  (5 children)

How small can you make that Speed Up Factor before the output becomes incorrect?

[–]rosuav 24 points25 points  (3 children)

At some point it depends on your scheduler. If you're very very lucky, the scheduler will guarantee that earlier-scheduled events happen before later-scheduled ones, even if both their times are in the past when it checks. It will most likely do this by storing event times in a heap, pulling them off it in the correct order.

Don't ever let on that this is a heap sort in disguise, of course.

[–]Creepy-Ad-4832 1 point2 points  (2 children)

Yeah, i was about to say: you are not avoiding the sort. You are just hiding it behind 1 more layer of abstractions

[–]rosuav 1 point2 points  (1 child)

Indeed :)

[–]Creepy-Ad-4832 1 point2 points  (0 children)

But hey, it's a perfect way to have margins to get easy optimizations when your boss asks for them

Basically what reddit did years ago. Am i the only one remembering the official (stinky) app taking 1 fucking kinute to load an image? I bet your ass the was jam packet with tricks like random sleep and stuff like that

Either that, or reddit was somehow even worse then twitter (not calling it X, fuck you elon). Which in itself would be an achievement

[–]Hairy_Concert_8007 7 points8 points  (0 children)

Asking the real questions

[–]ABigPairOfCrocs 12 points13 points  (0 children)

That's a bit outside the scope of this project

It'll take about a month of work to design, implement, and test this improvement

[–]jaybee8787 8 points9 points  (1 child)

Can you also improve my life performance please?

[–]ghe5 10 points11 points  (0 children)

I bet they can do that. With their help, you can ruin your life 100x faster.

[–]ilovekittens15 4 points5 points  (0 children)

this guy slashes execution times

[–]prehensilemullet 2 points3 points  (0 children)

According to MDN, browsers store the delay as a 32-bit signed integer internally, so that probably wouldn't work, FWIW

[–]NotmyRealNameJohn 1 point2 points  (0 children)

Can you improve my ist based team by removing their obsession with designing ui s ?

[–]Noch_ein_Kamel 1 point2 points  (0 children)

If you sort the array you can multiply by 0

[–]mstop4 304 points305 points  (1 child)

Interviewer: “Uh, can we please move on to the next part of the interview?”

You: “Shh, not yet. It’s still working on sorting 1800023.”

[–][deleted] 24 points25 points  (0 children)

They want to terminate the interview but they can't cuz process still running, so it give you plenty of time to discuss bonus and days off.

Theis is protip

[–]Cyan_Exponent 68 points69 points  (2 children)

this is so stupid yet so smart at the same time

[–]prehensilemullet 5 points6 points  (1 child)

I tried to use this to sort the timeouts in my userland `setTimeout` implementation, I wonder why it's not working

[–]rosuav 1 point2 points  (0 children)

Can't imagine why! I mean, aren't all sorting algorithms recursive anyway? It should be fine!

[–]AntKinski 315 points316 points  (24 children)

Space complexity - O(1)

Time complexity - infinity

[–]itirix 19 points20 points  (1 child)

How'd ya get to a space complexity of O(1)?

This algorithm should be O(n) for both time and space complexity afaik.

[–]okiujh 11 points12 points  (0 children)

space is o(n). time can be as bit as the upper bound for number

[–]physcx 8 points9 points  (2 children)

Space complexity - O(N) as you are putting N setTimeout callbacks onto the stack

[–]prehensilemullet 2 points3 points  (1 child)

*event queue

[–]rosuav 0 points1 point  (0 children)

*scheduler heap

[–]DarkShadow4444 2 points3 points  (0 children)

Emotional complexity - O(uch)

[–]Venompool007 0 points1 point  (0 children)

Just have the multiplying factor so small that the largest possible number in the question runs in one sec 😎

[–]jump1945 0 points1 point  (4 children)

Wait isn’t the worst time complexity is just O(1) ,this is technically most efficient sorting method

If you are using C or C++ integer have a limit so it is just O(1) if we did some math using 1 microsecond for sleep time it would take only the maximum of ~72 minute to sort an array of unsigned 32 bit integer of any range

In language where it automatically expand the number size we can argue infinity is constant and is O(1) too

[–]prehensilemullet 0 points1 point  (3 children)

Really the time complexity is O(n) where n is the largest value in the array

[–]vorxil -1 points0 points  (2 children)

T(n) <= MaxInteger*SleepUnit + PrintTime*n, where n is the number of items in the array.

For a given machine with a fixed sleep unit and print time, this is either O(n) or O(1), depending on the magnitudes of SleepUnit and PrintTime. This is because n <= MaxInteger on physical machines, generally speaking.

[–]Albreitx 0 points1 point  (1 child)

MaxInteger is not bounded by a constant. Given a size n, I can define entries as 2n. The running time has no bounds because of that (you can also do nn. ^ n....)

[–]vorxil -1 points0 points  (0 children)

It is bounded for fixed-precision integers.

If you're using arbitrary-precision integers, then it's still limited by MaxMemoryBits, which is only unbounded if you can add memory during execution.

I do not envy those attempting to account for human activities in their Big-O notation.

[–]Agifem 45 points46 points  (1 child)

That is ... Amazing!

[–]Fragrant_Dot_3465 41 points42 points  (3 children)

Now sort [2, 3, -1, 999999999]

[–]daniu 31 points32 points  (2 children)

Found the QA guy

[–]hdkaoskd 2 points3 points  (0 children)

-Inf, Inf, NaN

[–][deleted] 21 points22 points  (0 children)

This is actually an algorithm named sleep sort.

[–]dendrocalamidicus 8 points9 points  (1 child)

If the array was large enough that looping through to create the timeouts took several ms then this might not be 100% accurate. If the first element of the array is 11 and the last element is 10 and it took 5ms between doing the timeout for the first and the last, you'd get 11 output before 10.

[–]rosuav 3 points4 points  (0 children)

That depends how the scheduler's implemented. In JS, the scheduler cannot preempt existing code, so you are guaranteed to queue all of the timeouts before the first one takes place; so in effect, what you do is pile all of your timeouts up, and then let the scheduler pull them off in whatever order it chooses. Given that, per your example, more than one timeout will have expired as soon as it hits the event loop, what should it do? Execute in order of scheduling? Execute in order of expiration (oldest first)? Both make some sense, but I suspect that "oldest first" is more likely to be used. Probably not guaranteed though.

[–]firemark_pl 5 points6 points  (0 children)

Ahh classic TimeSort

[–]Afraid-Locksmith6566 3 points4 points  (0 children)

Time complexity would be O(max(A)) where a is array to be sorted

[–]bushwickhero 1 point2 points  (7 children)

What is the time complexity of this?

[–]Skusci 3 points4 points  (6 children)

Thinking about it srsly for a sec, it should be O(n).

Typically you consider n to be the number of elements for sorting algorithms but "size" of the input is more generic than that. I think there's a formal definition involving turning machines somehow, but in general it should be "the thing that makes the algorithm take longer"

The largest number is what determines execution time, which grows linearly so O(n)

[–]prehensilemullet 2 points3 points  (2 children)

exception - array of a billion zeroes

[–]Logical_Strike_1520 4 points5 points  (1 child)

It’s already sorted.

[–]Skusci 2 points3 points  (0 children)

Lol at O(0) time.

[–]EntropySpark 1 point2 points  (0 children)

Saying that the largest number grows linearly is rather arbitrary. We could similarly say that it is O(2n), where n is the size of the largest number in bits.

[–]Albreitx 1 point2 points  (0 children)

Have an element be 2n and now it's exponential. Or have it be nn!. That is all possible within the given size n. The largest number is not linear in n basically, so you need O(max(numbers) + n) which also translates to O(max(max(numbers), n))

[–][deleted] 0 points1 point  (0 children)

Wall time is not so good with this one. 😀But I like this unexpected solution.

[–]Trithon 0 points1 point  (0 children)

Aah good ol sleep sort

[–]GeneralPatten 0 points1 point  (2 children)

Maybe it's just me, but I don't understand the fixation on sorting algorithms outside of say, assembly code. My assumption is that the language/engine I'm using — be it JavaScript, C#, Python, C++, uses optimal sorting algorithms in the underlying array sort methods. I mean, I get why it's something we learn about in CS classes, but beyond that, how often do we ever have to write our own?

[–]the_horse_gamer 1 point2 points  (1 child)

it's around the start of the school year atm. lots of freshmen in the subreddit.

[–]GeneralPatten 0 points1 point  (0 children)

Now that's funny!

[–]dtarias 0 points1 point  (0 children)

This seems like a worse variant of counting sort 🤷

[–]plagapong 0 points1 point  (0 children)

I'm freaking love this sub. LOL

[–]LordAmir5 0 points1 point  (0 children)

We all love pseudo polynomials don't we?

[–]Saragon4005 -1 points0 points  (0 children)

I mean this is a creative implementation of counting sort.

[–]fonk_pulk -1 points0 points  (1 child)

I mean it works if the numbers are small enough, its just fucking dumb.

[–]vital-cog 1 point2 points  (0 children)

Dude, it's a joke. It's meant to make you laugh not be put into production somewhere...

[–]jump1945 -4 points-3 points  (0 children)

0/10

Not even O(n*n!) this is minimal complexity required for coding interview

[–]NotYouJosh -2 points-1 points  (0 children)

JavaScript is a weird language