Dec 27

popobox折腾记 不指定

felix021 @ 2013-12-27 00:49 [IT » 硬件] 评论(0) , 引用(0) , 阅读(5630) | Via 本站原创
其实这货已经到手一个多月了,最初是在v2ex上看到这个帖子,发现它居然只要29块钱(其实是因为出了2代,1代亏本清仓),虽然CPU只是arm9 360MHz的,但是有256M内存、2GB Flash、原生Linux系统,这样一个嵌入式设备能做的事情也不少了,于是果断在京东下单。

11月12号到手,然后没几天各个地方就都卖断货了。外观上看起来做工还是可以的,大小像一般家用路由器一样,有2个USB口,其中一个是USB2.0,另一个官方说仅用于向该设备供电(这样就不需要电源适配器了),但是在扣扣群里看到帖子说是可以改造。可惜sandy那套螺丝刀工具套装找不到了,那个特殊的六角形螺丝拆不了,只能先折腾软件了。

popo里头内置了一套它们的云服务(用python写的,通过它的服务器中转,可以在公网上分享USB存储设备上的内容),并且默认启用了samba服务供内网访问,而且居然还启动了一个minidlna服务。不过这些东西都太耗内存了,怪不得这样一个设备需要256M的内存,直接被吃掉了一大半。全都停掉以后,内存占用只有17M,可用200多M,比外头的好多vps可是大多了(我现在就用着一个64M的openvz vps来翻墙)……预装的Linux里头有transmission,扣扣群里还流传着一个官方给2代提供的迅雷远程下载插件,在一代也可以用,不过其实没什么意思,自从买了迅雷会员以后,都是在迅雷离线下载好再直接下载到本地。。。

系统默认的ssh很奇怪,可能是精简得太厉害了,连scp都不支持,按照群里某教程换了个dropbear上去,然后参照Yongke同学的这篇Blog,给上面倒腾了一个chroot的debian,不过我没有蛋疼地搞一个loop的img,而是直接放在一个文件夹里,拷贝和解压的时候都省了好多时间,还免了挂载这一步。有了debian以后能做的事情就很多了,可是因为手头的mk802性能比它好得多,而且稳定运行了1年多时间(最长连续200+天,因意外被重启。。),所以好像也没什么需要它干的事情,所以就放着了。

第二天远程到公司,发现有个人在群共享里放了个kernel module,可以把boot所在的nand分区显示出来,这样就可以挂载了。然后我就2乎乎地用yaffs把那个分区挂载上去了……然后……实际上那个分区并不是那样的,但是yaffs可不管这个,挂载出了一个空分区,还自动创建了一个lost+found文件夹……当时我就快哭了。经过了多番折腾,把分区dd出来,然后再用别人dd出来的对比,修改,再mtd-utils工具包里的nandwrite写回去,最后终于……砖了。

于是很无耻地向京东申请换货,京东倒是很爽快,第二天就给换了一个。原样再倒腾一遍,然后就一直撂着了,直到上周,因为给电脑升级CPU(i5 4570s)买配件,顺便买了一套螺丝刀套装,19号到货以后,按照群里的图,把NR127和NR128两个口短接了(用的就是当时给机械键盘换轴的时候买的电烙铁套装),于是那个本来仅用于供电的USB口也可以被识别成一个USB1.1口了。

点击在新窗口中浏览此图片

然后想着干脆再折腾一下,于是在淘宝上下单买了个USB转TTL适配器,杜邦线,以及一堆导线什么的(最后没用上导线),23号收到以后当晚就开始折腾,搞得房间烟雾缭绕……其实松香的味道还是挺好闻的。倒腾了几次,在扣扣群里朋友的指导下,才搞清楚原来RX是要接TXD、TX是要接RXD。用putty连上对应的COM口,设置115200的Baud Rate,终于连上了它的console,以后瞎倒腾不愁变砖了。最后成品图如下,虽然焊点很难看,但是杜邦线从底部通风口引出去的设计不错吧XD,这样就可以在不给外壳动手术的情况下把外壳合上用TTL了。

点击在新窗口中浏览此图片

