我有一个N 64位整数列表,其位代表小集.每个整数最多有k位设置为1.给定位掩码,我想找到列表中与掩码匹配的第一个元素,即element & mask == element.
例:
如果我的列表是:
index abcdef
0 001100
1 001010
2 001000
3 000100
4 000010
5 000001
6 010000
7 100000
8 000000
而我的掩码是111000,与掩码匹配的第一个元素是索引2.
方法1:
线性搜索整个列表.这需要O(N)时间和O(1)空间.
方法2:
预先计算所有可能掩码的树,并在每个节点保留该掩码的答案.这需要O(1)时间进行查询,但需要O(2 ^ 64)空间.
题:
如何在比O(N)更快的时间内找到与掩模匹配的第一个元素,同时仍然使用合理的空间量？我可以在预计算中花费多项式时间,因为会有很多查询.关键是k很小.在我的应用程序中,k <= 5且N为数千.面具有很多1; 你可以假设它是从64位整数的空间中均匀绘制的.
更新:
这是一个示例数据集和一个在Linux上运行的简单基准程序:http://up.thirld.com/binmask.tar.gz.对于large.in,N = 3779且k = 3.第一行是N,后跟N个无符号的64位整数,表示元素.编译make.运行./benchmark.e >large.out以创建真正的输出,然后您可以对其进行区分.(掩码是随机生成的,但随机种子是固定的.)然后find_first() …
所以这是问题所在:
鉴于input = [100 80 66 25 4 2 1],我需要找到最好的组合给我50.
看看这个,最好的是25 + 25 = 50,所以我需要数组中的2个元素.
其他组合包括25+4+4+4+4+4+4+1和25+4+4+4+4+4+2+2+1...等
我需要找到所有可能性,这些可能性为我提供了我想要的价值.
编辑:以及最好的可能性(一个条款数量最少)
这是我到目前为止所做的:首先构建一个新的数组(简单的for循环遍历所有元素并存储在一个新的temp数组中),检查高于我的数组的所有元素(所以对于输入50,元素100, 80,66更高,所以丢弃它们然后我的新阵列是[25 4 2 1]).然后,由此,我需要检查组合.
我做的第一件事是一个简单的if语句检查是否有任何数组元素与我想要的数字完全匹配.所以,如果我想要50,我会检查阵列中是否有50,如果没有,我需要找到组合.
我的问题是,我不完全确定如何找到每一个组合.我一直在努力尝试提出一段时间的算法,但我总是最终陷入困境.
任何帮助/提示将不胜感激.
PS - 我们可以假设数组总是按照从LARGEST到SMALLEST值的顺序排序.