Всегда ли предполагается, что верхние границы индексированных диапазонов являются исключительными?

Таким образом, в Java, когда указан индексированный диапазон, верхняя граница почти всегда исключительна.

От 1_:

_2 _

Возвращает новую строку, которая является подстрокой этой строки. Подстрока начинается с указанного beginIndex и продолжается до символа с индексом endIndex - 1

От java.util.Arrays:

_ 6_

from - начальный индекс копируемого диапазона, включительно
to - конечный индекс копируемого диапазона, исключая.

От java.util.BitSet:

_10 _

fromIndex - индекс первого устанавливаемого бита.
toIndex - индекс после последнего устанавливаемого бита.

Как видите, похоже, что Java пытается сделать это согласованным соглашением о том, что верхние границы являются исключительными.

Мои вопросы:

  • Это официальная авторитетная рекомендация?
  • Есть ли заметные нарушения, которых нам следует опасаться?
  • Есть ли у этой системы название? (аля "на основе 0" против "на основе 1")

УТОЧНЕНИЕ: Я полностью понимаю, что набор N объектов в системе с нулевым индексом индексируется 0..N-1. Мой вопрос в том, что если задан диапазон (2,4), это может быть либо 3 элемента, либо 2, в зависимости от системы. Как вы называете эти системы?

СНОВА, проблема не в системе "первый индекс 0 последний индекс N-1" и "первый индекс 1 последний индекс N"; это известно как система на основе 0 и 1.

Проблема заключается в том, что в системах (2,4) есть 3 элемента, а в системах (2,4) - 2 элемента. Как вы это называете, и является ли одно из них официально санкционированным?


java collections range indexing
person polygenelubricants    schedule 13.03.2010    source источник
comment
Это называется полуоткрытым диапазоном.   -  person fredoverflow    schedule 14.03.2010
comment
Ах да, я слышал этот термин раньше. Значит, вы бы сказали, что коллекции Java основаны на 0 с полуоткрытыми диапазонами?   -  person polygenelubricants    schedule 14.03.2010

Ответы (6)


arrow_upward
5
arrow_downward

В общем да. Если вы работаете на языке с синтаксисом, подобным C (C, C ++, Java), то массивы имеют нулевой индекс, а большинство структур данных с произвольным доступом (векторы, списки массивов и т. Д.) Будут иметь нулевой индекс. также.

Начало индексов с нуля означает, что размер структуры данных всегда будет на единицу больше, чем последний действительный индекс в структуре данных. Люди, конечно, часто хотят знать размер вещей, поэтому удобнее говорить о размере, чем о последнем действительном индексе. Люди привыкли говорить о закрытии индексов в исключительной манере, потому что массив a[], состоящий из n элементов, уже давно имеет последний действительный элемент в a[n-1].

Есть еще одно преимущество использования исключительного индекса для конечного индекса, которое состоит в том, что вы можете вычислить размер подсписка, вычитая включающий начальный индекс из исключительного конечного индекса. Если я вызываю myList.sublist(3, 7), я получаю подсписок с 7 - 3 = 4 элементами в нем. Если бы метод sublist() использовал инклюзивные индексы для обоих концов списка, мне нужно было бы добавить дополнительную 1 для вычисления размера подсписка.

Это особенно удобно, когда начальным индексом является переменная: получение подсписка myList, начинающегося с i, длина которого составляет 5 элементов, - это всего лишь myList.sublist(i, i + 5).

При всем вышесказанном вам следует всегда читать документацию по API, а не предполагать, что данный начальный или конечный индекс будет включающим или исключающим. Точно так же вы должны задокументировать свой собственный код, чтобы указать, являются ли какие-либо границы включающими или исключающими.

person Joe Carnahan    schedule 13.03.2010
comment
+1, так как вы всегда должны читать документацию по API, и вы должны задокументировать свой собственный код, чтобы указать - person matt b; 14.03.2010
comment
Просто чтобы прояснить отношение к OP, я считаю, что популярность полуоткрытых диапазонов в Java напрямую связана с использованием полуоткрытых диапазонов в C, что, в свою очередь, стало естественным продолжением индексации с нулевым отсчетом. Итак, я думаю, что обсуждение индексации с нуля имеет отношение к исходному вопросу. (При этом я виноват, что не указал в своем исходном ответе явной связи между индексированием с нуля и полуоткрытыми диапазонами.) - person Joe Carnahan; 14.03.2010

arrow_upward
3
arrow_downward

Благодарим FredOverflow в его комментарии, в котором говорится, что это называется «полуоткрытым диапазоном». Таким образом, можно предположить, что Коллекции Java можно описать как «основанные на 0 с полуоткрытыми диапазонами».

Я собрал некоторые обсуждения полуоткрытых и закрытых диапазонов в другом месте:

Siliconebrain.com - 16 веских причин использовать полуоткрытые диапазоны (отредактировано для краткости):

  • Количество элементов в диапазоне [n, m) равно m-n (а не m-n+1).
  • Пустым диапазоном является [n, n) (а не [n, n-1], что может быть проблемой, если n итератор, уже указывающий на первый элемент списка, или если n == 0).
  • Для числа с плавающей запятой вы можете написать [13, 42) (вместо [13, 41.999999999999]).
  • +1 и -1 почти никогда не используются при работе с диапазонами. Это преимущество, если они дорогие (например, финики).
  • Если вы пишете поиск в диапазоне, то факт, что ничего не найдено, можно легко указать, вернув конец как найденную позицию: if( find( [begin, end) ) == end) ничего не найдено.
  • В языках, в которых индексы массива начинаются с 0 (например, C, C ++, JAVA, NCL), верхняя граница равна размеру.

