C++: 배열들의 전체 순서쌍

cpp
(얼음나무) #1

배열들이 주어졌을 때 배열 각각에서 원소 하나씩을 뽑아 만들 수 있는 모든 순서쌍을 구하고 싶을 때가 있습니다.

예를 들어 {1, 2} / {‘a’, ‘b’} / {0.1, 0.2}의 3개의 배열이 주어진다면
(1, ‘a’, 0.1), (1, ‘a’, 0.2), (1, ‘b’, 0.1), … 등등으로 이루어진 원소 8개 (= 2 x 2 x 2)짜리 배열을 구하고 싶은 거죠.

Python에서는 이것을 itertools.product()로 쉽게 구할 수 있습니다.

하지만 C++에서는 표준 라이브러리에서 그런 함수를 지원해주지 않죠. 그렇다고 다중 for문을 쓸 수도 없는 일…

어쩌다가 자주 쓸 일이 생기다 보니 인터넷의 코드를 여기저기 참고해서 시험삼아 짜봤습니다.

#include <vector>
#include <tuple>
#include <utility>

template <typename Callable>
void cartesian_impl(Callable callable) {
    callable();
}

template <typename Callable, typename TypeFirst, typename... Types>
void cartesian_impl(Callable callable,
    const std::vector<TypeFirst>& firstContainer, const std::vector<Types>&... remaining)
{
    for (const TypeFirst& firstElement : firstContainer) {
        cartesian_impl([&](const Types&... types) {
            callable(firstElement, types...);
        }, remaining...);
    }
}

template <typename... Types>
decltype(auto) cartesian_product(const std::vector<Types>&... containers)
{
    std::vector<std::tuple<Types...>> result;
    cartesian_impl([&](const Types&... types) {
        result.emplace_back(types...);
        }, containers...);
    return result;
}

#include <iostream>

template <std::size_t n, typename TupleType>
class print_tuple_impl
{
public:
    print_tuple_impl(const TupleType& tp) {
        print_tuple_impl<n - 1, TupleType> tpi(tp);
        std::cout << ", " << std::get<n - 1>(tp);
    }
};

template <typename TupleType>
class print_tuple_impl<1, TupleType>
{
public:
    print_tuple_impl(const TupleType& tp) {
        std::cout << std::get<0>(tp);
    }
};

template <typename TupleType>
void print_tuple(const TupleType& tp) {
    std::cout << "(";
    print_tuple_impl<std::tuple_size<TupleType>::value, TupleType> tpi(tp);
    std::cout << ")\n";
}

#include <string>
#include <cassert>
// #include <chrono>

int main() {
    std::vector<int> ints = { 1, 3, 6 };
    std::vector<std::string> strs = { "a", "b", "c" };
    std::vector<double> dbls = { 2.6, 3.9, 5.2 };

    auto prods = cartesian_product(ints, strs, dbls);
    assert(prods.size() == ints.size() * strs.size() * dbls.size());
    for (const auto& prod : prods) {
        print_tuple(prod);
    }
        
}

위의 코드를 테스트해보면 다음과 같이 아웃풋이 잘 나옵니다.

(1, a, 2.6)
(1, a, 3.9)
(1, a, 5.2)
(1, b, 2.6)
(1, b, 3.9)
(1, b, 5.2)
(1, c, 2.6)
(1, c, 3.9)
(1, c, 5.2)
(3, a, 2.6)
(3, a, 3.9)
(3, a, 5.2)
(3, b, 2.6)
(3, b, 3.9)
(3, b, 5.2)
(3, c, 2.6)
(3, c, 3.9)
(3, c, 5.2)
(6, a, 2.6)
(6, a, 3.9)
(6, a, 5.2)
(6, b, 2.6)
(6, b, 3.9)
(6, b, 5.2)
(6, c, 2.6)
(6, c, 3.9)
(6, c, 5.2)

아쉬운 점은 좀 큰 테스트 케이스로 시간 측정해보니 상당히 느리네요.
어떻게 개선할 수 있을지는 좀더 생각해 봐야겠습니다.

3 Likes
(얼음나무) #2

