We’re rewarding the question askers & reputations are being recalculated! Read more.
3 added 52 characters in body
source | link

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

No probabilistic analysis requiredO(1) time for every single acces. Also, I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..

EDIT: If we don't assume RAM model, even so, then the expected complexity of an access would be O(1) under assumptions of all indices being access uniformly. The time bound step would be finding which main_array has the data and that would be computed by looking at the bits in the index. The probabilistic analysis here is same as that of VList.

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

No probabilistic analysis required. Also, I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..

EDIT: If we don't assume RAM model, even so, the expected complexity of an access would be O(1). The time bound step would be finding which main_array has the data and that would be computed by looking at the bits in the index. The probabilistic analysis here is same as that of VList

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

O(1) time for every single acces. I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..

EDIT: If we don't assume RAM model, then the expected complexity of an access would be O(1) under assumptions of all indices being access uniformly. The time bound step would be finding which main_array has the data and that would be computed by looking at the bits in the index. The probabilistic analysis here is same as that of VList.

2 added 288 characters in body
source | link

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

No probabilistic analysis required. Also, I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..

EDIT: If we don't assume RAM model, even so, the expected complexity of an access would be O(1). The time bound step would be finding which main_array has the data and that would be computed by looking at the bits in the index. The probabilistic analysis here is same as that of VList

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

No probabilistic analysis required. Also, I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

No probabilistic analysis required. Also, I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..

EDIT: If we don't assume RAM model, even so, the expected complexity of an access would be O(1). The time bound step would be finding which main_array has the data and that would be computed by looking at the bits in the index. The probabilistic analysis here is same as that of VList

1
source | link

Comment was getting too long, and my previous answer was complex enough not to further muddy it, but based on your VList link, here's another answer:

Main data structure: List (no need to be linked) of arrays (I'll call them main_arrays), doubling in size whenever capacity is constrained. Start with 1 sized main_array, then add a 2-length main_array, then a 4-length.

Maximum such array size would depend on computer's bitness, so 2^64 for a 64 bit computer. 2^64 total capacity vector would require 63 such main_arrays in our data structure. So allocate a 63 (or 64) size auxilliary array (I will call it aux_array) to keep references to end points of each of these main_arrays. Allocation of space would be constant time if OS pleases. Adding entry to aux_array is constant time.

Now the trick here is that for all practical purposes, specially when one is talking about C++ stl, we can use RAM model for analysis, which means all bit operations would be constant time.

Say we've so far allocated n=5 main_arrays, total vector capacity so far is: 2^0 + 2^1 .. 2^4 = 2^n - 1 = 31.

Now to access (k = 3)th element, subtract k from 2^n - 2, (2^5-2)-3 = 27.

J = Bitwise OR the result such that 64-n initial bits of this result are 1.

Now find the first 0 bit from left in this integer.(This is constant time in RAM model)

Lets say the index is q. let p = 63 - q.

End address of main_array that stores this element is aux_array[ p ]. H = Create a new integer which is 0.left_shift( p bits, insert 1).

Value at address aux_array[ p ] - ( J & H ) should give you your array value.

No probabilistic analysis required. Also, I might have made some off by one errors, but none so bad that it changes the complexity of the algorithm (I think! :-)).

Happy to know if there are mistakes in this algorithm..