Мне сказали, что код, например:
for (int i = 0; i < x.length(); i++) {
// blah
}
на самом деле O (n ^ 2) из-за повторных вызовов x.length(). Вместо этого я должен использовать:
int l = x.length();
for (int i = 0; i < l; i++) {
// blah
}
Это правда? Длина строки сохраняется как частный целочисленный атрибут класса String? Или String.length() действительно перемещает всю строку только для определения ее длины?
Нет, длина строки java - это O (1), потому что класс строки java сохраняет длину как поле.
Совет, который вы получили, относится к C, среди других языков, но не к Java. C strlen проходит массив char, ища символ конца строки. Джоэл говорил об этом в подкасте, но в контексте C.
В отличие от того, что было сказано до сих пор, нет гарантии, что String.length() - операция с постоянным временем в количестве символов, содержащихся в строке. Ни javadocs для класса String, ни спецификация языка Java не требуют String.length для операции с постоянным временем.
Тем не менее, при реализации Sun String.length() это операция с постоянным временем. В конечном счете, трудно представить, почему для любой реализации была реализована непостоянная временная реализация для этого метода.
Вы должны знать, что метод length() возвращает количество кодовых точек UTF-16, что не обязательно совпадает с количеством символов во всех случаях.
Хорошо, шансы на то, что на самом деле влияют на вас, довольно тонкие, но нет никакого зла, зная это.
Если вы не знали, что можете написать это так:
for (int i = 0, l = x.length(); i < l; i++) {
// Blah
}
Он немного чист, поскольку область l меньше.
String сохраняет длину в отдельной переменной. Поскольку строка неизменна, длина никогда не изменится. Он должен будет вычислить длину только один раз, когда он будет создан, что происходит, когда для него выделяется память. Следовательно, его O (1)
Я не знаю, насколько хорошо будет переводиться ссылка, но посмотрите источник String#length. Короче говоря, #length() имеет сложность O (1), потому что она просто возвращает поле. Это одно из многих преимуществ непреложных строк.
В соответствии с this длина - это поле объекта String.