浏览 2099 次
锁定老帖子 主题:Picece選擇算法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2008-02-04
from random import randrange, shuffle, choice class PiecePicker(object): def __init__(self, numpieces, config): self.config = config # config 的 list, dict 嵌套结构 self.numpieces = numpieces #片数? self.interests = [range(numpieces)] #interest是一个list,表示第i位的piece收到i个have,例如[[0,3],1,2]表示0和3两片没收到have,1的片收到一个have,2的片收到2个have,初始化为 [[0,1,2,3...piecenum]] self.pos_in_interests = range(numpieces) #第 i 位的数字表示片段 i 是 interest 数组中的相应的list中的位置。 通过这种方式在list中表示顺序。 self.numinterests = [0] * numpieces #list第i位收到have的个数. 例如:[2,3,5,2] 表示第0,1,2,3片分别有2,3,5,2个have , 初始化应该为[0,0,0,0...] self.have = [False] * numpieces #每一片的自身下载情况, 初始是 [false,false,false.......] self.crosscount = [numpieces] self.started = [] self.seedstarted = [] self.numgot = 0 #我收到的piece个数 self.scrambled = range(numpieces) shuffle(self.scrambled) def got_have(self, piece): numint = self.numinterests[piece] #已经有几个have了? self.crosscount[numint + self.have[piece]] -= 1 self.numinterests[piece] += 1 try: self.crosscount[numint + 1 + self.have[piece]] += 1 except IndexError: self.crosscount.append(1) if self.have[piece]: return if numint == len(self.interests) - 1: self.interests.append([]) self._shift_over(piece, self.interests[numint], self.interests[numint + 1]) def lost_have(self, piece): numint = self.numinterests[piece] self.crosscount[numint + self.have[piece]] -= 1 self.numinterests[piece] -= 1 self.crosscount[numint - 1 + self.have[piece]] += 1 if self.have[piece]: return self._shift_over(piece, self.interests[numint], self.interests[numint - 1]) def _shift_over(self, piece, l1, l2): #调整3个数组参数 p = self.pos_in_interests[piece] l1[p] = l1[-1] self.pos_in_interests[l1[-1]] = p del l1[-1] newp = randrange(len(l2) + 1) if newp == len(l2): self.pos_in_interests[piece] = len(l2) l2.append(piece) else: old = l2[newp] self.pos_in_interests[old] = len(l2) l2.append(old) l2[newp] = piece self.pos_in_interests[piece] = newp def requested(self, piece, seed = False): #request某个片段 if piece not in self.started: self.started.append(piece) if seed and piece not in self.seedstarted: self.seedstarted.append(piece) def complete(self, piece): #完成了某个片段 assert not self.have[piece] self.have[piece] = True #改have self.crosscount[self.numinterests[piece]] -= 1 # numinterest[piece] 是 piece 有 have 的个数 try: self.crosscount[self.numinterests[piece] + 1] += 1 except IndexError: self.crosscount.append(1) self.numgot += 1 l = self.interests[self.numinterests[piece]] # 跟 piece 有一样 have 的片的 list p = self.pos_in_interests[piece] # piece 在 同样 have 的 list 中的次序 l[p] = l[-1] #l[p] 就是 piece , l[-1] 为最后一个 self.pos_in_interests[l[-1]] = p # 把 p 交换到l 的最后一位, 在 pos_in_interest 中交换 del l[-1] #以上的几行的作用综合起来就是:完成了某个片段之后,把该 piece 在 pos_in_interest 中把它移动到最后一位 #但是,已经 download 完成的 piece , 为什么不在 interest 中把它删掉? try: self.started.remove(piece) self.seedstarted.remove(piece) except ValueError: pass def next(self, havefunc, seed = False): # 关键的方法, 如何选择下一个下载的piece bests = None bestnum = 2 ** 30 # 上限? if seed: s = self.seedstarted else: s = self.started for i in s: if havefunc(i): #i 片有 have if self.numinterests[i] < bestnum: bests = [i] bestnum = self.numinterests[i] elif self.numinterests[i] == bestnum: bests.append(i) if bests: # 如果不为空 return choice(bests) # choice 方法从 list中随机选择一个返回。 if self.numgot < self.config['rarest_first_cutoff']: #rareest_first_cutoff 默认为1 , 如果一个片也没有got, 就random_first for i in self.scrambled: if havefunc(i): return i return None for i in xrange(1, min(bestnum, len(self.interests))): #xrange 这个方法比较奇妙,会返回一个xrange型的对象 #a = xrange(0,100) print type(a) print a print a[0], a[1] 会输出 <type 'xrange'> xrange(100) 0 1 # 对 interest 从1 开始遍历:为什么是1? 0的不能选,因为没有have, 从1遍历,找到就跳出 #这样可以保证rarest first,因为这里的i代表着有have的个数,从最少开始找自然的就能满足这条规则。 for j in self.interests[i]: if havefunc(j): return j return None # 这些手段都找不到最终需要的piece,返回空 def am_I_complete(self): return self.numgot == self.numpieces def bump(self, piece): l = self.interests[self.numinterests[piece]] # 跟 piece 有一样 have 的片的 list pos = self.pos_in_interests[piece] # piece 在 同样 have 的 list 中的次序 del l[pos] l.append(piece) for i in range(pos,len(l)): self.pos_in_interests[l[i]] = i # 修正pos try: self.started.remove(piece) self.seedstarted.remove(piece) except ValueError: pass 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |