Сортировать вектор векторов и считать частоты уникальных происшествий, используя стандартную библиотеку - PullRequest
Новая
       25

Сортировать вектор векторов и считать частоты уникальных происшествий, используя стандартную библиотеку

0 голосов
/ 01 февраля 2019

Учитывая std::vector<std::vector<int>>:

  • Я хочу вывести отсортированный std::vector<std::vector<int>>
  • , который содержит только уникальный std::vector<int>
  • , а также частота (т. Е. count ) этих уникальных std::vector<int>

Мой вопрос состоит из двух частей:

  • как эффективно добиться этого, полагаясь только на стандартную библиотеку?
  • что приводит к плохой работе приведенного ниже кода?

Я пробовал следующее: 

std::vector<std::vector<int>> responseVectors 
{
    { 2,  3,  2 },
    { 3,  2,  3 }, 
    { 3,  2,  3 }, 
    { 3,  3,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 2,  1,  2 }, 
    { 0,  1,  2 }, 
    { 2,  3,  2 },
    { 3,  2,  3 }, 
    { 3,  2,  3 }, 
    { 3,  3,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 2,  1,  2 }, 
    { 0,  1,  2 }
};

std::vector<std::vector<int>> uniqueResponseVectors;
uniqueResponseVectors.reserve(responseVectors.size());

std::sort(responseVectors.begin(), responseVectors.end());
std::unique_copy(responseVectors.begin(), responseVectors.end(), std::back_inserter(uniqueResponseVectors));

std::vector<int> freqTotal;
freqTotal.reserve(uniqueResponseVectors.size());

for(auto&& vector : uniqueResponseVectors)
{
    int count = std::count(responseVectors.begin(), responseVectors.end(), vector);
    freqTotal.push_back(count);
}

И вывод должен быть: 

for(auto&& vector : uniqueResponseVectors)
{
    for(auto&& value : vector)
    {
        std::cout << "\t" << value << "\t";
    }

    std::cout << "\n";
}

// Printed result for the `uniqueResponseVectors`:
//
//    0               1               2
//    1               2               3
//    2               1               2
//    2               3               2
//    3               2               3
//    3               3               3

// Similarly for the `freqTotal`:
//
//    2
//    6
//    2
//    2
//    4
//    2

Дополнительный контекст:

  • Когда я попробовал приведенный выше код для большего набора данных (т. Е. responseVectors с размером 100000 и 12 для каждого std::vector<int>), это было медленно.

  • Я также пытался манипулировать responseVectors напрямую, вызывая std::unique и erase(), чтобы избежать создания копии.Затем я использовал цикл итератора для std::count, сколько раз встречается уникальный std::vector<int>.Однако это оказалось еще медленнее.

1 Ответ

0 голосов
/ 01 февраля 2019

На основе этого ввода я попытался конкретизировать решение, предоставленное YSC в моем случае, чтобы лучше понять, что происходит.Это сводится к использованию std::map, который является отсортированным ассоциативным контейнером : 

std::map<std::vector<int>, int> SortAndCountOccurences(std::vector<std::vector<int>>& vectors)
{
    std::map<std::vector<int>, int> result;

    std::for_each(vectors.begin(), vectors.end(), [&result](auto const& vector) {
            ++result[vector]; 
    });

    return result;
}

При следующем использовании: 

std::vector<std::vector<int>> responseVectors 
{
    { 2,  3,  2 },
    { 3,  2,  3 }, 
    { 3,  2,  3 }, 
    { 3,  3,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 2,  1,  2 }, 
    { 0,  1,  2 }, 
    { 2,  3,  2 },
    { 3,  2,  3 }, 
    { 3,  2,  3 }, 
    { 3,  3,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 1,  2,  3 }, 
    { 2,  1,  2 }, 
    { 0,  1,  2 }
};

std::map<std::vector<int>, int> sortedVectors = SortAndCountOccurences(responseVectors);

Который будет выводить: 

for(auto&& vector : sortedVectors)
{
    for(auto&& value : vector.first)
    {
        std::cout << "\t" << value << "\t";
    }

    std::cout << "-> x" << vector.second << " times" << "\n";
}

//    0               1               2       -> x2 times
//    1               2               3       -> x6 times
//    2               1               2       -> x2 times
//    2               3               2       -> x2 times
//    3               2               3       -> x4 times
//    3               3               3       -> x2 times

Примечание: Решение на YSC можно обобщить до что-нибудь итерируемое .

...