Одновременное объединение и пересечение двух карт в C ++

Question

Делая проект в колледже, я столкнулся со следующей проблемой: у меня есть две карты (Kmer1 и Kmer2), которые состоят из строки (ключа) и int (значения). Я должен рассчитать расстояние , которое следует этой формуле

[1-(I/U)]*100

Where...
     ...U = the sum of all int values inside Kmer1 U Kmer2
     ...I = the sum of all int values inside Kmer1 ∩ Kmer2

Consider that...
             ... The U and ∩ are made evaluating the keys (strings)
             ... When an element is in both maps:
                 - At the Union we add the one with higher int value
                 - At the Intersection we add the one with lower int value

Пример:

Kmer1 = AAB¹ AAC¹ AAG³
Kmer2 = AAG¹ AAT² ABB¹

Union = AAB¹ AAC¹ AAG³ AAT² ABB¹   U= 8
Intersection = AAG¹                I= 1
Distance = 87.5

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

Настройка:

Species::Kmer Kmer1, Kmer2;        //The two following lines get the Kmer from another
Kmer1 = esp1->second.query_kmer(); //object.
Kmer2 = esp2->second.query_kmer(); 

Species::Kmer::const_iterator it1, it2, last1, last2;
it1 = Kmer1.cbegin();           //Both Kmer are maps, therefore they are ordered and
it2 = Kmer2.cbegin();           //whitout duplicates.
last1 = --Kmer1.cend();
last2 = --Kmer2.cend();

double U, I;
U = I = 0;

l oop, где применяется формула:

while (it1 != Kmer1.cend() and it2 != Kmer2.cend()){
    if (it1->first == it2->first) {         
        if (it1->second > it2->second) {
            U += it1->second;
            I += it2->second;
        } else {
            U += it2->second;
            I += it1->second;
        }
        ++it1;
        ++it2;

    } else if (it1->first < it2->first) {
        U += it1->second;
        ++it1;
    } else {
        U += it2->second;
        ++it2;
    }
}

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

---

I've uploaded the whole code at Github: (Maybe it helps)
    - There is a makefile to build the code
    - There is a file called input.txt with a sample for this specific problem
    - Also inside the input.txt, after line13 (fin) I've added the expected output
    - Executing ./program.exe < input.txt should be enough to test it.

https://github.com/PauGalopa/Cpp-Micro-Projects/tree/master/Release

---

ВАЖНО Да! Я знаю почти все функции STL, которые могли бы сделать это в нескольких строках, НО ... Поскольку это проект колледжа, я привязан к ограничениям sillabus, поэтому учтите, что мне разрешено использовать только "map «строка», «вектор» и многое другое. Нет, я не могу использовать «алгоритм» (я действительно sh мог бы). Я проясню любые сомнения относительно того, что я могу делать или использовать в комментариях.

Answer 1

Вот довольно простое решение, использующее только некоторые свойства std::map, без итератора. Я надеюсь, что вам разрешено использовать такое решение.

#include <iostream>
#include <map>
#include <string>

int main () {
    std::map <std::string, int> A = {{"AAB", 1}, {"AAC", 1}, {"AAG", 3}};
    std::map <std::string, int> B = {{"AAG", 1}, {"AAT", 2}, {"ABB", 1}};

    std::map <std::string, int> Union;
    int sum_A = 0, sum_B = 0, sum_Union = 0, sum_Inter = 0;;

    for (auto &x: A) {
        Union[x.first] = std::max (Union[x.first], x.second);
        sum_A += x.second;
    }
    for (auto &x: B) {
        Union[x.first] = std::max (Union[x.first], x.second);
        sum_B += x.second;
    }   
    for (auto &x: Union) {
        sum_Union += x.second;
    }
    sum_Inter = sum_A + sum_B - sum_Union;
    double distance = 100.0 * (1.0 - double(sum_Inter)/sum_Union);

    std::cout << "sum_Union = " << sum_Union << " sum_Inter = " << sum_Inter << "\n";
    std::cout << "Distance = " << distance << "\n";
}

Answer 2

Добавьте эти две петли сразу после основного while l oop.

while (it1 != Kmer1.cend()){
    U += it1->second;
    it1++;
}
while (it2 != Kmer2.cend()){
    U += it2->second;
    it2++;
}

Answer 3

Этот l oop должен работать:

while ( true ){
    bool end1 = it1 == Kmer1.cend();
    bool end2 = it2 == Kmer2.cend();
    if( end1 and end2 )
        break;

    if( end2 or it1->first < it2->first ) {
        U += (it1++)->second;
        continue;
    }
    if( end1 or it2->first < it1->first ) {
        U += (it2++)->second;
        continue;
    }
    auto p = std::minmax( (it1++)->second, (it2++)->second );
    I += p.first;
    U += p.second;
}

Answer 4

Немного более чистый подход для unordered_mapping, но который все равно будет работать с mapping, - это добавить все элементы Kmer1 в U и общие элементы в I. Затем добавьте все неразделенные элементы Kmer2 в U:

for(it1 = Kmer1.cbegin(); it1 != Kmer1.cend(); it1++) {
    auto other = Kmer2.find(it1->first);
    if(other == Kmer2.cend()) {
        U += it1->second;
    } else {
        U += max(it1->second, other->second);
        I += min(it1->second, other->second);
    }
}
for(it2 = Kmer2.cbegin(); it2 != Kmer2.cend(); it2++) {
    if(Kmer1.count(it2->first) == 0) {
        U += it2->second
    }
}

Для правильно реализованной unordered_mapping (ha sh таблицы) операция find будет O(1), не O(log(n), что делает его немного быстрее.