最近在看《编程之美》，为找工作面试做准备。该书中2.20程序理解和时间分析一题没有给出解答，所以简单写一下我自己的答案。
题目如下：
阅读以下C#代码，回答问题：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| using System;
using System.Collections.Generic;
using System.Text;
namespace FindTheNumber
{
class Program
{
static void Main(string[] args)
{
int [] rg =
{2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,
18,19,20,21,22,23,24,25,26,27,28,29,30,31};
for(Int64 i = 1; i < Int64.MaxValue; i++)
{
int hit = 0;
int hit1 = -1;
int hit2 = -1;
for (int j = 0; (j < rg.Length) && (hit <= 2); j++)
{
if((i % rg[j]) != 0)
{
hit++;
if(hit == 1)
{
hit1 = j;
}
else if (hit == 2)
{
hit2 = j;
}
else
break;
}
}
if((hit == 2) && (hit1 + 1 == hit2))
{
Console.WriteLine("found {0}", i);
}
}
}
}
} |
1> 这个程序要找的是符合什么条件的数？
2> 这样的数存在么？符合这一条件的最小的数是什么？
3> 在电脑上运行这一程序，你估计要多长时间才能输出第一个结果？时间精确到分钟(电脑配置：单核CPU2.0GHz，内存和硬盘资源充足)
我的解答：
阅读全文…
陆陆续续花了一个月的时间，终于看完了CSAPP(Computer System：A programmer‘s perspective 注：第二版已出：英文版 中文版)，头一次看那么厚(900页)的原版书，看完还是有一点点成就感的。
从同宿舍的鲁博士那里第一次听说这本书，了解到该书从一个程序员的视角详细剖析了整个计算机系统，涵盖了组成原理、汇编语言、体系结构、操作系统、网络等计算机基础知识，当时就决定找工作之前一定要看看这本书，现在终于搞定，也算是间接复习了一下前述几门课程。
这次阅读用的是鲁博士的书，再次印证了买来的书没有借来的书看得彻底的“真理”……
在阅读过程中，对该书的各个章节做了一些标注，以备将来重新翻阅的时候参考。这些标注主要从两个角度进行，一是对我找工作应试（包括笔试和面试）有没有用，二是对我自身的技术提高有没有用，所以分为应试和修炼两个指标，参照流行的打分标准将其分为从★到★★★★★五个等级。现记录如下：
阅读全文…
学过计算机组成原理的同学都知道在计算机中，浮点数是通过3个部分来表征的，1个bit的符号位，k个bit的指数位和n个bit的有效数位，对于C语言中的float和double，k、n值分别是8、23和11、52。
我们可以想象一下，表征浮点数的bit是有限的，因而其组合也是有限的，是无法完全表征所有实数的，事实上，连一些10进制下看上去很简单的数也都无法精确表示。比如，你可以试一下下面几行代码：
1
2
3
4
5
6
7
| #include <stdio.h>
int main()
{
double a = 0.1;
printf("%.20lf",a);
return 0;
} |
你会看到输出的其实是0.10000000000000001000。
正是由于很多实数无法精确表示，所以在计算机处理浮点数的时候，需要进行大量的舍入操作，那么计算机默认是采用什么样的舍入策略呢？
以前我一直以为计算机采用的就是人们日常所熟悉的“四舍五入”法则，因为在printf函数中，如果指定输出精度小于实际精度的话，输出的结果就是按四舍五入产生的。其实这是printf函数故意设计成这样以符合人们的日常习惯的。
实际计算机中，当需要进行舍入操作时，运用是一种叫“round-to-even”的策略，即“向偶数舍入”，举个简单的例子就可以明白了，比如1.235和1.245，舍入后都是1.24, 也就是说要使得舍入后的最后一位有效数字是偶数。
为什么要采用这样的策略，而不直接使用我们已经习惯的“四舍五入”呢。原因在于，在进行舍入的时候，最后一位数字从1到9, 舍去的有1,2,3,4；正好可以和进位的9,8,7,6相对应，而5却被单独出来了，如果我们采用四舍五入每次都将5进位的话，在进行一些大量数据的统计时，就会累积比较大的偏差，而如果采用”round-to-even”的策略，在巨大多数情况下，5舍去还是进位的几率差不多，统计时产生的偏差也就相应要少一些了。
最近在实现PLSV，写了一个matlab的版本，效果却远没有原作者论文上说的好。
给作者发信索要代码，答曰：本人已在公司工作，出于保密，不能给你代码，不过在这个网页(需翻墙)上有别人写的代码，你可以看一看。
看了那个blog上的代码，是一个日本人写的perl代码，一看代码风格很严谨，遂认为是精品，于是慢慢品读，但因为我是头一次读perl的代码，所以边看边查，做了一点记录。
代码太长，附在文章最后吧，先是我做的一点记录：
#!/usr/bin/perl
这一行是Linux类系统下脚本的第一行，指定脚本执行环境，python也有。
use
导入模块，类似java的import
定义变量，直接使用一个$符号，比如$a，就表示定义了一个名为a的标量。这个不管是int，float，string，char……一律使用这个表示。
定义数组，直接使用符号@，比如@array，表示定义一个名为array的数组。基本上和上面的差不多，但是perl中好像是没有直接的二维数组的定义。
定义Hash，使用符号%，比如%hash，表示定义一个名为hash的哈希结构。哈希结构基本上在前期用的不多，在后面的时候，可以和数组组合成比较强大的结构体。
阅读全文…
先再次感叹一下自己的Java没学好……
以前本科上Java课的时候，记得最清楚地一件事就是Java里没有指针，当时曾经疑惑过，那怎么用Java写链表呢。但是也没有深想，后来要用到也是一直用像List，vector这样的现成结构。
直到最近用Java用得比较多，才逐渐搞清楚了Java中对象引用的概念，于是想到其实可以通过对象引用实现链表。写了个小程序测试一下，果然OK。
阅读全文…
这是最近的一个需求：
有一个算法库，里边的每一个算法是一个类，并且都有公共的入口函数，需要根据一个定义好的xml文档，依次执行指定的算法。
这里用到了两个以前不会的知识，一个是xml文档的处理，另一个是类的动态加载。
通过搜索，最后采用JDOM对xml进行操作，通过Java的reflect机制进行动态类加载，现记录如下：
xml的文档定义如下：
< ?xml version="1.0" encoding="gb2312"?>
<jobs>
<algorithm name = "pdm.filters.PDAttributeExchange">
<setting>
<set name="jobPriorityType"></set>
<set name="numOfMapTasks"></set>
<set name="numOfReduceTasks"></set>
</setting>
<input />
<header>/home/maxd/data/3d.header.arff</header>
<data>maxd/input</data>
<output>
<header>maxd/xmloutputheader/3d.header.arff</header>
<data>maxd/xmloutput</data>
</output>
<arguments>
<arg name="attributeField1">A1</arg>
<arg name="attributeField2">A3</arg>
</arguments>
</algorithm>
</jobs>
处理代码如下：
阅读全文…
今天看到一段这样的代码：
1
2
3
4
| template
inline void _construct(T1 *p, const T2& value){
new(p) T1(value);
} |
然后发现自己好圡，竟然是头一次看到new函数这样的用法，网上查了一下才知道原来这叫 placement new，简单来说就是在p所指的内存处构造对象，不再申请内存。
在网上找到一篇对placement new 说的比较清楚的文章，没找到原作者是谁，所以就不给链接了，直接转载如下：
阅读全文…
今天在《Programming Pearls》上看到这样的问题，有一个非降序数组d[]，包含1000个数，可能有重复的数，求数K在数组中最靠前的下标。如果找不到的话，结果为-1。
这种类型的二分之前已经写过不下数十次了，于是我信手敲下如下代码：
[code=cpp]
l = 0; r = 999;
ans = -1;
while(l <= r)
{
mid = (l+r)/2;
if(d[mid] >= k)
{
ans = mid;
r = mid-1;
}
else
l = mid+1;
}
[/code]
上面这段代码是我写了很多次的二分之后总结出来的，因为二分的很多其他写法在不同的条件下稍不注意就会出现错误。这里说的不同的条件包括：求满足条件的最小的值； 求满足条件最大的值等等。
而上面的代码可以通用我到目前为止遇到的所有情况(仅仅是改变一下ans = mid; 的位置即可)，所以一直这么写二分。
但是看了书上给的代码，觉得不但也能适合所有情况，而且很好验证其正确性：
阅读全文…
