Difference between an array, list, vector, and a tuple.
in [Theory]
|
Prev: Countless Hum de dumm dum dumpty, I count 2 lines.of astonishing drivel
Next: Proposed quantum algorithm for inverting one-way permutations
From: Ollie Saunders on 15 Oct 2009 13:07 I'm trying to understand what is really meant by these words in computer science. It seems like lots of programming language have different definitions of what these are (read: an array in C is not the same as an array in Ruby). The reason I ask this question is because I was designing my own programming language a while ago and I was having difficulty giving the correct names to the data structures.
From: Mark T. B. Carroll on 15 Oct 2009 13:19 Ollie Saunders <oliver.saunders(a)gmail.com> writes: > I'm trying to understand what is really meant by these words in > computer science. It seems like lots of programming language have > different definitions of what these are (read: an array in C is not > the same as an array in Ruby). > > The reason I ask this question is because I was designing my own > programming language a while ago and I was having difficulty giving > the correct names to the data structures. Associations I tend to have with these are: vector: one-dimensional array, so, fixed size, O(1) lookup, contiguous allocation list: Lisp-like cons (singly-linked list), so O(n) lookup, can grow tuple: fixed size (typically small), heterogeneous elements, element position determines its type As you're finding, there are myriad variants, but I hope the above guides a little. Advanced underlying implementations using anything from skip lists to 2-3 finger trees can improve features and performance. Mark
From: Ollie Saunders on 15 Oct 2009 14:50 On Oct 15, 6:19 pm, "Mark T. B. Carroll" <Mark.Carr...(a)Aetion.com> wrote: > Ollie Saunders <oliver.saund...(a)gmail.com> writes: > > I'm trying to understand what is really meant by these words in > > computer science. It seems like lots of programming language have > > different definitions of what these are (read: an array in C is not > > the same as an array in Ruby). > > > The reason I ask this question is because I was designing my own > > programming language a while ago and I was having difficulty giving > > the correct names to the data structures. > > Associations I tend to have with these are: > > vector: one-dimensional array, so, fixed size, O(1) lookup, contiguous > allocation > list: Lisp-like cons (singly-linked list), so O(n) lookup, can grow > tuple: fixed size (typically small), heterogeneous elements, element > position determines its type > > As you're finding, there are myriad variants, but I hope the above > guides a little. Advanced underlying implementations using anything > from skip lists to 2-3 finger trees can improve features and > performance. > > Mark If a vector is 1D, is it a vector if you can store vectors within vectors?
From: Mark T. B. Carroll on 15 Oct 2009 15:31 Ollie Saunders <oliver.saunders(a)gmail.com> writes: > On Oct 15, 6:19 pm, "Mark T. B. Carroll" <Mark.Carr...(a)Aetion.com> > wrote: )(snip) >> vector: one-dimensional array, so, fixed size, O(1) lookup, contiguous >> allocation (snip) > If a vector is 1D, is it a vector if you can store vectors within > vectors? Maybe. (-: It's not something that really comes up for me. Exact definitions will vary from language to language. I'd not prohibit it, especially, given a vector whose elements are of some parametrically polymorphic type, why not let them be vectors? In practice when I'm thinking vector-of-vectors, at pseudocode level I'm often thinking of them as multi-dimensional arrays, especially in languages which only ever really have one-dimensional arrays (i.e. vectors) and actually expect you to have pointers to arrays as elements if you want multiple dimensions. (An irrelevant aside: of course, array of pointers to arrays can be useful for efficiently storing large triangular matrices.) From a practical point of view, if some facet of your new language can be made just like that of some popular language without costing you simplicity, power, harmony, etc., then it can certainly assist with teaching and adoption to borrow accordingly. For instance, one lesson from the past couple of decades is, alas: if you want your language to be adopted popularly, give it C++-like syntax. Or, at least, syntax not needlessly dissimilar from some familiar to those you hope to attract. Mark
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen on 16 Oct 2009 07:07
Ollie Saunders <oliver.saunders(a)gmail.com> writes: > I'm trying to understand what is really meant by these words in > computer science. It seems like lots of programming language have > different definitions of what these are (read: an array in C is not > the same as an array in Ruby). > > The reason I ask this question is because I was designing my own > programming language a while ago and I was having difficulty giving > the correct names to the data structures. Array: May be multidimensional, lookup of arbitrary elements in constant time, size determined at initialisation/allocation time and can not (easily) be extended. List: One-dimensional, O(n) access to nth element, but also O(N) iteration over elements, where N is the size of the list. Size can easily be extended by adding new elements to existing lists. Two lists can share tails. Concatenation is O(n). Vector: Often a synonym for one-dimensional array. Tuple: Size specified by type, elements can be of different type, but the type of each element is determined by the type of the tuple. Essentially equivalent to a record, but with numbered fields instead of named fields. Tuples are often generic, where records are typically not. Additionally: Record: A collection of named fields, accessed by specifying field name. Also called "structs". Object: Like a record, but where some fields can be methods, i.e., functions that each have the full object as an implicit parameter (usually called "this" or "self"). Union: A value that can be from one of a (usually small) number of specified alternative types. In most cases, it is possible to test which of the types the value is from (disjoint unions) but in other cases not (like in C). Also called "sum types" or "variants". Sequence: May be a synonym for a list, but can also be a structure where subsegment (part of sequence from element m to element n) and concatenation are O(log(N)), where N is the size, but where accessing even the first element may also be O(log(N)). Multiset: Collection where the order of elements do not matter, but their multiplicity do. So [1,2,2] is the same as [2,1,2], but different from [1,2]. Set: Collection where neither order nor multipliciy matters, so {1,2} is the same as {2,2,1}. Map: Binds keys to values, where keys and values can be of any type (though some languages impose restrictions on key types) and where you can add new bindings cheaply. Maps are also called "associative arrays". Torben |