w.rdc.sae.sina.com.cn:3307|nj41yyozkz|nj41yyozkz Thinking in Algorithm Application (Sina internal training by kobe @2009.6) « SAE云计算
Twitter FaceBook
Home
Sina App Engine
illuminati
illuminati
Posted by kobe, and filed under 计算机理论

Thinking in Algorithm Application

-C++ description

by kobe

引言:

.适合听众
.目的初衷
.选材标准
.参考文献

开场白:

.算法能解决什么问题?

一,查找
二分查找:
1,接口设计
涉及话题:
1,数据定长是否必须?
2,数据有序是否必须?
C++实现:
std::equal_range
预备知识:
1,什么是二分查找
相关阅读:
1,http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html

哈希:
1,线性探测、高次探测
2,拉链=>对象分配
涉及话题:
1,为什么推荐用素数为底取模?
2,为什么bloom filter冲突概率低?
3,一台服务器上同时跑2个计算排行榜的cron,一个周期是20分钟,一个周期是30分钟,有什么问题?
C++实现:
boost::hash
预备知识:
相关阅读:
1,《算法导论 第2版》,11.3
2,http://en.wikipedia.org/wiki/Bloom_filter

二,排序
排序:
1,局部排序
2,最大N个元素
3,原地排序
4,集合操作(交、并)
涉及话题:
1,快速排序有什么方式减少栈消耗?
2,有序性带来什么好处?
3,播客如何显示热门视频排行榜?
C++实现:
1,std::sort
2,std::nth_element
3,C++建堆
4,C++实现优先队列
预备知识:
1,快速排序的原理
相关阅读:
1,《算法导论 第2版》,9.2
2,《算法导论 第3版》,27.1
3,《计算机程序设计艺术 卷3 中文版》,5.2.2

三,随机
随机算法:
1,随机排列
2,随机组合
涉及话题:
1,内存中的已知长度的用户数据,随机抽奖怎么实现?
2,mysql中的博客数据,随便逛逛怎么实现?
3,未知长度的用户数据,随机抽奖怎么实现?
4,假如设计一个系统,支持CCTV NBA直播结束的短信抽奖,如何设计是最轻量级的实现?
C++实现:
1,std::random_shuffle
2,std::next_permutation
预备知识:
相关阅读:
1,《计算机程序设计艺术 卷2 中文版》,3.4
2,《计算机程序设计艺术 卷4 英文版》,7.2.1.2
3,http://www.sgi.com/tech/stl/next_permutation.html

四,字符串
字符串查找:
1,简化版kmp
2,多字符串匹配
涉及话题:
1,strstr等的效率如何?
2,做博文的多关键词过滤,怎么实现最快?
C++实现:
1,std::string的好处
预备知识:
1,KMP的基本原理
相关阅读:
1,http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

字符串匹配:
1,元素有序要求
2,元素无序要求
涉及话题:
1,两个字符串,如何判断相似度?
2,两个索引表,如何判断相似度?
C++实现:
1,std::vector的好处及拷贝
预备知识:
相关阅读:
1,《算法导论 第2版》,15.4

五,树
搜索树:
1,遍历方式
2,逆波兰
3,扩展节点信息
涉及话题:
1,最优雅的遍历树的方式是什么?
2,一个用树实现的索引表,怎么同步到硬盘上?
3,老虎机游戏中,每个游戏者都想实时知道自己的金币排名,怎么实现?
C++实现:
1,std::map
2,删除陷阱
3,序列化
预备知识:
1,基本二叉树
2,二叉树遍历
相关阅读:
1,《计算机程序设计艺术 卷1 中文版》,2.3.1
2,《现代编译原理-C语言描述》,13.1
3,《编译原理 第2版 中文版》,5.4.1
3,《算法导论 第2版》,14.2
4,http://www.boost.org/doc/libs/1_39_0/libs/serialization/doc/index.html

六,图
图:
1,遍历
2,图的含义
涉及话题:
1,SNS中,每个用户都可以对好友发feed,如何找出关键用户?
2,Google图片搜索中的图片排重的实现原理?
C++实现:
1,boost::graph
预备知识:
1,图的遍历
相关阅读:
1,PageRank for Product Image Search
2,Deeper Inside PageRank
3,The Anatomy of a Large-Scale Hypertextual Web Search Engine
4,The Second Eigenvalue of the Google Matrix

七,内存分配
内存池:
1,适用范围
2,定长对象内存池
3,非定长对象内存池
涉及话题:
1,C++中的对象内存池和C的对象内存池,实现有什么重要区别?
2,boost中的object_pool有什么重要缺陷,怎么比它更快?
C++实现:
1,boost::pool
预备知识:
相关阅读:
1,《计算机程序设计艺术 卷1 中文版》,2.5
2,http://www.boost.org/doc/libs/1_38_0/libs/pool/doc/concepts.html
3,《深入理解linux内核》,6.2.1

八,常见技巧
1,局部
2,延迟
3,抽样
4,迭代
5,平摊
涉及话题:
1,黑石国际五子棋AI冠军如何保证在规定时间内出招?
2,满屏NPC时,星际争霸如何保证两个圣堂武士合体寻路流畅?
3,kai心网抢车位游戏数据显示的策略变化的好处?
4,用户数据存放在两个库里,如何最快的实现库合并?
5,linux内核如何实现O(1)时间进程调度?
预备知识:
相关阅读:
1,《人工智能游戏编程箴言 中文版》,3.4
2,《More Effective C++ 中文版》,条款17
3,《算法导论 第2版》,17.3
4,《linux内核设计与实现 中文版》,4.2.3

九,开放话题
1,新浪版C++真的比C快吗?
2,我们能否写出比STL还快的算法?
3,我们用担心C++慢吗?
4,研究算法有用吗?

十,经验
1,80:20
2,有所得必有所失
3,选择适当的语言、适当的实现、适当的算法
4,一定要使用标准库,尽量避免使用非标准库
5,不尊重用户是一种罪,而欺骗用户是一种美

edited by kobe, 2009.5.13

13th 四 2010
Tags:
illuminati

3 Responses to “Thinking in Algorithm Application (Sina internal training by kobe @2009.6)”

  1. jiangtao 说:

    不错 这是提纲 还是已经完成了

  2. kobe 说:

    培训已经在2009年6月完成,这是当时培训的提纲,另有培训的ppt。主旨是把单机算法和实际互联网应用结合,其实完全可以写成书,不过目前没时间。

  3. Junyi Sun 说:

    Hi, Kobe.

    Could you please give me a copy?
    I will never sent it to other people without your permission.

    Thank you!

Leave a Reply

 
Designed by