Nov 8

RMQ再学习笔记 不指定

felix021 @ 2010-11-8 23:54 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(12406) | Via 本站原创
2年多以前看的算法,当时基本看懂了(实际上还是有问题的),今天再翻出来,感觉基本忘了,重新实现一遍,试着自己把推导过程也写写。非常赞的算法。

RMQ: Range Minimum Query, 区间最小值查询。已知数组在区间 [0, n) 有定义,给出 i, j (0 <= i < j <=n),求 [i, j) 之间的最小值。

朴素算法非常简单,但是显然,每次查询是O(N)的,效率很低:
min = +INFINITE
FOR k = i TO j - 1
  IF min > arr[k]
    min = arr[k]
  END IF
END FOR
RETURN min

由于经常遇到需要多次查询的情况,所以朴素算法不合意。一个比较好的改进是使用线段树/树状数组,首先通过O(NlogN)预处理,让每个分支节点保存了其所有叶子节点的最小值(由底向上递推)。这样每次查询的时候,就可以在O(logN)的时间内得到结果。具体代码稍繁琐,这里不写了。

最好的方法,是用叫做sparse_table的算法,其思路和线段树很像,区别是通过O(NlogN)的预处理,可以让查询的时间复杂度降低到O(1)。其具体思路为:

预处理:
1. 记F[s][p] = min{ arr[i] | s <= i < s + 2^p} = min(arr[s..(s + 2^p - 1)])。例如, F[1][2] = min{ arr[i] | 1<= i < 5} = min(arr[1..4])。
2. 由1,易推知,F[s][0] = min { arr[i] | s <= i < s + 1} = arr[s].
3. 通过由底向上递推的预处理得到所有满足(s + 2^p <= n, 即区间[s, s + 2^p) 包含于[0..n)区间内)的F[s][p] = min(F[s][p-1], F[s+2^(p-1)][p-1])。例如, F[2][3] = min(arr[2..9]) = min(min(arr[2..5]), min(arr[6..9])) = min(F[2][2], F[6][2]) = min(F[2][3-1], F[2 + 2^(3-1)][3-1])。

查询[i, j):
1. 令 k = log2(j - i)取整,则 (j - 2^k) <= (i + 2^k),即区间 [i, i + 2^k) 和 [j - 2^k, j) 必定覆盖 [i, j)。例如,区间[3, 8),k = log2(8-3)取整 = 2,则 [3, 7), [4, 8) 覆盖 [3, 8)。
2. RMQ[i, j) = min(F[i][k], F[j - 2^k][k]).

----扩展---
LCA(树中任意两个节点的最近公共祖先)问题,是可以通过RMQ+DFS来完成的,详见LCA问题。ZOJ 1141是一道纯LCA问题。

具体实现和检验代码如下(做了一点改进,F[s][p]中存放的是[s, s + 2^p)中最小值在数组中的索引):
Nov 2
C标准中的qsort函数,可以对任意类型的数组进行快速排序,用起来也还算方便,不过行为有一点诡异。加上之前曾经看过一篇文章(沈大写的,曾经登上过ecom的双周刊,居然在这个youalab.com也等出来了-。-),说是qsort不是线程安全的,所以把glibc的代码翻出来,看看qsort的具体实现。

用Ubuntu的话,找代码就很容易了:
引用
$ apt-get source libc6
$ cd eglibc-xxxx
$ grep -r . -Hne qsort | grep void

可以看到qsort是在stdlib.h里面的,源码在msort.c 302行,调用了qsort_r函数:
void
qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
  return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);                                                     
}
其中__compar_fn_t就是 int (*)(const void *, const void *)类型的函数指针,__compar_d_fn_t则是 int (*)(const void *, const void *, void *)类型的函数指针(为什么还有个void *呢?很神奇~求解)。

qsort_r函数也在msort.c中,约164行起。为了榨干CPU的性能,写了很多代码来优化效率,其流程大致是:

