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

Post author:iceyer
Post published:2014年5月21日
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)的算法。

继续阅读

在Windows7 X64 上安装Tiny Issue

Post author:iceyer
Post published:2013年12月11日
Post category:Web
Post comments:0评论

安装准备：
Windows 7 X64
PHP Version 5.5.6 (Win64)
http://windows.php.net/download/#php-5.5-ts-VC11-x64
VC11 x64 Thread Safe
Apache/2.4.7 (Win64)
http://www.apachelounge.com/download/
httpd-2.4.7-win64-VC11.zip
MySQL
tinyissue

一、Apache安装配置

1.解压httpd-2.4.7-win64-VC11.zip 到 D:\Dev\Apache24并创建 D:\www 目录

2.修改配置文件httpd.conf
(1)ServerRoot “c:/Apache24” 改为 ServerRoot “D:/Apache24”; //Apache程序的位置。
(2)ServerName 前面的“#”号去掉;
(3)DocumentRoot “c:/Apache24/htdocs” 改为DocumentRoot “D:/www”; //网站的根目录
(4)<Directory “c:/Apache24/htdocs”> 改为<Directory ” D:/www “>;
(5)DirectoryIndex index.html 改为DirectoryIndex index.html index.php index.htm //支持更多的默认页
(6)ScriptAlias /cgi-bin/ “c:/Apache24/cgi-bin/” 改为ScriptAlias /cgi-bin/ “d:/dev/Apache24/cgi-bin/”
(7)<Directory “c:/Apache24/cgi-bin”> 改为<Directory “D:/Apache24/cgi-bin”>

3.安装服务

httpd.exe -k install -n "Apache Server 2.4"

在services.msc中找到服务并开启服务。

4.测试Apache服务器
访问 http://localhost/
出现It works！表明安装基本正常

二、PHP安装设置

1.解压php-5.5.6-Win32-VC11-x64.zip到D:\Dev\PHP

2.复制份php.ini-development，并改名为PHP.ini。

3.打开Apache24下httpd.conf，在最后加上

# php5 support
LoadModule php5_module "D:/Dev/PHP/php5apache2_4.dll"
AddHandler application/x-httpd-php .php
# configure the path to php.ini
PHPIniDir "D:/Dev/PHP/"

php5apache2_4.dll使用php-5.5.6-Win32-VC11-x64.zip中自带的即可。

4. 重启 Apache 服务器。

5.在www目录下新建一个index.php，内容为<?php phpinfo(); ?>
访问http://localhost/index.php
出现php的信息就说明php已经成功安装。

三、MYSQL安装

1.从http://dev.mysql.com/downloads/mysql/
下载64位社区版本的MYSQL。

2.打开MYSQL Workbench，添加新用户tinyissue，和新数据库tinyissue-db

3.配置PHP.ini识别MYSQL
(1)extension_dir = “ext”，去掉前面的“;”，并改为
extension_dir =”D:\Dev\PHP\ext”
(2)添加如下两行
extension=php_mysql.dll
extension=php_mysqli.dll
重启Apache服务(通过services.msc)

四、安装tinyissue

1. 下载tinyissue，解压到D:\www\tinyissue

2. 修复与PHP5.5.6兼容问题
yield在高级版本中变成了关键字，不能将自定义函数命名为yield。
(1)找到Section.php，修改

public static function yield()
{
return static::yield(static::stop());
}

为

public static function yield_section()
{
return static::sections_yield(static::stop());
}

(2)找到helper.php，修改

function yield($section)
{
    return Laravel\Section::yield($section);
}

为

function helper_yield($section)
{
    return Laravel\Section::sections_yield($section);
}

3.配置Apache，修改httpd.conf，增加

<Directory "E:/www/tinyissue">
    AllowOverride None
    Options None
    Order allow,deny
    Allow from all
    Options Indexes MultiViews ExecCGI FollowSymLinks
    DirectoryIndex index.php
</Directory>

4.访问http://localhost/tinyissue/install/进行安装

5.OK～

继续阅读

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

Post author:iceyer
Post published:2013年12月8日
Post category:C++ Dev IceSee
Post comments:0评论

