Оптимальный способ найти общие элементы между парами комбинаций

Обновить

April 2019

Просмотры

119 раз

1

У меня есть список заказанных товаров типа А, которые каждый из которых содержит подмножество из списка элементов B. Для каждой пары элементов в А, я хотел бы, чтобы найти число элементов B, которые они разделяют (пересекаются).

Например, если у меня есть эти данные:

A1 : B1  
A2 : B1 B2 B3  
A3 : B1  

Тогда я хотел бы получить следующий результат:

A1, A2 : 1  
A1, A3 : 1  
A2, A3 : 1  

Проблема у меня делает алгоритм эффективной. Размер моего набора данных о 8.4K элементов типа А. Это означает, что 8.4K выбрать 2 = 35275800 комбинаций. Алгоритм Я использую просто проходит через каждую комбинацию пару и делать пересечение множеств.

Суть того, что я до сих пор находится ниже. Я хранение считается, что ключом в карте, со значением как вектор пара. Я использую структуру графа данных для хранения данных, но только «график» операции я использую get_neighbors (), который возвращает B подмножество для элемента из A. я знаю, что элементы в графе заказал из индекса от 0 до 8.4K.

void get_overlap(Graph& g, map<int, vector<A_pair> >& overlap) {

map<int, vector<A_pair> >::iterator it;

EdgeList el_i, el_j;
set<int> intersect;

size_t i, j;

VertexList vl = g.vertices();

for (i = 0; i < vl.size()-1; i++) {
    el_i = g.get_neighbors(i);

    for (j = i+1; j < vl.size(); j++) {
        el_j = g.get_neighbors(j);

        set_intersection(el_i.begin(), el_i.end(), el_j.begin(), el_j.end(), inserter(intersect, intersect.begin()));
        int num_overlap = intersect.size();

        it = overlap.find(num_overlap);
        if (it == overlap.end()) {
            vector<A_pair> temp;
            temp.push_back(A_pair(i, j));
            overlap.insert(pair<int, vector<A_pair> >(num_overlap, temp));
        }
        else {
            vector<A_pair> temp = it->second;
            temp.push_back(A_pair(i, j));
            overlap[num_overlap] = temp;
        }
    }
}

}

Я бежал эту программу в течение почти 24 часов, а й элемент в цикл достиг итерацию 250 (я печатаю каждый я в лог-файл). Это, конечно, далеко от 8.4K (хотя я знаю, как Итерации продолжаются, количество сравнений будет укорачивать, так как у = я + 1). Есть ли более оптимальный подход?

Edit: Чтобы было ясно, цель здесь, в конечном счете найти верхний к перекрывается пар.

Изменить 2: Благодаря @Beta и другие для указывая оптимизаций. В частности, корректирование карты напрямую (вместо того, чтобы копировать его содержимое и сброс значения карты) значительно улучшили производительность. В настоящее время она работает в считанные секунды.

1 ответы

1

I think you may be able to make things faster by pre-computing a reverse (edge-to-vertex) map. This would allow you to avoid the set_intersection call, which performs a bunch of costly set insertions. I am missing some declarations to make fully functional code, but hopefully you will get the idea. I am assuming that EdgeList is some sort of int vector:

void get_overlap(Graph& g, map<int, vector<A_pair> >& overlap) {

map<int, vector<A_pair> >::iterator it;



EdgeList el_i, el_j;
set<int> intersect;

size_t i, j;

VertexList vl = g.vertices();

// compute reverse map
map<int, set<int>> reverseMap;
for (i = 0; i < vl.size()-1; i++) {
    el_i = g.get_neighbors(i);
    for (auto e : el_i) {
        const auto findIt = reverseMap.find(e);
        if (end(reverseMap) == findIt) {
            reverseMap.emplace(e, set<int>({i})));
        } else {
            findIt->second.insert(i);
        }
    }
}

for (i = 0; i < vl.size()-1; i++) {
    el_i = g.get_neighbors(i);

    for (j = i+1; j < vl.size(); j++) {
        el_j = g.get_neighbors(j);

        int num_overlap = 0;
        for (auto e: el_i) {
            auto findIt = reverseMap.find(e);
            if (end(reverseMap) != findIt) {
                if (findIt->second.count(j) > 0) {
                    ++num_overlap;
                }
            }
        }

        it = overlap.find(num_overlap);
        if (it == overlap.end()) {
            overlap.emplace(num_overlap, vector<A_pair>({ A_pair(i, j) }));
        }
        else {
            it->second.push_back(A_pair(i,j));
        }
    }
}

I didn't do the precise performance analysis, but inside the double loop, you replace "At most 4N comparisons" + some costly set insertions (from set_intersection) with N*log(M)*log(E) comparisons, where N is the average number of edge per vertex, and M is the average number of vertex per edge, and E is the number of edges, so it could be beneficial depending on your data set. Also, if your edge indexes are compact, then you can use a simplae vector rather than a map to represent the reverse map, which removed the log(E) performance cost.

One question, though. Since you're talking about vertices and edges, don't you have the additional constraint that edges always have 2 vertices ? This could simplify some computations.