整型序列排序到底有多快？

  • Post author:
  • Post category:IceSee
  • Post comments:0评论

稍微对算法研究的人应该知道，在通用算法中，随机快速排序有着最好的时间效率，为O(nlgn)。但是如果对问题做一个限制，假设输入的序列长值为32位的无符号型整数，那么对这样的序列进行排序，时间复杂度是多少了？

为了处理这个问题，我们首先要介绍两种不是太常用的排序：计数排序以及稳定排序。

一、计数排序

计数排序是一种典型的空间换时间的排序方案。假设排序序列为：

A {x1, x2, x3, …, xn}

并且对A中任意元素xi；满足xi<k；

解决方案：

count = int[k]

for v &lt;-- xi

count[v] ++

icount = k;

for i in [n, ..., 1]

while(k)

if count[k] &gt; 0

B[i] = k

count[k]--

break

else

k--

计数排序的时间复杂度为O（n）实际上需要考虑xi<k这一个强限制条件，其时间效率为T(n)=k+n

对于32位整型，k达到4亿大小，导致这个排序在时间以及空间复杂度上是不可行的。

但是，如果是8位整型，k=256,那么这个算法将有着极高的效率。

那么我们可以将一个32整型分解为4个8位整型，如果有一种算法能够对4个一组的数据进行快速排序，那么这个问题就迎刃而解了。

幸运的是，我们能够找到这样的一个算法，这要感谢IBM的创始人。

稳定排序

稳定排序就是这样一种算法。稳定排序又叫尾排序，即排序时先排列最低位。

对于一个整型，需要使用4次稳定排序才能将数据进行重排。

综合两种算法，对整型的最快排序为时间为：

1024+4n

这是一个T(n)=O(n)的算法。

继续阅读 整型序列排序到底有多快？

使用单件构造器(SingletonConstructor)顺序初始化单件

使用单件构造器(SingletonConstructor)保证单件顺序初始化

对于单件模式时，目前主要有两种方法，即静态初始化以及动态初始化
对于动态初始化，由于锁(Double Check Lock)的加入，必然无法应用于高性能要求的场合。
对于静态初始化，单件的初始化顺序是不能保证的，如果单件直接存在依赖关系，这将导致初始化失败。
为了解决这个问题，引入一个单件构造器，由单件构造器来负责对各个单件进行显式的初始化

单件构造器（SingletonConstructor）定义如下：
1.单件构造器是所有其他单件的友元。
2.单件构造器是所影响域存在的唯一的静态初始化单件。

//Head file
class SingletonConstructor{
private:
    SingletonConstructor();
    ~SingletonConstructor();
    SingletonConstructor(SingletonConstructor const&);
    SingletonConstructor& operator=(SingletonConstructor const&);

    static SingletonConstructor s_SingletonConstructor_;
};

calss SingletonA{
public:
    friend class SingletonConstructor;
    SingletonA& Instance()
    {
        return *s_SingletonA_;
    }
private:
    SingletonA()
    {
        if (!s_SingletonA_)
            s_SingletonA_ = this;
    }

    ~SingletonA();
    SingletonA(SingletonA const&);
    SingletonA& operator=(SingletonA const&);

    static SingletonA *s_SingletonA_;
}

calss SingletonB{
public:
    friend class SingletonConstructor;
    SingletonB& Instance()
    {
        return *s_SingletonC_;
    }
private:
    SingletonB()
    {
        if (!s_SingletonB_)
        s_SingletonB_ = this;
    }
    ~SingletonB();
    SingletonB(SingletonB const&);
    SingletonB& operator=(SingletonB const&);
    
    static SingletonB *s_SingletonB_;
}

calss SingletonC{
public:
    friend class SingletonConstructor;
    SingletonC& Instance()
    {
    return *s_SingletonC_;
    }
private:
    SingletonC()
    {
        if (!s_SingletonB_)
        s_SingletonB_ = this;
    }
    ~SingletonC();
    SingletonC(SingletonC const&);
    SingletonC& operator=(SingletonC const&);
    static SingletonC *s_SingletonC_;
}

//Cpp file
SingletonConstructor SingletonConstructor::s_SingletonConstructor_;

SingletonConstructor::SingletonConstructor()
{
    m_SingleA = new SingletonA();
    m_SingleB = new SingletonB();
    m_SingleC = new SingletonC();
    //Or you can use std::vector<SingletonBase *> instead of m_Single*
}

SingletonConstructor::~SingletonConstructor()
{
    delete m_SingleC;
    delete m_SingleB;
    delete m_SingleA;
    //Or you can use std::vector<SingletonBase *> instead of m_Single*
}

单件构造器的思想在于显式初始化各个单件。

继续阅读 使用单件构造器(SingletonConstructor)顺序初始化单件

重游校内网

  • Post author:
  • Post category:IceSee
  • Post comments:0评论

今天光了突然有了兴致，重新注册了一个校内帐号（以前那个自己删除了），其实只是想看看几个老朋友最近过的怎样。

登录后却发现L君的帐号已然不见，QQ上一问才知道他也同我一样，早就删号离去了。这令我不得不想一想SNS的用户黏度问题。像校内这种基于校友关系的社区网站，其用户亲和度是很高。想象一下，如果你周围所有同学都在玩校内，就你一个人在上MSN上晃悠，估计你也会很快被孤立吧。三年前校内刚出现时，其热度非凡，基本上周围同学人手一号，大有取QQ而代之的势头。可惜好景不长，没过多久上校内的人渐渐少了。到底是什么使的人们渐渐远离校内呢？

我想这无非有以下方面的原因：

1.隐私问题。校内网要求提供几乎真实的个人信息，这本是校内的亮点之一，不过并不是每个人都想让自己的个人信息暴露给众人。何况现在“人肉搜索”如此发达，校内网基本上是“人肉er”的首选信息源。

2.价值取向问题。校内网提供的的服务基本偏向于年轻人的娱乐应用，这并不符合所有人的胃口。很多人一开始可能会让觉得新奇，忍不住想要试试，但时间一久，他们也会渐渐失去兴趣，进而离开，不过校内网也在通过自己的应用程序来扩展其应用，丰富其内容。

3.其他传统通信软件的竞争，这里说传统主要是指QQ。可以说有网络的电脑，就可以上校内；但是没网络的电脑，也可能装有QQ。如今的QQ已然拥有国内甚至国际上最大的用户资源，校内网的用户基本上也同时是腾讯的用户，在腾讯提供相同质量服务（如腾讯的校友网）的情况下，很难说用户会选择那边。另一方面，校内网提供的信息交流功能，绝大多数QQ已经拥有，甚至QQ做的更好，用户更倾向与同别人进行即时聊天，而非通过校内来交流。

当然，校内网还是有它自己的的用户群，这种SNS社区网络也是当前网络发展的 一种潮流，不过要断言其前景，恐怕现在还为时过早。

继续阅读 重游校内网