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?
Why do you hate freedom?
When Big O Fools You
91–100 of 134 posts
Re: When Big O Fools You
#92Earlier quoted context omitted.
Furthermore amortization isn't always accounted for in Big-O. Inserting into into the head of a linked list is O(1), and for a vector it is O(n). But on modern hardware vector inserts are much faster. If your software engineering begins and ends with Big-O notation, your likely doing a terrible job. Measure, and test. Always.
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.
What's worse, the field is constantly changing. What was true on one architecture may not be true on another, and even different generations of a single architecture can change a lot.
Re: When Big O Fools You
#93This 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…
Some languages, such as Perl, start the array in the middle to avoid exactly this situation.
Re: When Big O Fools You
#94The author is doing less than 10 insertions per benchmark, that's practically a constant O(1), even if you have to copy the entire array 5 or 10 times don't affect the Big O analysis
Re: When Big O Fools You
#95Earlier quoted context omitted.
Yes, then it would be a discussion about append performance instead of insert performance. Might be handy to do if you know that all the changes to an array will be inserts at the front, then you can just write the array in reverse and also read in reverse. But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will re…
> But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data. This is true if you already have a reference to the middle of the list. If you don't (say, because you want to insert while preserving the fact that the list is sorted), then inserting into a linked list is O(n) just…
Memory reads and memory writes are not the same. Linked list insert in the middle needs to do only O(1) writes. But because linked lists preclude memory prefetch, they should not be used these days.
Re: When Big O Fools You
#96Earlier quoted context omitted.
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…
I deleted from my comment an explicit calling out of this feedback loop, as it was implied, I thought, by the statement that the measurement and testing were both important, but of limited value by themselves.
However I disagree that measurements have any meaning unless they are conducted as experiments, or potentially as exploratory work looking for an experiment to conduct. Even such exploratory work needs to be driven by at least the loosest of hypotheses, since measuring everything is infeasible. So this is just as much an experiment, just one you don't have a high expectation of predicting the outcome of.
Either way, this recognition of the necessity of at least a minimal hypothesis in all of these scenarios is typically lacking is my fundamental point.
The cycle of revision of that hypothesis is clearly the next step and, as I say, I thought clearly implied.
Re: When Big O Fools You
#97Earlier quoted context omitted.
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 programming field isn't lacking in typical programmers with hypotheses. What it's lacking are typical programmers who are checking their hypotheses.
If you take the word hypothesis at its meanest, and ignore everything else I said, sure. But a hypothesis that is grounded in an absence of analysis or understanding of the situation, or an appreciation of the existing body of literature related to a topic, or any other informing principle, is of limited value.
i.e., it's not about checking your hypothesis, it's about checking the method by which you formed your hypothesis.
Checking your hypothesis is fine, but of value only to reject, not to actually find a hypothesis you can accept.
Re: When Big O Fools You
#98Technically speaking, he ought to be using Big Theta (Θ) to describe his bounds. Throwing Big O around to describe everything is foolish.
Re: When Big O Fools You
#99Earlier quoted context omitted.
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 ?
The awful thing about writing benchmarks is that if you don't give the worst case example, people give you shit for coming up with metrics that say whatever you want to say.
If you give metrics for the case that should be worst for your argument, people give you shit about using such a stupid example.
There's no way to avoid someone giving you grief no matter what you do.
Re: When Big O Fools You
#100Earlier quoted context omitted.
Can't you just imagine it is reversed, where the_array[num_things-1] is the first ?
Yes, then it would be a discussion about append performance instead of insert performance. Might be handy to do if you know that all the changes to an array will be inserts at the front, then you can just write the array in reverse and also read in reverse. But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will re…
Stay strong.