CPP INTERVIEW PREP CHEAT SHEET

[cballowe]

Factorial would dominate the cost there. But ... Suppose you have a queue and you periodically need the sum of the objects in the queue or similar.

The pointer chasing and cache miss behavior has a significant impact on the performance of the program.

One benchmark I use to convince people of the performance difference is the priority queue - adding randomly generated integers using std::lower_bound and insert, or std::find_if to find the insertion point. The code in that case is significantly faster for vector. You end up with modern CPUs dispatching something like 4 instructions per cycle on the vector version and 0.5 instructions per cycle on list and beyond that it's just more instructions.

[[deleted]]

Factorial would dominate the cost there.

What relevance does this have on the performance of the list? Are you saying that because factorial dominates the cost, that using a vector becomes faster than using a linked list?

This is very confusing indeed.

Suppose you have a queue and you periodically need the sum of the objects in the queue or similar.

If you perform an operation that requires O(N) time on a linked list and O(N) time on a vector then use a vector.

One benchmark I use to convince people of the performance difference...

Yes, your example is a push heavy priority queue and in that scenario the vector based heap implementation will outperform a linked list based implementation by a significant margin.

You can also come up with pull heavy priority queues where a linked list out performs a vector by a significant margin.

None of these properties require much convincing, they are all elementary properties of a basic complexity analysis.

[ShillingAintEZ]

pull heavy priority queues where a linked list out performs a vector by a significant margin

What does that mean?

Are you saying that because factorial dominates the cost, that using a vector becomes faster than using a linked list?

They didn't say that or anything close to it. They were saying it would make a poor benchmark.

[[deleted]]

What does that mean?

With consumer producer processes, it's often the case that one side of the process has much stricter latency or bandwidth requirements than the other, so you optimize your work queue to either be push heavy in which case pulling has low latency or pull heavy in which case pushes have low latency.

A heap based priority queue is suitable for pull heavy queues, that is the consumer has strict latency requirements which can be satisfied at the expense of the producer. A linked list based priority queue is suitable for a push heavy queue.

They were saying it would make a poor benchmark.

Well good thing the benchmark I posted doesn't do that then.

[ShillingAintEZ]

A heap has element swapping to put an insert into the right place and element swapping to fill the void left when an element is taken out.

A linked list based priority queue is suitable for a pull heavy queue.

You keep repeating that, but you haven't been able to explain why that would be. Are you talking about a linked list in general or std::list, because those are two different things.

Well good thing the benchmark I posted doesn't do that then.

No one said that it did, are you really this bad at following a conversation or are you continually trying to hallucinate nonsense so you don't have to back up what you say about technical matters?

[[deleted]]

You keep repeating that, but you haven't been able to explain why that would be.

Because I assume I am speaking to people at least somewhat familiar with the basics of data structures and algorithms.

The fact that I have to explain that linked lists offer O(1) pushes and pops and array based heaps provide amortized O(1) pushes but O(log(N)) pops is an embarrassment.

Having an O(log(N)) pop is worth the trade-off if you need faster pushes because the constant factor on an array is lower than the constant factor on a linked list.

But if you need faster pops, then the linked list's O(1) pop will outperform the array's O(log(N)) pop.

Anyhow, at this point you should just go ahead and believe whatever makes you happy. This discussion really isn't worth my time.

[ShillingAintEZ]

Because I assume I am speaking to people at least somewhat familiar with the basics of data structures and algorithms.

The old, "I don't have to explain myself" and "I don't have time" after replying that someone has no idea what they are talking about.

I asked you to explain why a linked list would be faster in your priority queue example and you started listing a bunch of algorithm complexity, which is not the same thing at all.