CS巴别塔(1)

A Complete Program Inside a Tweet?

Posted in Uncategorized by Kenny Yuan on 2010/09/21

这是一篇无聊的文章,对此不感兴趣的读者可自行选择:关Tab、关窗口、退订、拔网线、砸电脑、自残、自焚、人体炸弹、当黑暗大BOSS毁灭人类、入党……





Boss

Boss





OK,你还在,我也还在,那么我来继续记流水帐:《能否在一条tweet中写一个求值程序?》

看到有人讨论面试问题,其中有人提到用“现场写一个计算器”来作为考题。在瞎掰了很久之后,我决定自己实际试试,因为“光说不练是假把式”么……当然,既然是自我挑战,那目标就设高一点:试着在一条推中写完表达式求值程序……

……嗯……显而易见地,我失败了!不过我在一条推的长度内写完了一个后辍(RPN)表达式的求值程序,共113字符:

(defun r(e)(let((s()))(dolist(x e)(if(numberp x)(push x s)(push(eval(reverse(list(pop s)(pop s)x)))s)))(car s)))

用的是标准的stack解法。

至于将中辍转后辍的程序,我只写出来这个:

(defun v(e)(let((s())(o())(m'((+ 1)(* 2)(- 1)(/ 2))))(dolist(x e)(if(listp x)(setf x(v x)))(if(numberp x)(push x o)(progn(do()((or(null s)(<(cadr(assoc(car s)m))(cadr(assoc x m)))))(push(pop s)o))(push x s))))(r(append(reverse o)s))))

足足有235字符!看来目标是达不到了……(@googollee老大也失败鸟——嗯,我很happy)

不知道有没有哪位读者是语言达人,可以完成这个伟大的目标呢?

最后声明一下:直接eval,或者调用bc这些玩赖的方式肯定能行,但太没技术含量……

——路人甲:还有比这篇日志更没有技术含量的?

——路人乙:大家洗洗睡了吧!

于是,我去准备洗洗睡了……

(如果哪位有好点子,请一定别忘了留言)








Advertisements
Tagged with: ,

神话

Posted in Uncategorized by Kenny Yuan on 2010/05/12
  1. HDD的C:盘比D:盘快
  2. LCD的黑屏和白屏几乎一样费电
  3. Cache大了不保证CPU更快
  4. CPU和compiler相互影响设计方案
  5. 32位机可以管理超过4G的地址(数据总线和地址总线是两回事儿)
  6. 虚拟机技术的流行是在个人电脑出现之前
  7. 低优先级process可以优先于高优先级process被OS调度运行
  8. 实时OS(或程序)不代表速度快
  9. srand()时用奇数效果更好
  10. main()函数不写return也会返回0
  11. C++中不存在所谓的“默认位拷贝copy ctor”或者“默认位拷贝assignment operator”
  12. LISP不是编程语言
  13. Fortran有好几十年都没有递归
  14. 最早的高级语言连if-else都没有
  15. Pascal是编译到字节码的(第一个推广使用字节码的)
  16. “内存分Stack, Heap和自由存储区”这种很多年前流行的说法有概念错误
  17. quick sort也可以是stable
  18. 有些Tree比Hash快
  19. “关系”是指笛卡尔积的子集
  20. NTFS其实也有链接
  21. 编译器每18年性能翻一翻
  22. 关于Windows/Mac/Linux的优缺点,有无数的谎言
  23. 电磁辐射是人类生存之根本
  24. 以上均为true

如何在午休时间写一个QT程序以便能够挣到同事的五毛

Posted in Uncategorized by Kenny Yuan on 2010/04/28
作者的话:本文有两个目的:1、Zhuangbility;2、教你如何变成五毛;3、展示QT的生产力。
译者的话:本文并非虚构,是真实发生过的——如有雷同你肯定认识我,欢迎到我座位这边来喝可乐(你一定知道这个典故的)

在30分钟内用QT写一个抓屏程序

(注:Qt这个词应该读成Cute,而不是Queue-Tee)


※ ※ ※ ※
叮咚、叮咚、叮咚——00:29:59
叮咚、叮咚、叮咚——00:29:58
叮咚、叮咚、叮咚——00:29:57
※ ※ ※ ※

此截图程序可以实现以下功能:

+跨平台运行
+可以截取全屏幕或者其中一部分
+鼠标选中的区域为高亮,未选中的区域亮度减半
+截屏后可以反复选择,直至满意为止
+保存文件到桌面并退出
+复制图像到剪切板并退出


※ ※ ※ ※
叮咚、叮咚、叮咚——00:25:59
叮咚、叮咚、叮咚——00:25:58
叮咚、叮咚、叮咚——00:25:57
※ ※ ※ ※

整个程序主要有三个关键点:(1)抓屏到内存;(2)随着鼠标选取,加亮显示内存中的图片;(3)将图片的一部分保存到剪切板或者文件。
在QT中,这三个问题很好解决,问题(1)可以直接调用QT函数:

    QPixmap px = QPixmap::grabWindow(QApplication::desktop()->winId())

※ ※ ※ ※
叮咚、叮咚、叮咚——00:24:59
叮咚、叮咚、叮咚——00:24:58
叮咚、叮咚、叮咚——00:24:57
※ ※ ※ ※

问题(2)也不难,只需要提前做一点点工作,在抓图后保存两个图片,一个是正常的,另一个是变暗之后的:


    screen_ = px.toImage();
将刚刚截屏得到的图像转换成设备无关的内存表示
    darkScreen_ = screen_;
在内存中对RGB减半处理,使图像变暗,先计算每行的字节数:
    int bytesPerLine = darkScreen_.width() * darkScreen_.depth() / 8;
然后处理每个行
    for ( int i = 0 ; i < darkScreen_.height() ; ++ i )
    {
        uchar* lineBuf = darkScreen_.scanLine(i);
scanLine函数可以取得指定行的起始指针,不必再自己计算了。取得行指针后对每像素RGB值进行操作
        for ( int x = 0 ; x < bytesPerLine ; ++ x )
            lineBuf[x] /= 2;
    }

在这里没有尝试加速图片变暗的过程,效率问题最后再综合考虑。

※ ※ ※ ※
叮咚、叮咚、叮咚——00:22:59
叮咚、叮咚、叮咚——00:22:58
叮咚、叮咚、叮咚——00:22:57
※ ※ ※ ※

有了这两张图片,就可以进行绘图了:

void Widget::paintEvent(QPaintEvent *)
{
声明绘图对象,目标为窗口
    QPainter painter(this);
全屏绘制暗图像:
    painter.drawImage(0, 0, darkScreen_);
在选定的区域绘制亮图像:
    painter.drawImage(currentRect_, screen_, currentRect_, Qt::AutoColor);
}

currentRect_是在鼠标事件中保存的当前选择区域,它的计算也很简单,在鼠标的移动消息处理器中:


void Widget::mouseMoveEvent(QMouseEvent * e)
{
    if ( dragging_ )
        end_ = e->globalPos();
保存旧区域,用于后面的区域合并
    QRect oldRect = currentRect_;
设置新区域
    currentRect_.setTopLeft(start_);
    currentRect_.setBottomRight(end_);
调用normalized函数解决负宽度或者负高度问题
    currentRect_ = currentRect_.normalized();
QRect::united()函数用来求两个rect合并后的rect,可以省去许多手工计算。
且QT的repaint()函数也不需要关心背景擦除问题,QT4以上都是自动double buffer
    repaint(oldRect.united(currentRect_));
}

至此,问题(2)处理完毕。


※ ※ ※ ※
叮咚、叮咚、叮咚——00:18:59
叮咚、叮咚、叮咚——00:18:58
叮咚、叮咚、叮咚——00:18:57
※ ※ ※ ※

为处理问题(3),需要得到指定图像的指定区域,并且一个图像对象来表示。将这个功能编写成以下辅助函数:


static QImage clipImage(const QImage& srcImage, QRect rect)
{
    QImage image(rect.size(), QImage::Format_RGB32);
    const QImage* target = &srcImage;
    QImage targetImg;
    if ( srcImage.depth() != 32 )
    {
        targetImg = srcImage.convertToFormat(QImage::Format_RGB32);
        target = &targetImg;
    }
    int bytesPerPixel = image.depth() / 8;
    for ( int i = 0 ; i < image.height() ; ++ i )
    {
        uchar * line = image.scanLine(i);
        const uchar * srcLine = target->scanLine(rect.top() + i);
        memcpy(line,
               srcLine + rect.left() * bytesPerPixel,
               rect.width() * bytesPerPixel);
    }
    return image;
}

这个函数有点长,但思路却很简单:
1、先创建一个小图像,宽高与选区相同
2、取得源图像的数据,复制到小图像中
3、返回小图像

有了这个辅助函数之后,想保存文件,就可以这样写:


QImage img(clipImage(screen_, currentRect_));
img.save(pathName, "png");
想把图片放到剪切板的话,可以这样写:

QApplication::clipboard()->clear();
QApplication::clipboard()->setImage(clipImage(screen_, currentRect_), QClipboard::Clipboard);
QImage(QApplication::clipboard()->image(QClipboard::Clipboard)); // Retrieve data from clipboard to make it owns the data

※ ※ ※ ※
叮咚、叮咚、叮咚——00:10:59
叮咚、叮咚、叮咚——00:10:58
叮咚、叮咚、叮咚——00:10:57
※ ※ ※ ※

再往下就是处理一些鼠标和键盘事件,比如在双击时复制到剪切板并退出,在按Ctrl+S时保存到文件并退出,按ESC时直接退出,等等

最终完成,编译,修改typo并运行,发现速度还可以,故取消profiling和性能调优计划,直接和DLL一起打包。至此任务完成,领取五毛工资。


※ ※ ※ ※
叮咚、叮咚、叮咚——00:00:09
叮咚、叮咚、叮咚——00:00:08
叮咚、叮咚、叮咚——00:00:07
叮咚、叮咚、叮咚
叮咚、叮咚、叮咚——00:00:05
叮咚、叮咚、叮咚
叮咚、叮咚、叮咚——00:00:03
叮咚、叮咚、叮咚——00:00:02
叮咚、叮咚、叮咚——00:00:01
叮咚、叮咚、叮咚——00:00:00

(EOF)
Tagged with: , ,

On Computer Programming Paradigm

Posted in Uncategorized by Kenny Yuan on 2010/02/24

Once again, 我又title party了。其实本文就是一个关于Programming Paradigm关系的个人总结。废话不多说,上图:

(最后一条是八褂)

P.S. 关于Paradigm的翻译,见过一些人翻译成“范形”的。但我不太喜欢这样说,因为在口语中会有混洧(“泛形”);而且我发现不少人在第一次接触“范形”这个词的时候会误解它的意思。所以我更倾向于把它叫做“编程方式”——在口语中也正是这样用的,比如:

——Bjarne S.:你准备用什么方式来写这种程序呢?

——John M.:当然是用LISP写一个Domain Specific Language,然后再混合一些面向对象的编程方式

Tagged with: ,

这是你应该做的

Posted in Uncategorized by Kenny Yuan on 2009/12/04

——“阿姨!你的钱包掉了!”
——“谢谢你!小朋友!你真是一个心灵高尚的人!”
——“不用谢!这是我应该做的,我的名字叫少先队员……”(伴随着一串银铃般地笑声,小朋友消失在风里,没有留下姓名……)

嗯,我承认这是恶搞了一把那个年代的小学生作文——韩寒出现之前的那种小学生作文。这种作文中有一个隐含的前提:“拾金不昧、做好事不留姓名”这种事情,在那个时代的背景下,会被判断为“这是我应该做的”。


那么,在换了一个时代背景之后,什么才是“你应该做的”呢?或者我们换一个容易观察的角度——在一个特定的职业中(医生/教师/学者/警察/记者/公仆/开发商/律师/法官/摔倒的老太/etc),什么才是“你应该做的”呢?怎样算是平庸?怎样算是正常?怎样算是杰出和优秀?做到什么程度才算是完成了本职工作,才算是完成了“你应该做的”事情?

——既然我这个BLOG是和“码农”这个职业息息相关的,那现在我们就假设你是一个码农:

你精通各种算法,宰杀了无数遍“猪”与“鸡”(珠与玑),对RBTree/BSPTree/SuffixTree/HashTree的原理和应用张口就来;你会估计和比较各种算法的O/Θ/Ω/OO;你知道如何深入浅出地讲解算法,知道如何编程实现和实测的表现,你还能够在实际工作中选用正确的算法……那么,你觉得自己很优秀,还是说“这是你应该做的”?

你精通不少语言,也精通一些很“难”的语言中的很“讨厌”的特性,比如C++中的重载决议/偏模板特化/名字空间/多继承/etc,你还能够紧追语言的“最新发展”,对GC/closure/multimethod/Continuation/AMB这些“新发明”的东西了如指掌(嗯,好吧,其实这些不是新的,只是从LISP那里借鉴了一下下)……那么,你觉得自己很优秀,还是说“这是你应该做的”?

你懂得多数流行平台的开发,掌握多数开发包的API;你能够使用各种辅助工具进行综合、高效地调试;在解决问题时你有丰富的经验和清醒的头脑,以及实证至上的谨慎;你对开发/profiling/testing有良好的理解和实践,模式/重构/TDD/etc对你来说是合手的工具而不是限制你的牢笼……那么,你觉得自己很优秀,还是说“这是你应该做的”?

你了解不同用户的兴趣在哪里、对软件错误的容忍度有多高,你知道不同设备上的用户习惯于如何操作,你知道用户愿意在哪个功能上掏钱,你懂得如何借鉴和超越竞争对手的产品,你能够跟上当前用户对功能的期望(甚至预见到未来的)……那么,你觉得自己很优秀,还是说“这是你应该做的”?

你了解可用性的意义、懂得色彩学,能够设计出有条理、不凌乱的界面,能够发明用户喜爱的操控方式,能够设计贴心、聪明的功能,还能够用PS/AI/Painter制作素材,并且用程序实现你的设计……那么,你觉得自己很优秀,还是说“这是你应该做的”?(另,引用:“说一个软件具有‘可用性’,能算是一种赞美吗?只是合格罢了!”)

你精通计算机原理结构,知道各种外设的IO速度,对它们访问方式有精晰的理解,会写device driver,而且你还知道典型外设产品的可靠性在什么样的数量级上……那么,你觉得自己很优秀,还是说“这是你应该做的”?

你设计过不同规模的系统,知道在什么样的级别下应该使用什么样的技术;你知道性能热点通常在哪里,也精通于查找和解决热点;你知道如何平衡功能、时间和质量,知道如何在特定情况下取舍;你知道流行的架构的优缺点,你知道哪种硬件能够构成什么样的系统、当机时间控制在什么样的级别上;你知道如何安排指标去区分高低端产品,知道在给定的预算/成本下能够提供什么样的产品,你还知道如何对系统进行cost down却不会损失可靠性……那么,你觉得自己很优秀,还是说“这是你应该做的”?

你熟悉各种软件开发模式;你有丰富的知识积累,却又不守旧、勇于接受新鲜事物;你非常善于开会,能够在很短的时间内取消语言表面上的分歧让大家达成一致……那么,你觉得自己很优秀,还是说“这是你应该做的”?

你勤劳肯做,工作中不偷奸耍滑,很有大局观而且也重视细节问题;你性格温和,乐于助人,团队成员都说你是一个非常好相处的人,连没见过面的同事也对你赞不绝口……那么,你觉得自己很优秀,还是说“这是你应该做的”?

……

造句练习:你能够……能够……还能够……即使在XX的时候也能够YY……那么,你觉得自己很优秀,还是说“这是你应该做的”?

……

如果你做到了以上若干条(注),那么在我看来,你成功地完成了你自己的本职工作,完成了自己做为一个工程师(而不是科学家)的“应该做的事情”——也许你比身边人的平均水平要高出一截,也许你超过了整个业界的平均水平,但那是不是就意味着“优秀”呢?如果那仅仅是你“应该做到的”呢?

最后,你做为一名人类,能够进行独立的思考,在清晰逻辑和丰富知识的基础上拥有批判性的思维,你懂经济、懂民主;你不愤青、不脑残、不意淫、不从众;你不受洗脑和煽动的影响、不信武术和中医……那么,你觉得自己很优秀,还是说“这是你应该做的”?

……

在你的眼里,什么才是“你应该做的”?

……

延伸阅读
(下面的每一个链接都能对应到上面文章里的某句话,用来例证,而不是证明)
Teach Yourself Programming in Ten Years, by Peter Norvig http://norvig.com/21-days.html
The Pragmatic Programmer 注重实效的程序员, 中文摘录版 http://qiri007.spaces.live.com/blog/cns!99F80D7BAD95F281!8913.entry
Algorithm Repository, by Steven Skiena http://www.cs.sunysb.edu/~algorith/
快排为什么那样快, by Pongba http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/
Beating The Averages, by Paul Graham http://www.paulgraham.com/avg.html
http://www.xys.org/xys/ebooks/others/science/dajia10/zhongyi2621.txt
97 Things Every Software Architect Should Know, http://97-things.near-time.net/wiki/97-things-every-software-architect-should-know-the-book
Anti Pattern, KornerHill译自Wiki http://blog.csdn.net/KornerHill/archive/2008/05/03/2373577.aspx
常见逻辑谬误(转) http://groups.google.com/group/pongba/browse_thread/thread/2cfa868f6a098d6b/7e300428d0bd8866
Java语言学校的危险性, by Joel Spolsky, 阮一峰(译) http://www.ruanyifeng.com/blog/2008/12/the_perils_of_javaschools.html
What Every Programmer Should Know About Memory, by Ulrich Drepper
Proebsting’s Law, by Todd Proebsting; Moore’s Law, by Gordon Moore

注:上面列举了许多的条目,但是这些条目涉及了很多领域,所以并不要求一个人同时具备这些能力。

(完)

Tagged with: ,

1990-1995年间学习编程语言的回忆录

Posted in Uncategorized by Kenny Yuan on 2009/08/17

绝对必要、又臭又长的作者声明:
1、虽然是回忆录,但本人是码农不是艺妓,想来看艳情的可以洗洗睡了。(推荐你看《往事回忆录》,那个很艳情,而且不黄不暴力)
2、我不是成功人士,想看成功人士的奋斗经历来励志的,可以关窗口了。(推荐你看《小兵传奇》,那个很成功、很励志)
3、我没开发过大项目,想看内核技术和巨型软件构建经验的,可以打酱油了。(推荐你看最近出的写WinNT故事的那本翻译书,不过我还没看过,只是听说不错)
4、我没有高学历,想围观高学历的地球原住民的,可以飞过、飘过、走过、路过、虫洞过了,这里没沙发。(推荐你看《新语丝》,有闲心的还可以去找找,看到底在加州理工的CS博士列表里面有没有唐峻)
5、写回忆录不是为了要显摆什么,记忆中是什么样就怎么写(当然,记忆重构是无法避免的)。本人绝不像某些国内伪专家一样装B,别人说什么东西好的时候,非得过来插一句说“我XX年前就见识过了”。那种人我最讨厌了,所以本文绝无半点那种倾向。所以,如果想跟我学装B也不要往下滚动了,我这人的特点是有一说一,认为自己好的也说,认为自己差的也说。(装B最好的方法是把一些人人尽知的东西,另一群不知道的人中传播,最好自己写BLOG来传播,参考经典著作而不要直接抄袭,这样最能装B!)
6、本人今年30岁,在1990年的时候我11岁,科特学习机也已经上市,已经具备了学习计算机的生理上的可能性,和客观条件上的可能性。各位福尔摩斯和柯南们可以回家了。

Basic

Basic是我编过的最多程序的语言,没有之一。虽然后来工作后也写过一些30-50MB CPP源码的项目,但我一直坚信BASIC是我写过最多程序的语言(大约是因为易得性直觉吧,估计真实数据不是这样的)。当时的BASIC是我自己唯一拥有的计算环境——科特学习机的F-BASIC。Basic是我见过的第一种编程语言,在我还没学会打字的时候就开始用它编程了。当时最大的愿望是写一个游戏程序。现在回想起来,这算是家长禁买游戏卡带给逼出来的发奋图强了。

当时的F-BASIC里有背景图可以组成画面,有超级马利中多数的卡通角色可以用程序控制。编写一个游戏程序从技术上看起来是可行的,而且我还有大量的时间,没有资金预算的问题——虽然这个项目的可行性评估完美通过,但最终还是理所当然地失败了,这是我人生中的第一个失败的软件项目,住在100公里外的表弟最终也没有能够玩到我写的游戏。原因倒是很简单:F-BASIC没有BASIC中的陷阱编程(一种类似于中断的东西,可用来捕获键盘输入),无法及时控制卡通人物行动,运行速度也太慢。这件事情的“蝴蝶效应”直到现在还余波未消——在讨论可行性的时候,我总是习惯于搞清楚“是不是真的可以”,不满足于从文字中求证,而是要测试过才放心。(当然,从另一个角度来看,所有的技术问题最终都是管理问题,这就是另外的话题了)

虽然游戏项目可耻地失败鸟,但收获还是有的。最大的收益就是学会了将问题转换为计算机表达,比如讨厌的约瑟夫问题,我一直不会用公式计算,都是在纸上画圈圈和叉叉,挪到计算机上还是挺节约白纸的;小学奥赛的经典名题“鸡兔同笼”在穷举法面前也不堪一击(虽然有无数求解公式,但我一直记不住);在《世界数学名题趣谈》上看到的那个可以计算PI值的无穷展开的算式,我也是没有用笔算的耐心的(如果让我也算出几百位PI之后发现出错了,同样也会吐血的),所以,写个分数运算程序,用计算机来运算还是很爽的——虽然当时的字串最长仅允许32字节,即使拼起来用,最终算不出几位有效数字。

在这种简陋的F-BASIC中,我还体验了一把“多媒体编程”。使用F-BASIC中的PLAY语句,播放三个声部的伴奏乐谱,然后录下来给音乐老师作教学用,作为交换,我可以弹她的电子琴。因为直接写那些不断重复的“CDEFGAB”唱名字串很繁,我开始用程序来生成字串,这是我第一次接触到程序和数据之间的相互转化问题。但很遗憾地是,F-BASIC不能由数据生成程序(如果有向磁盘LOAD和SAVE的标准BASIC倒还可能,F-BASIC是向录音机存储数据的)。后来当我见识到了eval之后不由得大喜过望——数据向程序转化的东西终于有了。

除了这些之外,BASIC对我的负面影响也很大,比如良好命名,模块划分等方面,它带给了我许多不好的习惯。这些在后来学习LISP的过程中阻碍了我很长一段时间,后来才慢慢改掉。记得有句名言说第一个学BASIC的程序员不会是好程序员,但我感觉这话太过绝对了。或许它表明了一种趋势和倾向,但并不是一定如此。人,长着脑袋,就是用来学习和改进的。

dBaseIII

中国最早的信息化就是用的这玩意,无数个单位买来“先进”的286微机就是为了“会计电算化”或者“电子信息化”,所用的工具九成九都是dBaseIII。当时的教育台里也总会有一个戴着龟壳大眼镜的谢顶老大爷,操着难懂地普通方言话,来讲解dBaseIII。我一直没有把dBase系列看成一个真正的计算机语言,最初以为它是数据库,现在觉得它是个带一定编程手段的查询语言。当时听说它比COBOL要先进不少,所以为了迈向“高大全”的目标,就把它顺便也学了。后来的《跟我学电脑》丛书,第四册整本讲的都是dBaseIII,我翻了无数遍,在纸上默写语法和程序,并且将样本数据进行了演算,最终搞明白了这种“语言”。借着为某些单位修理dBaseIII系统的机会,我“偷”到了不少上机时间。另外,在纸上推演dBaseIII数据的时候,也被迫学习了索引/二分之类的基础知识,认识到了算法和数据预处理的重要性,为后来学习《数据结构》等打下了基础。

Lisp

Lisp一直是我最喜欢的语言,没有之一;但LISP也是我一直没有能够掌握的语言之一(这回有“之一”了)。

我是在《跟我学电脑》那套从书中的《计算机语言发展历史》章节中知道LISP的,而且听起来它有一个很牛B的名字——人工智能语言。当时的中央电视台的译制片栏目放了一部195x年的美国电影《地球停转之日》(不是后来Keanu Reeves主演的那个翻拍版本),那里面的机器人功能很牛B,而且能听懂外星主人的语言,甚至人类小妞学着说的时候,它还知道把人类小妞给保护起来——我当时就认定这机器人一定是人工智能的了。于是就买了LISP的书来学习。这本书里讲的是Sun工作站上的Common LISP,还附带讲了LISP机的辉煌历史——这让我后来很自然地就接受了“用IDE工作”的理念,而且在相当长的一段时间排斥命令行编译(直到后来学了GNU MAKE才改正过来)。当然,对于LISP机关掉GC等待内存耗尽的故事,那本书里是不会讲的。这也是中国“学者”的通病,如果他说什么东西是好的,就只说优点不说缺点。这一点读书时一定要注意。

LISP对我来说的一大特点就是自然,计算机不像BASIC那样地讨厌,而是变成了一个很自然的描述工具。现在想来,这和LISP的历史渊源是有很大关系的——LISP最早就是John McCarthy发明的一种数学符号,而不是一种编程语言。只不过他的一个学生偶然在IBM 704机器上实现了可以解释执行的计算机语言LISP——关于IBM 704 blah blah这一大段是我死记硬背的,我这辈子还没见过这种机器,估计也没机会见识了。

正因为LISP的原始发明意图就是在纸上推演的数学符号,所以使用它的时候完全感觉不到太多的障碍,这种障碍在别的语言中有很多表现,这里就不一一举例了,相信大家都有体会。LISP的这个渊源,对当时的我来说,还有一点有着非同寻常的意义:它可以在纸上演算并求得结果,求解过程是可以直接用人类的大脑来做的,而不像C语言那样几乎不得不用机器语言来做。举个例子,虽然CAR这个函数名称的由来和寄存器有关,但是它却有着非常直观的含义——砍掉LIST中的第一个元素:(car ‘(1 2 3)) -> (2 3)。至于为什么我得在纸上演算,原因很简单:在那段时间里,如果一个中国的初中生能够接触SUN的小型机,那他一定是牛B到不能再牛B的人物——很明显我不是,所以我只能在纸上演算。

虽然LISP很直接和自然,但当时的我只有初二数学水平+一门粗浅握的《逻辑代数》,又没有太多的编程实践经验,所以对于某些东西的掌握还是很困难的,比如“闭包”这个怪物的意义,就让我困惑了很多年,直到后来看到了它和对象的等价式后才恍然大悟)

学习LISP对我的影响很大,从小的方面来看,有“看得见的万能之手”——完美的MACRO系统;递归——人来负责简洁清晰的算法,机器来负责提高运算效率;GC——白胡子老管家式的周到服务;程序和数据的大一统——后来知道这叫S表达式;IF-ELSE——这个也是LISP的发明人John McCarthy在LISP里发明的(不是ALGOL 60),嗯,我承认这一条基本上是用来刁难人的;从大的方面来看,学习LISP让我开阔了视野,在后来的许多年里,都只把C风格的语言当成低级语言,而没有陷入语言成瘾的状态,对于2000年以后流行的各种语言也持有一种积极接受的态度——本来这些就都是从LISP里拿来的嘛!记得有一句名言,大致是说:1、世界上只有两种计算机语言,C风格的和LISP风格的;2、一个现代语言的发明,就是在C的风格基础上借用一些LISP的“先进”概念(比如精通LISP的James Gosling发明了带有GC的JAVA)

Prolog

最早知道Prolog还是在《跟我学电脑》那套书里知道的(若干年后才知道是自大的法国人强行发明的),当时书中称这种语言是“下一代的计算机语言”,是计算机业的未来。为了“不输在起跑线上”(当时很流行这句话),我立即就去把书买了回来,虽然不时地翻出来看,但一开始根本就没看懂;而且这本书上说:对于学生来说,同时学习Prolog和LISP是很难的事情,因为风格不统一。我当时在学LISP,所以Prolog就放弃了好长一段时间。

后来在某一天,偶然翻看Prolog的时候,我突然间就顿悟了(不过我没有像阿基米德那样光着屁股裸奔)。比如在Prolog里定义一个逻辑关系,根本不用像BASIC那样绞尽脑汁定义变量存储,也不用像LISP那样编写函数去递归求解,如果我说farther(A, B).的话,那就是有一个A是B的父亲,至于A和B是什么,Prolog不知道、也不必知道,甚至对于father这个谓词它也不知道,它只知道这其中的逻辑关系。当然,如果仅仅能够接受这样的输入,也没什么意思,但Prolog可以在这些云山雾罩的关系的基础上,继续定义逻辑关系,并且最终还能自动求解,比如:定义一个grandfather,就可以在father的基础上定义谁是谁的爷爷(多说一句:Prolog默认没有交换律——请按群论来理解这个“交换律”的意思)。

过去学的种种语言,无论是LISP、C++还是BASIC,编程的人都得替计算机想出如何求解的过程来(不论看起来复杂的迭代,或者看起来简洁的递归,其实都是在定义求解的过程),而且往往还得发明一些东西来帮助计算机:比如用BASIC这样的东西来求解约瑟夫问题,还得用自定义规则,用来模拟语言本身不支持的链表结构。但是Prolog就不一样了,它就像一个解题机器一样,你告诉他一堆事实和规则,然后就可以提问了——完全不需要告诉它解题的“过程”。Prolog其实也并不知道答案“到底是什么”,但是它可以按照你定义的规则求解出你所需要的答案(可能需要多打几次分号)。至此,我发现我的逻辑代数白学了,学一个简单的Prolog语法就全部解决了嘛!

从那以后,我一直疑惑为什么LISP被称为人工智能语言而Prolog不是。而且“谓词”这个概念被我深深地记在了心中。到后来听说ISO14882 C++98标准中竟然有谓词Pred,我着实兴奋了好久,但后来仔细一研究,原来跟Prolog的完全不是一回事。不过,C++模板编程在某些方面来看倒是很有Prolog的风格,这也是有一段时间我不自觉地陷入了“template误区”的原因之一。

C++

借一句当年流行的歌:“你这样,一个语言,让我欢喜让我忧……”。最早我学C++仍然是因为《跟我学电脑》这套丛书,那里面介绍了B语言转化为C语言,然后升级为C++语言(根本没提和UNIX的关系!)。既然要学,那我就学一个最好的吧!于是就略过了C,直接学的C++。所以在之后的10多年里,我一直很鄙视“学C++必定要先学C”这样的说法。当时买的是张国锋写的C++的书,大约是91年版或者92年版的,只是在讲语言,没有讲编译、链接和调试。因为我是BASIC出身,又喜欢LISP,所以在“如何将程序变为机器码”这一环节是一直是缺失的,直到后来整了一套Visual Studio 97(VC++ 5.0)的光盘才真正开始熟悉整个的编译-调试过程。我还记得第一次碰到“找不到链接符号”这个错误时,我用了好几天才搞明白是函数体忘了写。在这方面的知识一直仅仅是够用,直到后来在做过一个集成开发环境(IDE)后才得到了加强:许多问题都是在解析过OMF文件信息之后才真正理解的。因为自己有这一段经历,所以我在教别人的时候一直强调:第一天就必须要上机来熟悉开发环境。懂得如何生成代码和调试代码,是作为一个编译型程序员必不可少的技能。

C++的教材在讲class的时候喜欢用复数(complex)作为例子。对于当时只有初中二年级数学知识的我,这就不啻于天书了,许多年一直没能明白虚、实分量的相加代表了什么。还好里面有一个动物的比喻能够帮我理解OO的概念。但也仅限于封装、继承、多态等基础知识,很长一段时间我没有意识到C++是多范型的程序语言。后来我学习C++开始转向“实用”这个“目标”(其实是学Windows SDK):先是学习了MFC,然后开发过许多控件和程序,帮老师做过学校的课题,往杂志投稿过一些VC程序,大约在99年左右,我开始有些飘飘然了,觉得C++不过尔尔(其实是连C++和VC都没分清)——这种心理一直持续到大约一两年后,有一次偶然在CSDN上看到某装B人士,正在以极为不屑的态度批评一个发贴者不懂“面象对象”,他祭出的武器就是OCP。经过google得知OCP的内容后,我不由惊叹“此为神器也!”,继而开始拜读Bertrand Meyer的《OOSC》,从此再也不敢“翘尾巴”了。之后的许多年里,我一直在观察周边的人,发现许多人的OO教育从一开始都是错的。我认为这不仅仅是我本人的一个教训,也是教育的失败:当你让学生接触到某种东西的时候(例如OO),只给他看一些零碎的基础概念(封装、继承),教一些基本的实现手段(语法),从来不说这种东西的思想精髓在哪里(OCP/LSP/etc.),也没有提供任何延伸阅读材料,反倒是在一个封闭的小圈子里不停地说这东西好,这东西就是某个样子的——事实上这个“样子”却违悖了其中的精髓思想,而且一说就是十多年不间断(因为教材是抄来抄去的?)。若干年后,某些曾经被错误教育的有识之士终于意识到了问题,从国外重新引进了原本的精髓思想。但也已经无法成为主流了,错误积累的太过深重,OO本身已经完全毁掉了。

说到C++几乎不得不说《设计模式》。国内的中文译本大约是在2000年出版的。在当时设计模式很受人们推崇,给人一种万能药的感觉,仿佛有了它中国就不必再担心软件结构的设计问题了。在我看来这又是典型的“大炼钢铁”式的思维——一味地追寻成功者的足迹,不管是不是充分条件(甚至不管是否必要)。我一直觉得设计模式在国内吹嘘得过分了。从OCP等原则出发,可以推出许多模式;从LISP语言看过去,许多模式就是一陀额外的屎——但是这个想法一直不敢太公开(人微言轻啊),直到后来读到Peter Norvig的那个Presentation。

C++的98标准及相关的一些知识是在CSDN论坛上得知的,后来疯狂地购买和阅读C++的相关书籍,几年后名单上的差不多有20本书以上。至此,算是重学了一遍C++(书单中还真包括一本《C++ Primer》)。看过之些书这后,在之前的OO的基础上,明白了对象模型的细节,熟知了STL和模板的应用(甚至有超级古怪的应用),熟记了一些常见的陷阱和Workarounds,甚至还背诵过三字节操作符这样罕见的东西。现在回想起来,学习这些东西的机会成本,其实还是蛮高的。

古老的C++语言因为泛型编程而焕发了“第二春”,但我对C++语言的兴趣却开始慢慢消失。虽然一直还在关注着这一领域,但也只是在关注了。从网上随处可见的关于C++的争论之中,我能体会到一些人不是因为理智,而是因为某种情结和瘾癖而在捍卫着C++,他们的思维陷入了一个怪圈中。一开始我觉得这是因为见识的问题,后来意识到,归根结底还是因为open mind的问题。等到了“否定C++以外的东西”成为了你的第一反应的时候,或者当你总是下意识地寻找和传播C++的好处的时候,你的大脑很可能就开始封闭了。这是一件很危险的事情,而且更危险的是你自己很难意识到这种状态。有一段时间,我曾经几乎要陷到这种状态当中去,幸运地是,偶然有一次聊天时说到LISP,在我向别人介绍LISP的强大的同时,我突然感觉到天灵盖处的一阵颤栗,仿佛冥冥之中的设计好的某段程序重新启动了,十年前学习各种编程语言时的感受重新涌入了大脑,迫使几乎侵占了所有地盘的C++重新回归了它应该有的位置。后来LP推荐《心理学》给我看。在此之前,我曾经因为一本特别差劲的教材,而误解心理学为伪科学——这一错就是十多年!在LP的推荐之下,我看了David Myers的《心理学原理》,才终于接触到了真正的心理学(其它好书也有一堆,这里同样就不列举了)。学过了心理学之后,我对自己当时的心态也就有了一个更加清醒的认识。我决定把这些写下来的原始动机,也是为了总结+自醒,也供他人借鉴。

Pascal

将Pascal写进来有点时间线的问题,因为Pascal是在上高中为了参加奥赛而学的。但既然上面讲C++时,已经说了后来发生的事情,这里也一并说一说吧:Pascal语言,我也是对着书在纸上啃下来的,没有上机。有了前面学过的那些语言作为基础,学Pascal只用了不到一周的课余时间。这个事情对我的影响却是负面的,有很长一段时间,我错误地以为学习一门新语言是简单地事情——有了原来打的基础,学习语言本身的确是很简单,但是我却忽略了程序库的重要性。我一直不会JAVA语言就是因为它的语法太平淡了。虽然我在上大学时,也有过一本1000多页的《JAVA内裤大全》,但JAVA还是被我给错过了。

(更新:昨天浏览了一下,发现写出来一个大BUG,看来狂打字的时候脑子果然是不灵光的,但既然这么久过去了,BUG我也不改了,留着给人用来挑错吧,呵呵)

Tagged with: ,

科普一下算法的度量——Big O, Big Omega, Big Theta以及Udi Manber的大OO

Posted in Uncategorized by Kenny Yuan on 2009/05/20

[引子]
在很久很久以前……久以前……久以前……久以前——有一个阿拉伯的故事……伯的故事……伯的故事……伯的故事——故事的发生是这样的……是这样的……是这样的……这样的——大约是90年代初期,当时还算天真无鞋、聪明蟀气的俺,一不小心看到一本老教授们给小盆友们编的奥赛辅导,里面给出了一个无法证明但是被我无数次证伪的公式:程序=算法+数据结构。于是我立即去买了《Data Structure》,也就不小心中了绿毒(Pascal第一版),大学时又被迫买了蓝毒(ISBN7-302-02368-9)

(据说ISBN自带校验,码矩为2,哪位达人可以算一算,看我上面抄写的书号是不是有问题?严重怀疑俺们大学老师卖D版书的说)

现在终于可以开始解毒:科普一下算法的度量——Big O符号、Big Omega符号和Big Theta符号的区别,以及Udi Manber的大OO符号

[正文]
大O符号是德国人Paul Bachmann在1894年引入的,此人精通数论,研究过费马大定理。在他生活的年代还没有计算机,认为mathematics在CS中灰常重要的人可以长笑三声了(当心引来一个红脸的放屁虫)

定义啊定义
–> 正常人类请跳过,火星人驻足,金星人可以去逛街了
A、大O的定义:
如果存在正数c和N,对于所有的n>=N,有f(n)<=c*g(n),则f(n)=O(g(n))
B、Big Omega的定义
如果存在正数c和N,对于所有的n>=N,有f(n)>=c*g(n),则f(n)=Omega(g(n))
C、Big Theta的定义
如果存在正数c1,c2和N,对于所有的n>=N,有c1*g(n)<=f(n)<=c2*g(n),则f(n)=Theta(g(n))
(友情提示:大O和大Omega主要是>=和<=的区别)

简而言之
–> 正常人类观看,火星人请去multiverse求解EPR paradox(http://en.wikipedia.org/wiki/Epr_paradox),注意不是ERP,这个EPR和空洞骗钱的企业软件ERP不一样(其实EPR比ERP更加“空洞”,呵呵)

重来重来,呵呵——简而言之,广而告之:
1、O是一个算法最坏情况的度量(悲观主义者喜欢这个符号)
2、Big Omega是最好情况的度量(favorite notation of optimist)
3、Big Theta表达了一个算法的区间,不会好于某某,不会坏于某某(不这就是中庸之道嘛,偶喜欢)

不管是O,Omega,还是Theta,都隐藏了常量C的信息,因为一般来说这个常量是不重要的,当n值变得很大的时候,对时间和空间的耗用,还是由函数本身的阶来决定的。如果n很小,用什么算法都可以,所以我们一般用极大的n值来对比算法的优劣。但是在实际使用算法的时候就要注意,如果n值不大,就先去优化别处吧!

如果想看些具体的例子可以到这里:http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic3/

可能会有人极不赞同“常量C不重要”这句话,举(抬)一个例子:如果C=10^80(也就是宇宙中的粒子数量),那该怎么办?

先不说这种杠抬得是不是“欠抽”,因为一个自洽的系统欢迎任何抬杠,但是在编程时多半是不行的。别说这么大的常量复杂度了,就是用些边界条件,随手往里抛一些“单位元”或“逆元”,不少算法都会趴下。(用人类语言解说上述名词的结果为:单位元——0或1,视加法群和乘法群而定;逆元素——改变正负号。参见代数系统中群的概念http://en.wikipedia.org/wiki/Group_(mathematics) 注意wiki中的链接是有后半个括号的)

如果你也认为常量C很重要,那么恭喜你了——不光是geek和IT愤青,连Udi Manber(http://manber.com/)也是这么想的!Udi提出了一个新的符号,OO,用来表达这个常量C太大的情况。如果O(n)=1,但是未能表达出来的那个邪恶的常量C,其真实的取值是10^80,那个,这个算法还是不能被使用。

多八褂一句:Udi Manber后来去了google,还做了VP。想来也对,做算法(尤其是搜索算法)和网络研究的大牛,去google工作也算是众望所归吧。

[伊索寓言式的结论]
这故事是说,学习要先找对教材。:P

Tagged with:

我为什么学习了编程

Posted in Uncategorized by Kenny Yuan on 2009/05/20

大约是小学3年级到4年级的时候,我从家里的大书架上翻出一本书,书名大概是《逻辑代数及其应用》,浅灰色的书皮,上面有很多类似电路的纹路,还印着好多算式,差不多就是下面这样子:

0+1=1
1+0=0
0+0=0
0*1=0
1*1=1
0*0=0
……

一看到这本书,我立刻就开始喜欢了——WK!真是太简单了!都是0和1,连2都没有哇!太好了,我就学它了!

于是,就开始慢慢陷入了“英国人不说谎话”和“法国人才买机票”的一类的问题中……

P.S.上初中的时候学习了Prolog,目的就是从不再做人肉解题机。可惜现在几乎全忘了

再P.S.推荐一个视频:用多米诺骨牌来解释逻辑门 (http://www.youtube.com/watch?v=SudixyugiX4)

Tagged with: