首页 手机软件 手机游戏 单机游戏 资讯文章 专题下载 游戏合集 文章合集 php下载 php教程 电脑软件
+ -
当前位置：首页 → 问答吧 → 讨论一个点名的算法问题

讨论一个点名的算法问题

时间：2010-07-02

来源：互联网

本帖最后由 群雄逐鹿中原 于 2010-07-02 13:35 编辑

在N个人中间点名，找到最近、最频繁被点名的10个人。

现在用这个方式决定最近+最频繁：
每次点名，有一个序列号加1，  no++
每个人保留最近两次点名时的序列号：N2（次近）   N1（最近），
    两次序列号的间隔越小，说明被点名的越频繁。

所以通过N1 - N2 的值排序，就找到最频繁的前10个人。

------------------------------------------------------------------------

问题在这里，还有最近的要求，
如果当前点名总序列号为 no=100, 某个人的 N2=3, N1 = 10,
那么显然有100 - 10次没点到他了。所以他的 N1 - N2 = 7这个频繁程度的值，参考性就不大了。

所以最后需要按照  max(N1 - N2,  no - N1) 的值排序，找出“最近+最频繁”。

因为每点名一次，no的值都加1。所以每个人的排序的参考值，没次点名都可能变化。用什么数据结构能满足这个要求？

作者: 群雄逐鹿中原   发布时间: 2010-07-02

hash?

作者: prolj   发布时间: 2010-07-02

排2次序不就可以了么

作者: hellioncu   发布时间: 2010-07-02

LRU最近最少使用页面置换算法

作者: 没本   发布时间: 2010-07-02

就用数组或者vector不就行了，取人时排序得结果副本，取前十个。复杂的数据结构没必要。

作者: 没本   发布时间: 2010-07-02

我觉得没必要使用非常精确的LRU，使用一种大概来模拟LRU就可以了：
1，只要一条链表和每个人保有的一个count记数就行了。count用来模拟频率（count>=0），每个人按频率count大小从高到低串成一条链表。
2，当其中一人被点名时，它的count++，而其余的count--，然后只要将这个人在链表中做一次插入排序就行了。

如下某一时刻的链表：括号内为频率count
a(9) -> b(6) -> c(3) -> d(1) -> e(0)

如果此时d被点名，重新排序后：
a(8) -> b(5) -> d(2) -> c(2) -> e(0)

作者: maxxfire   发布时间: 2010-07-02

回复 maxxfire


    这种方法结构和实现较简单，不过需要遍历整个链表。。

作者: maxxfire   发布时间: 2010-07-02

最近好确定，最频繁是怎么确定的？被点次数多？

作者: windfail   发布时间: 2010-07-02

本帖最后由 狗气球 于 2010-07-02 15:18 编辑

楼主没有给出最近的定义。

就是说优先级到底怎么算。

作者: 狗气球   发布时间: 2010-07-02

最近最頻繁，也真不知道怎么定义，
其实就是没本讲的页面置换问题，为了最大限度的减少置换次数，想到了最近最频繁这个模型。

作者: 群雄逐鹿中原   发布时间: 2010-07-02

6楼的办法不行的，反应太迟钝。如果先点名小王1000次，像小王这样被点到的有10个人，最后再连续点名小李999次，
小李还是不会被选择为活跃分子。

作者: 群雄逐鹿中原   发布时间: 2010-07-02



QUOTE:
6楼的办法不行的，反应太迟钝。如果先点名小王1000次，像小王这样被点到的有10个人，最后再连续点名小李999 ...
群雄逐鹿中原 发表于 2010-07-02 15:51


小李是最近点到的，小王是最频繁占到的，你要的是哪个？

作者: windfail   发布时间: 2010-07-02



QUOTE:
小李是最近点到的，小王是最频繁占到的，你要的是哪个？
windfail 发表于 2010-07-02 16:10



每此被点到名的，都要装进麻袋里。最多有10个麻袋，麻袋不够时，就解放一个旧人出来。
我要装麻袋次数最少的方案。
所以不是最近的，也不是最频繁的。

作者: 群雄逐鹿中原   发布时间: 2010-07-02



