Radix Sort && Counting Sort && Pigeonhole Sort && Bucket Sort

05 Nov

ymfoi |  November 5th,2011 | Discoveries, OI |  No Comments »

一直以来就没有搞清楚基数排序(Radix Sort)和计数排序(Counting Sort)还有桶排序(Bucket Sort)的关系，今天wiki了一下，总算有了答案。

基数排序是利用排序关键字具有字典序特征的特点，对关键字进行分割，分若干轮子排序来达到最后使整个序列排好序的效果。至于子排序，可以以是其他的各种排序方法，基数排序仅仅指的是关键字分割这一思想。

计数排序顾名思义，就是开一个与关键字相匹配范围的表，对数据进行登记（即计数）。再通过按顺序遍历表，算出表中每个关键字序比它小的关键字有多少个。最后重新遍历原数据，根据处理过的表直接得出应该放的位置。注意表中记录的仅仅是数值，而没有把待排序的对象放进去。

这个算法有个特殊应用，如果需要排序关键字就是对象的全部，就可以在遍历表时，直接输出表中对应数值个相同对象就行了。

而桶排序是指将数据按关键字放入表中后，分别递归地对每个表内部进行排序，再按序遍历表输出。

基数排序的子排序算法常常使用计数排序实现（就是网上一搜一大把的那种开3个数组for3次，下标嵌套3层的那种）

有些资料上什么链表式基数排序又是怎么回事呢？

链表式是指子排序不是使用计数排序，而是一种叫鸽巢排序(Pigeonhole Sort)算法，其实就是桶排序省掉“递归地对每个表内部进行排序”步骤得到的算法，实际上递归的那部分被基数排序的多轮排序给完成了，使用了计数的基数排序本质上是拥有递归思想桶排序的一种特殊实现。

 

参考文献：

http://en.wikipedia.org/wiki/Radix_sort

http://en.wikipedia.org/wiki/Counting_sort

http://en.wikipedia.org/wiki/Pigeonhole_sort

http://en.wikipedia.org/wiki/Bucket_sort

Extract the resources of Topcoder!

23 Sep

ymfoi |  September 23rd,2011 | Discoveries, My Life, OI |  3 comments

由于学校最近总是隔三差五停网，感到压力很大，遂研究如何离线做TC的题。本以为google一下全是方法，结果搜了半天才好不容易翻到一个人在github上传的python脚本。

结果发现用不了，无奈看了下代码，改了一处。最终用是用上了，可是获取数据太慢了，二来我不太会python。于是想写个bash script（其实我也不熟。。= =）。因为以前写过一个POJ邮件批量发送器，所以登录神马的就用curl来解决，个人觉得比wget高效。

最让人头疼的是分析html，从中提取数据的部分了。 我本来就只会点sed，多行匹配弄死人啊啊啊~（人家python可以用BeautifulSoup来搞定）看来是该好好学学“二外”了，python,bash神马的，awk神马的，都应该熟练掌握啊。

最终还是把脚本搞出来了，私认为看上去不错。

http://repo.tedyin.com/tcget/

