Пространственно-эффективное представление графа в Java?

Question

Я хочу иметь неориентированный граф, где узлы помечены парой (в настоящее время для этого используется String []) и могут быть произвольно связаны с другими узлами. Я начал с типа Hashtable. Оказывается, это недостаточно эффективно для меня - у меня будет около 60 000 узлов (в конечном итоге, намного больше этого числа).

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

Answer 1

Если эффективность использования пространства является вашим приоритетом, тогда вы можете пожертвовать эффективностью времени на операциях с графами и покончить с Hashtable (который, я полагаю, вы используете для хранения помеченных ссылок узла). Просто переключитесь на массив и возьмите на себя стоимость сравнения значений меток в операциях с графами:

public class Node {
    private Links[] links;

    // ... the ops ...

    public static final class Link {
        String label;
        Node   target;
    }
}

Если вы хотите еще больше сжать использование памяти и ваше пространство меток конечно (то есть метки не являются уникальными для данного узла; например, «родитель» - метка, которая встречается снова и снова), тогда подумайте об использовании пользовательской Label класс на шаблон веса , поэтому вы не дублируете экземпляры String.

Answer 2

Ваша главная проблема - размер диска при сериализации или размер в памяти?

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

Answer 3

Если вам нужна постоянная масштабируемость, рассмотрите возможность использования существующей базы данных графов, такой как Neo4J , которая может обрабатывать ОЧЕНЬ большие графы, которые вы описываете (миллионы или миллиарды отношений). Я использовал его для графиков около 25 миллионов узлов с хорошими результатами.