大概就是这样了,只是因为有mk802在先,好像这货还是不知道可以用来干啥。。。
Nov 20
UPDATE@2014-01-09:注意,在gdb attach成功以后,这个进程会被暂停,可能会导致一些问题。

场景:Linux下,进程 p 打开了文件 f 并在后台持续地往 f 中写入日志。某日发现磁盘空间不够,把 f 删掉了,这时 ls 已经看不到 f 的存在,但是 df 发现磁盘空间占用并未减小,而 lsof 仍然可以看到该文件被占用(并显示一个 "(deleted)" 后缀)。更不幸的是,进程 p 是需要长期驻留在后台运行的,不能直接干掉它。

解决:简单地说就是替进程解决这个文件。

1) 根据链接文件名,可以查到该文件在进程中的 fd :

    $ ls -l /proc/[PID]/fd

2) 通过 gdb 连上该进程(一般需要root权限)

    $ sudo gdb
    (gdb) attach [PID]

3) 清除该文件所占空间

    (gdb) call ftruncate(3, 0)    #这里假定fd = 3
    $1 = 0

这种方式治标,但不治本 —— 随着进程的继续运行,被删掉的 f 仍然会占用越来越多的空间;但是又不能残暴地直接 close(3) ,否则 p 的后续写入操作会出错,可能导致进程报错结束。

但是还是有办法的:

4) 移花接木

    (gdb) call dup(3)
    $2 = 4
    (gdb) call open("/dev/null", 2)    #注:2 = O_RDWR,x86/x86_64/arm上都是这个值。
    $3 = 5
    (gdb) call dup2(5, 3)
    $4 = 3
    (gdb) call close(4)
    $5 = 0

注:未测试该招式是否可能因多线程竞争导致错误。

OVER.
Nov 12

我想写篇日志 不指定

felix021 @ 2013-11-12 15:21 [杂碎] 评论(4) , 引用(0) , 阅读(9594) | Via 本站原创
从高考完开始,每月保持至少一篇的节奏,终于还是在今年被打破了。幸好3月写得多,我还可以说今年平均每月还有一篇;但是明年恐怕就没这底气了。

其实并不是不想写博客了,只是因为无从下手敲键盘。工作上没什么值得写的事情。没有什么困难的东西,有点新意的也就是象征性地接触了一下以前想搞搞但是一直动力不足的hadoop什么的,安装说明什么的还是不写比较好...

八月以来,拾起三月看断的SICP,陆陆续续地看到了第四章,连自己都有点意外。虽然从书中学到了不少东西,但似乎也没有什么适合总结写下来的,也许是因为还没“悟道”吧,只能先把代码提交到 GitHub ,期望着哪天看完了能写点什么。

这几个月生活的主要亮点之一是买了Kindle Paperwhite以后,看了好多书。历史、哲学、金融、文学,都有涉猎,挺有意思的。最近把《量子物理史话》又看了一遍,然后开始看《明朝那些事儿》。不仅买了很多电子书,还莫名其妙心血来潮买了好多纸质书,其中有几块大部头,比如《30天自制操作系统》、《编译原理》、《什么是数学》……感觉有很多只能拿来垫显示器了,有点囧,尽量看吧。不管怎么说,买了kpw以后增加了自己的阅读量,挺好的,因此在这里顺便强烈推荐一下。

最后征集一下早餐的问题。在吃了两个月华夫饼、接着又泡了两个月永和豆浆粉以后,想换点什么新的、适合在办公室搞定的东西,求推荐……

p.s. 再顺便推荐几本好书吧,Kindle电子书 //亚马逊有Kindle for PC/Mac/iOS/Android

《上帝掷骰子吗:量子物理史话》 ¥2.99

《时间的形状:相对论史话》 ¥5.00

哲学家们都干了些什么? ¥0.99

搞懂金融的第一本书 ¥3.99

重说中国近代史 ¥1.60

明朝那些事儿(1-7套装) ¥15.00
Aug 22
本篇来自这个问题:python中创建父类对象的问题

