2 ms·
Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just
by jayd16 8y ago
Resizing a fully contiguous circle buffer would cause a copy every element as well forcing you to make a single contiguous memory section. Array of arrays just needs to resize the top level array.
- manwe150 8y agoBut the copy only has to move n items, but was constructed with m items, where n < m (and usually n << m). Where n is the max size of the queue and m is the total number of items that will ever be enqueued. On the other hand, an array of arrays (no recursion) doesn’t change the big-O complexity cost, just the constant multiplier. That should definitely improve performance of the uncommon operation (the copy), but hypothetically might slow down the actual queuing operations (and drastically reduce throughout) But maybe you meant the array of arrays to be recursive? That seems like it would alter the big-O (from n+m to log(n)+m). But typically m>>n, so the net result is the same.