자바의 ArrayList는 그것은 알려져 루프

-1

를위한 대를 포함하는 I 객체가 나는가() 메소드가 포함되어 사용할 수 있습니다 ArrayList에에 있는지 여부를 찾고자하는 경우 :자바의 ArrayList는 그것은 알려져 루프

if(arraylist.contains(obj)) { // do things }

또는 나는을 위해 사용할 수 루프 (I은 등호() 메소드 오버로드 것을 제공) : 그것은 다른 게시물에 언급 된 바와 같이

for(Object o : arraylist) { 

    if(obj.equals(o)) { 

     // do things 

    } 

}

이 포함()를 실제로 루프와 등호() 메서드 내부에서의 사용합니다. 그러므로, 제 질문은 arraylist가 더 커질 때 contains()가 더 많은 시간을 가질 것으로 기대하는 것이 논리적입니까?

"for 루프"를 피하기 위해 contains()을 사용하므로 런타임이 낮고 일정하게 유지되기 때문에이 코드를 사용하고 있습니다. 그러나 arraylist 크기가 커지면 코드가 상당히 느리게 실행됩니다. .

출처

2014-02-17 Kotsos

입니다 . – Vallentin

@Vallentin 그것은 내가 생각하고 있던 것입니다. 하지만 수동으로 작성한 for 루프 대신 contains()를 사용하면 성능상의 이점이 없거나 적어도 중요한 것은 아닙니다. 맞습니까? – Kotsos

확실히 arraylist의 크기가 증가하면 느려질 것입니다. 'contains()'의 사용법은 한 줄로되어있어 for 루프보다 읽기 쉽고 더 쉬울 것입니다. –

arraylist가 더 큰 경우 contains()가 더 많은 시간이 걸릴 것으로 예상하는 것이 논리적입니까?

예. ArrayList Javadoc의 말 :

isEmpty, get, set, iterator 및 listIterator 작업은 일정 시간 동안 실행됩니다. add 연산은 상각 된 상수 시간에 실행됩니다. 즉, n 요소를 추가하려면 O (n) 시간이 필요합니다. 다른 모든 작업은 선형 시간 (대략 말하면)에서 실행됩니다.

따라서 ArrayList.contains()의 복잡성은 ArrayList를 각 소자를 검사 할 필요 때문에 말이 O (N)이다. 다른 옵션은 없습니다. ArrayList가 정렬되지 않고 그 값이 주어지면 특정 요소에 대한 다른 액세스 경로가 없기 때문입니다.

출처

2014-02-17 14:01:09

"상수 요소는 LinkedList 구현에 비해 낮습니다." 즉, ArrayList 대신 List 인터페이스의 LinkedList 구현을 사용하면 contains() 메소드가 거의 일정한 시간을 갖게되는 것입니까? – Kotsos

아니요, * 요인 *은 복잡성 분석에 중요하지 않습니다. 또한, ArrayList의 인자가 더 낮아서, ArrayList가 O (n)이면 LinkedList가 O (2 * n)와 같을 것이라고 기대합니다. 이것은 ArrayList보다 나을 것입니다. –

답장을 보내 주셔서 감사합니다. – Kotsos

arraylist가 더 큰 경우 contains()가 더 많은 시간이 걸릴 것으로 예상하는 것이 논리적입니까?

예.

contains()는 내부적으로 for 루프와 equals() 메소드를 사용합니다.

검색 할 요소가 많을수록 더 많은 시간이 소요됩니다.

상수 조회가 필요한 경우 해시 세트를 사용해 볼 수 있습니다 (상황에 따라 다를 수 있음). 또는 데이터가 정렬 된 경우 이진 검색을 사용하여 O (n)에서 O (lg (N))로 이동할 수 있습니다.

출처

2014-02-17 14:01:43

예, List의 경우 은 목록의 크기에 비례하여 시간이 걸립니다. 회원을 더 빠르게 확인할 수 있어야하는 경우, 예를 들어, HashSet을 사용하여 일정 시간 동안 회원 자격을 확인할 수 있습니다.

출처

2014-02-17 14:02:41

또는 이진 검색을 사용하는 정렬 된 arraylist – holap

잠깐 만요. ;) – Bex

그리고 물론 그것은 문제의 대상의 위치에 달려 있습니다. 하지만, 최악의 경우 모든 요소를 확인해야합니다. – Puce

많은 사람들이 이미 지적했듯이 : 예, 의미가 있으며 피할 수 없습니다.

contains() - 경우를 최적화하려면 복사본을 채울 필요가없는 경우 ArrayList 대신 HashSet을 사용하는 것이 좋습니다. HashSet은 검색 속도가 훨씬 빠릅니다.

출처

2014-02-17 14:04:23 Bex

메서드는 내부 구현이 예제로 제공 한 것과 마찬가지로 for 루프이기 때문에 반드시 시간이 걸릴 것입니다.

ArrayList에있는 항목이 많을수록 완료까지 걸리는 시간이 길어집니다. 여기

"나는 코드가 ArrayList의 크기가 커질수록 상당히 느리게 실행 것을 알 수 있습니다.", 감각을 만드는, 더 큰 배열이기 때문에, 다음을 통해 검색 할 더 많은 요소가 비슷한 질문 Any big difference between using contains or loop through a list?

출처

2014-02-17 14:10:28 krato

이전에 그 해답을 보았습니다 만 contains()와 foreach | iterator의 비교를 언급하고 있었고 저는 그것이 다소 다른 상황일지도 모른다고 생각했습니다. 보이는 것처럼 나는 틀 렸습니다. – Kotsos

자바의 ArrayList는 그것은 알려져 루프

답변

관련 문제