Сравните элементы между ними и получите ключи общих значений - PullRequest
0 голосов
/ 27 сентября 2018

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

Например, со следующим набором данных:

      Vals
Key Col1 Col2
1    4     5
2    6     9
4    8     4
6    10    10

общие значения будут 4 и 10. Поэтому он в этом случае получает новую коллекцию с парами (ключ col1, ключ col2) {{1, 4}, {6, 6}}

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

Обе коллекции не обязательно имеют одинаковые ключи (например, карту), и данные могут быть чем-то иным, чем int (я использую двоичные данные, и обычно ключи являются целыми числами (длинный без сингла).

Вот мой пример кода (очень очень медленный код):

struct p {
    unsigned long int p1;
    unsigned long int p2;
};

vector<int> table1 = tables1(n); /* bigger n -> more samples */
vector<int> table2 = tables2(n); /* n = 10000 generate 150k per table */

vector<p> common;

for (unsigned long int i = 0;i < table1.size(); i++) {
    for (unsigned long int j = 0; j < table2.size(); j++) {
        if (table1[i] == table2[j]) {common.push_back ({i, j};}
    }
}

Есть ли способ с картой, набором, или что-то, чтобы сделать это быстрее? (яначинаю с с ++)

Ответы [ 2 ]

0 голосов
/ 27 сентября 2018

Кажется, что следующий (очень простой) код обрезает горчицу:

#include <map>
#include <vector>
#include <iostream>

struct p
{
    p (int p1, int p2) : p1 (p1), p2 (p2) { }
    int p1;
    int p2;
};

std::vector<int> table1;
std::vector<int> table2;
std::vector<p> common;

#define N   100000

int main ()
{
    table1.reserve (N);
    table2.reserve (N);

    for (int i = 0; i < N; ++i)
        table1.emplace_back (rand ());

    for (int i = 0; i < N; ++i)
        table2.emplace_back (rand ());

    std::map <int, int> map1;
    for (int i = 0; i < N; ++i)
        map1 [table1 [i]] = i;

    common.reserve (N);

    int n = table2.size();
    for (int i = 0; i < n; i++)
    {
        auto f = map1.find (table2 [i]);
        if (f != map1.end ())
            common.emplace_back (i, f->second);
    }

    for (auto x : common)
       std::cout << x.p1 << ", " << x.p2 << "\n";
}

Вывод:

12727, 93810
12766, 48493
16044, 71990
43202, 35849
46218, 81007
82512, 70112
98740, 72244

Обратите внимание на использование reserve и emplace_back для векторов.

Запустите его на Wandbox

Я попытался увеличить N до 1000000, и он все еще работал.Неупорядоченная (хешированная) карта может быть быстрее.

0 голосов
/ 27 сентября 2018

Фактически вы сравниваете все значения между ними и хотите знать ключи этого значения в каждой коллекции.

В этом случае я бы предложил просто инвертировать ключ и значение на каждой карте.Это приведет к следующей структуре:

      Vals
RevKey1 RevVal1 RevKey2 RevVal2
4       1         5     1
6       2         9     2
8       4         4     4
10      6        10     6

Затем вам нужно будет просто перебрать первую карту и найти тот же ключ во второй карте:

map<int,int> col1;
map<int,int> col2;
map<int,pair<int,int>> common ; 
...
for (auto& x: col1) {
    auto y= col2.find(x.first); 
    if (y!=col2.end()) 
        common[x.first]=make_pair(x.second,y->second);
}
cout<<"Result:"<<endl;
for (auto& x:common ) 
    cout << x.first << "<-" << x.second.first << " in col1 and " <<x.second.second << " in col2"<<endl;

Демонстрация в режиме онлайн

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

...