[9326] in The GTK GIMP ToolKit mailing list archive
[gtk-list] Re: g_list_append is O(n^2)
daemon@ATHENA.MIT.EDU (Paolo Molaro)
Thu Oct 15 07:49:10 1998
Date: Thu, 15 Oct 1998 13:36:43 +0200
From: Paolo Molaro <lupus@lettere.unipd.it>
To: gtk-list@redhat.com
Mail-Followup-To: gtk-list@redhat.com
In-Reply-To: <19981015121045.A19751@haegar.physiol.med.tu-muenchen.de>; from Robert Wilhelm on Thu, Oct 15, 1998 at 12:10:45PM +0200
Resent-From: gtk-list@redhat.com
Reply-To: gtk-list@redhat.com
On Thu, Oct 15, 1998 at 12:10:45PM +0200, Robert Wilhelm wrote:
> g_list_append() does not work in linear time as it is required for the STL
> equivalent.
Try this one:-)
lupus
================
0 2204156
1 12699572
2 28484574
3 38576775
4 49636045
5 60547701
6 71348351
7 82215037
8 93160597
9 104297383
10 115034585
11 126251893
12 137442333
13 147558109
14 158730751
15 169689437
16 181341952
17 192446293
18 203515295
19 217015485
0 166447
1 158621
2 158318
3 160887
4 157309
5 158328
6 158361
7 157119
8 158891
9 159040
10 162876
11 158772
12 158762
13 167609
14 157952
15 158863
16 169396
17 166699
18 160477
19 161234
0 323255
1 323905
2 315927
3 318636
4 308098
5 320329
6 304208
7 342137
8 325215
9 318712
10 303769
11 327615
12 312733
13 309733
14 306547
15 313762
16 321045
17 318121
18 312337
19 317512
================
#include <glib.h>
#include <stdio.h>
#include <list>
// time stamp counter on pentium
inline unsigned long long get_ticks(void)
{
unsigned long high, low;
__asm__ __volatile__(".byte 0x0f,0x31"
: "=a" (low), "=d" (high));
return ((unsigned long long) high << 32) + low;
}
stl()
{
unsigned long long t;
int i,j;
list<void *> L;
for(i=0;i<20;i++)
{
t = get_ticks();
for(j=0;j<1000;j++)
{
L.insert(L.end(),NULL);
}
printf("%d %lld\n",i,get_ticks()-t);
}
}
glib()
{
unsigned long long t;
int i,j;
GList *list = NULL;
for(i=0;i<20;i++)
{
t = get_ticks();
for(j=0;j<1000;j++)
{
list = g_list_append(list,NULL);
}
printf("%d %lld\n",i,get_ticks()-t);
}
}
eglib()
{
unsigned long long t;
int i,j;
GList *list = NULL;
GList *head = NULL;
for(i=0;i<20;i++)
{
t = get_ticks();
for(j=0;j<1000;j++)
{
if (!list) {
list = g_list_append(list,NULL);
head = list;
} else
head = g_list_append(head,NULL)->next;
}
printf("%d %lld\n",i,get_ticks()-t);
}
}
int main()
{
glib();
eglib();
stl();
return 0;
}
--
"The number of UNIX installations has grown to 10, with more expected."
- _The UNIX Programmer's Manual_, Second Edition, June, 1972.
--
To unsubscribe: mail -s unsubscribe gtk-list-request@redhat.com < /dev/null