也许可以认为这是Python设计的缺陷导致的,因为Python 3.0只需要用 `super().some_attr` 就行了。至于为什么需要两个参数,可以大概分析一下,如果有错,欢迎指正。

先介绍下背景知识:super是从Python 2.2开始随着 `new-style class` 一起引入的,也只能应用于所谓的 `new-style class` (即直接或间接继承于 `object` 的class),可以在一定程度上解决所谓`钻石继承`的问题。2.2起所有python内置class都是new-style class。

那么super是什么呢?实际上它是一个builtin的type,你调用 `super(Base, self)` 会返回一个 `__class__ = super` 的对象,这个对象可以作为一个代理,通过BFS的顺序(实际上列表已经保存在`Base.__mro__`里了)去访问第一个**直接定义**了目标属性的基类里的属性。`super(type, obj_or_subtype).attr` 基本上可以认为是  `find_in_mro_provide_by(obj_or_subtype, "attr")` ,有点晦涩。

**注意**,super()返回的不是“父类对象”,而是一个super类型的对象;实例化的时候,第一个参数是一个类型(type),第二个参数可以是type的instance,也可以是type的subclass。

介绍完基础知识,可以先说说为什么要有第二个参数。理由很简单 —— 我们知道 self 代表当前对象,每个对象的方法在定义的时候都需要显示地把self作为第一个参数,你本来应该写成这样
   
    some_class.some_method(obj, *args, **kwargs)

但是因为Python语法允许 `obj.some_metod(*args, **kwargs)` (本质上是个语法糖) ,所以你可以写得简单点(不必显式地给出方法的第一个参数)。而super对象则不同,它没有语法上的直接支持,所以在内部invoke some_method的时候必须指定某个对象,而这个对象的得你自己塞给它,也就是说把这个super对象绑定(bound)到第二个参数上。所以实际上并不是非要用self作为super的第二个参数,甚至super并不是必须在class内部才能调用:
    class A(object):
        def foo(self):
            print self.name

    class B(A):
        def __init__(self, name):
            self.name = name

    b1 = B('b1')
    super(B, b1).foo() #produces 'b1'


至于为什么要有第一个参数,如果你看了 `help(super)` 就会发现它居然提供了个单参数的版本:

    super(type) -> unbound super object

这个理解起来比较困难点。先说这个`unbound`,没绑定,就是说这个super对象没有实际绑定到某个对象上,它并不是可以直接用的。要怎么用呢?那就得注意到`help(super)`里面有一个 `__get__` 方法,也就是说,super类还是一个Descriptor类!哎,这个Descriptor类展开又是好大一段,简单地说就是它可以把自己和某个object的属性绑定,使得访问这个属性的时候,实际上是在调用它的`__get__/__set__`方法:
    class Descr(object):
        def __get__(self, obj, tp): #最后一句传进来的 obj=x, tp=X
            return 'get!'

    class X(object):
        t = Descr()

    x = X()
    print x.t #this produces 'get!'


回到unbound super, 为了使用它,就要通过 __get__ 方法把它再绑定到一个对象上。由于Descriptor的属性,特别适合这么用:
    class A(object):
        def foo(self):
            print 'foo'

    class B(A):
        def foo(self):
            self._super.foo()
    B._super = super(B) #这还不能直接写在B的定义里,多蛋疼啊。

    b = B()
    b.foo() #produces 'foo'


这是它的一个可能用法。我不确定是否还有其他更合适的用途,但是在这里实际上也并不是很好,尤其是遇到staticmethod的时候还会出错,再加上绕了这么大一个弯,实在不是很推荐使用。

据说unbound super的使用非常少,不知道现实意义有多少,也不知道当初为什么设计成这个样子,总之由于Python3.0已经改了(虽然仍然保留了unbound super),所以基本上还是可以认为这是设计的历史遗留问题。

参考文献(unbound super主要参考了这个系列):Things to Know About Python Super

[1] http://www.artima.com/weblogs/viewpost.jsp?thread=236275
[2] http://www.artima.com/weblogs/viewpost.jsp?thread=236278
[3] http://www.artima.com/weblogs/viewpost.jsp?thread=237121
Aug 16