Полуоткрытые и закрытые диапазоны

Преимущества полуоткрытых диапазонов:

  • Допустимы пустые диапазоны: [0 .. 0]
  • Поддиапазоны легко перейти в конец оригинала: [x .. $]
  • Легко разделить диапазоны: [0 .. x] и [x .. $]

Преимущества закрытых полигонов:

  • Симметрия.
  • Возможно, легче читать.
  • ['a' ... 'z'] не требует неудобного + 1 после 'z'.
  • [0 ... uint.max] возможно.

Последний пункт очень интересен. Действительно неудобно писать предикат numberIsInRange(int n, int min, int max) с полуоткрытым диапазоном, если Integer.MAX_VALUE может быть легально в диапазоне.

person polygenelubricants    schedule 14.03.2010

arrow_upward
2
arrow_downward

Его просто от 0 до n-1 на основе.

Список / массив содержит 10 элементов 0–9 проиндексированных.

У вас не может быть индексированного списка на основе 0, который равен 0-n, где cout равен n, который включает элемент, который не существует ...

Это типичный способ работы.

  1. Да.
  2. Диапазоны Excel / Таблицы / Рабочие книги.
  3. Индекс (информационные технологии)
person Adriaan Stander    schedule 13.03.2010
comment
Я понимаю, что набор из N объектов в системе с нулевым индексом имеет индекс 0..N-1. Мой вопрос в том, что если задан диапазон (2,4), это 3 элемента или 2? - person polygenelubricants; 14.03.2010
comment
Это будет зависеть от контекста списка объектов, на который вы ссылаетесь. Как упоминалось ранее, документация должна помочь вам в этом. Скорее всего, он основан на 0, но, как я уже упоминал, есть отклонения ... - person Adriaan Stander; 14.03.2010

arrow_upward
0
arrow_downward

Эта практика была введена Джошем Блохом в API коллекций в качестве контракта.

После этого он стал стандартом в java, и когда кто-то решает создать публичную библиотеку, он предполагает, что должен сохранить контракт, потому что пользователи ожидают увидеть уже известное поведение в новых библиотеках.

person Roman    schedule 13.03.2010
comment
Так это же система Блоха? Конечно, это должно было иметь историческое использование до Java / Java Collections Framework? - person polygenelubricants; 14.03.2010
comment
Я не знаю его названия и не уверен, что он существует. Я смотрел видео на YouTube, где Джош Блох рассказывал о хороших принципах проектирования API. И там он сказал, что принцип включающей нижней границы и исключительной верхней границы на самом деле является стандартом и никогда не должен нарушаться при разработке публичных библиотек. Он также упомянул о том, что он был первым (или одним из первых, я не помню), кто ввел его в java. - person Roman; 14.03.2010
comment
Я не понимаю, почему люди проголосовали против вас, потому что, в отличие от некоторых других здесь, вы действительно получаете то, о чем я прошу. - person polygenelubricants; 14.03.2010
comment
Я не сторонник отрицательных оценок ;-), но мне любопытно, где задокументирован этот контракт. Это шаблон, которому последовательно следуют в API коллекций, и, конечно, все это заметили, но я никогда не видел, чтобы он именовался или централизованно документировался. Тем не менее, шаблон передачи размера массива или строки (который совпадает с эксклюзивным конечным индексом, если начальный индекс равен нулю) возник задолго до Java, верно? - person Joe Carnahan; 14.03.2010
comment
@ Джо Карнахан: Я не уверен, что это где-то задокументировано (но если я этого не знаю, а вы этого не знаете, то это не значит, что это не задокументировано), но каждый Java-разработчик среднего или более высокого уровня знает, что это принцип не должен нарушаться, если вы хотите, чтобы другие люди использовали ваш продукт. Apache Commons и Google Collections, а также множество других библиотек (например, Google Data API) соблюдают этот контракт. - person Roman; 14.03.2010
comment
Интересная теория, но массив в информатике и Vector, String и т. Д. В Java API уже были основаны на 0 задолго до эры Блоха. - person BalusC; 14.03.2010
comment
@BalusC: Я не думаю, что @polygenelubricants согласна с тем, что существует связь между индексированием с нуля и обычаем использовать исключительные конечные индексы при описании диапазонов. Я думал, что соединение было ясным (размер массива с нулевым отсчетом = исключительный конечный индекс для этого массива), но, очевидно, эта связь не так ясна, как мы с вами думали. - person Joe Carnahan; 14.03.2010

arrow_upward
0
arrow_downward

Индексы в массивах, подобных структурам данных, действительно всегда отсчитываются от нуля. String в основном поддерживается char[]. Фреймворк коллекций находится под капотом на основе массивов и так далее. Это упрощает разработку / поддержку / использование API без изменения «скрытого» способа доступа к желаемым элементам в массиве.

Однако есть некоторые "исключения", такие как методы установки на основе параметра indexindex для _ 3_ и методы получения на основе columnindex _ 4_. Они основаны на 1. За кулисами они также не представляют собой массив значений.

Это, вероятно, вызовет новый вопрос: «Почему индексы массива основаны на нуле?». Наш уважаемый ученый-программист Э.В. Дийкстра объясняет здесь, почему это следует начать с нуля.

person BalusC    schedule 13.03.2010

arrow_upward
0
arrow_downward

Самый простой способ представить себе полуоткрытые диапазоны: первый термин определяет начало элементов в диапазоне, а второй термин определяет начало элементов после диапазона. Имейте это в виду, и все это будет иметь гораздо больший смысл. Кроме того, согласно ответу @polygenelubricants, арифметика во многих случаях работает лучше.

person Carl Manaster    schedule 14.03.2010