> 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
