Какой тип разреженного вектора я должен использовать? - PullRequest
Новая
       20

Какой тип разреженного вектора я должен использовать?

0 голосов
/ 23 апреля 2019

Данные

У меня есть N разных (отсортированных) векторов индексов (std::vector<unsigned int>). Индексы находятся в диапазоне [0; L-1]. Вот два больших правила об этих данных:

  • Только от 0,1% до 10% возможных индексов присутствуют в любом месте
  • Если индекс найден в данном векторе, то он, вероятно, будет найден несколько раз в других векторах.

Следовательно, возможный набор данных с N=10 векторами и с L = 200 может быть 

{45, 110, 119, 145, 170}
{9, 45, 110, 145, 178, 170}
{45, 145}
{45, 178, 183}
{45, 53, 110, 170}
{9, 119, 123, 179}
{9, 45, 119, 130, 131, 170, 190, 199}
{9, 45, 110, 170, 199}
{31, 45, 145}
{9, 178, 183}

Цель

Я хотел бы вычислить частоты каждого индекса. Я бы сделал что-то вроде 

std::vector<double> computeFrequencies(std::vector<std::vector<unsigned int>>& data)
{
    assert(data.size() == N);

    std::vector<double> frequencies(L);
    for (unsigned Ni = 0 ; Ni < N ; Ni++)
    {
        for (unsigned i = 0 ; i < data[Ni].size() ; i++)
        {
            assert(data[Ni][i] < L)
            frequencies[data[Ni][i]]++;
        }
    }

    for (unsigned i = 0 ; i < L; i++)
    {
        frequencies[i] /= (double) N;
    }

    return(frequencies);    
}

Затем я снова пройдусь по объекту, возвращенному функцией computeFrequencies только один раз. 

for (unsigned i = 0 ; i < L; i++)
{
    foo(frequencies[i]);
}

Вопрос

Объект frequencies содержит много нулей, и поэтому я должен вместо этого использовать разреженный вектор. Я не очень разбираюсь в разреженных матрицах. Какой тип разреженного вектора я должен использовать?

Я рассматриваю возможность использования boost::numeric::ublas::coordinate_matrix<double><double>, потому что, когда я перебираю все N векторы, я постоянно добавляю новые ненулевые значения, и я думаю, что для решения этой проблемы будет полезна матрица координат. Обратите внимание, что в целом для этой функции меня больше беспокоит использование оперативной памяти, чем время вычислений.

1 Ответ

1 голос
/ 24 апреля 2019

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

Чтобы выполнить задачу, как вы ее описали:

  1. Объедините отсортированные векторы водин отсортированный вектор.Как сделать эффективное K-way merge всплывает здесь время от времени: объединение N отсортированных файлов с помощью K-way merge
  2. Итерация по новому вектору и подсчет количества дубликатов каждогозапись (легко, так как они все будут вместе), чтобы получить ваши частоты и foo их, как вы идете.

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

...