21–30 of 134 posts
Earlier quoted context omitted.
The process of weeding out. Sometimes it's better to select against sensitive people.
Why would you select against people with poor vision?
But all in all it is a good page for people with poor vision.
No low-contrast and no white background, which are both considered bad on screens.
If the author sees this: please consider changing your color choices. It'd make reading the content you put so much work into producing easier for everyone. I couldn't finish the post. The 90s hacker's lair colors were that offensive.
Yeah, every website needs to be plastered with big Fisher Price[tm] Facebook buttons and have unreadable hipster light-gray-on-white text.
I don't know how long it will take us till we finally stop with the white backgrounds...
In no so many words, the article is pointing out that O(n) + O(1) is not necessarily quicker than O(n) + O(n): both add to O(n) (since only the highest-order factor matters), and the constant factor is unsurprisingly better for array lists. He's not benchmarking an O(1) operation against an O(n), or anything surprising, or even pointing out a "hidden" O(n) operation, it's simply a demonstration that O(n) + O(1) = O(n…
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 abstract level, it's faster because it reduces lots cache misses.
This is a great point and I'll probably have to do some performance measurements and change parts of my code now. I should be more careful with sacrificing contiguous storage for O(1) insertions. It is also worth noting that some manuals say that appending to an array list is O(1) amortized. Which is true, if you make an amortized analysis (which essentially distributes the workload of copying the array into a larger…
Insertion into an array list at a uniformly-distributed location is always O(n): you can't avoid moving half the list. Appending is amortized O(1).
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 ArrayList will be in O(1) given enough insert operations.
Essentially, you over-allocate in order to save time. You're trading time complexity for space complexity.
A really good explanation on amortised analysis can be found here on Wikipedia, which explicitly treats ArrayList:
https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr...
As always, a look into the source code of your language of choice helps. In Python, a list object over-allocates using a very peculiar, but finely tuned formula: https://github.com/python/cpython/blob/09dc3ec1713c677f71ba7...
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 them for that reason only (assuming that there is any non-perf reason to stick with them) is a premature optimization.
But if you ARE optimizing, yeah, you need to think about how often worst-case occurs. Because big O only tells you about worst-case. NOT the average.
In no so many words, the article is pointing out that O(n) + O(1) is not necessarily quicker than O(n) + O(n): both add to O(n) (since only the highest-order factor matters), and the constant factor is unsurprisingly better for array lists. He's not benchmarking an O(1) operation against an O(n), or anything surprising, or even pointing out a "hidden" O(n) operation, it's simply a demonstration that O(n) + O(1) = O(n…
Also, Big-O notation is a theoretical construct for thinking about complexity that works well for academic proofs but glosses over many real world considerations. Those ignored constant factors can be large and the datasets are not always large enough to amortize their cost.
If your software engineering begins and ends with Big-O notation, your likely doing a terrible job. Measure, and test. Always.
Yes! All abstraction has a price. This is what people really mean when "all abstractions leak." Basically, all code and runtime features have a cost in terms of developer resources, cpu, memory, etc. The "inner game" of development isn't being able to muster huge amounts of "cleverness" power. The "inner game" is being able to put whatever resources you have to the best possible use.
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…
If the author sees this: please consider changing your color choices. It'd make reading the content you put so much work into producing easier for everyone. I couldn't finish the post. The 90s hacker's lair colors were that offensive.
The process of weeding out. Sometimes it's better to select against sensitive people.