Silver

偶然发现WCF REST 诡异现象，微软的高手能否来解答下？

silver — Thu, 15 Dec 2011 14:18:38 GMT

1.构建一个REST Service：

[OperationContract]

[WebGet(UriTemplate = "GetImage")]

public Stream GetImage()

    var bmp = new Bitmap(100, 100);

    var gr = Graphics.FromImage(bmp);

    gr.Clear(Color.Blue);

    var stream = new MemoryStream();

    bmp.Save(stream, System.Drawing.Imaging.ImageFormat.Gif);

    //var bmp2 = new Bitmap(stream);

    //bmp2.Save("2.png");

    WebOperationContext.Current.OutgoingResponse.ContentType = "image/GIF";

    return stream;

2.在浏览器输入：http://localhost:8000/REST/GetImage 得到错误图片：

3. 去掉1步中的注释，则（其他浏览器也成功）：

这是什么问题？如何通过WCF返回内存中的动态图片呢？（不通过FileStream，网上有很多这种例子）。

Scrum的故事(转)

silver — Tue, 29 Nov 2011 05:13:00 GMT

2001年2月，17位敏捷先驱齐聚犹他雪鸟度假村，起草《敏捷宣言》的时候，Scrum只是众多方法中不太起眼的一个。十年之后，Scrum却成为最流行的敏捷方法，几乎成为敏捷的代名词。

本文来介绍下Scrum的两位创始人——Jeff Sutherland与Ken Schwaber。

大家可能不会想到，Jeff Sutherland的第一份工作居然是美国空军战斗机飞行员，还曾于1967年获得了“壮志凌云”称号，完成过100次飞越北部越南的作战任务。服役后期，他到斯坦福大学拿下统计学硕士学位，并在美国空军学院教授数学统计学和概率学。11年军旅生涯结束后，他成为了科罗拉多医学院的教师并获得了博士学位。在诺贝尔化学奖得主莱纳斯·鲍林的赞助下，他以放射学、生物学及预防医学助理教授的身份参与了维生素与癌症研究中心的创立，担任八年国家癌症中心的主要研究员，负责科罗拉多地区所有癌症患者的数据统计和IT方案与研究，整合了国家注册、临床试验、流行病学研究和癌变的超级计算机数学模型。1983年，他进入了一家遍及北美、经营着150家银行的公司，职务为先进系统副总裁及ATM业务部总经理。此后，Sutherland先后担任了11家软件公司的CEO、CTO或者工程副总裁，积累了丰富的软件开发经验。

Scrum的另一位主角Ken Schwaber最初的职业也很特别——商船经理。在随后40多年开发生涯的前10年中，他曾经编写过操作系统，搞过嵌入式，为IBM大型机开发系统软件；先后在芝加哥大学、伊利诺伊理工学院、王安公司实验室工作，并逐渐展现出在软件开发方法上的天赋。在CASE工具和结构化方法热门的时候，他自己创办了ADM公司，从事软件开发方法培训服务。期间，公司开发了软件方法自动化工具MATE，用来生成各种软件流程所需的模板、计划等，生意很好。

Sutherland和Schwaber相识于1980年代早期。1987年，两人开始合作。一天，Sutherland问Schwaber：“你们开发MATE工具都用了现在流行的哪一种方法？”“当然什么都没用，”Schwaber回答，“要不然公司早就完蛋了。”他们意识到问题的严重性，开始与开发者交谈，研究新方法。

1993年，Sutherland读到了两位日本管理教授竹内弘高和野中郁次郎介绍制造业里出现的新的产品开发方法Rugby（橄榄球）的文章。这种方法的特点是整个流程都由一个高性能、跨功能的团队执行到底。他受到启发，结合自己多年的经验，与Easel公司的John Scumniotales和Jeff McKenna一起开发了一套方法，取名为Scrum（来源于橄榄球术语，不是缩写）。

而Schwaber则从杜邦公司一位化工过程控制专家那里取经，意识到项目分为两种：确定性项目，一切都已经确定，可以自动化生产流程；实验性项目，充满不确定性，哪怕一点微小的变化也会牵一发而动全身，因此只能用各种仪表不断监控，随时做出调整——这就是每日站会的由来。

两人在一个IBM项目合作，并做了更详尽的研究，Scrum诞生了。1995年OOPSLA大会上他们第一次向世人介绍了Scrum。可当时，两个人的公司都还在做千年虫和各种重型开发方法咨询方面的业务呢。

进入新世纪，互联网带来的巨变使敏捷方法受到了更多开发团队的青睐，而其中Scrum以其扩展性、门槛低、名字和术语更容易被项目经理接受等因素，逐渐成为最受欢迎的敏捷流派。而推出CSM等系列认证，虽然争议颇大，但客观上对Scrum扩大影响力起到了重要作用。

今天，Scrum的影响已经远远超出软件开发，成为零售、军事、风险投资甚至学校里完成各种任务的创新方法，正在改变着世界。著名思想家Steve Denning曾表示，如果有诺贝尔管理学奖的话，应该授予Scrum的创始人。

原文地址

编程之美连载——连续子数组和的最大值

silver — Wed, 20 Apr 2011 04:47:19 GMT

问题

给定一整数数组，求连续的子数组和的最大值，例如：
1， -2， 3， 5， -3， 2 最大值为8
0， -2， 3， 5， -1， 2 最大值为9

分析

《编程之美》中给出的算法很精炼，然而解释却比较复杂，如果从“分级组合”的角度去理解要方便很多。

解法

设置两个整数变量：cur 和sum，从给定数组中依次取出所有元素，加到cur 上去，当cur<0 时候重置cur。sum 记录cur 出现过的最大值：