QUOTE:
每此被点到名的，都要装进麻袋里。最多有10个麻袋，麻袋不够时，就解放一个旧人出来。
我要装麻袋次数 ...
群雄逐鹿中原 发表于 2010-07-02 16:13



哦，那没本的那个应该是最好的了

作者: windfail   发布时间: 2010-07-02

回复 群雄逐鹿中原
拿事实证明，数组比双向链表快得不是一点半点的。没有绝对的必要，我从来不用链表。
12 : 7349
  1. $ cat nc.cpp
  2. #if defined(_V_)
  3. #include <vector>
  4. #else
  5. #include <list>
  6. #endif
  7. #include <algorithm>
  8. #include <cstdlib>
  9. #include <cstdio>
  10. using namespace std;

  12. #define MAX(a,b) ((a)>(b))?(a):(b);
  13. struct item_t
  14. {
  15.         item_t():no(0),val(0){N[0]=N[1]=0;}
  16.         int     id;
  17.         int     no;
  18.         int     N[2];
  19.         int     val;
  20. };

  22. #if defined(_V_)
  23. typedef vector<item_t> ii_t;
  24. #else
  25. typedef list<item_t> ii_t;
  26. #endif

  28. bool sfun( const item_t & v1, const item_t & v2 )
  29. {
  30.         return v1.val > v2.val;
  31. }

  33. int main(int argc, char ** argv)
  34. {
  35.         if( argc<3 )
  36.         {
  37.                 printf("Usage: ./nc 人数 点名次数\n");
  38.                 return -1;
  39.         }
  40.         const int N = atoi(argv[1]);
  41.         const int No = atoi(argv[2]);
  42.         int i=0;
  43.         ii_t ii(N);
  44.         for( ii_t::iterator iii=ii.begin(), iie=ii.end(); iii!=iie; ++iii )
  45.                 iii->id = i++;
  46.         srandom(10); //每次用相同的种子
  47.         //点名
  48.         for( int no=0; no<No; ++no )
  49.         {
  50.                 int iN = random() % N;
  51. #if defined(_V_)
  52.                 item_t & it = ii[iN];
  53.                 it.no++;
  54.                 it.N[1] = it.N[0], it.N[0] = no;
  55. #else
  56.                 ii_t::iterator iins=ii.end(), idel=ii.end();
  57.                 for( ii_t::iterator iii=ii.begin(), iie=ii.end();
  58.                                 iii!=iie; ++iii )
  59.                 {
  60.                         item_t & it = *iii;
  61.                         if( it.id==iN )
  62.                         {
  63.                                 idel = iii;
  64.                                 it.no++;
  65.                                 it.N[1] = it.N[0], it.N[0] = no;
  66.                                 it.val = it.N[0] - it.N[1];
  67.                         }
  68.                         else
  69.                         {
  70.                                 it.val = MAX( it.N[0]-it.N[1], no-it.N[0] );
  71.                                 if( idel!=ii.end() && iins==ii.end()
  72.                                                 && it.val<idel->val )
  73.                                         iins = iii;
  74.                         }
  75.                 }
  76.                 ii.insert(iins, *idel);
  77.                 ii.erase(idel);
  78. #endif
  79.         }
  80. #if defined(_V_)
  81.         //计算值
  82.         for( ii_t::iterator iii=ii.begin(), iie=ii.end(); iii!=iie; ++iii )
  83.                 iii->val = MAX( iii->N[0]-iii->N[1], No-iii->N[0] );
  84.         //排序
  85.         sort(ii.begin(), ii.end(), sfun);
  86. #endif
  87.         //输出前十个
  88.         int c10=0;
  89.         for( ii_t::reverse_iterator iii=ii.rbegin(), iie=ii.rend();
  90.                         iii!=iie && c10<10; ++iii, ++c10 )
  91.         {
  92.                 printf( "[id:%d-no:%d-N1:%d-N2:%d-val:%d]\n",
  93.                         iii->id, iii->no, iii->N[0], iii->N[1], iii->val );
  94.         }
  95.         return 0;
  96. }

  98. $ g++ nc.cpp -o ncv -D_V_
  99. $ g++ nc.cpp -o nc
  100. $ time ./ncv 2000 100000
  101. [id:1720-no:46-N1:99990-N2:99976-val:14]
  102. [id:1581-no:50-N1:99962-N2:99911-val:51]
  103. [id:1302-no:52-N1:99993-N2:99930-val:63]
  104. [id:1741-no:52-N1:99954-N2:99878-val:76]
  105. [id:1188-no:40-N1:99903-N2:99877-val:97]
  106. [id:470-no:58-N1:99886-N2:99772-val:114]
  107. [id:116-no:65-N1:99881-N2:99764-val:119]
  108. [id:835-no:61-N1:99912-N2:99780-val:132]
  109. [id:1994-no:48-N1:99894-N2:99754-val:140]
  110. [id:274-no:46-N1:99849-N2:99795-val:151]

  112. real    0m0.012s
  113. user    0m0.008s
  114. sys     0m0.003s
  115. $ time ./nc 2000 100000
  116. [id:1720-no:46-N1:99990-N2:99976-val:14]
  117. [id:1581-no:50-N1:99962-N2:99911-val:51]
  118. [id:1302-no:52-N1:99993-N2:99930-val:63]
  119. [id:1188-no:40-N1:99903-N2:99877-val:96]
  120. [id:1741-no:52-N1:99954-N2:99878-val:76]
  121. [id:274-no:46-N1:99849-N2:99795-val:150]
  122. [id:1872-no:52-N1:99802-N2:99745-val:197]
  123. [id:470-no:58-N1:99886-N2:99772-val:114]
  124. [id:116-no:65-N1:99881-N2:99764-val:118]
  125. [id:835-no:61-N1:99912-N2:99780-val:132]

  127. real    0m7.349s
  128. user    0m7.341s
  129. sys     0m0.007s
  130. $
