深入理解排序算法(一):插入排序、冒泡排序、选择排序

写在前面:开始系统地梳理知识,暂且先把一些想法记录下来,后续有时间再做进一步整理和完善,比如展开文字、配以实例和图片等。

排序算法是最常用的算法之一,分析排序算法的三个重要指标:时间复杂度、空间复杂度以及稳定性。

基于比较的排序算法时间复杂度一般在O(nlogn)到O(n2)之间。

空间复杂度为O(1)的排序称为就地(in-place)排序,或者原址排序,非就地排序的空间复杂度一般为O(n)。

稳定性指的是序列中相等的元素在排序后的前后位置是否会发生变化,如果不变则排序算法是稳定的(stable),否则为不稳定。

排序可以按从小到大,也可以按从大到小的顺序排列,后面我们在讨论和实现算法时都以前者为准。

插入排序、冒泡排序、选择排序是三种最简单直接的排序算法,都是基于比较+交换,由内外两层循环实现,其中外循环次数为n-1,内循环次数跟外循环的循环变量相关,平均时间复杂度为O(n2),空间复杂度为O(1)。 继续阅读“深入理解排序算法(一):插入排序、冒泡排序、选择排序”

Windows下编译FFmpeg

FFmpeg是一套跨平台的音视频录制、编码、解码以及转码方案,支持多种编码算法和多种文件格式,是应用最为广泛的多媒体开源项目之一。由于其代码是在Linux平台下开发,所以无法直接在Windows下编译,本文简单记录了Windows下使用MinGW编译FFmpeg代码的过程。

1. 安装MinGW和MSYS

编译 ffmpeg需要用到MinGW和MSYS,可以分别单独安装二者,也可以直接使用他人整合好的统一安装包。 继续阅读“Windows下编译FFmpeg”

Select2的一些使用问题

好久没写技术文章了,先写个简单的凑凑数。

HTML中的select控件只能选择,不能通过输入的方式快速筛选选项,基于jQuery的select2很好的实现了该功能。除此之外,它还支持远程加载数据和多选,是一个不错的第三方扩展。

Select2是兼容于原生select的,我们只需通过jQuery获得select对象,然后调用select2()方法,便能动态创建一些辅助元素(如input控件),从而改变select的外观和响应方式。

Select2的网址是:http://select2.github.io,上面有详细的使用说明和示例。 继续阅读“Select2的一些使用问题”

选择开源代码还是自己发明轮子?从Laravel说起

在软件开发领域,要实现某个系统或功能,经常需要一些基础设施(Infrastructure),这些基础设施或是库(Library),或是框架(Framework),或是独立的应用(Application)。有了这些基础设施,开发者就能把工作重心放在业务逻辑上,快速的进行开发。而基础设施可以是来自于第三方的开源代码,也可以是自己发明的轮子,在项目中,我们应该选择开源代码还是自己发明轮子呢?这是开发人员经常争论的一个话题。 继续阅读“选择开源代码还是自己发明轮子?从Laravel说起”

零基础学习Mahout:搭建单机环境

一、Mahout是什么?

mahout-logo-brudman

Mahout是Apache的一个开源项目(http://mahout.apache.org/),提供了机器学习领域的若干经典算法,以便开发人员快速构建机器学习和数据挖掘方面的应用。

Mahout是基于Hadoop的。从名称上看也很有意思,Hadoop是一个大象的名字,而Mahout则是象夫、看象人,可见二者联系之紧密。(这让我不由联想到Sun和Eclipse…)

我写此文时是一个完全没用过Mahout的门外汉,对Hadoop也没有实际使用经验,算是真正的零基础。我的目标是希望以最简单的方式搭建起一个Mahout的开发环境,以最快的速度让Mahout工作起来,以方便后续的学习。

于是,经过一番折腾,便有了本文。本文记录了Windows下Eclipse+Maven+Mahout单机环境的搭建过程。我不知道这是不是最简单的Mahout开发环境,但它应该算得上是比较简单的。 继续阅读“零基础学习Mahout:搭建单机环境”

使用Redis实现游戏实时排行榜

游戏中存在各种各样的排行榜,比如玩家的等级排名、分数排名等。玩家在排行榜中的名次是其实力的象征,位于榜单前列的玩家在虚拟世界中拥有无尚荣耀,所以名次也就成了核心玩家的追求目标。

一个典型的游戏排行榜包括以下常见功能:

  1. 能够记录每个玩家的分数;
  2. 能够对玩家的分数进行更新;
  3. 能够查询每个玩家的分数和名次;
  4. 能够按名次查询排名前N名的玩家;
  5. 能够查询排在指定玩家前后M名的玩家。

更进一步,上面的操作都需要在短时间内实时完成,这样才能最大程度发挥排行榜的效用。 继续阅读“使用Redis实现游戏实时排行榜”

WordPress的几大核心要素

每个系统都有那么几个核心概念,理解了这些核心概念及其关系也就从很大程度上理解了整个系统。

WordPress也是如此。WordPress管理后台的大部分功能都很直观易用,对于初学者,几乎不用借助任何帮助就能发表博文。但对于第一次接触WordPress的人还是会有几个疑问,比如:文章和页面有什么区别?应该如何对文章进行分类管理?怎样创建菜单?等等。

只要了解了文章、页面、分类、标签、菜单这几个WordPress的核心要素,这些问题也就迎刃而解。 继续阅读“WordPress的几大核心要素”

别人的域名解析到我的网站怎么办

很多时候,不去亲自动手做一件事情,就不会遇到各种稀奇古怪的问题。

就像今天,在搜索我的域名时,居然发现搜索引擎收录的是一个第三方的域名,而点击这个域名也能正常访问我的网站。

显然,这是第三方将他的域名解析到了我的主机IP上。造成这种情况的原因有可能是因为我这个IP以前是他的,后来他的主机到期了然后IP分配给了我,也可能是他在域名解析设置时写错了IP地址,当然还可能是他故意写错IP地址。这当中,第一种可能性更大一些。

由于我们无法阻止他人将域名解析指向自己的网站,就跟无法阻止他人给自己的邮箱发邮件一样。我们只能在自己的网站收到来自第三方的请求时进行处理。

其中一个方法是接受第三方域名的访问,但将地址改写为我们的域名。这就用到的URL rewrite功能,以Apache为例,修改站点目录下的.htaccess文件:

<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteCond %{HTTP_HOST} !^第三方域名$ [NC]
RewriteRule ^(.*)$ http://自己的域名/$1 [L,R=301]
</IfModule>

其中R=301表示执行301重定向,用户通过第三方域名访问后,地址栏的域名会自动变成我们自己的。

也可以将R=301换成F,这样服务器会产生一个403 Forbidden错误。

当然,还有一些其它做法,这里不一一列出。