首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

算微薄用户中有N个相同个人标签的算法

2012-02-09 
求一个算微薄用户中有N个相同个人标签的算法大家都玩过微薄吧?假设有10000个微薄用户。每个微薄用户设置了1

求一个算微薄用户中有N个相同个人标签的算法
大家都玩过微薄吧?
假设有10000个微薄用户。每个微薄用户设置了10个左右的个性标签。 这1w个用户设置的标签形成的标签库里面一共有2000个标签。

现在要算出有N(N>1 )个标签相同的用户。将有N个标签相同的用户分一个组。

小弟想了一个笨办法,但是计算次数太多了,求高手给算法。

[解决办法]
说实话,你的数据量太小了,这样小的数据量可以这样做:

在内存里建一个大数组,2000*10000 也就是20M字节。以用户ID为列标,标签ID为行标,存储用户和标签的对应关系,有关系为1,没关系为0。然后执行数据表排序操作,使得数组左上角的1尽量密集。

在这个数组中用笨办法找吧,找起来很快的。现在的计算机内存动则数G,你的数据量规模就算扩大100倍也依然能用这个方法。
[解决办法]
抱歉,楼上的跟贴中有错误,请斑竹删除,这里重发一次。

想了一个算法,还没有具体计算复杂度,但是觉得会比那个所有组合都罗列出来的方法要快。
先设一个集合类:
Class SharePictureSet
{
Vector<bool> PictureStatus; //size = 2000 照片数
Vector<person> Persons;
Static const int NumberOfShared = N; //共享照片数
}

这个类的第一个成员PictureStatus用来存储拥有的照片,照片编号对应数组索引,此照片存在则此索引对应的数组值为1,否则为0,第二个成员Persons用来代表这个共享照片的集合中有多少人,NumberOfShared指共享照片数 N。

开始的时候,有1w个人,我们生成1w个SharePictureSet对象,每个对象的Persons中只有一个人,PictureStatus 用来存储这个人所拥有的照片,如果我们对照片编号,假设这个人有3号和5号照片,那么PictureStatus[3]=1, PictureStatus[5]=1, 数组中其他值等于0。

1,现在对这 1w 个SharePictureSet对象(第一层对象)进行两两计算,设两个对象s1,s2 。
对s1, s2 中PictureStatus进行布尔运算 (bitwise &),运算结果即为共同照片,如果他们的共同照片数 >= N,那么就生成一个新的SharePictureSet对象,新对象的PictureStatus就是布尔(&)运算的结果,Persons 则合并存储s1,s2中两个人。

2,对新生成的SharePictureSet对象(第二层)再次进行两两计算,方法如上,生成第三层SharePictureSet对象,但有所不同的是,从第二层对象开始,两两计算(设k1,k2)如果生成新的对象,那么就要销毁这两个旧的对象k1,k2,而且,新对象中的Persons 不但要合并存储k1,k2中所有的人,而且人员要唯一,如果k1,k2中有相同的人,结果算作一个人存入新的集合。在新对象中,如果某个对象的Persons是另一个对象Persons的子集,这个Persons是子集的对象要销毁。
如此反复,直到某层SharePictureSet对象两两 之间再也无法生成新的对象,也就是两两 之间 没有大于等于N个照片共享。

3,把从第二层开始产生的所有SharePictureSet对象都放到一起,因为从第二层开始,两两计算中已经删除了旧的对象,所以不用再检查对象间是否存在相互包含与重复。

热点排行