复制代码

作者: 没本   发布时间: 2010-07-02

回复 没本


    汗， 我对链表相当的偏爱。。

作者: peidright   发布时间: 2010-07-02

回复 peidright


    那说明你该改改认识了。

作者: 没本   发布时间: 2010-07-02

回复 peidright


    我最喜欢用散列，其次是数组，都是相当稳定不容易出错的。

作者: 没本   发布时间: 2010-07-02

回复 没本

, 脸表比数组满很多，这个我再仔细考察下，。。看c++代码，头昏。

弱弱问下，散列是什么?.. hashtable 么？

作者: peidright   发布时间: 2010-07-02

内层循环的
if( idel!=ii.end() && iins==ii.end()
改成
if( idel!=iie && iins==iie
能减少2.5秒时间。

作者: 没本   发布时间: 2010-07-02

散列也音译成哈希表。

作者: 没本   发布时间: 2010-07-02

链表的优势在于随机插入，数组优势在于随机访问
要排序什么的用数组当然比链表快

作者: windfail   发布时间: 2010-07-02

我想的比较迂腐，在考虑能不能用几个std::map构造出自适应排序的办法来。还没想好。

话说回来，可能还是没本直接排序的办法好，一万个数之内，std::map算上本身的开销，未必比vector好多少。

作者: 群雄逐鹿中原   发布时间: 2010-07-02

忘了一点，会随时有新人加入这个游戏的，新人会比较怕vector

作者: 群雄逐鹿中原   发布时间: 2010-07-02

用std::map肯定做不到，你得自己实现一个红-黑树，插入计算和做旋转需要要括大范围，修改值。

作者: 没本   发布时间: 2010-07-02



QUOTE:
忘了一点，会随时有新人加入这个游戏的，新人会比较怕vector
群雄逐鹿中原 发表于 2010-07-02 17:05




    随时有新人加入没有问题，直接vector::push_back，再赋值一下id字段就行了，不影响最后的排序结果。

作者: 没本   发布时间: 2010-07-03

相关阅读 更多

热门阅读

热门下载

更多
关于本站 免责申明 联系我们

Copyright 2006-2020 php爱好者(phpfans.net) All Rights Reserved.备案号：湘ICP备2023016114号-2

本站为非盈利性网站，不接受任何广告。本站所有资源均由网友上传，如有侵权，请发邮件至 [email protected] phpfans.net