From mboxrd@z Thu Jan  1 00:00:00 1970
From: erik quanstrom <quanstro@quanstro.net>
Date: Sat, 14 Nov 2009 10:11:12 -0500
To: 9fans@9fans.net
Message-ID: <2e8d67f23406cbeb2f169c610896ab91@ladd.quanstro.net>
In-Reply-To: <<372549f4a1e93be164e3f5016203c1c3@yyc.orthanc.ca>>
References: <<372549f4a1e93be164e3f5016203c1c3@yyc.orthanc.ca>>
MIME-Version: 1.0
Content-Type: text/plain; charset="US-ASCII"
Content-Transfer-Encoding: 7bit
Subject: Re: [9fans] rows to cols?
Topicbox-Message-UUID: 9bdf6ea6-ead5-11e9-9d60-3106f5b1d025

> It's dog slow (actually, avl(2) is), but its effectively
> unbounded for the input dataset size.

i haven't found avl to be slow, so i was interested in
this.  after stripping out the tmp file and the
unnecessary runes, prof tells me this for a
2000x10000 array.  (normal runtime ~20s)

minooka; prof /mnt/term/usr/quanstro/8.out prof.116938
  %     Time     Calls  Name
50.0  115.833 486724015	_insertavl
12.5   28.961 466724015	cmp
11.9   27.586        1	main
11.4   26.465 466724015	balance
 3.9    9.080 168888891	Bgetc
 3.9    9.069 168888890	Bputc
[...]
 1.5    3.376 20000000	findsuccessor

okay, you're measuring that building an avl tree
takes n log(n)/log(2).  if it were not, i'd be worried!  note
also that the ratio of time(_insertavl)/time(findsuccessor)
= log(n)/log(2).  findsuccessor is the meat of walkavl.

in http://iwp9.org/papers/upasexp.pdf i talked about
a similar issue with hash tables.  if all you do is build
a fast-access structure, then they can be really slow.

- erik