var cur = array[0];

var sum = cur;

for (int i = 1; i < array.Length; i++)

cur = cur < 0 ? array[ i ] : cur + array[ i ];

if (sum < cur) sum = cur;

return sum;

扩展问题二解法

如果要求得到最大和的连续子数组的起始位置，那么通过以上思路就更加容易写出代码：

int start1 = 0, start2 = 0, end = 0;

var cur = array[0];

var sum = cur;

for (int i = 1; i < array.Length; i++)

    if (cur < 0)

        cur = array[ i ];

        start2 = i;

    else cur += array[ i ];

    if (sum < cur)

        sum = cur;

        end = i;

        start1 = start2;

//返回 [start1, end]

本例中，我们用start1，start2 来记录起始位置，end 来记录终止位置。start2 相当于“工作变量”，start1 保存历史最大和连续子数组的起始位置。

扩展问题一解法

如果给定的是数组是首尾相连的循环数组，如何求解？首先设计一个函数，求解给定数组中，从from 开始的，最多到to 结束的最大和连续子数组的末尾位置，思路和前面解法类似。

int MaxSum_Position(int[] array, int from, int to)

    int step = Math.Sign(to - from);

    int end = from;

    var cur = array[from];

    var sum = cur;

    for (int i = from + step; i != to + step; i += step)

        cur += array[ i ];

        if (sum < cur)

            sum = cur;

            end = i;

    return end;

有了这个函数以后，可以将循环数组中的问题分成两种情况：一种是连续子数组跨越了0 位置的，一种是没有跨越的：

int sum1 = MaxSum(array);//不跨越0 位置的最大和

int i = MaxSum_Position(array, 0, array.Length - 1);

int j = MaxSum_Position(array, array.Length - 1, 0);

int sum2 = 0;

if (i > j) j = i + 1;

for (int k = 0; k < array.Length; k++)

sum2 += array[ k ];

if (k == i) k = j - 1; //跳过中间空缺部分

return Math.Max(sum1, sum2);

讨论

本题是“相同算法不同思想”的例子，通过另外一个角度去看算法，不但更加容易理解，并且求解扩展问题也更容易。

编程之美连载——游戏 24 点

silver — Wed, 20 Apr 2011 04:26:53 GMT

帮卢编辑看看大家对《编程之美》题目的反馈，才想起我有一些题目还没贴，写出来大家提提意见：）

问题

给 4 个1～13 之间数：n1 n2 n3 n4，是否能只使用四则运算使这4 个数运算得到24？

分析

依次拿出给定的4 个数字，计算1～4 级的情况，规则为“四则运算”。

需要说明的是，这道题和前面题目每级发展方法有点不同：前面都是拿出一个元素，将所有i 级扩展到i+1 级；然而在本例中，存在计算优先级(括号方案)的问题，例如：照原来的方法，可以得到n1 *(n2+ n3 + n4)的情况，但是无法得到(n1 + n2 ) * (n3 + n4)的情况。
因此，发展方法改为：先将n 个数放入1 级（1 个数不需要计算），然后执行n 步计算：

1 级和自己发展到2 级，1 级和2 级发展3 级…
2 级和自己发展4 级，2 级和3 级发展5 级…
以此类推…

解法

首先设计一个表达式类Expression，用以表示n 个数四则运算所能得到的表达式，然后设计一个表达式集合类ExpreSet，用来装相同数字所有组成的所有表达式，关键代码如下：

for (int i = 0; i < nExpres.Length; i++)

    for (int j = i; j < nExpres.Length - 1; j++)//以i 级为基准向上发展

        if (i + j + 2 > nExpres.Length) break;//大于输入数字的数量，无需再往上发展

        for (int ii = 0; ii < nExpres[ i ].Count; ii++)

            for (int jj = (i == j ? ii + 1 : 0); jj < nExpres[ j ].Count; jj++)

            { //第i 代和第j 代两两组合

                var ex1 = nExpres[ i ][ii];//较短表达式

                var ex2 = nExpres[ j ][jj];//较长表达式

                if (ex1.IsOverlap(ex2)) continue;//排除已包含相同数字的表达式

                nExpres[i + j + 1].TryAdd(ex2, ex1);//发展下一级

其中：

nums 为输入的整数数组；

nExpres = new ExpreSet[nums.Length];// nExpres [ n ]中装了所有n 个数字所能组

合出的表达式；

nExpres [0]中装了1 个数字能够组成的所有表达式。

讨论

运行程序，任意输入4 个数字：5 9 12 3，得到：

1. (5-(9/3))*12 = 24
2. (9-5)*3+12 = 24
3. 12-((5-9)*3) = 24

4. (12-9+5)*3 = 24
5. (5-(9-12))*3 = 24
6. (12+5-9)*3 = 24
7. (12-(9-5))*3 = 24
8. (12-9)*(3+5) = 24

在ExpreSet.TryAdd(exp1,exp2)方法中，已经考虑到了加法和乘法的交换率问题，所以排除了一些不必要的解。本程序实际上能够解决任意多个数字运算的情况。

有些细节容易忽略

silver — Tue, 15 Mar 2011 03:24:54 GMT

看见一篇比较有意思的文章，分享下…

原文地址：http://www.cnblogs.com/vwxyzh/archive/2010/07/03/1770410.html#commentform

前些日子，爆出N篇说c#/.net太慢的，要求删除c#/.net部分特性的文章。

撇开那些文章不说，c#/.net慢似乎是业界公认的铁则，不论大家如何证明c#/.net其实不比c++慢多少，但是应用程序级别的性能却依然这么慢。

那么c#/.net慢在哪里？

很不幸的是大部分c#程序是被大部分程序员拖慢的，也许这个结论不太容易被人接受，却是一个广泛存在的。

String的操作

几乎所有的程序都有String操作，至少90%的程序需要忽略大小写的比较，检查一下代码，至少其中大半的应用程序有类似这样的代码：

if (str1.ToUpper() == str2.ToUpper())

或者ToLower版的，甚至我还看到过有个Web的HttpModule里面写上了：

for (int i = 0; i < strs.Count; i++)
    if (value.ToUpper() == strs.ToUpper())
        //...

想一下，每个页面请求过来，都要执行这样一段代码，大片大片的创建string实例，更夸张的是还有人说这是用空间换时间。。。

性能测试

说这个方法慢，也许还有人不承认，认为这个就是最好的方法，所以这里要用具体测试来摆个事实。

首先准备一个测试性能的方法：

private static TResult MeasurePerformance<TArg, TResult>(Func<TArg, TResult> func, TArg arg, int loop)
{
    GC.Collect();
    int gc0 = GC.CollectionCount(0);
    int gc1 = GC.CollectionCount(1);
    int gc2 = GC.CollectionCount(2);
    TResult result = default(TResult);
    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < loop; i++)
    {
        result = func(arg);
    }
    Console.WriteLine(sw.ElapsedMilliseconds.ToString() + "ms");
    Console.WriteLine("GC 0:" + (GC.CollectionCount(0) - gc0).ToString());
    Console.WriteLine("GC 1:" + (GC.CollectionCount(1) - gc1).ToString());
    Console.WriteLine("GC 2:" + (GC.CollectionCount(2) - gc2).ToString());
    return result;
}

