From: MikkelFJ Date: 2002-09-17T22:33:37+09:00 Subject: Re: Is Ruby Array#shift/unshift Efficient? "William Djaja Tjokroaminata" wrote in message news:am593i$l3s$1@grapevine.wam.umd.edu... > Hi Matz, > In using a scripting language, aren't we concerned with the underlying > data structure itself? Is the answer: > > 1) Beside array and hash, other data structures are not "practical", in > the sense that they are very rarely used. I have been looking into a deque-like datastructure I call an I-Tree or index tree. It is a linked list of buffers where all buffers are leaf nodes of a tree indexed but the size of the subtree. It is a slight variation of the B-Tree. This datastructure uses memory move operations within a single buffer, but does not need to move the entire vector for insertion at the front, back or in the middle. At the same time I'm using B-Trees instead of hashes because hashes tend to be most efficient for large collections while many collections are not that large. However, the implementation of in-memory B-Tree and I-Tree is not trivial compared to an array and a hash table. > 2) In a scripting language, the efficiency of array vs. list is immaterial > as compared with the overhead of the scripting language itself. I disagree. Some scripting languages are really fast exactly because they have efficient datastructures well integrated with memory management, where it can be quite tedious to achieve the same result in C++, although STL has helped a lot. In fact I believe this is the reason that Ruby has a quite good performance in praxis. > 3) Or something else? > > I think this is interesting, as in C++ I always have to decide at least to > use a vector or a list (or even a deque) when I need an ordered > collection. But in Ruby, there is no such choice (at least using the > built-in classes). I seldom uses deque mostly by habit because vector and list does the job, but in reality all I need is the deque datastructure. You only need a few good datastructures. Mikkel