先运行./fecth.sh获取SRM最近200次比赛列表，结果会存到/tmp/matches里。然后编辑tcget.sh里面的username和passwd，改成自己的(下数据时要用）。最后./tcget.sh 脚本就会根据matches上的比赛把所有的题目和数据搞下来，挺快的。

注意因为是利用Topcoder官网的Top Submission中A了的代码下面附带的数据来得到题目数据的，对于那些比赛中无一人A的题就没法了。但90%题目应该都有数据，那些没有数据的说明我根本做不了啊（比赛时无一人A。。。）。

Git Repository

17 Sep

ymfoi |  September 17th,2011 | Discoveries |  3 comments

不打算同步到sf上了，于是研究了一下如何在虚拟空间里面搞个代码仓库。

成果总算有了~ http://www.tedyin.com/webrepo/

 

介绍：

Git是一个版本控制系统(Version Control System)，和SVN以及Mercurial类似。简单地说就是一个可以同步和管理代码的工具。比如开发一个工程，如果没有版本控制系统，那么就很难协调几个成员同时对这个工程的开发。所以为了让工程的开发更加透明和易于管理，一般在一个大家都能访问的服务器上设置一个仓库（Repository），然后这个服务器上运行着一个接受对于仓库请求的服务。对于开发人员，可以用客户端连接到服务器进行工程副本的获取和修改同步等等操作。Git就是这样的一个软件，由Linus Torvalds亲自操刀编写，为的是更好地维护日益暴涨的Linux内核代码。不过由于它简单快捷，所以就风靡了。

我在网站的空间里面用一个目录来放置Repository，为了让仓库可以从Web界面浏览，使用了一个轻量级Git的Web前端——CGIT。这样就可以从网页上浏览仓库里的文件了。

 

Update 20111009:

搞定了语法高亮。自己配了个颜色，感觉不错。详见这里

 

Plan for furture affairs v2.0 (alpha)

05 Sep

ymfoi |  September 5th,2011 | My Life |  5 comments

NOI已经结束。

我还缺一个NOIP一等奖。

因此9月到11月是个特殊时期。

现将暂行计划置于下方，随时进行调整和充实。

 

语文数学回班上课。

物理看借来的力学和电磁学书，同时参考教材。

英语每天保证至少1小时学习时间，提高词汇量、听说能力以及语法。

主要方法是听VOA,CNN,BBC,etc.（或高三英语课本）的听力材料，进行短时间内复述，尽量多地使用原表达。

在熟悉了剧本（字幕）之后看电影的某一片段，尝试进行表演。

感谢Ms. Yang对英语学习的建议~

 

NOIP这边跟着高一高二的做练习题，重新刷一遍USACO。

Bugs Fixed

05 Sep

ymfoi |  September 5th,2011 | Discoveries, My Life |  No Comments » 

在从长春回来之后换了联想的Thinkpad E40s本本，有一段曲折的经历。
刚入手的晚上发现本本的T键明显松动，像翘翘板一样。于是第二天去问销售员。
他说不是什么问题，用镊子重新卡好了键。

一天后的下午，我看到高二和高一的暑假NOIP集训题，顺手写了一道。
在按下熟悉的F8时，gdb跳出来了，然而在gdb提示符后面多了一个字符。
后来发现是F7，F8的毛病，按了一次实际响应了两次。我切到windows底下试了试，问题还是存在。
于是打电话再问，他说要找维修中心的出具鉴定才能换机。我马上和我爸一起到了维修中心。
工作人员测试之后确认了问题是BIOS firmware的或者硬件，我RP太低了，在等待服务的过程中维修中心就停电了。
鉴定单来电之前是打印不成了，等到6点他们下班也没来电。

第二天终于取得了单子，也换到了机子，倒腾了硬盘上已经有的数据。累啊。。

F7,F8恰好也是配合Fn进行亮度调节的键，我总觉得是BIOS写囧了之类的。
今天去官方驱动上看了下，BIOS从1.11升到了1.17，遂更新。果然，问题没有了。

Change Log 很好地印证了这一点。

以前总觉得像BIOS这种firmware升级Fix的bug也估计是些对一般用户无关痛痒的东西。
这次因为Bug大热天跑断腿啊~~~

CHANGES IN THIS RELEASE
Version 1.17

[Important Updates]
  Nothing

[New functions or enhancements]
- Intel CPU Microcode Upgrade rev 00000017h
- Support battery charging with 65W AC adapter for E420s.
- Prevent back flashing to 8JET30WW or older to support new BIOS/EC flashing
  tool.

[Problem fixes]
- Fixed issue that brightness level is not preserved after resume from standby
  mode on Windows XP.
- Fixed issue that Peak Shift schedule does not start on time.
- Fixed issue that scan code is not sent properly for F7 and F8 key.
- Correct FRU part number displayed on Power Manager.
- Fixed issue that fan error is sometimes detected during BIOS POST.
- Fixed an issue where expected serial number might not be stored in serial
  number field of SMBIOS type 3 structure depending on system setting.
« Older Entries
Newer Entries »

Teddy

Studies,OI and Love