Because ordinal counting has been a tenant of computer science since inception.
Why do arrays start at 0?
661–670 of 702 posts
Re: Why do arrays start at 0?
#662Earlier quoted context omitted.
The analogy is slightly off though. The first position of an array occupies 1 unit of memory. 0 is not a possible measurement in the world of arrays. Maybe a null terminated string could have length 0 if you don't count the terminator. But that 0 is a property of the "string" abstraction. The actual "array" would still be length 1.
An array of length 0 starts at 0 and ends with 0
> An array of length 0 starts at 0 and ends with 0
Nope. The moment you "start" somewhere you occupy 1 unit of memory. Thus no longer an "array of length 0".
There is no such thing as an array of length 0. It absolutely does not exist. You cannot write source code to represent it.
ie assuming we are talking about the pure data structure of an array. Some languages may have some abstraction built on of arrays (ie c-strings) that can have length 0 but these are not "arrays" and if they are defined they still occupy 1 unit of memory for the terminator.
Re: Why do arrays start at 0?
#663I may think that counting 0 as a natural number makes a lot of math more elegant, but clearly I’m just too dumb to rise to the level of wrong. fruits = ['apple'] \\ Hello I have fruits x = len(fruits) \\ Only one kind tho lol fruits[x] \\ OK here is what I have SUBSCRIPT OUT OF RANGE I have always hated zero indexing for this reason (other than thinking in assembler where it is beautiful). It is of course useful in m…
> If zero indexing were so great, mathematicians would have made it the default centuries if not millennia ago
They did. For any context where the index contributes to the math[1] (i.e. is not simply a label convention like "the x (first) component") the index always start at zero. Polynomials, Fourier series, geometric series, Bessel functions (both their order and their series expansions), etc.
[1]: Except, of course, when a divergent 1/0 term shows up.
Re: Why do arrays start at 0?
#664Earlier quoted context omitted.
It's fundamentally a distinction between end-index and start-index. Most human counting uses end-index. I.e. "1" is after 1-thing (has passed, is physically obtained, etc.). Most computer counting uses start-index + length, for efficiency and to better generalize. I.e. "1" is at the memory address immediately before the "1"st item. Which ultimately creates the "0 index is 1st thing" linguistic confusion. PS: Also, la…
good take! i think a more accurate and complete idea is that humans refer to a thing in its entirety , with things being lined up and scanned in order as only a potential convenience if you ask someone to identify an object, they'll point to the middle (or center of the most important component) of the object, not to the 'start' or 'end' of it in their field of vision.. that said, the human perspective is subtle and…
They may point to the middle, but that's not a reference to half an object. ;)
The assumption is that the thing is its entirety, as you said.
Hypothetically, I imagine an array index reference, in human terms, would be communicated as "this thing starts here" or "this is the beginning of this thing."
Which isn't a concept or phrasing we have much occasion to use, other than for routes or long length-measured objects?
Re: Why do arrays start at 0?
#665Earlier quoted context omitted.
That gets really dicey if you're storing the value of the index in a variable. Does the programmer need to know that if it's an INDEX they're storing that goes from 1-256 they can fit that into an 8-bit value because the compiler will magic away that last bit? Speaking of which, how will the compiler know which 1's are really 0's and which 256's are really 255's? Will it compile that 1+1=1 if I use that result as an…
not really? It just changes how the compiler emits the x := *(addr + idx) operation where instead of doing something like ldr x, [addr, idx] it just does sub t1, idx, #1 ldr x, [addr, t1] If we're talking about C, accessing invalid/OOB indices is undefined and so if idx happens to be zero and unsigned, we'll overflow and hit something unexpected, which is fine.
That's what I was thinking too, except that they have a point. You might end up using more bytes to store indexes as variables (if the index is 256 for example), than you would with zero indexing.
Re: Why do arrays start at 0?
#666Earlier quoted context omitted.
You are demanding a lot from the type system. Search for OffsetArrays in https://yuri.is/not-julia/ for practical problems encountered in trying to make this feature work in a language whose compiler does try to be smart.
The type system does tell you if this is used. `::OffsetArray`.
Yes, but did the programmer tell the type system that they are expecting an OffsetArray, they have tested it, and it will work correctly?
The existence of a mechanism does not guarantee its correct use. As that link demonstrates.
Re: Why do arrays start at 0?
#667Earlier quoted context omitted.
If we use inclusive ranges where 0 ≤ i ≤ N, then len(range(N)) == N+1. e.g. len(range(3)) == len([0, 1, 2, 3]) == 4
Wait, why would range(3) start at 0 and not 1 in a 1-based language?
You said: "I don't understand why 0 ≤ i ≤ N wouldn't have worked instead". Was that a typo? Did you mean 0 < i ≤ N?
Re: Why do arrays start at 0?
#668Earlier quoted context omitted.
That's not possible - the subtract and multiply need to be consecutive (adjust index before multiply by element size), so even if it was a single instruction it would still take longer than a multiply that didn't have to wait for a preceding subtraction. The only way to avoid the speed penalty would be either to have a wasted element at offset 0, or to maintain the array base address as (address - (1 * element-size))…
That goes against my intuition. Multiplication in hardware to this day relies on addition. Is one adder going to add an extra cycle? Or would that time be amortized? Take a look at slides 45-46 here. https://acg.cis.upenn.edu/milom/cis371-Spring08/lectures/04_... Do you know the answer to that question? (I don't, but if someone does, it will settle this issue).
I don't know, but looking at that 3-input add makes me think you may be right and the extra addition/subtraction could perhaps be combined into the multiplication.
OTOH, for arrays who's contents are size 2^n (char, short, int, long) I'm sure the generated code isn't using multiply in the first place.
Anyways, an optimizing compiler could certainly remove much of any overhead added by 1-based indexing .. for an array access in a for loop it could, if necessary, calculate the "base-1" address once at start of loop.
Personally, having grown up with assembler and C, and still using C++ today, I'm quite happy with 0-based.
Re: Why do arrays start at 0?
#669There were a number of systems oriented languages that, while algol-like in syntax, used zero-based array indexing, predating C. BCPL was intended to be a generic systems oriented language, but Burroughs had ESPOL for their mainframe architecture, and HP wrote their operating systems and compilers in SPL, which was specific to their stack-oriented HP3000 architecture. All these used zero-based indexing, because for l…
On a cursory look, I'd say one based is more intuitive, for the sole fact that the a[len(a)] is the last element. Actually I remember there was a small time when I started programming in assembly it took me a while to get used to reasoning about the end of the array.
much of intuition is made, not innate, at least for things as abstract and arbitrary as languages and notation. If you come at this question from a point of view where an array is a block of memory words indexed by a pointer - which is pretty much how system programmers back in the day when I did such things, 50 years ago - then zero based seems natural and obvious. The pointer to the array is the array, and the first element in the array is the pointer plus zero, the second, the pointer plus one, and so on. Once you start thinking that way. For multi-dimensions, the arithmetic just falls out as well.
But I don't think the fact that many of us developed that intuition, makes it inherently better. It just makes it more intuitive for those of us who developed that inuition. I've written oodles of codes with both paradigms. Either works. Zero is just more natural, to me.
Re: Why do arrays start at 0?
#670No post body was provided.