более эффективный метод доступа к элементам разреженной матрицы - PullRequest
Новая
       23

более эффективный метод доступа к элементам разреженной матрицы

4 голосов
/ 01 октября 2010

Я написал небольшой класс разреженной матрицы с членом: 

std::map<int,std::map<int,double> > sm;

Метод ниже - это функция, которую я использую для доступа к элементам матрицы, если это невозможно через итератор: 

double matrix::operator()(int r,int c) const
{
    std::map<int,std::map<int,double> >::const_iterator i = sm.find(r);
    if(i==sm.end()) { return 0.0; }
    std::map<int,double>::const_iterator j = i->second.find(c);
    if(j==i->second.end()) { return 0.0; }
    return j->second;
}

И все же эту функцию нужно вызывать очень часто. Кто-нибудь знает, как улучшить эту функцию? Спасибо вперед.

Ответы [ 2 ]

5 голосов
/ 01 октября 2010

Если вы хотите писать собственный код, а не использовать библиотеку, это изменение может значительно повысить производительность: 

std::map<std::pair<int,int>, double> sm;

Чтобы увеличить дальше, вы можете перейти к хешированным контейнерам: 

std::unordered_map<std::pair<int,int>, double> sm;

(используйте tr1, boost или C ++ 0x)

РЕДАКТИРОВАТЬ: в первом случае вы можете перебрать row следующим образом: 

for(auto& cell : make_pair(
    sm.lower_bound(make_pair(row, 0)), sm.lower_bound(make_pair(row+1, 0))))
{ ... }

Я думаю, что вы можетесделайте вышеупомянутое одним вызовом equal_range с соответствующим функтором, если вы используете Boost.MultiIndex.

для всего: 

for(auto& cell : sm)
{ ... }

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

1 голос
/ 02 октября 2010

Вы, вероятно, возненавидите это, но для следующей (небольшой для отображения) строки матрицы:

1 0 0 5 9 0 0 0

вы можете иметь битовый массив (в данном случае 8 битов), где для каждого бита был установлен или очищен для отражения, если в этой позиции был ненулевой или ноль в этой позиции.

Тогда вы просто сохраняете ненулевые числа в обычном массиве, упакованном вместе, как: 

{ 1, 5, 9 }

и двоичные флаги

0x98 // двоичный код 1001 1000

И чтобы выполнить итерацию по строке матрицы, вы просто использовали бы битовые операции для цикла по массиву битов: 

while (! /* not at the end of the bit array */ ) {
    f = get_next_from_bit_array();  // This is just bitwise shift and bitwise & 
    if (!f) {
       val = 0;
    } else {
       val = compressed_row[i];
       i++;
    }
    do_action(val);
}

Мой код здесь только для демонстрации и не очень C ++, но я надеюсь, что вы поняли идею.

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

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

...