1. 判断额外所需内存大小,如果很小(<1024B),在栈上分配;否则获取系统内存参数——如果比可用内存小,试图在堆上分配;如果所需内存超过物理内存(为防出现不得不使用交换分区的情况致使性能恶化,故不分配),或者分配失败(可用空间不足),使用性能较差的stdlib/qsort.c中的_quicksort函数来排序。
    1.1. _quicksort位于 stdlib/qsort.c,对快排进行了两个改进:1. 将递归转化为递推; 2. 使用插入排序来处理4个元素以内的区间。不过用于交换两个元素的宏SWAP(a, b, size)没有额外的优化,比较意外(本来以为会考虑一次多个字节拷贝,或者使用duff device来减少循环)。

2. 分配成功的情况下,使用额外分配的空间,调用 msort_with_tmp() 函数来进行排序。
    2.1. 如果单个元素的大小超过32个字节,那么使用间接排序,分配空间时就有额外的判断,如果需要间接排序,则额外分配2n个指针的空间,前n个空间用于存放原指针,后n个空间用于按照所指元素大小存放排序好的指针。最后再按照排序好的指针顺序将元素拷贝。(注释中提到了Knuth vol. 3 (2nd ed.) exercise 5.2-10.,应该是指这个算法出自Knuth的《The Art of Computer Programming》卷3吧)
    2.2. 否则使用直接排序。这里也进行了一些优化,主要是为msort_with_tmp()提供p.var参数,完成针对元素的大小进行拷贝的优化:默认是使用gcc内置的__builtin_mempcpy来拷贝。
    2.3. msort_with_tmp对典型的快排也进行了非常赞的优化。
    2.3.1. 从msort_with_tmp的函数名和代码可以看出,这个算法不是就地排序,而是使用了第一步分配的O(N)的额外空间,这样可以让排序时的拷贝效率更高(这个优化应该对CPU的cache命中率也有较大的提高)。
    2.3.2. qsort_r传进来的参数p有个属性var
    (1) 默认情况下p.var = 4,使用mempcpy来进行拷贝。
    (2) 如果单个元素大于32bytes,p.var = 3, 表示是间接排序,拷贝的是指针,不是元素
    (3) 如果数组是按uint32_t对其的,且元素的大小是uint32_t的倍数,则可以进一步优化到每次按照uint32_t/uint64_t/unsigned long来进行拷贝,一次拷贝4或者8个字节,此时p.var = 0,1,2表示按照uint32_t, uint64_t, unsigned long拷贝。

直接在里头做了些注释,有兴趣的话可以更仔细地看看。可以的话自己去下了glibc的源码阅读,更有意思:D
Oct 22

灵魂守恒定律 不指定

felix021 @ 2010-10-22 23:54 [IT » 程序设计] 评论(2) , 引用(0) , 阅读(5597) | Via 本站原创
一切都是从,那道蚂蚁题,开始的
那题中的蚂蚁有20只,爬在长的木棒一根
左边蚂蚁10只向右爬
右边蚂蚁10只向左爬
蚂蚁爬的速度都相同
一碰头各自原速调头
然后就问,这些个蚂蚁,要碰多少次头才会从木棒上都掉下去

一说起这个问题,可能很多人有看过编程之美4.7 蚂蚁爬杆的问题:有一根27厘米长的细长木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置 处各有一只蚂蚁。木杆很细,不能同时通过2只蚂蚁。开始时候,蚂蚁的头朝左还是朝右是任意的,他们只会朝前走或者掉头,但是不会后退。当任意2只蚂蚁碰头后时,2只蚂蚁会同时掉转头朝反方向走。架设蚂蚁每秒钟可以走一厘米的距离。编写程序,求所有蚂蚁都离开木杆的最短时间和最长时间。

留一些空间不剧透,有兴趣的同学可以先想想然后再往下看。
Sep 30
看了下百度百科对UTF-8的说明,随手写的,基本能用。

比较诡异的是本来UTF8getchar想用strncpy的,但是这个函数有坑....

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define alloc(type, size) ((type *)malloc(sizeof(type) * size))

struct UTF8char
{
    unsigned short length;
    char data[7];
};

unsigned UTF8getcharlen(const char *s)
{
    unsigned char t = (unsigned char) s[0];
    if (t < 0x80) //0xxx xxxx
        return 1;
    else if (t < 0xe0) //110x xxxx
        return 2;
    else if (t < 0xf0) //1110 xxxx
        return 3;
    else if (t < 0xf8) //1111 0xxx
        return 4;
    else if (t < 0xfc) //1111 10xx
        return 5;
    else if (t < 0xfe) //1111 110x
        return 6;
    else //0xff
        return 1;
}