使用单件构造器(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*
}

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

继续阅读

freeglut 简明安装指南 for windows

Post author:iceyer
Post published:2013年11月16日
Post category:C++ Dev
Post comments:0评论

glut（GL Unity Tookit）是OpenGL的一套辅助开发函数库，但是由于缺乏更新以及非开源等原因，目前已经有12年没有维护，所以强烈建议更换到freeglut这个完全兼容的开源代替版本。

一、下载freeglut

freeglut的最新版本是2.8.1（Released: 5 April 2013）
可以从http://freeglut.sourceforge.net/获得其最新版本。

二、编译freeglut

freeglut提供了对windows平台良好的编译支持，在freeglut-2.8.1\VisualStudio目录下可以找到2008～2012版本的VS工程文件（经测试，VS2013也完全可以使用VS2012的工程文件）。
2.1. 打开对于版本的工程文件，选择对应的配置版本，建议Realese版本。
2.2. 生成–>生成解决方案
2.3. 生成文件在\freeglut-2.8.1\lib\x86目录，有freeglut.lib, freeglut.dll.

三、安装freeglut

3.1. Header文件安装：
将\freeglut-2.8.1\include\GL 目录复制到 Microsoft Visual Studio 12.0\VC\include目录下。
3.2. 库文件安装
将freeglut.lib文件复制到Microsoft Visual Studio 12.0\VC\lib目录下。
将freeglut.dll文件复制到C:\Windows\SysWOW64 【32位系统为 “C:\Windows\System32”】目录下。

四、使用freeglut

直接包含<gl/freeglut.h>文件即可。

继续阅读

Qt 5.1 编译中处理《error C2059: 语法错误:“常量”》错误

Post author:iceyer
Post published:2013年11月11日
Post category:C++ Dev
Post comments:3评论

新装了VS2013的环境，由于是64位系统并且Qt对VS2013支持不好，需要自己编译一下，但是编译过程中出现了些坑爹的问题：

error C2059: 语法错误:“常量”

报错的文件是win-math.h,代码如下：

enum {
  FP_NAN,
  FP_INFINITE,
  FP_ZERO,
  FP_SUBNORMAL,
  FP_NORMAL,
};

这段代码毫无疑问没有任何问题，但是FP_NAN这个宏可就有问题了，
FP_NAN在VS2013的标准头文件math.h被定义成了
#define _NANCODE 2
#define FP_NAN _NANCODE

结果这段代码就变成了：

enum｛
  2,
  FP_INFINITE,
  FP_ZERO,
  FP_SUBNORMAL,
  FP_NORMAL,
｝;

其他几个枚举值也有同样的问题，解决方法有两个：
一是删除这个枚举，毕竟在math.h中已有定义。
二是使用#undef：

#undef FP_NAN
#undef FP_INFINITE
#undef FP_ZERO
#undef FP_SUBNORMAL
#undef FP_NORMAL
enum FP_MATH_{
	FP_NAN,
	FP_INFINITE,
	FP_ZERO,
	FP_SUBNORMAL,
	FP_NORMAL,
};

继续阅读

头文件中使用static变量

Post author:iceyer
Post published:2013年9月15日
Post category:C++ Dev Ubuntu
Post comments:0评论

static是C/C++中让人迷惑的关键字。在一个文件对变量使用static关键字，则表示这个变量的作用范围仅限于本文件。
那么对于在头文件中使用static关键字，结果会如何呢。

首先，我们要明白，C++中对于头文件的处理。每个cpp文件在编译的时候都会将头文件(*.h)进行展开，这样就导致每个生成的*.o文件中均包含使用static修饰的变量，并且这个变量对其他文件不可见。结果是出现多份的变量，每个cpp文件中都只能访问本地的变量，这是一件较为危险的使用方法。

使用如下代码验证：

/*
    staticValue.hpp
    Check if static value will be copy in different .cpp s
*/
#pragma once

static int a = 0;

/*
    funcA.cpp
*/
#include <iostream>
#include "staticValue.hpp"

