小编Moh*_*mad的帖子

在作为特定集的子集的有限集合集中查找集合的最佳算法是什么？

例如,如果

A = {1, 2}
B = {2, 3, 4}
C = {3, 5}
D = {6}

和X = {1, 2, 3, 5}

然后,A和C是X的子集.

是否有一种算法可以在线性时间复杂度中做到这一点？

实现注意:集合的成员通常来自非常有限的范围,因此,使用C++ bitset来实现算法可能是个好主意.不是吗？

编辑:集合中的集合数通常非常大于X中的元素数(在示例中).有没有办法在X中的元素数量方面做这个线性？可能使用哈希或其他东西？

下面的代码几乎与http://docs.python.org/2/library/queue.html上的python官方Queue示例相同.

from Queue import Queue
from threading import Thread
from time import time
import sys

num_worker_threads = int(sys.argv[1])
source = xrange(10000)

def do_work(item):
    for i in xrange(100000):
        pass

def worker():
    while True:
        item = q.get()
        do_work(item)
        q.task_done()

q = Queue()

for item in source:
    q.put(item)

start = time()

for i in range(num_worker_threads):
    t = Thread(target=worker)
    t.daemon = True
    t.start()

q.join()

end = time()

print(end - start)

这些是Xeon 12核处理器的结果:

$ ./speed.py 1
12.0873839855

$ ./speed.py 2
15.9101941586

$ ./speed.py …

我在mongodb中有一个非常大的项目集合,其架构是我无法改变的.简化版本如下所示:

{event: { address: {ip: "1.1.1.1", port: 80}}}
{event: { address: {ip: "1.1.1.2", port: 80}}}
{event: { address: [{ip: "1.1.1.1", port: 80}, {ip: "1.1.1.1", port: 443}]}}
{event: { address: [{ip: "1.1.1.1", port: 8080}, {ip: "1.1.1.2", port: 443}]}}

每个事件可能有一个或多个地址.每个地址都有"ip"和"port".因此,在具有多个地址的事件中可能会重复"ip".

我想要做的就是计算每个IP地址的事件数量并找到最高IP地址.对于上面的示例,首选结果是:

[ { "ip" : "1.1.1.1", "count" : 3 },
  { "ip" : "1.1.1.2", "count" : 2 } ]

想到的一个问题是这样的:

db.collection.aggregate({$project: {ip: "$event.address.ip"}}, {$group: {_id: "$ip", count: {$sum: 1}}}, {$sort: {count: -1}}, {$limit: 5})

但结果是:

{
 "result" : [
  { "_id" : …