然后来准备一个堆string：

private static List<string> CreateStrings()
{
    List<string> strs = new List<string>(10000);
    char[] chs = new char[3];
    for (int i = 0; i < 10000; i++)
    {
        int j = i;
        for (int k = 0; k < chs.Length; k++)
        {
            chs[k] = (char)('a' + j % 26);
            j = j / 26;
        }
        strs.Add(new string(chs));
    }
    return strs;
}

然后来看看ToUpper的实现：

private static bool ImplementByToUpper(List<string> strs, string value)
{
    for (int i = 0; i < strs.Count; i++)
        if (value.ToUpper() == strs.ToUpper())
            return true;
    return false;
}

最后准备好main方法：

List<string> strs = CreateStrings();
bool result;
Console.WriteLine("Use ImplementByToUpper");
result = MeasurePerformance(s => ImplementByToUpper(strs, s), "yZh", 1000);
Console.WriteLine("result is " + result.ToString());
Console.ReadLine();

来看看执行结果：

Use ImplementByToUpper
2192ms
GC 0:247
GC 1:0
GC 2:0
result is True

来个对比测试，用string.Equals来测试一下：

private static bool ImplementByStringEquals(List<string> strs, string value)
{
    for (int i = 0; i < strs.Count; i++)
        if (string.Equals(value, strs, StringComparison.CurrentCultureIgnoreCase))
            return true;
    return false;
}

来看看执行结果：

Use ImplementByStringEquals
1117ms
GC 0:0
GC 1:0
GC 2:0
result is True

对比一下，使用ToUpper的速度要慢一倍，并且有大量的0代垃圾对象。那些号称是用空间换时间的人可以反思一下了，用空间换来了什么？负时间吗？

字典类的使用

继续说string的场景，有些人也许会想到用Hash表等类似结构来加速，不错，这是个好主意，只不过，Hash表不一定总是最佳方案，什么不相信？还是做个测试吧：

private static bool ImplementByHashSet(List<string> strs, string value)
{
    HashSet<string> set = new HashSet<string>(strs, StringComparer.CurrentCultureIgnoreCase);
    return set.Contains(value);
}

看看执行结果：

Use ImplementByHashSet
5114ms
GC 0:38
GC 1:38
GC 2:38
result is True

惊讶吧，速度比用ToUpper还慢了1倍多，而且2代垃圾也38次的回收（执行2代垃圾回收时，会强制执行1代和0代垃圾回收）。

不过使用Hash表等类似来加速这个想法本身是一个很正确的想法，不过前提是Hash表本身能够缓存，例如：

private static Func<string, bool> ImplementByHashSet2(List<string> strs)
{
    HashSet<string> set = new HashSet<string>(strs, StringComparer.CurrentCultureIgnoreCase);
    return set.Contains;
}

然后把main的方法修改为：

Console.WriteLine("Use ImplementByHashSet2");
result = MeasurePerformance(s =>
{
    var f = ImplementByHashSet2(strs);
    bool ret = false;
    for (int i = 0; i < 1000; i++)
    {
        ret = f(s);
    }
    return ret;
}, "yZh", 1);
Console.WriteLine("result is " + result.ToString());
Console.ReadLine();

再看看结果：

Use ImplementByHashSet2
6ms
GC 0:0
GC 1:0
GC 2:0
result is True

性能出现了飞跃性的增长。

更多

是什么拖慢了c#/.net？简单的说：不必要的创建对象，不必要的同步，循环执行低效的方法（例如被firelong重点批斗的反射，不过ms并没让你在循环里面使用Invoke），使用低效的数据结构和算法（看看缓存情况下Hash表类似结构的惊人表现，就知道区别了）

c#/.net的低门槛确实在一定程度上有利于把更多的程序员拉入c#/.net，但是也确实把整个c#/.net程序的代码水平降低了不少，这一点确实很令人担忧。

最后别忘了一点，一个系统能有多少性能，不是由这个系统中性能最好的部分决定的，而是由这个系统中性能最差的部分所决定的。配一台有16g内存，100t硬盘，加上顶级的显卡，缺配上386的cpu，这台电脑的性能就是386的性能。同样，c#/.net再好，写程序的人水平差，写出来的程序的性能自然也就差了。

