자바 코드의 속도를 높이는 방법은 무엇입니까?

이 메서드는 배열 크기의 절반 이상인 경우 양의 정수 배열에서 숫자를 반환하고 그렇지 않으면 -1을 반환합니다. 더 큰 배열 (10^5<size<10^8)의 실행 시간을 향상시켜야합니다. 어떤 제안?자바 코드의 속도를 높이는 방법은 무엇입니까?

public static int findResult(int arr[],int len){ 

    int val=0; 
    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>(); 
    for(int i=0;i<len;i++){ 
     if(map.containsKey(arr[i])){ 
      val = (Integer)map.get(arr[i]); 
      map.put(arr[i], val+1); 
     }else{ 
      val=1; 
      map.put(arr[i], val); 
     } 
    } 
    Iterator<Integer> it=map.keySet().iterator(); 
    while(it.hasNext()){ 
     int next=it.next(); 
     if((Integer)map.get(next)>(len/2)){ 
      return next; 
     } 
    } 
    return -1; 
}

출처

2013-05-05 Nishant

이것은 아마도 [codereview] (h ttp : //codereview.stackexchange.com/)이 아닙니다. –

또한 코드는 O (n) 시간에 실행됩니다. 그것은 정확히 천천히 아닙니다. – supersam654

(i) containsKey + get 대신에 하나의'get'을 사용하여'null'과 비교하십시오 (ii) 첫 번째 루프에서 가장 높은 숫자를 추적하고 두 번째 루프를 제거하십시오. (iii) 시작할 맵의 크기를 지정하십시오 많은 rehashing 연산을 피한다. – assylias

를 제공하는 것을 교체하는 것이 좋습니다 것입니다 그렇게 나쁘지 :

public static int findResult(int[] arr, int len) { 
    if(len == 0) return -1; 
    if(len == 1) return arr[0]; 

    int element = arr[0]; 
    int count = 1; 
    for(int i = 1; i < len; i++) { 
     if(arr[i] == element) { 
      count++; 
     } else if(count > 0) { 
      count--; 
     } else { 
      element = arr[i]; 
      count = 1; 
     } 
    } 

    count = 0; 
    for(int a:arr) { 
     if(a == element) { 
      count++; 
     } 
    } 

    return (count > len/2) ? element : -1; 
}

출처

2013-05-05 12:44:16 fgb

한 항목이 다수 인 경우에만이 알 고가 작동하지 않습니까? – assylias

@assylias 항목이 다수 인 경우 마지막 수는 <= len/2이고 -1을 반환해야합니다. – fgb

두 번째 루프를 놓쳤습니다. algo에 대한 좋은 설명이 있습니다. http://stackoverflow.com/a/3740548/829571 – assylias

해시 맵에 입력 할 때마다 반복되는 길이 (실행중인 두 번째 반복자 루프)와 비교하지 않는 이유는 무엇입니까? 이것은 hashmap이 완료 될 때까지 결과를 알았으므로 한 번만 수행하면됩니다.

출처

2013-05-05 12:25:45

이 IMO 짧고 더 효율적이다는

public static int findResult(int arr[], int len) { 
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for (int i = 0; i < len; i++) { 
     Integer val = map.get(arr[i]); 
     if (val != null) { 
      map.put(arr[i], val + 1); 
     } else { 
      map.put(arr[i], 1); 
     } 
    } 
    for (Entry<Integer, Integer> e : map.entrySet()) { 
     if (e.getKey() > (len/2)) { 
      return e.getValue(); 
     } 
    } 
    return -1; 
}

1) 원래 버전

if(map.containsKey(arr[i])){ 
     val = (Integer)map.get(arr[i]);

광산 하나

을 map.get 용도 2 방법은지도에 호출을 사용

while(it.hasNext()){ 
     int next=it.next(); 
     if((Integer)map.get(next)>(len/2)){

입니다 성능 현명한 심지어 수중 음파 탐지기 또는 FindBugs 그것을 iimediately 감지하고 내가 권투/언 박싱에 대한 필요성 제거, 당신은지도 않고이 작업을 수행 할 수 있습니다

출처

2013-05-05 12:28:22

이것은 여전히 O (n)이지만이 입력의 크기는 한 번 대 두 번 반복하는 데 차이를 만들 수 있습니다. 또한 map.contains를 get으로 변경하는 것은 여전히 같은 O (1)입니다. –

을 임시 변수를 사용하여 항상 가장 큰 금액 인 을 저장할 때마다 변수의 카운터를 늘릴 때마다 임시 변수보다 큰지 확인하고, 바꾸면 바꾸고, 그렇지 않으면이 방법으로 계속 수행 할 수 있습니다. 두 번째 루프 그리고 당신은 당신의 대답이 임시 변수에 있다는 것을 알고 있습니다

출처

2013-05-05 12:53:53 Dima

자바 코드의 속도를 높이는 방법은 무엇입니까?

답변

관련 문제