3 ms·

You got an off by one bug in your first example ;-)

jlebar 7y ago
You mean "(well ok, 3 would be a poor choice)"?
wruza 7y ago
If we used languages with 1-based arrays, then the first element was 1, the last was n, and find(x) could return 0 as an “item not found” marker instead of returning -1 or worse uint_max. Reasoning about counting from the end could be off-by-one easier: n+1-i instead of n-i-1, n-1-i or n-(i+1), whichever nonsense you like better. Looping: i=1, i<=n. Setting next: a[n+1]=x, where the capacity allows. But when you mention one of these languages, you get a bunch of “oh, 1-based arrays, so uncool, not an option”.
- cyphar 7y ago
  The downside of 1-based indexing is that pointer arithmetic stops being consistent with array indexing. Both approaches have downsides.
  - wruza 7y ago
    And one may see that as a nice way of ditching pointer calculus completely to the machine level where it belongs.
    - jstimpfle 7y ago
      fact is, array indexing is pointer arithmetic. And how do you for example index an array of 256 elements with one byte, with 1-based indexing?
      - wruza 7y ago
        257, 300, 100k elements? You do not index it with one byte, that simple. If that is a hard requirement (8-bit chip, low ram, etc), leave it to C or a special syntax. __ptr_offset(p, n), p+n, p: array[0..n] of x, option base 0, you name it. I mean, we can ask ourselves tens of such in-the-box questions for any feature that doesn’t fit it, but out-of-box world doesn’t really crave all of that by default.
        jstimpfle 7y ago
        No, I'm trying to show is that offset-indexing is the right way to do it: because it makes sense, mathematically. If you need more and better arguments, have a look at Dijkstra's "Why numbering should start at zero" (it also argues why we should have left-inclusive and right-exclusive bounds).
        wruza 7y ago
        >...unnatural by the time the sequence has shrunk to the empty one. That is ugly, ... I reread his article for clarity. He first makes the “ugly” argument, which originates from 1) natural number domain definition issues, and 2) only then he goes to the range definition argument based on 1). It may be valid when you’re working in your mind on math problems of natural numbers starting* with 0, which is a self-referential argument btw. But it doesn’t have to be applied to software arrays of items. Dijkstra’s argument is repeated as a mantra, but the general consensus is that representation of natural numbers (unsigned ints) brings more issues than ought to solve, so we don’t use them today, which defeats 1), and then 2) loses its causality. >>find(x) could return 0 as an “item not found” marker instead of returning -1 or worse uint_max Let’s test that against Dijkstra’s statement on range unnaturalness? Which is more unnatural, 0, -1, NSNotFound? Programmatically it doesn’t make any sense except in salary gains from mastering off-by-ones. * Edit: natural numbers start differently in different countries, but you may s/0/1/ there and it still holds, because he speaks about domain borderlines. The same holds true for e.g. [321..500].
        jstimpfle 7y ago
        It's not about number definition issues. The argument is convincing that the difference of upper and lower range bounds should equal the number of contained elements, and that it's ugly to represent empty ranges with an upper bound that is lower than the lower bound. (I agree and I held that opinion before even reading this article). Note that I rewrote his argument a little here, because it is not really about natural vs unnatural, but more about looking at the difference between upper and lower bound. Now, if I may presume that we can agree that the difference of the bounds should equal the number of elements, leading to left-inclusive and right-exclusive bounds, the question is would you rather have a lower bound of 0 (which is an entirely "natural" number that is already in the game for subsequences of length 0), or would you introduce an entirely new number for the upper bound, (size + 1), which also needs an addition operation to compute? I don't care about definitions of natural numbers. As demonstrated, numbering elements as offsets makes a lot of sense for purposes of indexing, and if you insist on starting with 1, then you need to either lower your base pointer by 1, or subtract 1 at every indexing operation (both is not exactly simple), and you frequently need to add 1 to the size. I have no issues with zero-based indexing, and I don't think I've ever had to write quirky code. The most "ugly" thing is that the last element must be indexed as (size - 1) (which also makes some sense, since the last element need not necessarily exist. The subtraction makes clear that this is dangerous). > Which is more unnatural, 0, -1, NSNotFound? I normally handle that as -1 which is absolutely ok, especially given that this value is special. I concede that you might prefer 0 since that aligns well with evaluating truthiness of integers. It also makes a lot of sense (mathematically/programmatically) to use "size" (i.e. one-past-last index) as not-found, but that breaks when arrays are resized.
