我正在将一些C++代码移植到Python,其中一个数据结构是一个多重集,但我不确定如何在Python中对此进行建模.
让我们ms成为C++multiset<int>
如何ms使用(发布一些例子)
multiset<int>::iterator it = ms.find(x)
ms.erase(it)
ms.insert(x)
ms.end()
ms.lower_bound(x)
ms.clear()
见下文,为什么+=在我原来的柜台上吹掉一把钥匙？
>>> c = Counter({'a': 0, 'b': 0, 'c': 0})
>>> c.items()
[('a', 0), ('c', 0), ('b', 0)]
>>> c += Counter('abba')
>>> c.items()
[('a', 2), ('b', 2)]
我认为至少可以说这是不礼貌的,"X被统计0次"和"我们甚至不算Xs"之间存在很大差异.它似乎collections.Counter根本不是一个反击,它更像是一个多重集.
但是计数器是dict的子类,我们允许用零值或负值构造它们:Counter(a=0, b=-1).如果它实际上是"一包东西",这不会被禁止,限制init接受可迭代的可迭代物品吗？
进一步混淆事项,对与操作员有不同行为的反制具update和subtract方法.看来这堂课正在发生身份危机!+-
反击是一个字典还是一个包？
在相应的多集包含元素的类型对象上应用next()和prev()函数的时间复杂度是多少？multiset<int>::iteratorN
据我所知,在STL中,多集合被实现为一个平衡的二进制搜索树,因此我希望每次操作时的复杂度为O(log N)(在最坏的情况下),以防我们遍历树直到找到合适的价值,但我有预感,这应该是平均O(1).
但是,如果树实现如下 - 当x在平衡二叉搜索树中插入元素时,我们还可以检索树中小于x的最大数字,并且树中的最小数字大于xO(log N).因此在理论上,我们可以让树中的每个节点都保持指向它next和prev元素的指针next(),prev()然后在每个查询的恒定时间内运行.
什么人可以分享一些关于什么的光？
我所需要的只是知道某些东西是否存在以及它存在多少次.我将迭代现有的东西并查询其中存在多少.
到目前为止我的实现使用multiset,我做如下:
std::multiset<thing> a;
auto previous = a.end();
for( auto each = a.begin(); each != a.end(); ++each ) {
if( previous == a.end() || *previous != *each ) {
a.count(*each);
}
previous = each;
}
我有一个things 的向量.但是他们有时会重复这个价值,我想要迭代唯一的 things并为每个独特的事做点什么.这个"东西"需要知道它thing在矢量上出现的时间量.
我上面发布的代码就是我现在如何解决我的问题,它似乎并不是我想要的最优雅的方式.
我只是遵循Stackoverflow准则:我告诉我的问题是什么,我告诉我(尝试过)的解决方案.
如果确实需要带有问号的句子,那么你可以去:有没有办法迭代一个独特的元素multiset？
如何创建所有K-组合,带重复一组给定(也称为K-multicombinations或multisubsets使用MATLAB)？
这类似于笛卡尔积,但两行只有它们的排序不同应该被认为是相同的(例如,矢量[1,1,2]=~=[1,2,1]被认为是相同的),因此生成笛卡尔积然后应用unique(sort(cartesianProduct,2),'rows')应该产生相同的结果.
示例:
调用nmultichoosek(1:n,k)应生成以下矩阵:
nmultichoosek(1:3,3)
ans =
1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3
我尝试用std :: priority_queue替换std :: multiset。但是我对速度结果感到失望。该算法的运行时间增加了50％...
以下是相应的命令：
top() = begin();
pop() = erase(knn.begin());
push() = insert();
我对priority_queue实现的速度感到惊讶，我预期会有不同的结果（对于PQ更好）...从概念上讲，多集被用作优先级队列。为什么优先级队列和多重集即使在情况下也具有如此不同的性能-O2？
十个结果的平均值，MSVS 2010，Win XP，32位，方法findAllKNN2（）（请参见下面的内容）
MS
N time [s]
100 000 0.5
1 000 000 8
PQ
N time [s]
100 000 0.8
1 000 000 12
什么会导致这些结果？尚未对源代码进行其他更改...感谢您的帮助...
MS实施：
template <typename Point>
struct TKDNodePriority
{
KDNode <Point> *node;
typename Point::Type priority;
TKDNodePriority() : node ( NULL ), priority ( 0 ) {}
TKDNodePriority ( KDNode <Point> *node_, typename Point::Type priority_ ) : node ( …我正在比较STL(g ++)priority_queue的性能,发现push和pop没有我想象的那么快.请参阅以下代码:
#include <set>
#include <queue>
using namespace std;
typedef multiset<int> IntSet;
void testMap()
{
srand( 0 );
IntSet iSet;
for ( size_t i = 0; i < 1000; ++i )
{
iSet.insert(rand());
}
for ( size_t i = 0; i < 100000; ++i )
{
int v = *(iSet.begin());
iSet.erase( iSet.begin() );
v = rand();
iSet.insert(v);
}
}
typedef priority_queue<int> IntQueue;
void testPriorityQueue()
{
srand(0);
IntQueue q;
for ( size_t i = 0; i < 1000; ++i )
{ …考虑以下比较功能:
bool compare(std::shared_ptr<myObject> &lhs, std::shared_ptr<myObject> &rhs){
return lhs->value < rhs->value;
}
现在的想法是初始化一个多重类型std::shared_ptr<myObject>,它对具有上述功能的元素进行排序.所以从我读过的书应该这样做:
std::multiset<std::shared_ptr<myObject>, decltype(compare)*> myset{compare};
题:
我的问题是,在声明中,我将传递一个函数指针来引用比较函数,但为什么我们使用{compare}来启动集合？它的重要性是什么？为什么有必要这样做？
这是一个后续问题，询问 如何在不重载operator（），std :: less，std :: greater的情况下为std :: multiset提供自定义比较器？
并且我试图通过以下方式解决。
可以向类的成员提供自定义比较lambda函数（自c ++ 11以来），std::multiset如下所示：
#include <iostream>
#include <set>
const auto compare = [](int lhs, int rhs) noexcept { return lhs > rhs; };
struct Test
{
std::multiset<int, decltype(compare)> _set{compare};
Test() = default;
};
很简单。
Test班上的成员是
std::map<std::string, std::multiset<int, /* custom compare */>> scripts{};
我尝试使用std::multisetwith自定义
Compare（案例-1）std::greater<> （案例-2）前两个选项是成功的。但是，lambda作为自定义比较功能的情况却无法正常工作。这是MCVC：https ://godbolt.org/z/mSHi1p
#include <iostream>
#include <functional>
#include <string>
#include <map>
#include <set>
const …