技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 计数和排序

计数和排序

浏览:1865次  出处信息

    以前看过一篇关于程序上的小技巧的文章,作者给出了正确的(或者至少可以称得上标准的)的解决方法,结尾他对这种技巧并不满意,认为是迫不得已才用的,等以后计算机发展了,可以使用“真实”的结果。我的想法和他截然相反,在我看来计算能力永远也追不上实际需求,我们会在越来越多的地方使用各种“有损优化”。这个词是我现想起来的,其实很多技巧都像 JPEG 标准一样,无伤大雅的丢弃了那些难以察觉的细节。

    任何列表类的东西(比方说站内消息、评论、论坛话题),最需要加缓存的地方有两个,首要的是列表的第一页,其次就是整个分类的计数(count(*) 之类,同时别跟我较真 InnoDB 下应该怎么写,下同)。顺便再说句,我对评论缓存了第一页后命中率高达 97%+,这是必须优化的地方。

    计数的基本作用仅仅是计算页码,但毕竟每页都需要显示。每次计数有变化就应该在 memcache (increment 方法)里和 mysql 字段(UPDATE += 1)里都存,当然,这都不可靠,还要在后台跑个计划任务来修正(毕竟某些耗资源的功能确实需要,例如删除某 spammer 在各论坛版块留下的很多垃圾贴,这时计数没必要立刻修正)。

    但让我奇怪的是很少有网站做排序上的优化:例如每页 10 条评论(假设是评论,而论坛的排序跟它相反),有 300 条,分成 30 页,那么在列第 20 页的时候不应该是 ORDER BY id DESC LIMIT 200, 10 而是 ORDER BY id ASC LIMIT 90, 10 。

    这个方式的好处不仅仅是在排很深的页时的消耗减半,计数和排序的两种优化配合,能适应更多复杂的情况:

    首先,计数被缓存,释放了压力,但不再精确,这会导致页数不准,实际有 30 页的时候,可能被记成了 32 页或者 28 页,显示效果可能就是最后多出两页空白页,或者少了两页(如果是论坛回贴,少两页最新的回复可是大问题)。而反向 ORDER BY 会把这种错误从尾部挪到的中间的页码,可能是一个 15、16 两页有大半是相同的,也可能是第 15、16 页之间有很多内容消失。他们的区别在于,最老和最新的内容很容易被点到,却很少有人会直接看中间的页码,而这种优化恰恰是针对大量页数据的时候,类似热门视频的评论、某超女的贴吧等情况。如果量很小,偏差可能只有一两条,而很难达到错几页的量级。把错误挪到更不容易被看到的地方比琢磨更精确的计数要节省的多。

    反向排序优化是我在做论坛的时候被迫使用的,因为总有 SB 去搞“真心话大冒险”“成语接龙”这种 SB 高楼贴,动不动就几万层高楼就堆出来了,那些 SB 还总以为这种空洞无聊的盖楼可以聚集人气而屡试不爽,我对此优化后根本不担心他们盖多少层了。

    页码错误的问题也经常能看到,贴吧现在可能改了,起码以前经常能看到末尾几页空白。抓一个现行,是豆瓣。

    http://www.douban.com/subject/3072124/comments?sort=vote&start=3860

    

    http://www.douban.com/subject/1309161/comments?sort=vote&start=200

    

    我估计豆瓣很快会修正这个问题,再贴个正常页面的截图,内容是在页码之前的(其实我是想问句,那位叫“影志”的老兄是豆瓣内部员工么?太彪悍鸟)

    

    这个截图还能说明个问题,在这个界面里,最后一页可以直接点过去的(大部分网站都是如此),而用户这么容易就会看到错误的空白,很不应该。


    虽然最近说的都是优化。但并不是所有问题都应该被提前考虑好,我主张出了问题再去修正(只要不是跟金融有关的程序)。牢记过度优化乃万恶之源。

建议继续学习:

  1. 如何使用1M的内存排序100万个8位数    (阅读:10913)
  2. 快速排序(Quicksort)的Javascript实现    (阅读:10102)
  3. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读:9049)
  4. 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序)    (阅读:6199)
  5. 深入浅出交换类排序算法(冒泡排序,快速排序)    (阅读:5997)
  6. Java程序员必知的8大排序算法    (阅读:4464)
  7. Mysql中的排序优化    (阅读:4369)
  8. Vim(gVim)对排序的妙用    (阅读:4227)
  9. 快速排序详细分析    (阅读:3957)
  10. 深入浅出选择类排序算法(简单选择排序,堆排序)    (阅读:3765)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1