Улучшение производительности слияния двух ArrayLists

Question

Я объединяю два ArrayList s со следующим кодом. Код работает и дает мне желаемый результат, но я хочу более эффективную версию. Вот условия.

1. Метод принимает два списка, и оба имеют список элементов в порядке убывания (5,4,3,2)
2. метод принимает целое число, чтобы решить, размер полученного ArrayList.
3. Размер первого списка входных данных никогда не превышает размер получаемого ArrayList.

Код:

public ArrayList<Integer> mergeList(ArrayList<Integer> first,ArrayList<Integer> second, int n){ 
    //case 1: when both list are null. 
    if(first == null && second == null) 
     return null; 
    //case 2: when first list is null but second list have elements 
    else if(first == null && second != null){ 
     return second.size() >=n ? new ArrayList<Integer>(second.subList(0, n)) : second; 
    } 
    //case 3: when first list have record and second list is null 
    else if(first != null && second == null){ 
     return first; 
    } 
    //case 4: when both list have elements 
    else { 
     first.addAll(second); 
     Collections.sort(first); 
     Collections.reverse(first); 
     return first.size()>=n ? new ArrayList<Integer>(first.subList(0, n)) : first; 
    } 
} 

}

Answer 1

Это зависит от того, что вы подразумеваете под «Более эффективным».

С точки зрения чего? Память, процессор, читаемость?

на основе кода выше, я делаю следующие предположения:

• Дискретность является более важным, чем чистое потребление/производительность памяти без каких-либо профилирующих измерений/требований «Первое правило оптимизации программы: Дон» Это второе правило оптимизации программ (только для экспертов!): Не делайте этого еще ». - Майкл А. Джексон
• Предпочитают нулевой образец объекта над возвращением нуля
• повторяющихся элементов желательно/требуется
• Используйте Comparator для выполнения обратного рода

---

private List<Integer> mergeList(List<Integer> list1, List<Integer> list2, final int newSize) { 

    // Enforce null object pattern 
    if (list1 == null) { 
     list1 = Collections.emptyList(); 
    } 
    if (list2 == null) { 
     list2 = Collections.emptyList(); 
    } 

    // If duplicates are not desirable, a TreeSet would perform automatic sorting. 
    List<Integer> result = new ArrayList<Integer>(list1); 
    result.addAll(list2); 

    Comparator<Integer> reverseSortComparator = new Comparator<Integer>() { 

     @Override 
     public int compare(final Integer o1, final Integer o2) { 
      return o2.compareTo(o1); 
     } 
    }; 

    Collections.sort(result, reverseSortComparator); 

    if (result.size() > newSize) { 
     return result.subList(0, newSize); 
    } else { 
     return result; 
    } 
} 

Answer 2

Похоже, что вы пытаетесь сохранить содержимое first и second. Если нет, то это будет делать только штрафом для вас и сделает ваш код быстрее и более удобным для чтения:

public ArrayList<Integer> mergeList(ArrayList<Integer> first,ArrayList<Integer> second, int maxLength){ 

    //case 1: when both list are null. 
    if(first == null && second == null) 
     return null; 
    //case 2: when first list is null but second list have elements 
    else if(first == null && second != null){ 
     return second; 
    } 
    //case 3: when first list have record and second list is null 
    else if(first != null && second == null){ 
     return first; 
    } 
    //case 4: when both list have elements 
    else if(first != null && second != null){ 
     first.addAll(second); 
     Collections.sort(first); //want to merge these two line into one 
     Collections.reverse(first); 
    } 
    return (ArrayList) first.size() > maxLength ? first.subList(0, n) : first; 
} 

Причина, почему это происходит быстрее, потому что с каждым addAll(), Java должны перебрать все пункты , копируя их в tempList. Я сохранил вызов Collections.reverse, потому что кажется, что вам нужно иметь данные в обратном порядке сортировки.