Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Always use [closed, open) intervals

fhur.me

Post reply on HN
Print view View original

141–150 of 169 posts

Re: Always use [closed, open) intervals

#141

Post by ufo »

dragontamer wrote: post #92
ufo wrote: post #87

Earlier quoted context omitted.

Dijkstra is a smooth talker and sometimes he's able to convince people that an argument is settled even when it is not... Here, he conveniently ignores examples that are better for [closed,closed], such as iterating backwards over the range. That is more annoying for [closed,open) because it turns into the abhorent (open,closed]. An argument I prefer is this: [closed,closed] is better for representing an index into t…

> That is more annoying for [closed,open) because it turns into the abhorent (open,closed]. What's wrong with (open, closed] ?? Especially if you're going backwards? for(int i=559; i>554; i--){ //do stuff with i } Perhaps the most important reason to do zero-indexed + [closed,open> and Its all non-intuitive because humans are really bad with off-by-one errors. ------ EDIT: I guess familiarity with [closed, closed] is…

The problem with that example is that you had to ±1 both of the ends of the original range. That is, you started with [555,560) and had to rewrite it to (554,559] for the reverse loop.

Re: Always use [closed, open) intervals

#142

Post by jissa »

cristoperb wrote: post #121
parekhnish wrote: post #120

Earlier quoted context omitted.

Even [closed, closed] intervals have that property: [a, b] + [b, c] == [a, c]

b would be included twice in that case, wouldn't it?

Right, I think the hotel room use case helps a lot with the intuitions here. And it helps to see the COUNTER EXAMPLE:

* Hotel A [Jan 10, Jan 13] means 4 nights; same as [Jan 10, Jan 14).

* Hotel B [Jan 13, Jan 15] means 3 nights; same as [Jan 13, Jan 16).

These intervals overlap! That is, if I try to get them together I book Jan 13 on both Hotel A and Hotel B.

With the half-open interval is really easy to spot: you cannot concatenate unless the open-end and the closed-begin are the same.

So you can concat [Jan 10, Jan 14) with [Jan 14, Jan 16); BUT you have an overlap if you see this [Jan 10, Jan 14) with [Jan 13, Jan 16) as in the previous examples.

With the closed interval this is hard to see. As in the example by @parekhnish; it seems that [Jan 10, Jan 13] and [Jan 13, Jan 15] are concatenable and there's no overlap. But the final operation ends up booking on Jan 13 twice.

Re: Always use [closed, open) intervals

#144

Post by jissa »

jissa wrote: post #142
cristoperb wrote: post #121

Earlier quoted context omitted.

b would be included twice in that case, wouldn't it?

Right, I think the hotel room use case helps a lot with the intuitions here. And it helps to see the COUNTER EXAMPLE: * Hotel A [Jan 10, Jan 13] means 4 nights; same as [Jan 10, Jan 14). * Hotel B [Jan 13, Jan 15] means 3 nights; same as [Jan 13, Jan 16). These intervals overlap! That is, if I try to get them together I book Jan 13 on both Hotel A and Hotel B. With the half-open interval is really easy to spot: you c…

Not to mention the sweetness of saying:

* Jan 14 - Jan 10 = 4 nights

* Jan 16 - Jan 13 = 3 nights

I actually had to edit my previous comment, because I said [Jan 10, Jan 13] was 3 nights INSTEAD of 4 nights.

I caught the error when I saw the [Jan 10, Jan 14) interval :-)

Re: Always use [closed, open) intervals

#145

Post by jwilk »

chkas wrote: post #45

Python uses "closed open" intervals with `range(0, n)`, the reverse is then `range(n - 1, -1, -1)`, which is then highly unintuitive. This in connection with 0-based array indexing makes certain algorithms then very cumbersome. For example Knuth-Shuffle . In Python this is: from random import randrange x = [10, 20, 30, 40, 50 ] for i in range(len(x) - 1, 0, -1): r = randrange(i + 1) x[i], x[r] = x[r], x[i] print(x) W…

I know Knuth wrote it that way, but there's no good reason why the iteration should be downwards. That is, you could write:

  for i in range(1, len(x))
and you would still get an unbiased shuffle algorithm.

The upwards iteration has a few advantages:

• You can start shuffling before you know how big the input is.

• Algorithm R for reservior sampling can be seen a specialized version of shuffling, in which you skip the work that wouldn't affect the first k items, or would only affect their order.

Re: Always use [closed, open) intervals

#146

Post by programmer_dude »

mhink wrote: post #133
programmer_dude wrote: post #131

Earlier quoted context omitted.

They are not even though they start counting from 1. The child is still zero years old.

It's a matter of (natural language) terminology. It's the difference between asking "which year of your life are you currently in" as opposed to "how many full years have elapsed since you were born?"

Agreed. My previous reply just pointed out that 1 is not "how many full years have elapsed since you were born?". The answer to this question is still 0.

Re: Always use [closed, open) intervals

#148

Post by chkas »

jwilk wrote: post #145
chkas wrote: post #45

Python uses "closed open" intervals with `range(0, n)`, the reverse is then `range(n - 1, -1, -1)`, which is then highly unintuitive. This in connection with 0-based array indexing makes certain algorithms then very cumbersome. For example Knuth-Shuffle . In Python this is: from random import randrange x = [10, 20, 30, 40, 50 ] for i in range(len(x) - 1, 0, -1): r = randrange(i + 1) x[i], x[r] = x[r], x[i] print(x) W…

I know Knuth wrote it that way, but there's no good reason why the iteration should be downwards. That is, you could write: for i in range(1, len(x)) and you would still get an unbiased shuffle algorithm. The upwards iteration has a few advantages: • You can start shuffling before you know how big the input is. • Algorithm R for reservior sampling can be seen a specialized version of shuffling, in which you skip the…

If you want to do it the other way around, you have to start at 0:

    for i in range(len(x) - 1):
        r = randrange(i, len(x))
        x[i], x[r] = x[r], x[i]

Re: Always use [closed, open) intervals

#149

Post by jwilk »

chkas wrote: post #148
jwilk wrote: post #145

Earlier quoted context omitted.

I know Knuth wrote it that way, but there's no good reason why the iteration should be downwards. That is, you could write: for i in range(1, len(x)) and you would still get an unbiased shuffle algorithm. The upwards iteration has a few advantages: • You can start shuffling before you know how big the input is. • Algorithm R for reservior sampling can be seen a specialized version of shuffling, in which you skip the…

If you want to do it the other way around, you have to start at 0: for i in range(len(x) - 1): r = randrange(i, len(x)) x[i], x[r] = x[r], x[i]

That probably works too, but it's even more awkard than the Knuth's one, and doesn't have the nice properties I mentioned.

I meant just:

    for i in range(1, len(x)):
        r = randrange(i + 1)
        x[i], x[r] = x[r], x[i]

Re: Always use [closed, open) intervals

#150

Post by chkas »

jwilk wrote: post #149
chkas wrote: post #148

Earlier quoted context omitted.

If you want to do it the other way around, you have to start at 0: for i in range(len(x) - 1): r = randrange(i, len(x)) x[i], x[r] = x[r], x[i]

That probably works too, but it's even more awkard than the Knuth's one, and doesn't have the nice properties I mentioned. I meant just: for i in range(1, len(x)): r = randrange(i + 1) x[i], x[r] = x[r], x[i]

Cool. Seems to work, but I don't think it's still Knuth Shuffle.
Post reply on HN