int funcA()
{
    std::cout<<"[funcA]"<<" &a\t= "<<&a<<std::endl;
    std::cout<<"[funcA]"<<" &::a\t= "<<&::a<<std::endl;
    return 0;
}

/*
    funcB.cpp
*/
#include <iostream>
#include "staticValue.hpp"

int funcB()
{
    std::cout<<"[funcB]"<<" &a\t= "<<&a<<std::endl;
    std::cout<<"[funcB]"<<" &::a\t= "<<&(::a)<<std::endl;
    return 0;
}

/*
    main.cpp
*/
#include <iostream>
#include "staticValue.hpp"

extern int funcA();
extern int funcB();

int main(void)
{
    std::cout<<"[main]"<<" &a:\t= "<<&a<<std::endl;
    std::cout<<"[main]"<<" &::a:\t= "<<&::a<<std::endl;
    funcA();
    funcB();
    return 0;
}

编译执行

iceyer@iceyer:~/$ g++ -g -o static-value main.cpp funcA.cpp funcB.cpp
iceyer@iceyer:~/$ ./static-value 
[main] &a:	= 0x602198
[main] &::a:	= 0x602198
[funcA] &a	= 0x6021a0
[funcA] &::a	= 0x6021a0
[funcB] &a	= 0x6021a8
[funcB] &::a	= 0x6021a8

继续阅读

如何设置FolderView的透明度为0

Post author:iceyer
Post published:2013年3月10日
Post category:Ubuntu
Post comments:0评论

FolderView是毫不逊色于Fences的桌面图标分类软件（好吧，别吐槽在linux上为什么需要这种东西啦）

Fences有个很炫的效果就是在鼠标离开时能够自动隐藏。其实改动FolderView的代码也可以轻松实现。

只要在鼠标进入和离开窗口时设置窗口的opacity属性即可。

	def on_mouse_enter (self, event):
		self.clicked = False
		self.opacity = 1
		self.redraw_canvas()
		self.show_tip()

	def on_mouse_leave (self, event):
		"""Called when the mouse leaves the Screenlet's window."""
		if not self.clicked:
                #设置为0
		        self.opacity = 0
			self.cursor_position = [-1,-1]
			self.redraw_canvas()
			self.hide_tip()#self.timer1 = gobject.timeout_add(2000, self.hide_tip)

另外的方法就是去修改screenlet窗口透明度限制，这对所有的控件都有效

继续阅读

Ubuntu下压缩文件乱码问题小结

Post author:iceyer
Post published:2012年6月11日
Post category:Ubuntu
Post comments:0评论

一、问题由来
Ubuntu的Unity和Gnome环境默认的压缩管理器是File-roller，这玩意会调用各种库和程序来完成文件的压缩和解压缩，这是个很好的做法，但可惜的是它调用的库各种不靠谱。好吧，如果你狠心把File-roller干掉，换上xarchiver或者Ark（这个没乱码，但是是QT支持，有洁癖者慎用），那么问题就好多了。
File-roller调用的库包括unrar，unrar-free，p7zip, p7zip-full, p7zip-rar，足足有5个，File-roller会按照一定的顺序来调用这些库，可惜这些库有各自的问题。
unrar，unrar-free在本人的电脑上会显示× unrar is not rar archive，然后完全无法解压。
p7zip, p7zip-full, p7zip-rar对rar乱码无解。

二、解决方法

1.使用unrar
完全卸载p7zip-rar，安装unrar。很多人能够通过这种办法解决，如果你能够正常使用，那么恭喜你了。如果不能，那么接着往下看。

2.使用带中文patch的p7zip
卸载掉p7zip, p7zip-full, p7zip-rar没错，卸掉所有的，然后去网上下载一个带中午补丁的p7zip，安装好，恩，无乱码的世界真美好。如果你足够蛋疼，那么接着往下看。

三、patch干了些什么？
对于一个linuxer来说，没有源码的东西，让人很不放心啊，这个中午patch能解决中文环境下的乱码问题，这么好的补丁问什么没有被Marge到代码中去呢？看看patch做了些什么吧……

