Как ускорить этот кусок кода Java?

Этот метод возвращает число из массива положительных целых чисел, если оно встречается более чем в полтора раза от размера массива, -1 в противном случае. Мне нужно улучшить время работы для больших массивов (10^5<size<10^8). Какие-либо предложения?Как ускорить этот кусок кода Java?

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/), а не SO. –

Кроме того, ваш код работает в O (n) времени. Это не совсем медленно. – supersam654

(i) вместо containsKey + get, просто используйте «get» и сравнивайте с «null» (ii) отслеживайте наибольшее число в первом цикле и избавляйтесь от второго цикла (iii) размер вашей карты, чтобы начать с и избегать многих операций перефразирования – 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

Я пропустил второй цикл. Вот хорошее объяснение этого алгоритма: http://stackoverflow.com/a/3740548/829571 – assylias

Почему вы не сравнить с длиной (второй цикл итератора вы работаете) после каждой итерации ввода в HashMap? Это было к тому моменту, когда хэш-файл сделан, вы знаете результат, и вам нужно сделать это только один раз.

источник

2013-05-05 12:25:45

Это ММО короче и эффективнее

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) оригинальная версия использует 2 метод вызывает на карте

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)){

настолько плохой производительности мудрый, что даже Sonar или FindBugs обнаружит его iimediately и предлагают заменить с тем, что я предлагаю

источник

2013-05-05 12:28:22

Хотя это еще O (n), размер этого ввода может иметь значение между повторением раз в два раза. Кроме того, изменение map.contains для вашего получения по-прежнему остается тем же O (1). –

вы можете использовать временную переменную, чтобы хранить всегда самую большую сумму, каждый раз, когда вы увеличиваете счетчик какой-либо переменной, проверьте, если она больше, чем ваша температура, если она есть, замените ее, в противном случае продолжайте, таким образом, вы можете сделать это без второй цикл, и вы просто знаете, что ваш ответ находится во временной переменной

источник

2013-05-05 12:53:53 Dima

Как ускорить этот кусок кода Java?

ответ

Смежные вопросы