Java에서 문자열 x에 대해 s.length()의 런타임 비용은 얼마입니까? 그것은 O (1) 또는 O (n)입니까?
for (int i = 0; i < x.length(); i++) {
// blah
}
은 x.length()를 반복적으로 호출하므로 실제로 O (n^2)입니다. 대신 다음을 사용해야합니다.
int l = x.length();
for (int i = 0; i < l; i++) {
// blah
}
사실입니까? 문자열 길이가 String 클래스의 개인 정수 속성으로 저장 되었습니까? 아니면 String.length() 정말 길이를 결정하기 위해 전체 문자열을 걷고 있습니까?
아니요, java의 문자열 클래스는 길이를 필드로 저장하기 때문에 Java 문자열의 길이는 O (1)입니다.
받은 조언은 다른 언어로는 C에 해당하지만 java에는 해당되지 않습니다. C의 strlen은 문자열 배열을 탐색하여 문자열의 끝을 찾습니다. Joel 's는 Podcast에서 Podcast에 대해 이야기했지만 C의 컨텍스트에서 설명했습니다.
코드는 각 반복마다 메소드 호출을 실행합니다 (컴파일러는 값이 변경되지 않는다는 것을 모릅니다). 루프 컨트롤 외부로 호출을 이동하면 메소드 호출이 제거됩니다. 이 루프의 실행 시간이 많이 변경 될 가능성은 희박합니다. –
현대 JIT는 length()가 최종 원시 값을 반환하는 간단한 클래스의 간단한 getter임을 인식하고 int 값 자체로 메소드 호출. –
sk - 길이()의 JIT 최적화를 테스트하고 그것이 사실임을 입증 한 블로그를 보는 것을 기억합니다. –
길이는 String 객체의 필드입니다.
링크가 얼마나 잘 번역되는지 모르지만, source of String#length을 참조하십시오. 즉, #length()은 필드를 반환하기 때문에 O (1) 복잡성을 갖습니다. 이것은 변경 불가능한 문자열의 많은 장점 중 하나입니다.
불변성은 아무 관련이 없습니다. 변경할 수없는 문자열 (예 : StringBuilder)과 동일한 길이의 트랙을 유지하는 가변 문자열 클래스를 가질 수 있습니다. 그리고 당신은 변경할 수없는 문자열을 가질 수 있습니다 (C에서 const char *). – Herms
그러나 immutability는 객체가 생성 될 때 한 번만 길이 값을 계산하면된다는 것을 보장합니다. 오브젝트가 변경 가능한 경우, mutator 메소드를 호출 할 때마다 새로운 계산이 필요합니다. 속담에 따라 나에게 지금 지불하거나 나중에 지불하십시오. – laz
엄밀히 말하면, 둘 다 맞습니다. 그러나 병행 성은 전체 사건에 렌치를 던졌습니다. 데이터 구조가 비동기 적으로 변경됨에 따라 보조 필드를 업데이트하려고 시도하는 것은 본질적으로 불가능하므로 변경 가능한 String 구현에서 액세스하는 대신 length()가 계산되는 경우가 많습니다. –
지금까지 말한 것과는 반대로 String.length()은 문자열에 포함 된 문자 수에서 일정한 시간 동안 작동한다는 보장이 없습니다. String 클래스 또는 Java 언어 사양의 javadoc에서는 일정 시간 작동이 String.length이 아니어야합니다.
그러나 Sun의 구현에서는 String.length()이 일정 시간 작동합니다. 궁극적으로 어떤 구현이이 메소드에 대해 일정하지 않은 시간 구현을 갖는지 상상하기 어렵습니다.
견딜 수 없으므로, String.length *는 항상 일정한 시간이 될 것이라고 생각하는 것이 안전하다고 생각합니다. –
length() 메서드는 UTF-16 코드 포인트 수를 반환하므로 모든 경우의 문자 수와 반드시 같지는 않습니다.
좋아요, 실제로 당신에게 영향을 미칠 가능성은 꽤 희박하지만 그것을 아는 데 아무런 해가 없습니다.
http://java.sun.com/javase/6/docs/api/java/lang/Character.html#unicode 기본적으로 일부 문자는 두 개의 char 값으로 표현되어야합니다. length()는 char [] 배열의 크기이므로 문자 수와 같지 않을 수 있습니다. 그러나 새디가 말했듯이 그것은 매우 드물다. –
String은 길이를 별도의 변수에 저장합니다. 문자열은 변경되지 않으므로 길이는 변경되지 않습니다. 길이를 계산할 때 한 번만 계산해야하는데, 메모리를 할당 할 때 발생합니다. 따라서는 O (1) 여러분이이 방법을 쓸 수 몰랐다 이벤트에서
:
for (int i = 0, l = x.length(); i < l; i++) {
// Blah
}
그냥 약간 l의 범위는 작은 청소기부터입니다.
문자열의 길이를 계산하는 것이 O (n) 인 경우에도 전체적인 복잡성은 여전히 O (n^2)가되지 않습니다. 길이는 한 번 계산되고 for 루프에서 경계 값으로 사용되며 각 반복에서 계산되지 않습니다. –
내가 아는 한 경계 값은 캐시되지 않습니다. 루프에서 경계가 수정되면 어떻게 될까요? –
경계는 매번 계산됩니다. for 루프의 검사는 임의의 표현식이라는 것을 기억하십시오. 컴파일러는 실제로 거기에있는 것을 신경 쓰지 않으며 가정을 할 수 없습니다. 매번 다른 것을 반환하는 메서드를 쉽게 호출 할 수 있습니다. – Herms