Re: [gtk-list] g_list_append is O(n^2)

[Paolo Molaro <lupus lettere unipd it>]

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.