|
::::::: Hmm? If you want to make a reference to a slice of the array, just copy the pointer and set a new offset, which is O(1). If you need to copy the content, then every block that's not empty should be copied, which involves all n elements that's currently filled. The point of taking a slice reference is to avoid this copying. --[[User:Ledrug|Ledrug]] 18:26, 13 September 2011 (UTC)
:::::::: Hmm.. ok... But you need to be careful about the set of allowed operations on a slice. For example, think about what happens to a slice that omits the first character of the original and then what happens when you add another character. Note that if you add to the slice, the behavior of the original is different if it was length 2 vs. if it was length 6. Something analogous can happen with cloning: with a suitably restricted set of operations (if adding is allowed but not dropping) you do not have to clone the entire set of data and can clone only the first block. --[[User:Rdm|Rdm]] 19:50, 13 September 2011 (UTC)
== Not really O(1) ==
I took the C implementation, and instrumented it with some basic benchmarking. The timing here does not seem to be O(1).
Here's my modification (needs #include <time.h>):
<lang C>struct timespec before, after;
void checkclock(int n) {
if (clock_gettime(CLOCK_REALTIME, &after)) perror("clock_gettime\n");
long m= 1000000000*(after.tv_sec-before.tv_sec)+after.tv_nsec-before.tv_nsec;
fprintf(stderr, "%d, time: %d ns, %g\n", n, m, n/(1.0*m));
}
int main()
{
int i, k= 1;
vlist v = v_new();
if (clock_gettime(CLOCK_REALTIME, &before)) perror("clock_gettime\n");
for (i = 0; i < 1000000000; i++) {
if (k==i) {
checkclock(k);
k*= 10;
}
v_unshift(v, i);
}
return 0;
}</lang>
Here's an example run:
<pre>1, time: 400 ns, 0.0025
10, time: 845400 ns, 1.18287e-05
100, time: 2646100 ns, 3.77915e-05
1000, time: 3445400 ns, 0.000290242
10000, time: 4235800 ns, 0.00236083
100000, time: 5758400 ns, 0.0173659
1000000, time: 13975400 ns, 0.0715543
10000000, time: 77276800 ns, 0.129405
100000000, time: 671778600 ns, 0.148859</pre>
This looks like it's slower than O(log n) (where n is the length of the list) for adding a number to the list.
But I cannot tell whether the implementation is a faithful implementation of this data structure, because I cannot find an adequate description of the data structure. Nevertheless, I suspect that there's something wrong with the description presented in the task description. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 04:28, 22 June 2022 (UTC)
| 