我有一个应用程序,我有许多集.一组可能是
{4,7,12,18}个
唯一数字,并且都小于50.
然后我有几个数据项:
1 {1,2,4,7,8,12,18,23,29}
2 {3,4,6,7,15,23,34,38}
3 {4,7 ,12,18}
4 {1,4,7,12,13,14,15,16,17,18}
5 {2,4,6,7,13,15}
数据项1,3和4与集合匹配,因为它们包含集合中的所有项目.
我需要设计一个超快速的数据结构来识别数据项是否是集合的成员包括属于集合的所有成员(因此数据项是集合的超集).我目前最好的估计表明将会少于50,000套.
我当前的实现将我的集合和数据作为无符号64位整数和存储在列表中的集合.然后检查一个数据项我遍历列表进行((set&data)== set)比较.它的工作原理和节省空间但速度很慢(O(n))而且我很乐意用一些内存来换取一些性能.有没有人对如何组织这个有更好的想法？
编辑:
非常感谢所有的答案.看起来我需要提供有关该问题的更多信息.我首先得到集合,然后逐个获取数据项.我需要检查数据项是否与其中一个集匹配.
这些集很可能是"块状的",例如对于给定的问题,1,3和9可能包含在95%的集合中; 我可以提前预测到这一点(但不是很好).
对于那些建议记忆的人:这就是memoized函数的数据结构.这些集代表已经计算过的一般解决方案,数据项是函数的新输入.通过将数据项与一般解决方案相匹配,我可以避免大量处理.
我正在为纸牌游戏编写AI,经过一些测试,我发现在我的alpha beta算法上使用MTD(f) - 一系列零窗口搜索 - 比单独使用alpha-beta更快.
MTD(f)算法在http://people.csail.mit.edu/plaat/mtdf.html中有详细描述
我遇到的问题是,对于MTD(f)搜索中的每个传递(对于每个猜测),我不重用我存储的任何先前位置,即使链接上的写入表明我应该(事实上清除)迭代之间的表加速了算法).
我的问题是,当我在转置表中存储一个位置和一个值时,我还存储了它有效的alpha和beta值.因此,第二次通过树以不同的猜测(因此alpha和beta)不可能重复使用任何信息.这是预期的,还是我错过了一些基本的东西？
例如,如果对于alpha = 3 beta = 4,我们得到7的结果(显然是截止)我应该将其存储在表格中,因为alpha = 3到beta = 6有效吗？或beta = 7？
是否有任何库或自动方式从任意结构中生成C#中的GUI？
例如,如果我有一个类层次结构,我可以通过添加类似[XmlAttribute("depth")]or的属性[XmlElement("node")]并将其传递给XML序列化程序来用XML 表示它.我可以使用不同的注释然后将其发送到某个GUI构造类来构建表单吗？
作为使用BlueJ for java的人的另一个例子,它提供了对gui环境中的类及其成员的访问(尽管它可以访问源代码).
在昨晚观看橄榄球的时候,我想知道是否有任何分数是不可能的,因为你只能得到3,5或7分的分数.不用花很长时间就可以得到任何大于4的数字.5 = 5,6 = 3 + 3,7 = 7,8 = 3 + 5,9 = 3 + 3 + 3,10 = 5 + 5,依此类推.
将该想法扩展为5,7和9会产生以下可能的分数:
5,7,9,10,12,14 // and now all numbers are possible.
对于7,9和11:
7,9,11,14,16,18,20,22,23,25,27 // all possible from here
我在脑海中做了这些,任何人都可以提出一个好的算法来确定最低分数,高于该分数,在给定一组分数的情况下,所有分数都可以达到.
我这样建模:
forall a < 10:
forall b < 10:
forall c < 10:
list.add(3a + 5b + 7c);
list.sort_smallest_first();
然后检查列表中是否有超过3的序列(可能的最小分数).对于除了琐碎案件之外的任何事情,似乎都是不切实际和缓慢的.
我在减少特定视图的查询数量方面遇到了麻烦.这是一个相当沉重的,但我相信它可以减少:
Profile:
name = CharField()
Officers:
club= ManyToManyField(Club, related_name='officers')
title= CharField()
Club:
name = CharField()
members = ManyToManyField(Profile)
Election:
club = ForeignKey(Club)
elected = ForeignKey(Profile)
title= CharField()
when = DateTimeField()
俱乐部有会员和官员(总裁,比赛总监).人们可以是多个俱乐部等的成员......官员在选举中当选,其结果被存储.
鉴于一名球员,我怎样才能找到每个球员俱乐部最近当选的官员？
目前我有
clubs = Club.objects.filter(members=me).prefetch_related('officers')
for c in clubs:
officers = c.officers.all()
most_recent = Elections.objects.filter(club=c).filter(elected__in=officers).order_by('-when')[:1].get()
print(c.name + ' elected ' + most_recent.name + ' most recently')
问题是循环查询,如果你是1个俱乐部的成员,那么它很好而且速度很快,但是如果你加入50个数据库我的数据库就会爬行.
编辑: Nil的回答做我想要的但没有得到对象.我真的不需要这个对象,但我确实需要另一个字段以及日期时间.如果查询有用:
Club.objects.annotate(last_election=Max('election__when'))
生成原始SQL
SELECT "organisation_club"."id", "organisation_club"."name", MAX("organisation_election"."when") AS "last_election"
FROM "organisation_club"
LEFT OUTER JOIN "organisation_election" ON ( "organisation_club"."id" = "organisation_election"."club_id" ) …在尝试在Windows下编译jinc并快速运行数百个编译器错误之后,我正在寻找一个可以为windows构建的高质量BDD库.最好是C或C++,但只要我能绑定它,我很高兴.