Intelligent datastructure?

[The Dragon De Monsyne]

In article <y0jaeqhejn4.fsf at vier.idi.ntnu.no>,
	mlh at idt.ntnu.no (Magnus L. Hetland) writes:
> 
> Hi!
> 
> I'm making a stripped-down language for teaching algorithms (and
> datastructures) without requiring much knowledge of a specific
> language - (it might end up being a stripped-down version of
> Python...)
> 
> I only have two datatypes - integers and sequences. The thing I have
> been thinking about lately is the implementation of the sequences. I
> want them to be usable both as simple lists or arrays, and as general
> hash-tables (with numeric keys) without the user having to care about
> the difference... Thus, you could make yourself a sequence like this:
> 
>   s = [1,2,3]
> 
> and then do something like
> 
>   s[100] = 4
> 
> without getting any complaints. (I think I will only allow positive
> integers as indices, but I'm not sure...)

[ --- 8< --- ]

	Basically what you are looking for is a 'sparse array'
(basically an array (list) that allows unfilled 'holes' in it, so you can 
add list[x] = 42 without needing to actually store x elements. 

	My suggestion is this, if you implement this in Python, just use a
dictionary. Python dictionaries are hashtables, which are pretty fast and 
efficient. 

I timed adding 10k integers to a list, and to an integer-keyed 
dictionary. The list took 2.25 sec, the dict took 0.5 sec. 
(caveat benchmark, YMMV)

--
#############
# I 
# Really,   
# Really,   
# Really,   
# Really,   
# Really,   
# Really,   
# Really,   
# Really,   
# __Really__  hate newservers that have bogus limits on quoted text. :P
############# 

-- 
	-The Dragon De Monsyne