-void CInArchive::ReadFileName(UInt32 nameSize, AString &dest)
+#include <iconv.h>
+void CInArchive::ReadFileName(UInt32 nameSize, AString &dest, const char *encoding)
{
...do something
}

这一段将ReadFileName函数增加encoding的控制参数

-  ReadFileName(headerNameSize, item.Name);
+  if (p[3] == NFileHeader::NHostOS::kUnix)
+    ReadFileName(headerNameSize, item.Name);
+  else
+    ReadFileName(headerNameSize, item.Name, MY_ENCODING);

这一段根据文件头信息来选择是使用默认处理方法还是自己修改的函数

+#define MY_ENCODING "gb18030"

在头文件中定义MY_ENCODING

相信这里大家看明白了，这个补丁只对gb18030编码有效。嗯嗯，估计永远不会被接受了……

继续阅读

在非终端下启动Matlab

Post author:iceyer
Post published:2012年4月2日
Post category:Matlab Ubuntu
Post comments:0评论

Ubuntu 的启动快捷方式是.desktop文件，而Matlab安装后默认是不创建这个文件的，如果自己去创建的话会发现必须将.desktop文件中的Terminal参数设置为true，Matlab才能正常启动。这对某些有各种奇怪癖好的人来说可能无法忍受了，并且你不小心关掉了一起启动的终端，matlab也会随之退出，这时就难免发生悲剧了。其实只要在matlab后面加一行 “-desktop”参数就行了，附上一个desktop文件的写法：

[Desktop Entry]
Name=Matlab
Comment=Matlab
Icon=/home/iceyer/Desktop/matlabicon/matlab.png
Exec=/home/usr/local/MATLAB/R2012a/bin/matlab -desktop
Terminal=false
Type=Application
GenericName[zh_CN]=Matlab R2012a

继续阅读

WPS for linux is comming

Post author:iceyer
Post published:2012年3月27日
Post category:Ubuntu
Post comments:0评论

WPS终于要来了，虽然以前WPS技术实现往QT转型时就在想会不会有跨平台版本，没想到金山真的把它给捣鼓出来了～看看论坛上放出的消息吧：

终于，我们带着日久弥新的WPS Office向一个新的世界迈出一步。

这可能只是很小的一步——面对桌面电脑占有份额依然较低、生态环境纷繁复杂的Linux桌面市场，我们对未来还没有全盘的把握和充分的信心，我们只能小步小步地摸着石头过河。

您，是否愿意和我们一起迎接新世界的挑战？

这又可能会是很大的一步——Linux及相关开源软件已走过了二十余年的风雨历程，业已占据了服务器、超级计算机、手机移动平台的大部分市场份额，而近年来，Linux桌面平台的可用性也在高速提升，应用软件也在不断丰富。然而，由于工程规模较大、用户需求较苛刻，办公软件，作为人们日常使用最多的软件之一，成为了完善Linux桌面可用性的最后一片大空白。能让用户（尤其是中文用户）普遍满意的办公软件的缺失，严重阻碍了Linux桌面的发展。

您，是否愿意和我们一起推动新世界的革新？

欢迎您加入WPS社区！

WPS for Linux 需要您的支持：
1. 为不同发行版制作安装包
2. 在不同的发行版和桌面环境下进行测试
3. 使用社区 bug 跟踪系统进行有效反馈(建设中)
4. 使用 wiki 系统(建设中)分享安装和使用心得
5. 以社区成员身份传递 WPS for Linux 项目的正确信息

请将申请信发送至 [email protected] 。形式不限，字数不限，但应包含以下信息：
1. 您常用的 Linux 发行版以及桌面环境或窗口管理器
2. 您常参与的开源社区、论坛以及相应的ID
3. 您愿意为社区做点什么（比如打包、测试、文档等）

PS:申请邮箱持续有效！

首批邀请码将在3月28日发放。请原谅我们社区组织经验的缺乏，也为了保证对反馈进行最迅速的响应，首批社区成员预计50人左右。只要有大家的支持，我们的社区一定会逐渐扩大

继续阅读

1
2
3
4
…
6
Go to the next page