снижение требований к памяти для списка смежности

StackOverflow https://stackoverflow.com/questions/1362689

Вопрос

Я использую adjacency_list< vecS, vecS, двунаправленныйS...> широко.У меня так много графиков загружены одновременно, что память становится проблемой.Я делаю статический анализ программы и хранят кал -граф и проточные графы разобработанного двоичного файла в графиках повышения.Таким образом, я могу иметь несколько десяти тысяч функций == Протоковые графы и один гигантский вызов.Я бы очень хотел уменьшить использование памяти для моих графиков, при этом используя BGL.

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

больше вопросов:
1) каковы затраты памяти при использовании свойств вершин и ребер?У меня есть немало из них.
2) Можно ли убедить BGL использовать термоусадочную площадь в соответствии с идиомой?Насколько я понимаю, списки смежности используют push_back, чтобы добавить края.Можно ли уменьшить использование памяти, заменив полученный вектор с копией себя?Может, копировав весь график?
3) Можно ли использовать распределители пула повышения с BGL?Насколько я могу сказать, BGL в настоящее время выполняет много небольших распределений - я бы очень хотел избежать этого по причинам эффективности пространства и времени выполнения.

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

с наилучшими пожеланиями,

Sören
Это было полезно?

Решение

В BGL есть малоизвестный тип графа, называемый графом «сжатые разреженные строки».Кажется, он совершенно новый и не связан с индексными страницами.Однако здесь используется красивый маленький трюк, позволяющий получить графическое представление как можно меньше.http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/compressed_sparse_row.html

Используя это для некоторых наших графиков, мне уже удалось сократить общее использование памяти на 20% — так что это действительно стоящая оптимизация.

Он также сохраняет свойства вершин/ребер в векторах, что также обеспечивает минимальные накладные расходы для них.

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

Другие советы

  1. Накладные расходы зависят от того, какую версию вы используете и используете ли вы «связанные» свойства или нет.Я использовал только связанные свойства и, читая код, ожидаю, что каждый пакет свойств будет стоить вам 2 указателя + размер используемого типа пакета + размер каждого из прикрепленных свойств.На самом деле в двоичном файле не осталось ничего из вещей, связанных с проверкой концепции.Однако, поскольку у вас есть код, почему бы просто не измерить стоимость?Если у вас нет инструментов, которые могли бы помочь, попробуйте просто сгенерировать графики известных размеров в буферах известных размеров.В конце концов что-то потерпит неудачу, и в этот момент у вас должны быть подсчеты.

  2. Вы пробовали позвонить adjacency_list<blah>.swap(adjacency_list& x)?Я надеюсь, что это уменьшит контейнеры соответствующим образом.

  3. ???

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

Поскольку BGL предназначен для взаимодействовать с устаревшими или пользовательскими графиками, вам, вероятно, лучше всего написать свой собственный график.

В качестве ответа на:

3) Можно ли использовать распределители пула повышения с BGL?Насколько я могу судить, BGL в настоящее время выполняет множество небольших распределений - мне бы очень хотелось избежать этого из соображений эффективности пространства и времени выполнения.

Код скопирован с здесь:

 template <class Allocator>
  struct list_with_allocatorS { };

  namespace boost {
    template <class Alloc, class ValueType>
    struct container_gen<list_with_allocatorS<Alloc>, ValueType>
    {
      typedef typename Alloc::template rebind<ValueType>::other Allocator;
      typedef std::list<ValueType, Allocator> type;
    };
  }

  // now you can define a graph using std::list 
  //   and a specific allocator  
  typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top