int UTF8getchar(UTF8char *c, const char *s)
{
    int i;
    c->length = UTF8getcharlen(s);
    for (i = 0; i < c->length && s[i] != 0; i++)
        c->data[i] = s[i];
    c->data[i] = 0;
    return (i == c->length);
}

int UTF8cmp(const UTF8char *c, const char *s)
{
    return strncmp(c->data, s, c->length);
}

int main()
{
    char linebuf[4096];
    UTF8char c;

    scanf("%s", linebuf);

    int reti = UTF8getchar(&c, linebuf);
    assert(reti != 0);

    printf("%d %s\n", c.length, c.data);
    return 0;
}
Aug 21

程序员的浪漫 不指定

felix021 @ 2010-8-21 18:11 [IT » 程序设计] 评论(1) , 引用(0) , 阅读(4773) | Via 本站原创
dim arr(3)
arr(1)=-12590
arr(2)=-20306
arr(3)=-15133
str = ""
for i = 1 to 3
    str = str & chr(arr(i))
next
CreateObject("SAPI.SpVoice").Speak str
Aug 21

sdbm hash for PHP 不指定

felix021 @ 2010-8-21 01:59 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3316) | Via 本站原创
上一篇提到了,使用sdbmhash来生成64bit摘要。这个算法,是需要用在PHP里头的,但是PHP在设计的时候有点囧,用于表示任意变量的 zval 这个struct里头,有一个union是用于存放不同数据类型的,而该union中用于表示整型的变量,就只有一个long。于是很杯具地:

1. 32bit OS下面的php只支持32bit整数
2. 不支持无符号整型

那个抑郁啊,于是只好用php的bcmath这个大整数库来实现上一篇的sdbmhash算法:
function sdbmhash($str)
{
    $mul = "65599"; // (1 << 6) + (1 << 16) - 1
    $mod = "18446744073709551616"; // 1 << 64

    $hash = "0";
    for ($i = 0; $i < strlen($str); ++$i)
    {
        $hash = bcmod(bcmul($hash, $mul), $mod);
        $hash = bcmod(bcadd($hash, ord($str{$i})), $mod);
    }
    return $hash;
}

大整数库是用字符串来模拟的,没有对位移的直接支持。于是刚开始的时候用 bcmul($hash, 1<<6) 之类来替代C实现中的位移;然后果断发现自己SB了,直接乘65599更合适。

当然了,由于是用字符串来模拟的,可以想象这段代码效率是很低的。但是有多低呢?在我的Ubuntu虚拟机上测试了一下,1w次对18个字符的hash需要大约2.4s,也就是说一次调用大约需要0.2~0.3ms。宿主机是windows(AMD M320, 2.1GHz),php的效率更低,大约花了3~4s。在同样的时间里,纯C实现,可以进行相同的运算10,000,000+次,效率比大约是PHP:C = 1:1000。

由于0.2~0.3ms这个数量级比较大了,于是决定把它写成一个PHP扩展。参照百度文库的这篇教程 http://wenku.baidu.com/view/044da6f8941ea76e58fa04b1.html 比较快就上手了。

最终实现的效率比是大约1:100。看来PHP的扩展开销还是很大啊。

记得前年曾经和@Sandy讨论过ASP、PHP、JSP的效率,他认为ASP和PHP在同一个数量级,和JSP差距很大(而我当初则认为PHP和JSP差距不大)。这个数据很好地证明了这一点。

最后,附上这个PHP扩展。
下载文件 (已下载 497 次)
Aug 21
前两天在找个摘要算法,要求很简单,冲突少,生成64bit摘要;安全性可以忽略。MD5/SHA-1是好算法,但是它们生成的摘要是128/160bit的。Qining最初提出了个算法,将MD5的128bit分成4个32bit,d[0..3],然后通过以下公式获得64bit摘要:
引用
concat(d[0] XOR d[2], d[1] XOR d[3])
看起来挺有模有样的,但是用0..100,000去测试,发现了3个碰撞,毕竟没有数学理论的支持,胡搞还是不行的。另外再尝试了下,把MD5的前64bit拿出来,效果倒是好,前100,000没有碰撞。只是这种做法毕竟不让人放心,于是到网上搜了一下,发现不少人有此需求,但是没有现成的算法,挺无奈的。还好,有个人一语道破天机:用个字符串hash算法就行了。