mixo:又一个翻墙socks5代理 不指定

felix021 @ 2013-8-16 17:23 [IT » 网络] 评论(0) , 引用(0) , 阅读(13303) | Via 本站原创
因为不满ssh tunnel的使用效果,所以2012年12月某天(大概是17号)心血来潮写了这个小东西,由于 [socks5协议]( http://www.openssh.com/txt/rfc1928.txt ) 本身很简单、加上gevent/greenlet使得异步开发跟同步似的,所以200行就搞定了。但是性能上问题很大——主要是加密有问题。尽管加密就是最简单的xor,但是因为python不适合处理大量的小对象,所以当时写了一个python扩展,性能上就没问题了,但是又多了一项麻烦的依赖。后来发现已经有更成熟的shadowsocks,于是就弃坑了,也一直没有发布。

今天[2013.08.16]心血来潮,用ctypes来实现同样的功能,似乎也挺合适的;不过跟shadowsocks比起来有两个地方做得不好,一是没有更“高级”的加密方式(他家用了M2Crypto,代码看起来很复杂),另一个是shadowsocks在本地先回应socks5请求,只把必要的host:port信息发送给server,减少了一个来回,而我原先的实现则是在server端实现完整的socks5(现在把step1搬到client了,因为改动很小)。

总之好歹也是个凑合能用的东西了,发布出来晾着吧,也许哪天有人就用上了呢。

项目地址: https://github.com/felix021/mixo
Aug 16

使用ctypes来扩展Python 不指定

felix021 @ 2013-8-16 08:58 [IT » Python] 评论(1) , 引用(0) , 阅读(14997) | Via 本站原创
为了扩展Python,我们可以[用C/C++编写模块](http://docs.python.org/2/extending/ ),但是这要求对Python的底层有足够的了解,包括Python对象模型、常用模块、引用计数等,门槛较高,且不方便利用现有的C库。而 [ctypes](http://docs.python.org/2/library/ctypes.html ) 则另辟蹊径,通过封装`dlopen/dlsym`之类的函数,并提供对C中数据结构的包装/解包,让Python能够加载动态库、导出其中的函数直接加以利用。

快速上手
-------

最简单的,我们可以从 libc 开始:
    felix021@ubserver:~/code$ python
    Python 2.7.3 (default, Jul  5 2013, 08:39:51)
    [GCC 4.6.3] on linux2
    Type "help", "copyright", "credits" or "license" for more information.
    >>> import ctypes
    >>> libc = ctypes.CDLL("libc.so.6")
    >>> libc.printf("hello, %s! %d + %d = %d\n", "world", 1, 2, 3)
    hello, world! 1 + 2 = 3
    25


由于ctypes库能够直接处理 None, integers, longs, byte strings 和 unicode strings 类型的转换,因此在这里不需要任何额外的操作就能完成任务。(注意,最后一行的25是printf的返回值,标识输出了25个字符)

自己动手
-------

[这里](http://wolfprojects.altervista.org/articles/dll-in-c-for-python/)有一个最简单的例子——实现一个 `int sum(int a, int b)`:

    //file foo.c
    #ifdef __WIN32
    #define DLLEXPORT __declspec(dllexport)
    #else
    #define DLLEXPORT
    #endif
   
    DLLEXPORT int sum(int a, int b)
    {
        return a + b;
    }


编译之得到 foo.so:

    $ gcc -fPIC -shared -o foo.so foo.c

然后在Python里头:

    >>> foo = ctypes.CDLL("./foo.so")
    >>> foo.sum(5, 3)
    8


真是超级简单。

丰衣足食
-------

下面来个稍微复杂点的例子:反转一个字符串。尽管ctypes可以直接处理string的转换,但是你不能直接修改string里的内容,所以这里需要变通一下。可能的解决方案有两个:

1. 在foo.c里面malloc一点空间然后返回。这样可以不修改原string,但是却要考虑释放该空间的问题,不太好处理。

2. 让Python分配好空间,将原字符串拷贝进去,再让foo里面的函数来修改它。ctypes为这种方案提供了`create_string_buffer`这个函数,正适合。

那就让我们用方案2来实现它:

    //file foo.c
    DLLEXPORT int reverse(char *str)
    {
        int i, j, t;
        for (i = 0, j = strlen(str) - 1; i < j; i++, j--)
            t = str[i], str[i] = str[j], str[j] = t;
        return 0;
    }


然后在Python里头:

    >>> s = ctypes.create_string_buffer("hello world!")
    >>> foo.reverse(s)
    0
    >>> print s.value
    !dlrow olleh


这样就OK啦。

补充说明
-------

以上的操作都是在Linux下完成的,在Windows下基本上一致,除了windows不能直接load libc.so.6,而是应该找 msvcrt :

    >>> libc = ctypes.cdll.msvcrt

或者直接导入文件

    >>> libc = ctypes.CDLL("msvcr90.dll")


小结
-------

前面演示了ctypes库的简单使用,已经能够完成许多任务了;但是它可以完成更多的任务,包括操作更复杂的例如结构体、数组等C数据结构,具体的这里不细说了,可以参考详细的[官方文档](http://docs.python.org/2/library/ctypes.html)

好了,就到这里。
Jul 30

MPI 简单上手 不指定

felix021 @ 2013-7-30 18:47 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(16637) | Via 本站原创
简单地说,MPI 就是个并行计算框架,模型也很直接——就是多进程。和hadoop不同,它不提供计算任务的map和reduce,只提供了一套通信接口,需要程序员来完成这些任务;它也不提供冗余容错等机制,完全依赖于其下层的可靠性。但是因为把控制权几乎完全交给了程序员,所以有很大的灵活性,可以最大限度地榨取硬件性能。超级计算机上的运算任务,基本上都是使用MPI来开发的。

~ 下载编译安装:

现在貌似一般都用MPICH,开源的MPI库,可以从这里获取: http://www.mpich.org/ ,现在的最新版本是3.0.4,编译安装过程可以参考安装包里的README的说明,基本步骤如下(万恶的configure):

引用

$ wget http://www.mpich.org/static/downloads/3.0.4/mpich-3.0.4.tar.gz
$ tar zxf mpich-3.0.4.tar.gz
$ cd mpich-3.0.4
$ mkdir ~/mpich
$ ./configure --prefix=$HOME/mpich --disable-f77 --disable-fc 2>&1 | tee c.txt #我禁用了fortran的支持
$ make -j4 2>&1 | tee m.txt
$ make install 2>&1 | tee i.txt
$ echo 'export PATH=$PATH:~/mpich/bin' >> ~/.bashrc


下面给出三个例子,参考教程:http://wenku.baidu.com/view/ee8bf3390912a216147929f3.html (注:22页有BUG,它把 MPI_Comm_XXX 错写成了 MPI_Common_xxx //包括全大写版本,共四处),给出了MPI框架中最常用、最基础的6个API的例子。更复杂的API可以参考mpich的手册。这些例子只是简单地演示了MPI框架的使用;实际上在使用MPI开发并行计算的软件时,还需要考虑到很多方面的问题,这里就不展开说了(其实真相是我也不会-.-,有兴趣的话可以请教 @momodi@dumbear 两位)。

1. 最简单的:Hello world

代码如下: hello.c
#include <stdio.h>
#include <mpi.h>

int main(int argc, char *argv[])
{
    MPI_Init(&argc, &argv); //初始化MPI环境

    printf("Hello world!\n");

    MPI_Finalize(); //结束MPI环境
    return 0;
}


编译:
$ mpicc -o hello hello.c

运行:
$ mpiexec -n 4 ./hello
Hello world!
Hello world!
Hello world!
Hello world!

可以看到这里启动了4个进程。注意 -n 和 4 之间一定要有空格,否则会报错。


2. 进程间通信

MPI最基本的通信接口是 MPI_Send/MPI_Recv:

#include <stdio.h>
#include <mpi.h>

int main(int argc, char *argv[])
{
    int myid, numprocs, source, msg_tag = 0;
    char msg[100];

    MPI_Status status;

    MPI_Init(&argc, &argv);

    MPI_Comm_size(MPI_COMM_WORLD, &numprocs); //共启动几个进程
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);  //当前进程的编号(0~n-1)

    printf("I'm %d of %d\n", myid, numprocs);
    if (myid != 0)
    {
        int len = sprintf(msg, "hello from %d", myid);
        MPI_Send(msg, len, MPI_CHAR, 0, msg_tag, MPI_COMM_WORLD); //向id=0的进程发送信息
    }
    else
    {
        for (source = 1; source < numprocs; source++)
        {
            //从id=source的进程接受消息
            MPI_Recv(msg, 100, MPI_CHAR, source, msg_tag, MPI_COMM_WORLD, &status);
            printf("from %d: %s\n", source, msg);
        }
    }

    MPI_Finalize();
    return 0;
}


编译运行:
$ mpicc comm.c
$ mpiexec -n 4 ./a.out
I'm 0 of 4
from 1: hello from 1
from 2: hello from 2
I'm 1 of 4
I'm 2 of 4
from 3: hello from 3
I'm 3 of 4


3. 来个复杂点的:数数前1亿个自然数里有几个 雷劈数

代码后附,答案是97(真少),不过这不是重点,重点是MPI对硬件的利用率是怎样 :D

测试机器是 16核 AMD Opteron 6128HE @2GHz,32G内存

单进程(无MPI版本):56.9s
4进程:15.3s
8进程:7.85s
12进程:5.35s

考虑到16核跑满可能会受到其他进程的影响(性能不稳定,4.2~4.9s),这个数据就不列进来比较了。

可以看出来,在这个例子里,因为通信、同步只有在计算完之后才有那么一点点,所以在SMP架构下,耗费的时间基本上是跟进程数成反比的,说明MPI框架对硬件性能的利用率还是相当高的。

具体代码如下:
#include <stdio.h>
#include <mpi.h>

int is_lp(long long x)
{
    long long t = x * x, i = 10;
    while (i < t)
    {
        long long l = t / i, r = t % i;
        if (l + r == x)
            return 1;
        i *= 10;
    }
    return 0;
}

int main(int argc, char *argv[])
{
    int myid, numprocs, source;
    const int N = 100000000;

    MPI_Status status;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

    printf("I'm %d of %d\n", myid, numprocs);
    int start = myid * (N / numprocs), stop = (myid + 1) * (N / numprocs);
    if (myid == numprocs - 1)
        stop = N;
    printf("start from %d to %d\n", start, stop);
    int ans = 0, i;
    for (i = start; i < stop; i++)
        if (is_lp(i))
            ans += 1;
    printf("%d finished calculation with %d numbers\n", myid, ans);

    if (myid != 0)
    {
        MPI_Send(&ans, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
    }
    else
    {
        int tmp;
        for (source = 1; source < numprocs; source++)
        {
            MPI_Recv(&tmp, 1, MPI_INT, source, 0, MPI_COMM_WORLD, &status);
            printf("from %d: %d\n", source, tmp);
            ans += tmp;
        }
        printf("final ans: %d\n", ans);
    }

    MPI_Finalize();
    return 0;
}
Jul 29
nth_element是一个用烂了的面试题,09年的时候我也曾经跑过一点数据(回头一看好像有点不太对,那时候CPU有那么慢吗?应该是当时没有把读取数据的时间给去掉吧),昨天看到 从一道笔试题谈算法优化(上)从一道笔试题谈算法优化(下) 这个系列,里面提到了从简单到复杂的6种算法,根据作者的说法,经过各种优化以后solution6达到了相当的效率。受到作者启发,我也想到了一种算法,于是花了些时间,把常用的几种算法实现了进行对比(包括对比stl里的nth_element)。

回到 nth_element 的问题:从 n 个数里头,找出其中的 top k (top可以是找最大 也可以是找最小)。简单起见,后面都以找最小为例。

那篇文章里的后面的3种算法和我的算法都是基于它的solution3进行优化的,所以先介绍一下solution3:

1. 将 n 个数的前 k 个拷贝出来
2. 找出这 k 个数的最大值 m
3. 对于每一个剩下的 n - k 个数 i :如果 i 小于 m ,将 m 替换为 i ,然后再找出新的 k 个数中的最大值 m
4. 返回过滤后得到的 k 个数

虽然第3步的判断条件成立时,这一步是 O(k) 的复杂度,但是在大部分情况下,这个判断条件都不成立,所以它需要执行的次数很少(这种效果越往后越明显,因为 m 的值越来越小,可以滤掉更多的数)。但是对于极端情况(或者接近极端的情况)——如果数组完全是降序排列的话,那么这个条件每次都会成立,会导致算法退化成 O(n * m) ,性能就不可接受了。

solution4~6的优化我觉得读起来有点晦涩,有兴趣的同学可以自己去看,这里不展开说了。它们都存在算法退化的情况。

我的算法可能理解起来要简单些,基本思路是偷懒:把缓冲区设置为 2 * k ,在扫数组的时候,如果这个数比当前保留的最大值还要小,就把它塞进缓冲区,直到缓冲区塞满了,再排序、取最大值、删多余的数。

1. 开辟一个 2 × k 的临时数组 r
2. 将 N[1..k] 拷贝到 r[1..k],并记录 r 的末尾 e = k + 1
3. 找出 r[1..k] 中的最大值 m
4. 对于每一个剩下的 n - k 个数 i:
4.1 如果 i 小于 m,将 m 塞到 r 的末尾 r[e];e = e + 1
4.1.1 如果 e == 2×k(r被塞满了),对 r 进行排序,得出前k个数中的最大值;抛弃后面的k个数,e = k + 1
5. 对 r[1..e] 进行排序
6. 返回 r[1..k]

这个算法的实际效果很好,在 n = 1亿、k = 1万 的情况下,对于随机的n个数,4.1条件成立的次数通常只有十几次,几乎可以忽略,因此大约只需要扫描整个数组时间的2~3倍即可。

但是这个算法同样存在退化的问题:如果全都是倒序排列的话,也变成O(n*m)了。幸而解决方案也很简单:对这个数组进行 n / 100 次的随机化(考虑到随机化耗时也比较大,100这个数字是试了几次以后发现的合适值,不一定最优,但是都差不多了):
void rand_factor()
{
    //randomization
    const int factor = 100;
    int r, t, i;
    for (i = n / factor; i > 0; i--)
    {
        r = rand() % n;
        t = a[0], a[0] = a[r], a[r] = t;
    }
}

p.s. 很不幸的是随机化这个方法对于solution3来说虽然提升也很明显,但是远远不够。solution4~6也不太行。

这里给出随机情况下和完全倒序情况下的性能对比吧(ubuntu 12.04 x86_64,i5 2400@3.1G):

引用
随机数据
========

随机化生成数据:    7.087s
遍历耗时:          0.053s
1/100随机化耗时:    0.064s

STL的nth_element:  0.841s

最大堆+随机化:    0.162s

Solution3+随机化:  3.121s
solution4+随机化:  2.825s
solution6+随机化:  0.249s

我的算法+随机化:  0.163s


倒序数据
========

无随机化生成数据:  0.150s
遍历耗时:          0.052s
1/100随机化耗时:    0.067s

STL的nth_element:  1.420s

最大堆+随机化:    0.301s

Solution3+随机化:  67.552s
solution4+随机化:  66.405s
solution6+随机化:  2.388s

我的算法+随机化:  0.170s



补充说明一下,nth_element算法在面试的时候可能给出的 n 会更大,以至于在内存中存不下,这时候通常会认为用堆来实现最好——因为只要O(k)的空间就可以搞定,而且最差时间复杂度是O(logk * n),但是要注意logk的常数实际上是很大的,所以你可以看到前面的数据里 堆算法 的效率并不是最好的。事实上这里给出的所有算法(不考虑随机化的话)也都只需要O(k)的空间;如果需要随机化的话也很简单,分段处理,只要保证每段能在内存中保存下来就行了。



最后上代码存档(为了方便测试用了些全局变量,看起来可能有点挫):
分页: 6/94 第一页 上页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]