В Java для строки x какова стоимость выполнения s.length ()? Это O (1) или O (n)?

Question

Мне сказали, что такой код:

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() действительно обходит всю строку, только чтобы определить ее длину?

Answer 1

Нет, длина строки java равна O (1), поскольку класс строки java хранит длину в виде поля.

Совет, который вы получили, верен для C, среди других языков, но не для java. C's strlen обходит массив char в поисках символа конца строки. Джоэл говорил об этом на подкасте, но в контексте C.

Answer 2

Вопреки сказанному, нет гарантии, что String.length() - это операция с постоянным временем в количестве символов, содержащихся в строке. Ни в javadoc для класса String, ни в спецификации языка Java не требуется, чтобы String.length была операцией с постоянным временем.

Однако в реализации Sun String.length() - это операция с постоянным временем. В конечном счете, трудно представить, почему любая реализация имеет реализацию с непостоянным временем для этого метода.

Answer 3

String хранит длину в отдельной переменной. Поскольку строка неизменна, длина никогда не изменится. Ему нужно будет рассчитать длину только один раз при ее создании, что происходит, когда для нее выделяется память Следовательно, его O (1)

Answer 4

Если вы не знали, что можете написать это так:

for (int i = 0, l = x.length(); i < l; i++) {
    // Blah
}

Это немного чище, так как область действия l меньше.

Answer 5

Вы должны знать, что метод length() возвращает количество кодовых точек UTF-16, которое не обязательно совпадает с количеством символов во всех случаях.

Хорошо, шансы на то, что это действительно повлияет на вас, довольно невелики, но знать об этом нет никакого вреда.

Answer 6

Я не знаю, насколько хорошо будет переводиться ссылка, но вижу источник String#length. Короче говоря, #length() имеет сложность O (1), потому что он просто возвращает поле. Это одно из многих преимуществ неизменяемых струн.

Answer 7

Согласно this длина представляет собой поле объекта String.