- jstimpfle 7y ago
  I think we should compromise on 0.5.

You mean "(well ok, 3 would be a poor choice)"?

If we used languages with 1-based arrays, then the first element was 1, the last was n, and find(x) could return 0 as an “item not found” marker instead of returning -1 or worse uint_max. Reasoning about counting from the end could be off-by-one easier: n+1-i instead of n-i-1, n-1-i or n-(i+1), whichever nonsense you like better. Looping: i=1, i<=n. Setting next: a[n+1]=x, where the capacity allows. But when you mention one of these languages, you get a bunch of “oh, 1-based arrays, so uncool, not an option”.

cyphar 7y ago
The downside of 1-based indexing is that pointer arithmetic stops being consistent with array indexing. Both approaches have downsides.
- wruza 7y ago
  And one may see that as a nice way of ditching pointer calculus completely to the machine level where it belongs.
  - jstimpfle 7y ago
    fact is, array indexing is pointer arithmetic. And how do you for example index an array of 256 elements with one byte, with 1-based indexing?
    - wruza 7y ago
      257, 300, 100k elements? You do not index it with one byte, that simple. If that is a hard requirement (8-bit chip, low ram, etc), leave it to C or a special syntax. __ptr_offset(p, n), p+n, p: array[0..n] of x, option base 0, you name it. I mean, we can ask ourselves tens of such in-the-box questions for any feature that doesn’t fit it, but out-of-box world doesn’t really crave all of that by default.
      - jstimpfle 7y ago
        No, I'm trying to show is that offset-indexing is the right way to do it: because it makes sense, mathematically. If you need more and better arguments, have a look at Dijkstra's "Why numbering should start at zero" (it also argues why we should have left-inclusive and right-exclusive bounds).
        wruza 7y ago
        >...unnatural by the time the sequence has shrunk to the empty one. That is ugly, ... I reread his article for clarity. He first makes the “ugly” argument, which originates from 1) natural number domain definition issues, and 2) only then he goes to the range definition argument based on 1). It may be valid when you’re working in your mind on math problems of natural numbers starting* with 0, which is a self-referential argument btw. But it doesn’t have to be applied to software arrays of items. Dijkstra’s argument is repeated as a mantra, but the general consensus is that representation of natural numbers (unsigned ints) brings more issues than ought to solve, so we don’t use them today, which defeats 1), and then 2) loses its causality. >>find(x) could return 0 as an “item not found” marker instead of returning -1 or worse uint_max Let’s test that against Dijkstra’s statement on range unnaturalness? Which is more unnatural, 0, -1, NSNotFound? Programmatically it doesn’t make any sense except in salary gains from mastering off-by-ones. * Edit: natural numbers start differently in different countries, but you may s/0/1/ there and it still holds, because he speaks about domain borderlines. The same holds true for e.g. [321..500].
        jstimpfle 7y ago
        It's not about number definition issues. The argument is convincing that the difference of upper and lower range bounds should equal the number of contained elements, and that it's ugly to represent empty ranges with an upper bound that is lower than the lower bound. (I agree and I held that opinion before even reading this article). Note that I rewrote his argument a little here, because it is not really about natural vs unnatural, but more about looking at the difference between upper and lower bound. Now, if I may presume that we can agree that the difference of the bounds should equal the number of elements, leading to left-inclusive and right-exclusive bounds, the question is would you rather have a lower bound of 0 (which is an entirely "natural" number that is already in the game for subsequences of length 0), or would you introduce an entirely new number for the upper bound, (size + 1), which also needs an addition operation to compute? I don't care about definitions of natural numbers. As demonstrated, numbering elements as offsets makes a lot of sense for purposes of indexing, and if you insist on starting with 1, then you need to either lower your base pointer by 1, or subtract 1 at every indexing operation (both is not exactly simple), and you frequently need to add 1 to the size. I have no issues with zero-based indexing, and I don't think I've ever had to write quirky code. The most "ugly" thing is that the last element must be indexed as (size - 1) (which also makes some sense, since the last element need not necessarily exist. The subtraction makes clear that this is dangerous). > Which is more unnatural, 0, -1, NSNotFound? I normally handle that as -1 which is absolutely ok, especially given that this value is special. I concede that you might prefer 0 since that aligns well with evaluating truthiness of integers. It also makes a lot of sense (mathematically/programmatically) to use "size" (i.e. one-past-last index) as not-found, but that breaks when arrays are resized.
jstimpfle 7y ago
I think we should compromise on 0.5.