Как оптимизировать этот комбинированный алгоритм?

Question

Я пишу программу молекулярной динамики, в которой необходимо взять атомы в молекуле и найти возможные пути их связывания.Для этого у меня есть вектор объектов Atom, и я генерирую пары комбинаций, используя следующий алгоритм:

    void CombinationKN(std::vector<std::vector<int>> &indices, int K, int N) {
        std::string bitmask(K, 1);
        bitmask.resize(N, 0);

        do {
            /* This loop takes forever with larger N values (approx. 3000) */
            std::vector<int> indexRow;

            for (int i = 0; i < N; i++)
            {
                if (bitmask[i]) indexRow.push_back(i);
            }

            indices.push_back(indexRow);
        } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
    }

Это простой алгоритм выбора N K (т. Е. Возвращаемые индексы могут содержать (1, 2)но не (2, 1)) где в моем случае N - это число атомов в молекуле, а К - 2.

. Затем я называю алгоритм следующим образом:

void CalculateBondGraph(const std::vector<Atom *> &atoms, std::map<int, 
    std::map<int, double>> &bondGraph, ForceField *forceField) {
    int natoms = atoms.size();

    std::vector<std::vector<int>> indices;

    utils::CombinationKN(indices, 2, natoms);

    for (auto &v : indices) {
        int i = v[0];
        int j = v[1];

        /*... Check if atoms i and j are bonded based on their coordinates.*/
    }
}

.Проблема с этим алгоритмом состоит в том, что для больших молекул, которые имеют 3000+ атомов, требуется вечность.Я думал о его распараллеливании (особенно с OpenMP), но даже тогда работа должна была бы быть распределена между несколькими потоками, и это все еще заняло бы много времени для завершения.Мне нужен способ оптимизировать этот алгоритм, чтобы он не занимал много времени для вычисления комбинаций.Любая помощь приветствуется.

Спасибо, Викас

Answer 1

Ваша CombinationKN функция намного дороже, чем должна быть, если K намного меньше, чем N - и если N велико, то, конечно, K намного меньше, чем N или вам не хватит памяти очень быстро.

Обратите внимание, что каждое действительное index_row является строго монотонно возрастающей последовательностью K целых чисел, меньших N и и наоборот ,Достаточно просто сгенерировать их напрямую:

void CombinationKN(std::vector<std::vector<int>> &indices, int K, int N) {
    std::vector<int> index_row;
    // lexographically first valid row
    for (int i=0; i<K; ++i) {
        index_row.push_back(i);
    }

    for(;;) {
        // output current row
        indeces.push_back(index_row);

        // increment index_row the the lexically next valid sequence
        // find the right-most index we can increment
        // This loop does O(1) amortized iterations if K is not large.  O(K) worst case
        int inc_index=K-1;
        int index_limit=N-1;
        while(inc_index >= 0 && index_row[inc_index] >= index_limit) {
          --inc_index;
          --index_limit;
        }
        if (inc_index < 0) {
            break; //all done
        }
        // generate the lexically first valid row with matching prefix and
        // larger value at inc_index
        int val = index_row[inc_index]+1;
        for (;inc_index<K; ++inc_index, ++val) {
            index_row[inc_index] = val;
        }
    }
}

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