3 ms·
Could you elaborate on the "logarithmic method"? The fastest technique I know of to insert into sorted arrays uses a square-root decomposition.
by senderista 7y ago
Could you elaborate on the "logarithmic method"? The fastest technique I know of to insert into sorted arrays uses a square-root decomposition.
- JoeAltmaier 7y agoInterval-halving? Is that a thing with trees?
- thesz 7y agoYou can split a collection of 2^(k-1)<=N<2^k elements into up to k arrays with length 2^i. Insertion into empty array with one element capacity is easy, insertion into array with single element creates an array with two elements. If you already have an array of two elements, you should merge these elements into array of 4 elements. The merge operation is fast and cache oblivious. Thus, insertion into a set of these arrays is fast. Query is not so fast - O(log^2N). But I can direct you to Cache-Oblivious Lookahead Arrays (COLA) paper where a technique to get back to O(logN) complexity for lookup is described. Or you can simple merge these arrays into one at the bulk insertion end. Source code (not mine): https://github.com/giannitedesco/cola https://github.com/giannitedesco/cola