如何通过匹配字段获取所有组合
How to get all combinations by matching fields
我有 4 个类。
夹克、衬衫、领带和套装。
class Outfit {
//...
shared_ptr<Jacket> jacket;
shared_ptr<Shirt> shirt;
shared_ptr<Tie> tie;
//...
}
class Jacket {
public:
Jacket(const string &brand, const string &color, const string &size);
// ... getters, setters etc. ...
private:
string brand, color, size
}
// The same for shirt and tie, brand, followed by color or size
我需要分别得到夹克和衬衫、夹克和领带之间所有可能的匹配。像这样：
vector<shared_ptr<Jacket>> jackets {
make_shared<Jacket>("some_brand", "blue", "15"),
make_shared<Jacket>("some_other_brand", "red", "14")
};
vector<shared_ptr<Shirt>> shirts {
make_shared<Shirt>("brand1", "doesnotmatterformatchingcriteria", "15"),
make_shared<Shirt>("brand6", "blue", "15"),
make_shared<Shirt>("brand3", "blue", "14"),
make_shared<Shirt>("brand5", "red", "15"),
make_shared<Shirt>("brand6", "red", "14")
};
vector<shared_ptr<Tie>> ties {
make_shared<Tie>("other_brand1", "blue"),
make_shared<Tie>("other_brand2", "blue"),
make_shared<Tie>("other_brand6", "blue"),
make_shared<Tie>("other_brand7", "blue"),
};
void getAllPosibilities(vector<Outfit> &outfits) {
for (const auto &jacket : jackets) {
for (const auto &shirt : shirts) {
if (jacket->getSizeAsString() == shirt->getSizeAsString()) {
for (const auto &tie : ties) {
if (jacket->getColor() == tie->getColor()) {
outfits.push_back(Outfit(jacket, shirt, ties));
}
}
}
}
}
}
所以基本上我想要所有的组合，无论品牌名称如何，只通过我指定的字段来匹配，但我认为这太慢了，考虑到我一直在嵌套 for 循环。在我的实际问题中，我有更多的字段要匹配，而且更多类，我认为这根本不理想。
除了这样做还有什么better/simpler解决方案吗？
如果您对所有情况都感兴趣，我认为不可能进行优化，原因很简单：
假设您有 2 个品牌的夹克、5 个衬衫和 4 个领带，那么您正在寻找 2*5*4，这意味着 40 种可能性。那只是您要寻找的数量，因此无需在那里进行优化。那么下面的循环就ok了：
for all jackets_brands:
for all shirts_brands:
for all ties_brands:
...
但是，假设您有一些标准，例如 5 个品牌中的一些品牌与 4 个品牌中的一些品牌不搭配。在这种情况下，最好更改 for 循环的顺序，如您在此处所见：
for all shirts_brands:
for all ties_brands:
if go_together(this_particular_shirts_brand, this_particular_ties_brand)
then for all jackets_brands:
...
通过这种方式，您可能会避免一些不必要的循环。
排序通常是个好主意：
static constexpr auto size_comp = [](auto&& a, auto&& b){
return a->getSizeAsString() < b->getSizeAsString(); };
static constexpr auto color_comp = [](auto&& a, auto&& b){
return a->getColor() < b->getColor(); };
std::sort(jackets.begin(), jackets.end(), size_comp);
std::sort(shirt.begin(), shirt.end(), size_comp);
std::sort(tie.begin(), tie.end(), color_comp);
auto ps = shirts.begin();
for (auto pj = jackets.begin(); pj != jackets.end() && ps != shirts.end(); ++pj)
ps = std::lower_bound(ps, shirts.end(), *pj, size_comp);
auto pt = std::lower_bound(ties.begin(), ties.end(), *pj, color_comp);
for (auto psx = ps; psx != shirts.end() && !size_comp(*pj, *psx); ++psx) {
for (auto ptx = pt; ptx != ties.end() && !color_comp(*pj, *ptx); ++ptx)
outfits.emplace_back(*pj, *psx, *ptx);
}
}
您在这里所做的在数据库中通常称为连接。作为 SQL 查询，您的代码将如下所示：
select * from jacket, shirt, tie where jacket.size == shirt.size and jacket.color == tie.color;
算法思路
嵌套循环连接
现在，您所实现的被称为 nested loop join，它的复杂度通常为 O(jackets * shirts * ties)，但是，您的衬衫里面有一个早期的 return -loop，所以你在那里节省了一些复杂性并将其减少到 O(jackets * shirts + jackets * matching_shirts * ties).
对于小型数据集，如您提供的，这种嵌套循环连接非常有效，通常被选择。但是，如果数据变大，算法会很快变慢。根据您可以节省多少额外内存以及对输入序列进行排序是否适合您，您可能希望使用利用排序的方法，正如@Deduplicator 最初指出的那样。
排序合并联接
sort-merge-join通常用于两个输入序列，这样两个序列都排序后，只需要遍历每个序列一次，排序复杂度为O(N log N)和 O(N) 用于实际的连接阶段。查看 the Wikipedia article 以获得更深入的解释。但是，当您有两个以上的输入序列时，逻辑会变得难以维护，您必须多次遍历其中一个输入序列。实际上，我们将 O(N log N) 用于夹克、衬衫和领带的分类，而实际连接部分的复杂度为 O(夹克 + 衬衫 + 颜色 * 领带)。
排序+二分查找加入
在@Deduplicator 给出的答案中，他们使用了排序，但方式不同：他们没有按顺序遍历输入序列，而是使用二进制搜索来快速找到匹配元素块。这为排序提供了 O(N log N)，为实际连接阶段提供了 O(jackets * log shirts + log tie * matching jacket-shirt combinations + output_elements)。
哈希连接
但是，如果您拥有的元素可以轻松地进行哈希处理，那么所有这些方法都可以胜过，因为哈希映射使我们能够以极快的速度存储和找到潜在的加入伙伴。在这里，方法是对除一个输入序列之外的所有输入序列进行一次迭代，并将元素存储在哈希图中。然后，我们对最后一个输入序列进行一次迭代，并使用哈希映射找到所有匹配的连接伙伴。同样，Wikipedia has a more in-depth explanation。我们可以在这里使用 std::unordered_map。我们应该能够在这里找到一个好的散列函数，所以这给了我们总共 运行 的时间 O(jackets + shirts + ties + total_output_tuples)，这是你可以多快的下限be: 你需要处理一次所有的输入序列，你需要产生输出序列。
此外，它的代码相当漂亮（恕我直言）且易于理解：
void hashJoin(vector<Outfit> &outfits) {
using shirtsize_t = decltype(Shirt::size);
std::unordered_map<shirtsize_t, vector<shared_ptr<Shirt>>> shirts_by_sizes;
using tiecolor_t = decltype(Tie::color);
std::unordered_map<tiecolor_t, vector<shared_ptr<Tie>>> ties_by_colors;
for(const auto& shirt : shirts) {
shirts_by_sizes[shirt->size].push_back(shirt);
}
for(const auto& tie : ties) {
ties_by_colors[tie->color].push_back(tie);
}
for (const auto& jacket : jackets) {
for (const auto& matching_shirt : shirts_by_sizes[jacket->size]) {
for (const auto& matching_tie : ties_by_colors[jacket->color]) {
outfits.push_back(Outfit{jacket, matching_shirt, matching_tie});
}
}
}
}
然而，在最坏的情况下，如果我们的散列没有给我们统一的散列，我们可能会遇到更糟糕的复杂性，因为 O(1) 访问会变得更糟。您需要检查哈希映射以发现这一点，并在这种情况下替换哈希函数。
实施
I've posted a working implementation of all four algorithms I discussed here on godbolt。然而，由于它们相当长，我只在这个答案中包含了（高级）散列连接算法
下界和输出元素
正如@Dominique 指出的那样，没有比 O(output_element_count) 更好的 运行 时间复杂度的方法了，因为您必须至少生成每个输出元素一次。因此，如果您期望您的结果（渐近地）接近夹克 * 衬衫 * 领带，则嵌套循环连接是开销最低的变体，因此应该是最快的。但是，我认为这里不会是这种情况。
我有 4 个类。 夹克、衬衫、领带和套装。
class Outfit {
//...
shared_ptr<Jacket> jacket;
shared_ptr<Shirt> shirt;
shared_ptr<Tie> tie;
//...
}
class Jacket {
public:
Jacket(const string &brand, const string &color, const string &size);
// ... getters, setters etc. ...
private:
string brand, color, size
}
// The same for shirt and tie, brand, followed by color or size
我需要分别得到夹克和衬衫、夹克和领带之间所有可能的匹配。像这样：
vector<shared_ptr<Jacket>> jackets {
make_shared<Jacket>("some_brand", "blue", "15"),
make_shared<Jacket>("some_other_brand", "red", "14")
};
vector<shared_ptr<Shirt>> shirts {
make_shared<Shirt>("brand1", "doesnotmatterformatchingcriteria", "15"),
make_shared<Shirt>("brand6", "blue", "15"),
make_shared<Shirt>("brand3", "blue", "14"),
make_shared<Shirt>("brand5", "red", "15"),
make_shared<Shirt>("brand6", "red", "14")
};
vector<shared_ptr<Tie>> ties {
make_shared<Tie>("other_brand1", "blue"),
make_shared<Tie>("other_brand2", "blue"),
make_shared<Tie>("other_brand6", "blue"),
make_shared<Tie>("other_brand7", "blue"),
};
void getAllPosibilities(vector<Outfit> &outfits) {
for (const auto &jacket : jackets) {
for (const auto &shirt : shirts) {
if (jacket->getSizeAsString() == shirt->getSizeAsString()) {
for (const auto &tie : ties) {
if (jacket->getColor() == tie->getColor()) {
outfits.push_back(Outfit(jacket, shirt, ties));
}
}
}
}
}
}
所以基本上我想要所有的组合，无论品牌名称如何，只通过我指定的字段来匹配，但我认为这太慢了，考虑到我一直在嵌套 for 循环。在我的实际问题中，我有更多的字段要匹配，而且更多类，我认为这根本不理想。
除了这样做还有什么better/simpler解决方案吗？
如果您对所有情况都感兴趣，我认为不可能进行优化，原因很简单：
假设您有 2 个品牌的夹克、5 个衬衫和 4 个领带，那么您正在寻找 2*5*4，这意味着 40 种可能性。那只是您要寻找的数量，因此无需在那里进行优化。那么下面的循环就ok了：
for all jackets_brands:
for all shirts_brands:
for all ties_brands:
...
但是，假设您有一些标准，例如 5 个品牌中的一些品牌与 4 个品牌中的一些品牌不搭配。在这种情况下，最好更改 for 循环的顺序，如您在此处所见：
for all shirts_brands:
for all ties_brands:
if go_together(this_particular_shirts_brand, this_particular_ties_brand)
then for all jackets_brands:
...
通过这种方式，您可能会避免一些不必要的循环。
排序通常是个好主意：
static constexpr auto size_comp = [](auto&& a, auto&& b){
return a->getSizeAsString() < b->getSizeAsString(); };
static constexpr auto color_comp = [](auto&& a, auto&& b){
return a->getColor() < b->getColor(); };
std::sort(jackets.begin(), jackets.end(), size_comp);
std::sort(shirt.begin(), shirt.end(), size_comp);
std::sort(tie.begin(), tie.end(), color_comp);
auto ps = shirts.begin();
for (auto pj = jackets.begin(); pj != jackets.end() && ps != shirts.end(); ++pj)
ps = std::lower_bound(ps, shirts.end(), *pj, size_comp);
auto pt = std::lower_bound(ties.begin(), ties.end(), *pj, color_comp);
for (auto psx = ps; psx != shirts.end() && !size_comp(*pj, *psx); ++psx) {
for (auto ptx = pt; ptx != ties.end() && !color_comp(*pj, *ptx); ++ptx)
outfits.emplace_back(*pj, *psx, *ptx);
}
}
您在这里所做的在数据库中通常称为连接。作为 SQL 查询，您的代码将如下所示：
select * from jacket, shirt, tie where jacket.size == shirt.size and jacket.color == tie.color;
算法思路
嵌套循环连接
现在，您所实现的被称为 nested loop join，它的复杂度通常为 O(jackets * shirts * ties)，但是，您的衬衫里面有一个早期的 return -loop，所以你在那里节省了一些复杂性并将其减少到 O(jackets * shirts + jackets * matching_shirts * ties).
对于小型数据集，如您提供的，这种嵌套循环连接非常有效，通常被选择。但是，如果数据变大，算法会很快变慢。根据您可以节省多少额外内存以及对输入序列进行排序是否适合您，您可能希望使用利用排序的方法，正如@Deduplicator 最初指出的那样。
排序合并联接
sort-merge-join通常用于两个输入序列，这样两个序列都排序后，只需要遍历每个序列一次，排序复杂度为O(N log N)和 O(N) 用于实际的连接阶段。查看 the Wikipedia article 以获得更深入的解释。但是，当您有两个以上的输入序列时，逻辑会变得难以维护，您必须多次遍历其中一个输入序列。实际上，我们将 O(N log N) 用于夹克、衬衫和领带的分类，而实际连接部分的复杂度为 O(夹克 + 衬衫 + 颜色 * 领带)。
排序+二分查找加入
在@Deduplicator 给出的答案中，他们使用了排序，但方式不同：他们没有按顺序遍历输入序列，而是使用二进制搜索来快速找到匹配元素块。这为排序提供了 O(N log N)，为实际连接阶段提供了 O(jackets * log shirts + log tie * matching jacket-shirt combinations + output_elements)。
哈希连接
但是，如果您拥有的元素可以轻松地进行哈希处理，那么所有这些方法都可以胜过，因为哈希映射使我们能够以极快的速度存储和找到潜在的加入伙伴。在这里，方法是对除一个输入序列之外的所有输入序列进行一次迭代，并将元素存储在哈希图中。然后，我们对最后一个输入序列进行一次迭代，并使用哈希映射找到所有匹配的连接伙伴。同样，Wikipedia has a more in-depth explanation。我们可以在这里使用 std::unordered_map。我们应该能够在这里找到一个好的散列函数，所以这给了我们总共 运行 的时间 O(jackets + shirts + ties + total_output_tuples)，这是你可以多快的下限be: 你需要处理一次所有的输入序列，你需要产生输出序列。
此外，它的代码相当漂亮（恕我直言）且易于理解：
void hashJoin(vector<Outfit> &outfits) {
using shirtsize_t = decltype(Shirt::size);
std::unordered_map<shirtsize_t, vector<shared_ptr<Shirt>>> shirts_by_sizes;
using tiecolor_t = decltype(Tie::color);
std::unordered_map<tiecolor_t, vector<shared_ptr<Tie>>> ties_by_colors;
for(const auto& shirt : shirts) {
shirts_by_sizes[shirt->size].push_back(shirt);
}
for(const auto& tie : ties) {
ties_by_colors[tie->color].push_back(tie);
}
for (const auto& jacket : jackets) {
for (const auto& matching_shirt : shirts_by_sizes[jacket->size]) {
for (const auto& matching_tie : ties_by_colors[jacket->color]) {
outfits.push_back(Outfit{jacket, matching_shirt, matching_tie});
}
}
}
}
然而，在最坏的情况下，如果我们的散列没有给我们统一的散列，我们可能会遇到更糟糕的复杂性，因为 O(1) 访问会变得更糟。您需要检查哈希映射以发现这一点，并在这种情况下替换哈希函数。
实施
I've posted a working implementation of all four algorithms I discussed here on godbolt。然而，由于它们相当长，我只在这个答案中包含了（高级）散列连接算法
下界和输出元素
正如@Dominique 指出的那样，没有比 O(output_element_count) 更好的 运行 时间复杂度的方法了，因为您必须至少生成每个输出元素一次。因此，如果您期望您的结果（渐近地）接近夹克 * 衬衫 * 领带，则嵌套循环连接是开销最低的变体，因此应该是最快的。但是，我认为这里不会是这种情况。