寻找最远点对（四） “旋转卡壳”

silver — Fri, 18 Feb 2011 06:29:45 GMT

1978年， M.I. Shamos's Ph.D. 的论文"Computational Geometry"标志着计算机科学的这一领域的诞生。当时他发表成果的是一个寻找凸多边形直径的一个非常简单的算法，即根据多边形的一对点距离的最大值来确定。

后来直径演化为由一对对踵点对来确定。 Shamos提出了一个简单的 O(n) 时间的算法来确定一个凸 n 角形的对踵点对。因为他们最多只有 3n/2 对，直径可以在 O(n) 时间内算出。

如同Toussaint后来提出的， Shamos的算法就像绕着多边形旋转一对卡壳。因此就有了术语“旋转卡壳”。 1983年， Toussaint发表了一篇论文，其中用同样的技术来解决许多问题。从此，基于此模型的新算法就确立了，解决了许多问题。

原文地址：http://cgm.cs.mcgill.ca/~orm/rotcal.frame.html

算法步骤：

1. Compute the polygon's extreme points in the y direction. Call them ymin and ymax.

2. Construct two horizontal lines of support through ymin and ymax. Since this is already an anti-podal pair, compute the distance, and keep as maximum.

3. Rotate the lines until one is flush with an edge of the polygon.

4. A new anti-podal pair is determined. Compute the new distance, compare to old maximum, and update if necessary.

5. Repeat steps 3 and 4 until the anti-podal pair considered is (ymin,ymax) again.

6. Output the pair(s) determining the maximum as the diameter pair(s).

伪代码为：

