LINUX.ORG.RU
решено Форум — Development  

java graph слишком частый вызов сборщика мусора

 , , ,


0

3

Нужно найти все компоненты связности в которых больше(или равно) четырех вершин. Игра под андроид, сборщик мусора вызывается раз в 3-4 секунды. Если убрать использование графа то ~ раз в минуту. Подскажите как правильно сделать? 

class Graph {
    int  NOT_VISIT = 0;
    int      VISIT = 1;
    int LAST_VISIT = 2;

    private class GraphNode {
        ArrayList<Integer> link = new ArrayList<Integer>();
        int type = 0;
    }

    ArrayList<GraphNode> nodes = new ArrayList<GraphNode>();
    ArrayList<Integer> removes = new ArrayList<Integer>();

    int MAX_COUNT = 4;

    public void createGraph(int n){
        removes.clear();
        nodes.clear();
        for(int i = 0; i < n; i++){
            nodes.add(new GraphNode());
        }
    }

    public void addEdge(int a, int b){
        nodes.get(a).link.add(b);
        nodes.get(b).link.add(a);
    }

    public void bfs(int startNode){
        int count = 1;
        Queue<GraphNode> queue = new LinkedList<GraphNode>();
        queue.add(nodes.get(startNode));
        nodes.get(startNode).type = VISIT;
        while(!queue.isEmpty()) {
            GraphNode node = queue.remove();

            for(int i : node.link){
                GraphNode localNode = nodes.get(i);
                if(localNode.type == NOT_VISIT){
                    localNode.type = VISIT;
                    queue.add(localNode);
                    count++;
                }
            }
        }

        if(count >= MAX_COUNT){
            for(int i = 0; i < nodes.size(); i++){
                if(nodes.get(i).type == VISIT){
                    removes.add(i);
                }
            }
        }

        for(GraphNode node : nodes){
            if(node.type == VISIT){
                node.type = LAST_VISIT;
            }
        }
    }

    public ArrayList<Integer> searchBigGroups(){
        for(int i = 0; i < nodes.size(); i++){
            if(nodes.get(i).type == NOT_VISIT){
                bfs(i);
            }
        }

        Collections.sort(removes, Collections.reverseOrder());
        return removes;
    }
}

UPD собственно вызов происходит так 

graphBall.createGraph(pBalls.size());

for (Contact contact : world.getContactList()) {
    if (contact.isTouching()) {
        if (contact.getFixtureA().getShape() instanceof CircleShape &&
                contact.getFixtureB().getShape() instanceof CircleShape) {
            if (contact.getFixtureA().getBody().getUserData() != null &&
                    contact.getFixtureB().getBody().getUserData() != null) {
                int a = (Integer) contact.getFixtureA().getBody().getUserData();
                int b = (Integer) contact.getFixtureB().getBody().getUserData();

                if (pBalls.get(a).color == pBalls.get(b).color) {
                    //graphBall.addEdge(a, b);
                }
            }
        }
    }
}

ArrayList<Integer> tmp = graphBall.searchBigGroups();
score += tmp.size() * 3;

for (int index : tmp) {
    // Удаляем все найденное 
    world.destroyBody(pBalls.get(index).body);
    pBalls.remove(index);
}

★★★

Последнее исправление: abs (всего исправлений: 5)

рекомендую добавить в теги android и dalvik, потому что андроидовская «жава» (и ее сборщик мусора) с настоящей жавой имеет мало общего, и этот топик смотрят те, кому по вопросу сказать нечего.

stevejobs ★★★★☆
()
Последнее исправление: stevejobs (всего исправлений: 2)

Хорошо бы профилировщиком подсчитать статистику создания новых объектов. В глаз видно что списоки Integer надо заменить на специализированную реализацию коллекции int, например из fastutil.

maxcom ★★★★★
()
Ответ на: комментарий от maxcom

Хорошо бы профилировщиком подсчитать статистику создания новых объектов.

Каким профилировщиком пользоваться? Опыта в этом мало.

abs ★★★
() автор топика
Ответ на: комментарий от abs

Если под Android, то нужно сделать дамп hprof файла с помощью DDMS, сконвертировать его в стандартный формат с помощью hprof-conv и анализировать его с помощью MAT (можно поставить standalone без Eclipse). Надеюсь, кто-нибудь подскажет путь попроще.

Weres ★★★
()

Заменил ArrayList на Array(структура libGDX которая якобы предназначена для того чтоб мусор не появлялся). Не сработало. Но дальше заменил кусочек кода

for(int i = 0; i < n; i++){
            if(i >= nodes.size) {
                nodes.add(new GraphNode());
            }else{
                nodes.get(i).link.clear();
                nodes.get(i).type = 0;
            }
        }

Немного помогло, теперь сборщик мусора вызывается раз в 10 секунд, но как по мне это все равно слишком часто.

abs ★★★
() автор топика

Ребят, все получилось! Заменил все на Array из libGDX

Финальный код такой 

class Graph {
    final static int  NOT_VISIT = 0;
    final static int      VISIT = 1;
    final static int LAST_VISIT = 2;

    Array<GraphNode> queue;

    private class GraphNode {
        Array<Integer> link = new Array<Integer>();
        int type = 0;
    }

//    ArrayList<GraphNode> nodes = new ArrayList<GraphNode>();
//    ArrayList<Integer> removes = new ArrayList<Integer>();

    Array<GraphNode> nodes = new Array<GraphNode>();
    Array<Integer> removes = new Array<Integer>();

    final static int MAX_COUNT = 4;

    public void createGraph(int n){
        removes.clear();
        //nodes.clear();
        for(int i = 0; i < n; i++){
            if(i >= nodes.size) {
                nodes.add(new GraphNode());
            }else{
                nodes.get(i).link.clear();
                nodes.get(i).type = 0;
            }
        }

       queue = new Array<GraphNode>();
    }

    public void addEdge(int a, int b){
        nodes.get(a).link.add(b);
        nodes.get(b).link.add(a);
    }

    public void bfs(int startNode){
        int count = 1;
        queue.add(nodes.get(startNode));
        nodes.get(startNode).type = VISIT;
        while(queue.size != 0) {
            GraphNode node = queue.pop();

            for(int i : node.link){
                GraphNode localNode = nodes.get(i);
                if(localNode.type == NOT_VISIT){
                    localNode.type = VISIT;
                    queue.add(localNode);
                    count++;
                }
            }
        }

        if(count >= MAX_COUNT){
            for(int i = 0; i < nodes.size; i++){
                if(nodes.get(i).type == VISIT){
                    removes.add(i);
                }
            }
        }

        for(GraphNode node : nodes){
            if(node.type == VISIT){
                node.type = LAST_VISIT;
            }
        }
    }

    public Array<Integer> searchBigGroups(){
        for(int i = 0; i < nodes.size; i++){
            if(nodes.get(i).type == NOT_VISIT){
                bfs(i);
            }
        }

        removes.sort();
        removes.reverse();
        //Collections.sort(removes, Collections.reverseOrder());
        return removes;
    }
}

abs ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development