On Jan 22, 11:10 pm, a...@pythoncraft.com (Aahz) wrote:
>
> >I know Python's number one concern will never be speed, but if Python
> >makes an O(1) operation into an unnecessarily O(N) operation for no
> >good reasons other than "it's too complicated, " or it "adds another
> >pointer to the structure," or "it adds another conditional check to
> >list_ass_slice for operations that aren't popping off the top," I
> >think it's reasonable to challenge the design philosophy.
>
> "Rough consensus and running code."
>
> You have a good point, but nobody will ever give your idea serious
> attention until there's a patch and benchmarks.
Here is a benchmark of O(N*N) vs. O(N) for two C programs. One does
memmove; the other simply advances the pointer.
show...@showell-laptop:~$ time ./slow
real 0m1.446s
user 0m1.444s
sys 0m0.004s
show...@showell-laptop:~$ time ./fast
real 0m0.003s
user 0m0.004s
sys 0m0.000s
show...@showell-laptop:~$ diff slow.c fast.c
23,24c23
< lst.size -= 1;
< memmove(lst.p, lst.p + 1, lst.size);
---
> lst.p += 1;
show...@showell-laptop:~$ cat slow.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct ob_item {
int whatever;
};
struct list {
struct ob_item *p;
int size;
};
struct list make_list(int n)
{
struct list lst;
lst.p = malloc(n);
lst.size = n;
return lst;
}
void list_pop_left(struct list lst) {
lst.size -= 1;
memmove(lst.p, lst.p + 1, lst.size);
}
int main() {
struct list lst;
int i;
int n = 40000;
int t;
lst = make_list(n);
for (i = 0; i < n; ++i) {
list_pop_left(lst);
}
}
--
http://mail.python.org/mailman/listinfo/python-list