begin

     p0:=pn;

     q:=NEXT[ p ];

     while (Area(p,NEXT[ p ],NEXT[ q ]) > Area(p,NEXT[ p ],q)) do

          q:=NEXT[ q ];

          q0:=q;

          while (q != p0) do

               begin

                    p:=NEXT[ p ];

                    Print(p,q);

                    while (Area(p,NEXT[ p ],NEXT[ q ]) > Area(p,NEXT[ p ],q) do

                         begin

                              q:=NEXT[ q ];

                              if ((p,q) != (q0,p0)) then Print(p,q)

                              else return

                         end;

                    if (Area(p,NEXT[ p ],NEXT[ q ]) = Area(p,NEXT[ p ],q)) then

                      if ((p,q) != (q0,p0)) then Print(p,NEXT[ q ])

                      else Print(NEXT[ p ],q)

end

end.

看起来貌似忒复杂了点啊~

解法

于是我搜索了下，查到如下实现算法：

//计算凸包直径，输入凸包ch，顶点个数为n，按逆时针排列，输出直径的平方

int rotating_calipers(Point *ch,int n)

    int q=1,ans=0;

    ch[ n ]=ch[0];

    for(int p=0;p<n;p++)

        while(cross(ch[p+1],ch[q+1],ch[ p ])>cross(ch[p+1],ch[ q ],ch[ p ]))

            q=(q+1)%n;

        ans=max(ans,max(dist2(ch[ p ],ch[ q ]),dist2(ch[p+1],ch[q+1])));

    return ans;

但是实现以后，用O(n^2)枚举算法对比测试发现有错误。

我个人认为，不应该用叉积去计算三角形面积来判断。因为三角形面积大的，不一定顶点离其他两个点距离就远，如下图：

因此，依据旋转卡壳的思想，我设计了如下算法：

var hull = GrahamScan.GetConvexHull(points);//获取凸包

int j = hull.max;//最右上点 最左下点是0

float maxD = 0;//存储最大值

for (int i = 0; i < hull.Count; i++)

    int preJ;

    float d, d2 = Distance(hull[ j ], hull[ i ]);

do

        d = d2;

        preJ = j;

        j = (j + 1) % hull.Count;

        d2 = Distance(hull[ j ], hull[ i ]);

    while (d2 > d);

    maxD = Math.Max(maxD, d);

    j = preJ;

return maxD;

思想为：先以最左下点和最右上点为初始“对踵点”开始旋转，记录最大的直径。利用的性质同样是：“对踵点”旋转的方向是一致的，也就是说，在凸包上面，一个点顺时针旋转以后，另外一个点不可能逆时针旋转。

此算法刚通过初步测试，希望大家提提意见。

寻找最远点对（三）增强堆栈

silver — Fri, 18 Feb 2011 02:58:40 GMT

对于前面提到的StackEx（增强堆栈），增强功能有：

1. 能够返回次栈顶；

2. 能够动态获取max；

不知道大家是否还记得《编程之美》中3.7 队列中取最大值操作问题，当时觉得还挺巧妙的：

“维护一个最大值的序列（link2NextMaxItem）来保证Max操作的时间复杂度为O（1），相当于用空间复杂度换取了时间复杂度”。

这里借用了这个思想，做了点改进。

解法

首先可以定义嵌套类，用于RotatingCalipers类内部使用

class StackEx : List<PointF>

构造函数利用基类的：

public StackEx(int capacity)

    : base(capacity)

设置两个变量：

public int max = 0;//指向最大元素

Dictionary<int, int> oldMax = new Dictionary<int, int>();//记录曾经最大值指针

这里用字典替代了link2NextMaxItem，原理一样，但灵活些。

Push操作：

public void Push(PointF item)

    Add(item);

    if (Count==1 ||

        (item.Y > this[max].Y || item.Y == this[max].Y && item.X > this[max].X))

        oldMax.Add(Top, max);//记录最高最右的点，提供给“旋转卡壳算法”

        max = Top;

Pop操作：

public PointF Pop()

    var top = this[Top];

    if (max == Top)

        max = oldMax[Top];

        oldMax.Remove(Top);

    RemoveAt(Top);

    return top;

两个值：

/// <summary>

///用于获取次栈顶

/// </summary>

public PointF Peek(int i = 0)

    return this[Top - i];

public int Top

    get { return Count - 1; }

体会

继承现有类简便又保证安全
使用Dictionary<int, int> oldMax能以O(1)得到最大值。

庆祝下IBM新一次人机对战获胜！

silver — Fri, 18 Feb 2011 02:19:12 GMT

今天收到Sam Palmisano庆祝邮件，非常高兴：）

在我初中的时候就听说IBM的“深蓝”击败国际象棋大师卡斯帕罗夫，引发了对计算机强烈的兴趣，虽然那个时候还在学习DOS下的WPS打字…

第一轮人类选手Ken大幅度领先Watson（沃森），但随后在double jeopardy的时候，被Watson反超回来。沃森又以最高分进入Final Jeopardy ，今天三位选手的分数是 Ken 19200, Watson 41413, Brad 11200，与前两日比赛得分相加，最后的成绩是：Watson 77147， Brad 21600，Ken 24000！Watson以绝对优势赢得人类历史上第一次人机智力问答比赛！

IBM超级电脑Watson在美国最受欢迎的智力竞猜节目'Jeopardy!' 中击败两名人类选手——IBM超级计算机沃森获胜，取得了信息科技上的有一次突破！IBM风雨百年，沃森见证未来！

不过Watson也是由人类发明创造出来的，Watson的胜利也是人类的胜利。

这代表着自然语言理解、人机交互的突破吧…

Watson最终胜出人机大战代表人类进步

IBM超级电脑人机对战第二场实录

新浪专题报道

寻找最远点对（二） Graham's Scan

silver — Wed, 16 Feb 2011 09:44:13 GMT

这个算法是由数学大师葛立恒(Graham)发明的，他曾经是美国数学学会(AMS)主席、AT&T首席科学家以及国际杂技师协会(IJA)主席。

细节可参考： http://www.cnblogs.com/devymex/archive/2010/08/09/1795392.html

这里主要解释发现的问题以及实现。

总结起来，算法步骤为：

1. 寻找锚点

在所有点中选取y坐标最小的一点H，当作锚点。如果存在多个点的y坐标都为最小值，则选取x坐标最小的一点。坐标相同的点应排除。

2. 排序

其它各点p和锚点构成的向量<H,p>与x轴的夹角进行排序。

3. 去掉凹进去的点

将点依次压入堆栈（第一个点是H），然后判断“待压点 - 栈顶 – 次栈顶”构成的角度是否凹进去，是就去掉顶点。

解法

1. 寻找锚点

int p = 0;//锚点初始指向0

for (int i = 1; i < points.Count; i++)

    if (points[ i ].Y < points[ p ].Y ||//如果Y更小

        points[ i ].Y == points[ p ].Y && points[ i ].X < points[ p ].X) //或者Y相等 X更小

        p = i;

2. 排序

points.Swap(0, p);//将锚点放到0位置

points.Sort(1, points.Count - 1, new PolarAngleCompare(points[0]));//按照角度排序

*注：PolarAngleCompare 是实现了IComparer<PointF>的比较方法类，后文解释。

3. 去掉凹进去的点

var stack = new StackEx(points.Count);

for (int i = 0; i < points.Count; i++)

    while (stack.Count > 1 && !LeftTurnTest(stack.Peek(1), stack.Peek(), points[ i ]))

        stack.Pop();

    stack.Push(points[ i ]);

return stack;

*注：StackEx是一个功能增强的堆栈，LeftTurnTest是判断凹凸，后文解释。

意外问题——“倒刺”

对于判断凹凸的实现，基本都采用向量的叉积而不是去计算角度。根据右手法则，逆时针旋转为正，顺时针旋转为负，因此可用以下函数判别：

/// <summary>

/// 求向量p2-p1,p3-p1的叉积

/// </summary>

public static float CrossProduct(PointF p1, PointF p2, PointF p3)

    return (p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X);

但是测试发现，当点的数量比较多的时候（>1000）就容易出现“倒刺”现象，如下图：

当发现这个的时候，也挺晕挺郁闷，但冷静下来观察，“倒刺”都有一定的规律——很尖：）别笑话，有道理

“尖”说明向量方向问题，也就是说，当叉积为0的时候，会有两种情况：同向和对向。

对向的时候是“尖刺”，并不满足凸包条件，同向的时候是平边，应该保留，否则最远点对会出现遗漏。

意外情况——“包外点”

当发现并解决了“倒刺”问题的时候，还挺开心以为“高枕无忧”了，结果偶然发现居然有些点在凸包外…如图所示：

真叫一个郁闷…因为无规律可观察，这个BUG估计难找了….

检查了程序并无逻辑错误…于是想到：是不是也是一样的边界问题？

哦~原来在第二步“排序”的时候，如果出现角度一样的点怎么弄？

如序列：B -A - C三个点，B - A向量和 C - A和x轴的夹角是一致的，那么可能出现“先长后短”和“先短后长”两种情况，前者就是“包外点”的罪魁祸首。

实现补充说明

按照角度排序的类：

class PolarAngleCompare : IComparer<PointF>

    PointF anchor;

    public PolarAngleCompare(PointF anchor)

        this.anchor = anchor;

    public int Compare(PointF p1, PointF p2)

        var product = CrossProduct(anchor, p2, p1);//求向量叉积

        if (product != 0)

            return Math.Sign(product);

        var d1 = Distance(p1, anchor);//求距离

        var d2 = Distance(p2, anchor);

        return d1.CompareTo(d2);//先短后长 避免出现遗漏

凹凸测试：

static bool LeftTurnTest(PointF p1, PointF p2, PointF p3)
{
    var cp = CrossProduct(p1, p2, p3);
    if (cp > 0) return true;
 
    //p2点必须在p1-p3线段上面
    if (cp == 0) return (p3.X - p2.X) * (p2.X - p1.X) > 0 || (p3.Y - p2.Y) * (p2.Y - p1.Y) > 0;
 
 
    return false;
}

增强堆栈受到过《编程之美》另外一篇文章的启发，下帖单独写写！

寻找最远点对（一）

silver — Tue, 15 Feb 2011 11:11:22 GMT

在一个实际项目中遇到“寻找最远点对”问题，猛然想起《编程之美》扩展问题提到过，开心地翻出来看，却发现“最近点对”的思路套“最远”貌似不合适。

然后开始查文献、做实验，改进算法，困扰半天也发现了不少实际问题，写出来大家参考。最后，算法用到系统中，虽然没有大幅提高遗传算法效率，但是系统评价功能明显比原来快了n倍，可谓酣畅：）

找回昔日研究《编程之美》感觉~~

问题

给定平面上N个点的坐标，找出距离最远的两个点。

背景

如果我们希望在城市道路网上设传感器，用以追踪车辆。那么这些传感器布应该设在哪里，布设多少？

首先来看看问题规模，例如：某城市二环内共有4210个路段，每个路段上有“设置/不设置”两种可能，那么所有可能的方案数为：

假设希望路网中不存在“行驶很远而不被追踪到的路径”，那么可以认为“用尽量少的传感器分割路网达到安全标准”的方案是优秀的。

对于这么大规模的问题，可以采用遗传算法（GA）进行优化求解。而在GA中，需要对每一个方案进行评估（按照一定的标准）。

那么，评估过程中，为了找出“行驶很远而不被追踪到的路径”，需要找到“最远点对”。

分析

类似于“最近点对问题”，这个问题也可以用枚举的方法求解，时间复杂度O(n^2)。

“寻找最近点对”是用到分治策略降低复杂度，而“寻找最远点对”可利用几何性质。注意到：对于平面上有n个点，这一对最远点必然存在于这n个点所构成的一个凸包上（证明略），那么可以排除大量点，如下图所示：

在得到凸包以后，可以只在顶点上面找最远点了。同样，如果不O(n^2)两两枚举，可以想象有两条平行线， “卡”住这个凸包，然后卡紧的情况下旋转一圈，肯定就能找到凸包直径，也就找到了最远的点对。或许这就是为啥叫“旋转卡壳法”。（当然这个方法还能解决凸包很多别的问题 http://cgm.cs.mcgill.ca/~orm/rotcal.html ）

总结起来，问题解决步骤为：

1. 用Graham's Scanning求凸包

2. 用Rotating Calipers求凸包直径，也就找到了最远点对。

该算法的平均复杂度为O(nlogn) 。最坏的情况下，如果这n个点本身就构成了一个凸包，时间复杂度为O(n^2)。

下帖开始分析算法：）

参考文献

http://blog.csdn.net/wangyangkobe/archive/2010/12/17/6081975.aspx 这个里面有挺多链接。

Rotating Calipers applet：http://big-o.nl/demos/computationalgeometry/rotatingcalipers/index.html

Graham's Scan applet ：http://www.cosc.canterbury.ac.nz/mukundan/cgeo/Gscan.html

C# 4.0 可选参数问题

silver — Sat, 28 Aug 2010 01:21:28 GMT

看见C#4.0可选参数功能挺兴奋的，一方面office编程不用写那么一大堆：

excelApp.get_Range("A1", "B4").AutoFormat(myFormat, Type.Missing,

    Type.Missing, Type.Missing, Type.Missing, Type.Missing, Type.Missing);

而可以简化为：

excelApp.Range["A1", "B4"].AutoFormat( Format: myFormat );

另外，原来一大堆函数重载也可以精简了，一个函数就能多用：

static void Print(int Copies=1, string ColorMode="Color", string DocumentName="") {...}

Print(1);

Print(1, "Color");

Print(1, "Color", "My doc");

Print(Copies: 1);

Print(ColorMode: "Color");

Print(DocumentName: "myDoc.txt");

Print(Copies: 1, ColorMode: "Color");

问题

但是，第一次想用“可选参数”精简下我原来的代码，就遇到问题了：

public PolyLine(PointF[] points, Color color = Color.White)

    figColor = color;

    mPoints = points;

    AddCenterPoint();

报错说：

Error 2 Default parameter value for 'color' must be a compile-time constant

没想结构体里面的静态属性都不行…又改成:

public PolyLine(PointF[] points, Color color = Color.Empty)

结果一样的错误，看了下定义：

// Summary:

//     Represents a color that is null.

public static readonly Color Empty;

是个静态只读字段，还是无法编译时确定value？

貌似限制还挺大..

学术搜索中的“作者识别”

silver — Wed, 25 Aug 2010 16:28:25 GMT

问题

遇到一问题：“重名的问题中外都有，例如：搜索 Michael Smith： http://academic.research.microsoft.com/Search.aspx?query=michael%20smith 你可以看到有很多 Michael Smith, 同时还有Mike 的拼写, 不同的 middle name 等问题。每篇论文提供的作者，单位信息也不一样怎么办?”

看到这个问题，我觉得根源可以描述为：从网上扒下m篇文章，其中可以抽取n个作者名字出来，现在需要确定哪些作者名字是指的同样一个人（合并问题）？

难点一：作者单位关系演变历程

例如： Michael David Smith 的 Affiliation history 可能是：

· Stanford University
· Harvard University
· University of Alberta
· University of Calgary
· Carnegie Mellon University

同一个作者，可能在很多单位发表过论文，如何识别出每个作者的单位关系演变历程？

难点二：名字多种写法

例如：Michael David Smith 也可能是 Michael D. Smith 或者其他拼写

对于非英语国家的作者，名字可能在文章中出现多种可能，例如：中文刊物发表的文章叫“张三”，英文的叫“ZhangSan”，或者直接是其他英文名。

难点三：文献信息不全

如果文献包含了作者简介，还比较好，但是很多只有单位信息。例如：Michael D. Smith 的《A High-Performance Microarchitecture with Hardware-Programmable Functional Units》只有Harvard University, Cambridge

信息来源

在思考方法之前，应该先考虑解决这个问题的信息来源：

作者单位信息。一般来说，每个能找到作者的文章都有单位信息，但是有上述“演变问题”。
作者简介。这个信息量大（性别、出生年月、出生地、单位、研究方向、邮箱、电话等），不也可能存在差异，如描述性差异、语言性差异（中文、英文）
作者个人主页。如果能找到这个，应该能找到挺多信息，如：发表文献列表等。
合作者，例如：通过发掘这些文献，能找出和 Michael D. Smith 一起写过文章的作者：

Glenn H Holloway
Mark A Horowitz
Kartik Hosanagar
Yu Jeffrey Hu
Yu Hu
Fang Huang
Lily Huang Lily Huang
David S Johnson
Mike Johnson
Mahmut Taylan Kandemir
David Ron Karger
Murali Krishnan
…

作者涉及领域，通过查看作者发表文章，可以推断出作者涉及过的研究领域，例如：Michael D. Smith的研究领域

Microprogram Design Aids, Microcode Applications, Memory Structures, Design Styles, Cache Memories, Multiple Data Stream Architectures (Multiprocessors) …

关键词。可以总结出作者列出过的所有关键词：

code instrumentation
embedded agile methodologies
embedded programming
embedded systems, agile methods, test driven development, tool support
embedded unit
empirical
feature selection
game tree search
general purpose microarchitectures
global instruction scheduling…

7. 投过的会议、刊物…

初步思路

初步考虑起来，这个“作者合并”算法应该非常复杂——得先建立作者属性集合，找到最可靠的信息（计算两个作者某些属性的相似度、关联度）进行合并，合并之后更新属性集合，然后继续迭代….

这个问题貌似会涉及到很多难点，需要更多时间考虑…

另辟蹊径

信息残缺、非结构化，难度很大，我想是否可以通过其他一些手段解决？——

可否无缝整合“学术搜索”、“Word 文献管理”、“Windows Live ID”，“Msn 空间” 等功能？

Word中一直缺少强大的“文献管理功能”，现在大家基本都用第三方工具。可否在Word中写文章的时候可以使用类似“Windows Live ID”登录，系统提供通过数据挖掘发现的个人文章，用户可以自行修改（删除不属于自己的）——通过强大方便的文献管理功能吸引大量用户使用，让作者自己完善文献信息？？
在Word中可以直接点击登录到“学术搜索”或者“Msn 空间” 上的“个人学术主页”，包含个人的照片、单位关系历史、发表文献等等一系列信息，方便修改。最好能够整合社交网络的各种功能，例如：人人网、博客、facebook, twiiter等，但是要突出学术交流的特色，提出一些创新功能吸引研究人员。可以学习Web of Science网站 Research ID 提供的那些功能。

期待结果：

如果通过完善自己在“微软学术搜索”上面的主页，能够增加自己文章的引用，能够得到其他作者的提问、评论、反馈，发展成一个比较大的社区，估计信息来源更加准确，搜索结果也会更加准确。
在一个人气社区上面可以建立前面帖子提到的“学术立方”。

从一件小事看软件的销售

silver — Mon, 23 Aug 2010 05:40:00 GMT

从一件小事看软件“细节决定成败”

一、近期准备给一些客户的demo，我用到了office 2010的试用版，确实挺多方便的功能，展示效果也挺好

二、经理及其他同事为了能打开我做的demo，也开始用office 2010，并且开始计划采购一批

三、大家在使用过程中发现，ppt中的视频经常出现“编码器不可用”的提示，无法播放——需要关闭所有打开的PPT文件，重新启动就可以了，这种现象在给客户的demo和讲课过程中是非常严重的问题

四、就因为这么一个小问题，大家普遍觉得office2010“不稳定”，放弃了采购计划

结论：由此可以看出，个人软件产品细节挺重要的...

写个程序做推理

silver — Sun, 22 Aug 2010 05:15:00 GMT

问题

教授选出两个从2到9的数，把它们的和告诉学生甲，把它们的积告诉学生乙，让他们轮流猜这两个数
甲说：“我猜不出”
乙说：“我猜不出”
甲说：“我猜到了”
乙说：“我也猜到了”

问这两个数是多少？

分析

初初看这个题目，感觉是他们在说废话～！@#￥%

不过，看过《越狱》的同学应该对这些spy敏锐的眼光，善于抓住线索而赞叹。

运行结果

何不写个程序来推理呢？运行一下得到：

第一个数是3 第二个数是4

第一个数是3 第二个数是6

解法

for (int i = 2; i < 10; i++)

    for (int j = i; j < 10; j++)

        var sums = DecomSum(i + j);

        if (sums.Count < 2) continue;

       //如果不满足第一个条件——甲说不知道 => 他得到的数可以分解为多个“数对”相加

        var products = DecomProduct(i * j);

        if (products.Count == 1) continue;

       //如果不满足第二个条件——乙说不知道 => 他得到的数可以分解为多个“数对”相乘

        if (!Condition3(sums)) continue;//如果不满足第三个条件——甲说：“我猜到了”

        if (!Condition4(products)) continue;//如果不满足第四个条件——乙说：“我也猜到了”

        Console.WriteLine("第一个数是{0}  第二个数是{1}\n", i, j);

        //Analysis(i, j);

        //Console.WriteLine("\n");

*注：List<Point> DecomSum(int sum) 函数是分解和

List<Point> DecomProduct(int product) 函数是分解积

再来看其中的函数：

bool Condition3(List<Point> sums)

    var unique = 0;

    foreach (var s in sums)

        if (DecomProduct(s.X * s.Y).Count == 1) unique++;

    if (unique == sums.Count - 1) return true;

    return false;

}//甲马上说知道了 => 他得到的数“和分解”出來的多个“数对”的积当中,

