Использует ли Java TreeSet меньше памяти, чем PriorityQueue? - PullRequest
Новая
       8

Использует ли Java TreeSet меньше памяти, чем PriorityQueue?

0 голосов
/ 26 июня 2018

Я делал это Вопрос и сначала решил его, используя PriorityQueue: - 

public ArrayList<Integer> solve(int A, int B, int C, int D) {
    PriorityQueue<Integer> q = new PriorityQueue<>();
    q.add(A);
    q.add(B);
    q.add(C);
    ArrayList<Integer> list = new ArrayList<>();
    while(list.size() < D){
        int val = q.poll();
        if(list.size() == 0 || list.get(list.size() - 1) != val)
        list.add(val);
        q.add(val*A);
        q.add(val*B);
        q.add(val*C);
    }

    list.sort(null);
    return list;
}

но он выдал java.lang.OutOfMemoryError: ошибка пространства кучи Java.
После замены PriorityQueue на TreeSet решение было принято: - 

 public ArrayList<Integer> solve(int A, int B, int C, int D) {
    ArrayList<Integer> res = new ArrayList<>() ;

    TreeSet<Integer> set = new TreeSet<>() ;
    set.add(A) ;
    set.add(B) ;
    set.add(C) ;

    for(int i = 0; i < D; i++) {
        int temp = set.first() ;
        set.remove(temp) ;
        res.add(temp) ;

        set.add(temp*A) ;
        set.add(temp*B) ;
        set.add(temp*C) ;

    }
    return res ;
}

Ответы [ 2 ]

0 голосов
/ 26 июня 2018

Речь идет не о структурах данных. В первом случае есть комбинация аргументов, которые могут привести к тому, что это утверждение никогда не будет истинным: 

if(list.size() == 0 || list.get(list.size() - 1) != val)

Это означает, что цикл никогда не завершается, и объект q растет, пока у вас не закончится память. Например, попробуйте позвонить с:

solve(1,1,2,5)

Разница в памяти между двумя структурами данных в этом случае не оказывает влияния. Существуют некоторые отличия, связанные с произвольным доступом и указателями «следующий / предыдущий», но здесь это не имеет значения.

0 голосов
/ 26 июня 2018

Это не имеет никакого отношения к объему используемой памяти, просто ваша программа, которая использует PriorityQueue, никогда не заканчивается, добавляя элементы к PriorityQueue снова и снова.

Это не заканчивается из-за вашего условия if(list.size() == 0 || list.get(list.size() - 1) != val) - оно никогда не выполняется, поэтому цикл while, который проверяет размер list (который никогда не изменяется), всегда имеет значение true, поэтому каждое выполнение цикла занимает 1 элемент из очереди, а затем добавляет к нему 3 элемента.

...