Java의 ArrayList에 최대 값 위치

Question

ArrayList에서 최대 값의 위치를 ​​찾는 효율적인 방법이 있습니까? 다음 코드를 작성했으며 아래 코드에서 2 행을 더 효율적으로 만들 수 있는지 알고 싶습니다.

static int getPatternCount(ArrayList<Integer> indicesInPool, int indexofEndStr) { 
     int position = indicesInPool.indexOf(Collections.max(indicesInPool)); 
     return (Math.abs(indexofEndStr - indicesInPool.get(position)) + 1); 
    } 

Answer 1

두 번째 줄은 목록을 두 번 반복합니다.

가장 큰 값을 찾고 루프가 발생한 위치를 추적하는 루프 (직접 작성)를 작성하면 성능을 향상시킬 수 있습니다.

ArrayList<Integer> list = ... 
int limit = list.size(); 
int max = Integer.MIN_VALUE; 
int maxPos = -1; 
for (int i = 0; i < limit; i++) { 
    int value = list.get(i); 
    if (value > max) { 
     max = value; 
     maxPos = i; 
    } 
} 
// maxpos now contains the (first) index of the largest value ... 
// ... or -1 if the list is empty. 

라이브러리 방법으로 제공되는 타사 라이브러리가있을 수 있습니다.

---

하나의 스레드에서이를 수행하는 더 빠른 방법은 없을 것이라고 생각합니다. 목록이 실제로 큰 경우 여러 스레드를 사용하여 목록의 다른 섹션을 스캔하면 성능이 향상 될 수 있습니다. 그러나 동기화 및 설정의 복잡성/오버 헤드가 발생할 수 있습니다. 실제 성능은 하드웨어 메모리 시스템에 의해 제한 될 수 있습니다. 즉 캐시 및 메모리 대역폭의 크기.

---

목록 사용 방법에 따라 다른 방법으로 가장 큰 값과 위치를보다 효율적으로 추적 할 수 있습니다.

• 만 목록의 마지막에 요소를 추가하고, 업데이트하거나 요소를 제거 않을 경우에, 당신은 가장 큰 요소와 위치 당신 append 및 요소 목록에 각 시간을 포함하는 변수를 업데이트 할 수 있습니다.

• 보다 일반적인 경우 업데이트 종류에 관계없이 최대 및 최대 위치를 추적 할 수있는 특수 사용자 지정 목록 유형을 디자인하고 구현할 수 있습니다 (). 그러나 데이터 구조가 복잡하고 메모리가 배가 고 get과 같은 작업은 O(1)에서 O(logN) 또는 그 이상이 될 것입니다.