只有一个“积分解”是不唯一的,其他都是唯一的

bool Condition4(List<Point> products)

    var condition3_satisfied_cnt = 0;

    foreach (var s in products)

        var sums = DecomSum(s.X + s.Y);

        if (Condition3(sums)) condition3_satisfied_cnt++;

    if (condition3_satisfied_cnt==1) return true;

    return false;

}//乙说：“我也猜到了” => 他得到的数“积分解”出来的多个“数对”的和当中，

只有一个的“和分解”满足Condition3

分析

取消其中”分析“代码的注释，得到：

第一个数是3 第二个数是4

分析：
条件一：7可以分解为：3+4,2+5,
条件二：12可以分解为：2*6,3*4,
条件三：
12(=3*4)：
12可以分解为：2*6,3*4,
10(=2*5)：
10可以分解为：2*5,

条件四：
8(=2+6)：
8可以分解为：4+4,3+5,2+6,
7(=3+4)：
7可以分解为：3+4,2+5,

第一个数是3 第二个数是6

分析：
条件一：9可以分解为：4+5,3+6,2+7,
条件二：18可以分解为：2*9,3*6,
条件三：
20(=4*5)：
20可以分解为：4*5,
18(=3*6)：
18可以分解为：2*9,3*6,
14(=2*7)：
14可以分解为：2*7,

