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

When Big O Fools You

jackmott.github.io

Post reply on HN
Print view View original

51–60 of 134 posts

Re: When Big O Fools You

#51

Post by jackmott »

justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

I think what you are saying is only true if you insert at the end of the ArrayList, (or at the beginning if you have one which leaves open space at either end)

If you insert into arbitrary positions, or the front of these particular array lists, it will be O(n) even ignoring the growth issue, because every element has to be copied over 1 spot.

Re: When Big O Fools You

#52

Post by SamReidHughes »

sn41 wrote: post #14

I agree with the fundamental point in the article, but isn't it well known that when you consider multiple levels of the memory hierarchy as a whole, big O notation needs to be modified to take into account the relative cost of access? I think the problem is not so much the big-O notation, but that the underlying assumption that the data access is from an "all main memory" model with no cache or secondary storage is…

That depends on whether you expect the data to already be in memory or not. If it's already in memory, you would care a lot about cache locality. And in general, you don't want to spuriously lose on some benchmark if there's anything you can do about it.

Re: When Big O Fools You

#53

Post by SamReidHughes »

billconan wrote: post #39

I think the overemphasis of big O, especially during job interviews, is a sad thing. I think multi-threading is an equally important skill, that gets less attention.

It's not. The reason is, a lot of stuff isn't multithreaded or is just a bunch of threads talking to a database. (I've been asked questions about multithreaded stuff, in interviews at companies that specifically did multithreaded stuff. Companies that talked to databases would be better off asking SQL stuff.)

Re: When Big O Fools You

#54

Post by barrkel »

justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

Amortising allocation won't help the article's example, which is insertion at the front, unless you have a quite unorthodox implementation of your array list (e.g. implementing something like a deque using a circular buffer).

The Python growth allocation doesn't look peculiar to me. It's just calculating exponential growth without floating point operations. Whether you over-allocate in 50%, 25%, 12.5%, or whatever proportional increments (all trivial to calculate using bit shifts), they are all enough to make dynamic growth of the array O(n) over time. Any exponential growth will do. If anything, Python's list growth looks to me like it trades off slightly too much time to save space. Actual results will vary depending on realloc implementation etc of course.

Re: When Big O Fools You

#55

Post by malisper »

qwertyuiop924 wrote: post #26

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

This advice applies a ton to databases. At my job, our application is heavily disk i/o bound, with a database query typically taking several seconds. I benchmarked how different sorting the rows in our db by time would be compared to our current layout (partially sorted by user, partially sorted by time, which was completely accidental). Sorting by time benchmarked ~10x faster, which is absolutely huge.

Re: When Big O Fools You

#56

Post by pmelendez »

qwertyuiop924 wrote: post #26

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

In games, critical systems and high traffic backend systems it means a lot.

Re: When Big O Fools You

#57

Post by gens »

bfstein wrote: post #46
justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

The nuance you're missing here is that the author is always inserting at the front of the arraylist. So even though the list grows dynamically, it still needs to move every value one spot over. e.g. arraylist: [0][1][2][3][ ] Even though there is space left in the array, we still need to move all the values one index to the right to be able to insert at the front, which takes O(n) time. In contrast, inserting at the…

Can't you just imagine it is reversed, where the_array[num_things-1] is the first ?

Re: When Big O Fools You

#58

Post by vonmoltke »

_benedict wrote: post #36
stcredzero wrote: post #31

Earlier quoted context omitted.

I would say, "If your software engineering begins and ends with [jargon] you're likely doing a terrible job. Measure, and test. Always." As a field, do we measure and test the effect of using various programming paradigms, patterns, and coding standards? I don't think most companies do this. Most developer decisions are made by "gut." As a field, we are still more like the "before" of Moneyball than the after.

There's a third option: analysis and understanding. This seems to be entirely forgotten by the "measure, test" crowd - the scientific method requires a hypothesis to test for measurements to be meaningful, and separately not all things that are produced are "tested" in every aspect, since many things are well established, and the application of that existing theoretical framework makes measurement and testing a waste…

> the scientific method requires a hypothesis to test for measurements to be meaningful

That's the simplistic grade school version. In practice, characterization and measurement is part of a feedback cycle that is used to develop and refine hypotheses. Experiments need a hypothesis to test, but measurements do not require experiments. Where the "measure, test" crowd usually goes off the rails is in not entering that scientific feedback cycle after the initial measurements and instead jumping to conclusions based on gut feel interpretation of them.

Re: When Big O Fools You

#59

Post by JohnLeTigre »

tillytal wrote: post #33
JohnLeTigre wrote: post #23

Earlier quoted context omitted.

Of course this was a single example. The main point is that the big O notation ignores the cache misses. For example: - try writing a quicksort as a template to avoid the comparison function calls - in the sorting loop, switch to an insertion sort when buckets have You will see speed improvements of 2 to 3 times faster than a vanilla implementation of quicksort. Although this approach is slightly more complex on the…

Surely the main point is that O(n) + O(n) = O(2n) = O(n) = O(n + 1) = O(n) + O(1) and the constant factors left out of O() often dominate execution time. Cache performance is just one example of a constant factor, right?

Cache performance is not constant, if it was, we wouldn't even consider it when optimizing.

The point is to use data that was recently fetched into the (faster) cache memory as much as possible instead of incuring the penalty of a cache miss

Cache performance really depends on memory access patterns.

Anyways :) I'm being pedantic here, I should probably go back to work.

Re: When Big O Fools You

#60

Post by qwertyuiop924 »

SamReidHughes wrote: post #38
qwertyuiop924 wrote: post #26

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

Big O notation is used to describe whatever you want it to. The average case is the usual choice, in fact.

Oh. Sorry.
Post reply on HN