음… 느리다는 말은 취소입니다. 다중 for문과 비교했을 때 그리 차이나지 않네요.

    constexpr int REPEAT_COUNT = 1e5;
    auto start = std::chrono::system_clock::now();
    for (int i = 0; i < REPEAT_COUNT; i++) {
        // auto prods = cartesian_product(ints, strs, dbls);
        std::vector<std::tuple<int, std::string, double>> prods;
        for (const auto& f : ints) {
            for (const auto& s : strs) {
                for (const auto& d : dbls) {
                    prods.emplace_back(f, s, d);
                }
            }
        }
    }
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << elapsed.count() << "s\n";

이게 약 4~5초

    constexpr int REPEAT_COUNT = 1e5;
    auto start = std::chrono::system_clock::now();
    for (int i = 0; i < REPEAT_COUNT; i++) {
        auto prods = cartesian_product(ints, strs, dbls);
        /*
        std::vector<std::tuple<int, std::string, double>> prods;
        for (const auto& f : ints) {
            for (const auto& s : strs) {
                for (const auto& d : dbls) {
                    prods.emplace_back(f, s, d);
                }
            }
        }
        */
    }
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed = end - start;
    std::cout << elapsed.count() << "s\n";

이것도 약 4~5초

(둘 다 VS2019 -O2 기준)

순회 -> tuple 만들기 자체가 좀 느린듯…
읽고 쓰는 원소 갯수는 27 x 10만 = 270만밖에 안 되는데 말이지요.

조금 더 제네릭하게 개선시키면 vector를 받는 것이 아니라
컨테이너의 구간을 정의하는 iterator pair들을 받도록 확장할 수도 있어보이는데… 요건 귀찮으니 나중에

1 Like
(뉴비) #3

와… itertools product 항상 많이 썼었는데 cpp 에서도 구현할 수 잇군요

(바보털) #4

result의 크기를 미리 계산해서 reserve 하면 성능을 개선할 수 있을 것 같읍니다.

(얼음나무) #5

음 말씀하신 건 글 올린 뒤에 시도해봤던 부분인데 시간 차이가 유의미하긴 했으나 크진 않았습니다. 대충 10% 안쪽… 실행하는 환경에 따라 다르겠지만요. std::vector의 push_back은 일단은 amortized O(1)이니…

물론 크기를 이미 알고 있기 때문에 미리 reserve하는 것이 더 좋겠지요.

예제에서 쓴 std::string 자체가 int, double 등의 primitive type보다는 덩치가 좀 있는 녀석이라 저렇게 느려진 것 같기도 합니다

1 Like
(바보털) #6

다중인자 템플릿 대신 auto로 적당히 때워도 됨미당. 컴파일러가 유도리있게 처리해주기 때문에…

void cartesian_impl(auto callable)
{
      callable();
}

void cartesian_impl(auto callable, const auto& firstContainer, const auto&... remaining)
{
      for(const auto& firstElement: firstContainer)
      {
            cartesian_impl([ & ](const auto&... types) { callable(firstElement, types...); }, remaining...);
      }
}

template< typename... Types >
auto cartesian_product(std::vector< Types >&... containers)
{
      std::vector< std::tuple< Types... > > result;
      cartesian_impl([ & ](const auto&... types) { result.emplace_back(types...); }, containers...);
      return result;
}

물론 컴파일된 결과물은 같아요.

2 Likes
(crmerry) #7

오 싱기싱기

(얼음나무) #8

이건 컴파일러 따라 다릅니다. GCC 8.1 (C++2a) 기준으로는

error: use of ‘auto’ in parameter declaration only available with -fconcepts
void cartesian_impl(auto callable, const auto& firstContainer, const auto&… remaining)
^~~~

이렇게 뜬다는… 9.1에서는 되던가요? C++20에서 추가되는 feature인걸로 아는뎀.

(바보털) #9

아뇨, gcc -v 하니까 gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)입니다. 컴파일 옵션은 -std=c++17 -O3 줬고요.

에러가 아니라 워닝으로 뜹니다.

(바보털) #10

원래 되는 거 아닙니까? 템플릿처럼 타입별로 만들어주던데…

(얼음나무) #11

https://en.cppreference.com/w/cpp/language/auto
https://en.cppreference.com/w/cpp/language/function_template#Abbreviated_function_template

https://www.quora.com/Can-we-use-auto-in-function-parameter-declaration-in-C++/answer/Sergey-Zubkov-1

옹… 이게 C++14 까진 (그리고 아마도 C++17까진) ISO C++ standard에서는 불허했으나 GCC extension들 중 하나에서는 지원되었고, C++20에서는 정식 편입된다는 것 같군요.

2 Likes