条件四：
11(=2+9)：
11可以分解为：5+6,4+7,3+8,2+9,
9(=3+6)：
9可以分解为：4+5,3+6,2+7,

小结

个人觉得这道题目挺有启发的——在生活工作中要保持“把握已知信息的态度”，还是我曾经提到的“能力是一种态度“

看来要多向Micheal Scofiel学习啊…

这个题目涉及到：”组合问题“、”推理问题“、”换位思考“，有点容易晕

刚刚搞定，有空再想想有没问题或者有没更好办法…欢迎大家批评指教

“学术立方”之遐想

silver — Sat, 21 Aug 2010 14:50:00 GMT

最近试用了，发现它用“人立方”技术展现作者之间的关系，挺酷的：

http://academic.research.microsoft.com/

结合最近的一些搜索需求，于是我便有了如下遐想：

能否充分利用“人立方”的技术，构造一系列“学术立方”出来？

1 “学科立方”

自复杂系统理论兴起以来，人们逐渐意识到学科分割带来的一些问题，学科之间的交叉与融合逐渐成为新的趋势。

02年诺贝尔经济学奖，卡尼曼的“前景理论”就挺好玩，看起来是很常见但是一直没人提出的一些现象。或许只有站在经济学和心理学的交叉点上，才能系统全面看待这些问题。