于是翻出以前的一篇日志字符串的Hash,从里头把sdbm哈希函数搞出来,测试了一下(跑了好几分钟呢),效果很赞,一亿以内的整数都没有问题,代码如下:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <assert.h>
using namespace std;

typedef unsigned long long ull;

ull sdbmhash(const char *s){
    ull hash = 0;
    while (*s){
        hash = (hash << 6) + (hash << 16) - hash + *s++;
    }
    return hash;
}

int main()
{
    const unsigned N = 100000000;
    ull *all = new(nothrow) ull[N];
    assert(all != NULL);
    unsigned i = 0;
    char tmp[100];
    for (i = 1; i <= N; ++i)
    {
        snprintf(tmp, 100, "%09u", i);
        all[i] = sdbmhash(tmp);
        if (i % (N / 20) == 0) printf("i = %u\n", i);
    }
    sort(all, all + N);
    ull * end = unique(all, all + N);
    printf("%u\n", all + N - end);
    delete[] all;
    return 0;
}
Jul 29

在VC6.0下用GDI+画图 不指定

felix021 @ 2010-7-29 00:50 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(3709) | Via 本站原创
1. 下载gdi+的sdk,安装。当然,可以简化一点,从这里[ http://download.csdn.net/down/1645798/huohuo1120 ]下载gdiplus所需文件包,解压并导入到vc6(将include和lib目录加入vc6的配置中)

2. 在VC6中创建一个Win32 Application,选择“一个简单的Win32程序”。假设项目名是main

3. 在StdAfx.h中加入
#include <winbase.h>
#define UNICODE
#include <comdef.h>
#ifndef ULONG_PTR
#define ULONG_PTR unsigned long*
#include <GdiPlus.h>
using namespace Gdiplus;
#endif

4. 在main.cpp的WinMain前面生命全局的两个GDI变量
GdiplusStartupInput gdiplusStartupInput;
ULONG_PTR          gdiplusToken;

5. 在程序退出之前的地方加上
GdiplusShutdown(gdiplusToken);

6. 画图

6.1 创建一个Bitmap对象
Bitmap *pBitmap = new Bitmap(width, height, PixelFormat24bppRGB);

6.2 从Bitmap中获取Graphics对象
Graphics *g = Graphics::FromImage(pBitmap);

6.3 使用各种东西的组合来搞g,比如Pen, Brush, Region, Rect, PointF, Font……
Pen pen_black(Color(255, 0, 0, 0), 3);
g->DrawLine(&pen_black, 0, 0, 100, 100);
更具体的说明和各种例子可以在这里找到:GDI+ SDK参考(翻译版本) http://download.csdn.net/source/642128

7. 保存文件,这个比较麻烦
int GetEncoderClsid(const WCHAR* format, CLSID* pClsid)
{
  UINT num= 0, size= 0;

  ImageCodecInfo* pImageCodecInfo= NULL;
  GetImageEncodersSize(&num, &size);
  if(size== 0)
    return -1;
  pImageCodecInfo= (ImageCodecInfo*)(malloc(size));
  if(pImageCodecInfo== NULL)
    return -1;

  GetImageEncoders(num, size, pImageCodecInfo);
  for(UINT j=0; j< num; ++j)
  {
    if(wcscmp(pImageCodecInfo[j].MimeType, format)== 0)
    {
      *pClsid= pImageCodecInfo[j].Clsid;
      free(pImageCodecInfo);
      return j;
    }
  }
  free(pImageCodecInfo);
  return -1;
}

......

CLSID encoder;
GetEncoderClsid(L"image/png", &encoder); // L"image/jpeg", ...
pb->Save(L"result.png", &encoder, NULL);
分页: 5/21 第一页 上页 1 2 3 4 5 6 7 8 9 10 下页 最后页 [ 显示模式: 摘要 | 列表 ]