341–350 of 409 posts
Being a lead does not make you infallible or even least wrong. You must always be learning and that means often being wrong.
Source: me, a lead
Earlier quoted context omitted.
I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. Of the many scenarios where amortized complexity is not okay, code in a tight loop where predictable performance is key, e.g. code running game logic, jumps immediately to the top of the list. The fact that you were unable to incorporate this into the conversation makes me suspect you were more interested in putting on…
Games work with time budgets of many milliseconds per frame, relatively long timescales from a cpu pov. It is rare to prefer predictable per iteration latency in loops over higher throughput unless the deferred batch of work is quite big. But of course this can compound in some cases, eg you have thousands of these arrays being extended in lockstep and they all trigger the extra work at the same time...
Earlier quoted context omitted.
Interestingly, you can use scheduling to make a non-amortized dynamic array. Your probably know this, but for other commenters who do not— Keep two arrays, of size n and 2n. Initially the first has capacity c = n/2 and the second has capacity 0. Reads go to the first array. When you append, append one element to the first array, and copy two elements to the second array. By the time the first array is full, it has be…
This is dangerous, but if well documented and understood it might be okay. Some data might contain unique things (for argument's sake, say a std::unique_ptr). It can get tricky since you need to know the implementation details of everything that gets inserted and it's ownership behavior, since elements can be kept at two places. (A copy in array n and one in 2n.) Then there is the fact that you basically make every i…
This is the exact same average cost per element, just spread out evenly. Consider that each element still gets copied to the array of twice the size once whether you use this technique or the classic amortized version. Same average performance without the hitches (although copying a larger block of memory at once would likely be a bit faster).
Earlier quoted context omitted.
Unfortunately, you are wrong. Arrays used as backing for lists are faster than linked list in almost all cases, assuming they are implemented correctly (as is the case in Java, which I bring as an example). Linked lists have a lot of huge downsides that are not easily captured in their naive big-O characterization. Big-O does not tell anything about how efficient things are. Two algorithms can have same big-O complex…
I’m not sure what I am wrong about, I’m simply pointing out that worse average case performance is sometimes desirable over better average case worse worst case performance. Context is everything. Also some things to note: a) game logic tends not to parallelize very well for various reasons, but even so it depends on the domain of the problem whether or not you can run a parallel algorithm on a linked list, b) if you…
I bombed an interview at a game company because I gave a right answer that I couldn't get them to understand. I don't remember the exact problem they wanted me to solve, but the answer involved a dynamic collection and they wanted it to grow with constant time complexity. They were probably looking for a linked list. But I said I'd use a dynamic array because those have constant time when averaged over a series of ap…
I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. Of the many scenarios where amortized complexity is not okay, code in a tight loop where predictable performance is key, e.g. code running game logic, jumps immediately to the top of the list. The fact that you were unable to incorporate this into the conversation makes me suspect you were more interested in putting on…
This flippant remark followed by the egotistical follow up is the kind of art I read hacker news for, thank you.
Earlier quoted context omitted.
I bet they weren’t as dumb as you think and you were passed on for being stubborn and drunk on ego. Of the many scenarios where amortized complexity is not okay, code in a tight loop where predictable performance is key, e.g. code running game logic, jumps immediately to the top of the list. The fact that you were unable to incorporate this into the conversation makes me suspect you were more interested in putting on…
Interviews are about shows, not boring answers.
Earlier quoted context omitted.
None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed.
> None of the comments above yours in the thread mention any form of the word "fast" or "speed". They mention "performance" in reference to big-O complexity. Big-O is not always about speed. I am sorry, do you want to say "performance" and "big-O" have nothing to with trying to make the program go faster? I think you have lost your way and need to backtrack a little bit. The whole point of big-O analysis is to be abl…
It's an important technicality that matters when you are doing performance tuning of code on modern CPU's. Big-O is asymptotic but omits the constant multiplier, so if you're comparing, for example, deletion from a naive binary search tree vs. an unsorted array, it's not necessarily obvious that a tree search on a naive pointer based tree (O(log n)) is faster than a find, swap, and delete (O(n)) until n is sufficiently large.
Another example is iterating through the pixels of a very large bitmap on the order of 10m+ pixels. While iterating through all pixels should be linear to the number of pixels (O(width * height)), assuming it's a row-oriented bitmap, which most are, scanning row by row can be substantially faster than scanning column by column because of caching behaviors.
Point being, big-O and actual performance are not always the same thing because the constant factor can sometimes dominate depending on what you're trying to do.
Earlier quoted context omitted.
I'm confused - that isn't what I understand O(1) to mean. To me, O(1) means only that there exists some constant that bounds the runtime, while individual invocations can absolutely be sometimes faster.
Well, not exactly. What it really means is that the execution time does not depend on the size of input (n). What it does not say is how much time it takes to execute, whether it is exactly same amount of time every time or whether there exists some kind of upper bound on execution time. For example, an algorithm that takes 1/(randFloat()) time to insert an element to the data structure where randFloat() returns any…
According to the definition, if 1/(randFloat()) = O(1) then there must be a constant M that satisfies 1/(randFloat()) (In practice on most systems there would be an upper limit since a float can't be infinitely close to zero, but let's act as if that wasn't the case.)
I was in a job interview several years ago and I was given the following prompt: "You have a database containing locations with their corresponding latitudes and longitudes. We want to be able to input an arbitrary latitude and longitude and have the program return all locations within a radius from that point from the database." My initial reaction was to say "I would use a GIS library/API", but the interviewer want…
There's a sizable portion of people believing that spherical coordinates can be directly converted to planar coordinates :-).
Earlier quoted context omitted.
They were technically correct. The lookup time on a binary search tree is O(H), which is equal to O(log2n) if the tree is balanced. Tree data structures invest a lot of complexity into keeping the tree balanced.
Doesn't this only affect inserts and deletes though? I mean I get your point, but on a read you can assume that a binary tree is balanced (by definition). Or am I missing something?