那么，能否构造一个“学科立方”呢？

展现学科之间的交叉融合关系？
展现学科之间的交叉程度及趋势（卡尼曼之后经济学和心理学交叉的文献情况？）
发现潜在学科群？

比如可以先以：“城市规划”为中心展现，然后如果用户点中“环境学”，再以它为新的中心展现（类似人立法效果）：

当然，还可以通过作者来分析，比如一个学科的人发表文章到另外一个学科的杂志。

2 “方法立方”

有时候科研人员会有这样的需求，比如：我搞了个将“遗传算法”和A*算法结合起来的并行求解方法，因为时间或者项目资源有限，只和EXCEL做了对比。

那么，“方法立方”能否展现：

一个方法（如：遗传算法、小波、马尔可夫链）等的起源、发展、所有改进分支？
每个分支上的改进链条？例如：谁在谁的方法上提出了什么，改进了多少？后来谁又在他的基础上又改进了多少?
我要解决某个问题，当今最好的最快的方法是？

3 “学术机构立方”

我想应该可以通过共同发表文章、新闻等（如IBM和东北大学成立“生态城市联合研究院”等）展现学术机构之间的合作情况：

以被搜索的学术机构为中心（如：清华大学），展现它主要和那些学术机构有过合作
连线可以是新闻，或者是共同发表文章的数量

4 “学术带头人立方”

例如，输入“人群动态学”，能否展现：

这个学科代表性人物有哪些？
他们之间是否有关系？
他们是否兼任相近学科的带头人？

5 “文献立方”

我觉得中国期刊全文数据库非常好用的一个功能是：打开一篇文献的页面它能够列出：

参考文献
共引文献
相似文献

这样能省去很多搜索的时间，通过多次利用这个功能，能够查到很多相关的文章。

那么，可否通过一些更加可视化的方式展现这个过程？

小记

暂时就想到这些，我想如果一系列“学术立方”全部推出的时候，应该是一个非常酷的引擎：）

当然具体实现还会涉及到很多技术难题…

我会继续思考类似问题，希望大家多提提意见。