我得到N个C布尔阵列.我想将这些组织成一个数据结构,允许我尽可能快地执行以下操作:给定一个新数组,如果此数组是任何存储数组的"超集",则返回true.对于超集,我的意思是:如果A [i]对于B [i]为真的每个i都为真,则A是B的超集.如果B [i]为假,那么A [i]可以是任何东西.
或者,就集合而不是数组而言:
将N个集合(每个都有C个可能的元素)存储到数据结构中,这样您就可以快速查找给定集合是否是任何存储集合的超集.
构建数据结构可能需要尽可能长的时间,但查找应该尽可能高效,并且数据结构不能占用太多空间.
我认为这本身就是一个有趣的问题,但对于我真正想要解决的问题,你可以假设如下:
对于O(NC)查找:只需迭代所有数组.但这太慢了.
对于O(C)查找:我在这里有一个很长的描述,但正如Amit在评论中指出的那样,它基本上是一个BDD.虽然这具有很高的查找速度,但它具有指数数量的节点.N和C如此之大,这需要太多空间.
我希望在这个O(N*C)和O(C)解决方案之间,可能有一个不需要指数空间的O(log(N)*C)解决方案.
对于O(sqrt(N)C)查找:将数组存储为前缀trie.查找数组A时,如果A [i] = 0,则转到相应的子树,但如果A [i] = 1 ,则访问两个子树.
我的直觉告诉我,如果你假设存储的数组是随机的,那么这应该使查找O(sqrt(N)C)的(平均)复杂度.但是:1.他们不是,阵列稀疏.2.这只是直觉,我无法证明.
我将尝试这个新想法和BDD方法,看看哪两个最好.
但与此同时,这个问题不会经常发生吗？它没有名字吗？还没有以前的研究吗？我真的觉得我在这里重新发明轮子.
algorithm complexity-theory set time-complexity data-structures
我的大多数类都有调试变量,这使它们看起来像这样:
class A
{
// stuff
#ifndef NDEBUG
int check = 0;
#endif
};
和方法可能如下所示:
for (/* big loop */) {
// code
#ifndef NDEBUG
check += x;
#endif
}
assert(check == 100);
几乎没有比#ifndef NDEBUG所有的东西更丑陋.不幸的是,我知道没有编译器可以在没有这些#ifndefs的情况下优化check变量(我不知道是否允许这样做).
所以我试图提出一个让我的生活更轻松的解决方案.以下是它现在的样子:
#ifndef NDEBUG
#define DEBUG_VAR(T) T
#else
template <typename T>
struct nullclass {
inline void operator+=(const T&) const {}
inline const nullclass<T>& operator+(const T&) const { return *this; }
// more no-op operators...
};
#define DEBUG_VAR(T) nullclass<T>
#endif
因此在调试模式下,DEBUG_VAR(T)只生成T.否则它只生成一个"null类",只有no-ops.我的代码看起来像这样:
class A {
// …假设我有一个存储前10个素数的数组,如下所示:
const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
只要我有1个.cpp文件,这一切都非常简单和简单.但是,如果我有多个.cpp文件,我真的不知道在哪里放这个数组.
一个明显的解决方案是:
// primes.h:
extern const int primes[10];
// primes.cpp:
extern const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
但是,问题是primes数组不再是编译时常量.假设x.cpp想要进行一些涉及素数[k]的繁重计算,使用ka编译时间常数,它必须进行实际的内存查找.我不喜欢那样.
那么我在哪里放置这个数组:
这个怎么样？
inline int prime(int i) {
static const int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
return primes[i];
}
PS:即使上面的"明显的解决方案"花了我相当长的时间来写.显然const变量默认有内部链接,所以我不得不在primes.cpp文件中添加"extern"以使其工作.