Damien Katz

Bingo. As a swiss army knife language and for web dev, I use pyhton where lists, tuples and dictionaries (maps) rule the day. Seeing code that iterates over an array looks odd to me these days.

But some people...they love their arrays. They learned 'em good and you're not gonna take 'em away.

A nice post on Lists/Tuples. It's about python but applies generally:

http://jtauber.com/blog/2006/04/15/python_tuples_are_not_just_constant_lists/

> Most uses of arrays are just as a collection of values, and can be better satisfied with a list

First, let's agree on some terminology as it's possible there's some confusion. To me, a list usually means a linked list. A resizable array (called a vector in many languages) is an array, as are pointer-allocated and fixed-size arrays (as often seen in C).

I think there are few situations where I would use a linked list instead of a resizable array. Why? Because for no particular benefit you will waste space for the link pointers and from memory allocator overhead. This brings worse cache behaviour. Also, when traversing the list you will suffer death by a thousand cache misses.

There are of course situations where a linked list is the best choice. For example, for insertions and removal at arbitrary positions (as opposed to the end), the linked list is the best choice.

Dan, python's list type is a resizable array, not a list in the LL/tree sense.

Now it's less compact than numpy's array types, but it's still an array.

the key here is "low-level" -- if i'm allowed to revise that to say performance-critical, in that context here's what arrays/vectors get you:

- much less memory allocation, deallocation, and associated overhead
- much less memory fragmentation
- much better spatial locality of reference
- better for CPU caches (especially for linear iteration)
- you can use it with glVertexPointer ;)

I get what python list are. My point is how they are used when iterating, not how they are implemented. I don't have to think in terms of an array when iterating over a list.

Another point is that even when there is a better option than an array or when there is iteration sugar for arrays, some developers still prefer to use array indexing syntax just because its familiar. I have had that exact conversation with several developers.

Its also worth noting that when you use a higher level data structure than an array, you may still be using an array. Take a heap for example. The majority of heaps are implemented as arrays underneath, allowing them to be stored quite compactly and yet traversing any link is still a constant time operation.

Fundamentally, the array is the basic model of storage in a computer. You can think of a hard drive partition as one large array, if it suits you. Whether or not you explicitly want to use an array data structure or something higher level, arrays shouldn't be discounted or trivialized.

In my .NET world, arrays are still a first-class citizen of the C# and VB.NET languages, but I have been thinking recently that they should not be...

I use arrays a lot in my method definitions, but only because its easier to read String[] than "IEnumerable(Of String)". For low-level memory mapped stuff, arrays are no-doubt useful, but higher-level OO code really doesn't need them.

You hit the nail on the head with the 'low level programming' point. It really does depend on your problem domain, and the language / framework you're attacking the problem with.

In most web development I'd agree that ordinal arrays aren't really used that often. PHP's "Array" is actually an ordered map (http://www.php.net/manual/en/language.types.array.php) and is usually iterated as you would a list.

Interesting discussion anyway :)

Arrays get used a lot in numerical work, but that's really a specialized kind of work.

As Dave points out, the PHP Array is a funny hybrid of a hashtable and a list.

Related to that, I think about the great Unicode scandal in Java: you know, the way that Java represents characters with a 2-byte representation. This doubles the memory consumption and halves the speed of Java applications that handle great quantities of us-ascii or mostly us-ascii text. On the other hand, you need more than 2-bytes to correctly represent Chinese and Mathematical characters, so the Java implementation doesn't deliver what it promises: random access to strings at the character level.

An alternate way to encode unicode strings in a language is to use a variable-length encoding such as UTF-8. This is definitely a good thing for those of us that use European languages, but it means that random access to characters requires a sequential scan.

This is much like the difference between arrays and lists.

As a PHPer, this doesn't bother me, because I mostly use sequential scans on strings anyway: anything based on a regex uses a sequential scan, and certainly tokenizers and parsers depend on sequential scan. Even many 'not-quite-sequential' algorithms such as Boyer-Moore search can be formulated as efficient algorithms on bytes rather than characters.

I think it's one of those hammer/nail situations. Different languages give you different tools, and you quickly learn which ones the language "likes" and which it doesn't. Functional languages love linked lists because they love immutable data, and linked lists are little immutable pieces that let you build arbitrary data structures, and let multiple structures share data, so copying them to make changes isn't as expensive as it would otherwise be.

In other languages, linked lists aren't used much anymore because, to be honest, they're really inefficient. If you're willing to use mutable state, then dynamic arrays are much, much faster for most purposes. Given library support, both are as easy to work with; in fact I'd say arrays are easier because the iterator state is easier to comprehend (an integer rather than a pointer). Although of course most languages have foreach or for-in constructs to avoid having to use indices.

As you can probably tell, I don't come from a hardcore functional background, although I'm learning Scala. I've used functional techniques for a very long time though, going back to Smalltalk-80 in 1984.