Dan Stromberg <drsali...@gmail.com>: > On Tue, Mar 18, 2014 at 3:03 PM, Marko Rauhamaa <ma...@pacujo.net> wrote: >> Dan Stromberg <drsali...@gmail.com>: >> For a proper comparison, I'd like a fixed, identical dataset and set >> of operations run against each data structure. >> >> How about this test program: > > I used to do essentially this, but it was time-prohibitive and > produced harder-to-read graphs - harder to read because the enormous > values of the bad trees were dwarfing the values of the good trees. > > Imagine doing 100000000 operation tests for the unbalanced binary > tree. For a series of random keys, it would do quite well (probably > second only to dict), but for a series of sequential keys it would > take longer than anyone would reasonably want to wait because it's > basically a storage-inefficient linked list. > > Rather than throw out unbalanced binary tree altogether, it makes more > sense to run it until it gets "too slow".
I disagree strongly. You should throw out unbalanced binary trees and linked lists and the like and concentrate on solid contenders. But it's your test. You do as you like. Anyway, even a well-thought-out test is subject to all kinds of criticisms due to the CPU architecture, the distribution of the key values, the quality of the data structure implementation etc etc. Marko -- https://mail.python.org/mailman/listinfo/python-list
