Представление интервалов или диапазонов?

В общем, всякий раз, когда вы представляете диапазон любого типа, у вас есть несколько вариантов выбора значений для начала и конца диапазона. Например, если вы хотите иметь диапазон, содержащий целые числа 1, 2, 3, 4, 5, вы можете выбрать следующие возможные значения:

  • begin = 0, end = 5 (aka begin < x <= end)
  • begin = 1, end = 5 (aka begin <= x <= end)
  • begin = 0, end = 6 (aka begin < x < end)
  • begin = 1, end = 6 (aka begin <= x < end (похоже, это выбирает С++ STL и многие другие библиотеки)).

Я не уверен, какие меры я должен использовать, чтобы выбрать один из этих вариантов.

Ответы

Ответ 1

Я надеялся, что кто-то даст мне ссылку на хорошую бумагу, которая E.W. Dijkstra написал на эту тему. Мне удалось подключить только правильные условия поиска в Google и найти ссылку, которую я искал. В документе "Почему нумерация должна начинаться с 0" , а также охватывает, почему диапазоны должны быть представлены с половинным интервалом открытия [начало, конец].

Основной аргумент имеет несколько частей:

  • Прямой опыт в среде программирования (язык программирования Mesa в Xerox PARC), который поддерживал все 4 разных варианта, привел к тому, что люди стандартизировали [начало, конец] из-за частых ошибок, сделанных со всеми другими вариантами.
  • Если у вас есть интервал, начинающийся с 0, с началом -1, или что-то подобное просто неудобно и сломано. Это сильно указывает на интервал, начинающийся с begin (т.е. Все варианты begin <= x).
  • Математика для определения размера интервала, для вычисления начала следующего соседнего интервала и целая куча других подобных вещей просто хорошо работает, если конец - это один из старт. Например, размер end - begin. А end - это begin следующего смежного интервала. В ваших расчетах есть меньше шансов для ошибок "один за другим".
    • В соответствующей заметке пустой диапазон [begin, begin) и очень очевиден. Это должно было быть довольно неудобным [begin, begin - 1], если бы оно было закрыто с обеих сторон. Это особенно неудобно, когда ваш диапазон начинается с 0.

Ответ 2

Я лично выбрал бы вариант

  • begin = 1, end = 5 (aka begin <= x <= end)

Мне нравится держать мои структуры ясными и похожими на человеческие рассуждения, насколько это возможно. Если вы сообщите кому-то "цифры от 1 до 5", то и 1, и 5 должны быть в наборе.

Конечно, если есть хорошие технические причины использовать что-то еще, то почему бы и нет, но если их нет, я бы выбрал вариант, который легче понять с первого взгляда.

Ответ 3

Я бы сказал, что это зависит от (неявного или явного) типа интервала, который вы пытаетесь выразить. Для поплавков и рациональностей я думаю, что предпочитаю полуоткрытые интервалы (так, по существу, min <= value < max или min < value <= max). Для интегральных значений преобразование между открытыми, закрытыми и полуоткрытыми интервалами тривиально, поэтому я, вероятно, тоже буду иметь полуоткрытые интервалы.

Ответ 4

Интересный вопрос. Я бы хотел предложить, поскольку цикл foreach теперь довольно вездесущий, и выбор становится менее актуальным. Вы можете просто прокрутить коллекцию, не зная, какое соглашение диапазона использует базовая реализация.