Как повысить производительность с помощью Java ArrayList

Question

Я использую огромный ArrayList с кодом ниже

public final List<MyClass> list = new ArrayList<>();

public void update(MyClass myClass) {
int i;
for (i=0; i < list.size(); i++) {
        if (myClass.foo(list.get(i))) {
            list.set(i, myClass);
            break;
        }    
    }    
    if (i == list.size()) {    
        list.add(myClass);    
    }    
}

Список очень большой. Есть что-то еще, что я могу сделать, чтобы повысить производительность в этом сценарии? Может быть, использовать какую-то функцию Java 8, заменить ArrayList или что-то в этом роде.

Другой код, который слишком долго запускается, связанный с этим списком, является кодом ниже:

public List<MyClass> something(Integer amount) {
list.sort((m1, m2) -> Double.compare(m2.getBar(), m1.getBar()));
return list.stream()
        .limit(amount)
        .collect(Collectors.toList());
}

Любая помощь приветствуется, спасибо всем

Answer 1

Есть что-то еще, что я могу сделать, чтобы повысить производительность в этом сценарии?

Проблема в том, что ваш алгоритм должен применять myClass.foo к каждому элементу списка, пока вы не найдете first match. Если вы делаете это последовательно, то сложность наихудшего случая равна O(N), где N - размер списка. (И размер списка велик.)

Теперь вы можете выполнять поиск параллельно. Однако, если может быть несколько совпадений, сопоставление с первым совпадением в списке будет непростым делом. И вы все равно получите O(N/C), где C - это количество доступных ядер.

Единственный способ стать лучше, чем O(N), - это использовать другую структуру данных. Но, не зная, что делает метод MyClass::foo, трудно сказать, какой должна быть эта структура данных.

---

Похоже, ваша вторая проблема - это попытка решить проблему «топ К из N». Это может быть реализовано в O(N log K) и, возможно, лучше; см. Оптимальный алгоритм для возврата лучших значений k из массива длины N .

Answer 2

Кажется, что выбор ArrayList не подходит.

В первом случае вы пытаетесь найти объект по его свойствам в списке. Чтобы найти объект в списке, вы должны проверить каждый элемент вашего списка. Чем больше список, тем дольше он будет. (сложность O (N) в худшем случае с ArrayList)

Если вы используете HashMap вместо List, вы можете использовать вашу собственность в качестве ключа вашей карты. Таким образом, вы можете выбрать объект, который нужно обновить напрямую, без проверки каждого элемента вашего списка. Время выполнения больше не будет зависеть от количества записей. (сложность O (1) в худшем случае с HashMap)

Если вы используете HashMap вместо ArrayList, ваш код обновления будет выглядеть следующим образом:

public void update(MyClass myClass) {
    map.put(myClass.getKey(), myClass);
}

(где getKey() - свойства, которые вы пытаетесь сравнить с вашим методом foo).

Но это только для первого случая. С имеющейся у нас информацией это кажется лучшим решением.