当前位置:  编程技术>综合

[1]find_first_zore_bit-一个位图的实现

如果希望在多个地方在一个域内分配一个一个全局唯一的ID（或者IP地址），该怎么办呢？最简单的方式我觉得就是使用位图。Linux内核对位图的支持很强，因此一年前的我直接将kernel里面的代码copy到了OpenVPN，直到我发现OpenVPN在32位平台编译不过去时，才发现问题-决不能将汇编代码随意复制，因为那是高度平台相关的。因此就想用C语言重新实现。
        关键问题是实现将某一个bit设置为1或者0。该怎么实现呢？如果有1000000000000+个位，我总不能搞一个大循环吧...那怎么办？我们知道循环肯定是消耗CPU最多的操作，因为对于循环而言，CPU（包括我们人）都是在做重复的事情，重复的事情是比较无聊的，那么怎么办呢？当然是使用CPU原生支持的指令了，那就是移位。类比Intel x86的页表机制，我们也能将一个字节做出很多“意义”。
        试想有以下的数组：char bits[1024];那么我们可以认为内存中有连续1024字节的空间属于我们，我们怎么寻址到其中的第index位呢？很简单，第一步，我们需要知道这个index所在的位属于数组的第几个元素，而这个很简单：

bits[i >> 3];

为什么要移位3位呢？因为char是8位，而二进制的8（0-7总共8个元素）个数字能表示为3位的二进制数，那么一个index的高5位（8-3）就表示了数组的下标。接下来就需要确定该index在一个byte中的位置，对于Intel系统，它就是：

7 -1 - (i & 0x07)

这样，bit定位就解决了，接下来就是如何设置对应的bit为0或者1的问题了，这更简单：

#define INDEXSFT 3
#define MASK 0x07
#define MAX_BITS 8192
#define BYTEBITS 8

char data_bits[MAX_BITS] = {0};

void set_bit(int i, int data)
{
    if (data == 0) {
        data_bits[i >> INDEXSFT] &= ~( 1 << (BYTEBITS -1 - (i & MASK)));
    } else {
        data_bits[i >> INDEXSFT] |= (1 << (BYTEBITS -1 - (i & MASK)));
    }
}

位图的基础已经实现，最关键的是如何找出第一个为0（即空闲）的bit，因此我们需要实现一个判断函数：

int test_bit(int i)
{
    int res = data_bits[i >> INDEXSFT] & (1 << (BYTEBITS -1 - (i & MASK)));
    return res;
}

那么最后，就剩下实现find_first_zero_bit了：

int find_first_zero_bit(int size)
{
    int i = 0, test_bits = 0;
    int bits = (size+8)/BYTEBITS;
    for (; i < bits; i++) {
        int j = 0;
        for (; j < BYTEBITS; j++) {
            int index = i*BYTEBITS+j;
            if (index > size) {
                return -1;
            } else if (!test_bit(index)) {
                return test_bits;
            }
            test_bits ++;
        }
    }
    return -1;
}

这样，一切就完成了。其实我们还会有有一个helper函数：

int find_first_zero_bit_set(int size)
{
    int zero_bit = find_first_zero_bit(size);
    if (zero_bit != -1) {
        set_bit(zero_bit);
    }
    return zero_bit;
}

整个实现很清爽，很容易维护。我在使用中还加入了序列化，文件锁的操作可以将位图同步到磁盘文件实现持久化，这里就不再赘述了。有一个问题，为何不用int或者long long数组呢？效率还会快一些，比8字节的char要好吧。因为我害怕那些big/littile endian的问题...
         遗留的问题是，怎么将上述实现用PHP以及bash完成，这么做的理由是对于打包少了一次编译的过程，代码也更好维护。姑且不论这么做的价值，最终我想在某个时间搞一次调查，那就是：有谁能一次性成功编写100+行的bash脚本。我每写一个脚本，都要试好几次才能成功，特别是是在makefile里面调用bash，有时3行代码要试一上午，最终发现最后的\标记后面有一个空格...
     ......

[2]libdvm.project

<?xml version="1.0" encoding="UTF-8"?>
<CodeLite_Project Name="libdvm" InternalType="Library">
  <Plugins>
    <Plugin Name="qmake">
      <![CDATA[00010001N0005Debug000000000000]]>
    </Plugin>
  </Plugins>
  <Description/>
  <Dependencies/>
  <VirtualDirectory Name="src">
    <VirtualDirectory Name="vm">
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Jni.c"/>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Init.c"/>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/ReferenceTable.c"/>
      <VirtualDirectory Name="oo">
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/oo/Class.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/oo/TypeCheck.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/oo/Array.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/oo/Resolve.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/oo/AccessCheck.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/oo/Object.c"/>
      </VirtualDirectory>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Thread.c"/>
      <VirtualDirectory Name="alloc">
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/CardTable.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/Heap.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/Alloc.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/HeapSource.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/Visit.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/clz.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/HeapTable.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/Verify.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/MarkSweep.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/DdmHeap.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/HeapBitmap.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/HeapDebug.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/alloc/HeapWorker.c"/>
      </VirtualDirectory>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Atomic.c"/>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/CheckJni.c"/>
      <VirtualDirectory Name="interp">
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/interp/Stack.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/interp/Interp.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/interp/Jit.c"/>
      </VirtualDirectory>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Native.c"/>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Sync.c"/>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Misc.c"/>
      <VirtualDirectory Name="reflect">
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/reflect/Reflect.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/reflect/Annotation.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/reflect/Proxy.c"/>
      </VirtualDirectory>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/UtfString.c"/>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Properties.c"/>
      <VirtualDirectory Name="mterp">
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/mterp/Mterp.c"/>
        <VirtualDirectory Name="out">
          <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/mterp/out/InterpC-portstd.c"/>
          <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/mterp/out/InterpC-portdbg.c"/>
          <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/mterp/out/InterpC-x86.c"/>
        </VirtualDirectory>
      </VirtualDirectory>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/AllocTracker.c"/>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/InlineNative.c"/>
      <VirtualDirectory Name="analysis">
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/analysis/DexVerify.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/analysis/RegisterMap.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/analysis/DexPrepare.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/analysis/Optimize.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/analysis/VerifySubs.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/analysis/CodeVerify.c"/>
      </VirtualDirectory>
      <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/Intern.c"/>
      <VirtualDirectory Name="native">
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/InternalNative.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/sun_misc_Unsafe.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/dalvik_system_DexFile.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/dalvik_system_VMDebug.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/dalvik_system_VMRuntime.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/dalvik_system_VMStack.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/dalvik_system_Zygote.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_Class.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_Object.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_reflect_AccessibleObject.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_reflect_Array.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_reflect_Constructor.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_reflect_Field.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_reflect_Method.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/vm/native/java_lang_reflect_Proxy.c"/>
        <File Name="../../android-omap-20111108-gingerbread/dalvik/v

[3]关于“人工智能”的思考

        (一点点想法和思考)

      “人工智能”，窃以为是计算机科学最引人入胜的一个方向，可惜的是我们还没能看到有任何突破性的进展，就像网易公开课对“斯坦福机器学习”课程的描述一样，“人工智能”似乎遇到了一个瓶颈。虽然如你所见，似乎智能化在ios上的siri之后越来越接近人们的生活了，但其实本质上并没有任何的突破。张钹院士有这样一个比喻“人类的技术发展正如同开门，当我们找不到这扇门的钥匙时，如果能够有一块砖头，我们多半会抄起砖头将门砸开。”现在的“人工智能”就是这样一块砖，至于砸开砸不开，那就很难说了。

       对这个问题国内外似乎有普遍的认识，All models are wrong, but some models are useful. — George Box，其实差不多也是这个意思，我们并没能找到人工智能的key，而是在用一些其它方法让程序看起来比较智能。再罗列一个东西吧，是网上看到的十大实验(?)之一：

       开始学习机器学习也有半年了，要说感受就是excited &  disappointed，excited是因为终于知道了一些人工智能的算法并且编了一些码跑起来，disappointed是因为我看不到这块砖砸开人工智能之门的希望，虽然"机器学习无疑是最有希望实现这个目标的方向之一"。

       今天拜读了图灵的里程碑论文《计算机器与智能》，在感叹图灵真是天才之余，着实认真思考了一番。图灵反驳了很多观点，其中我觉得由为有意思的一句话是“According  to the most extreme  form of this view the only way by which one could be sure that a machine thinks is to be the machine and to feel oneself  thinking”，即是“你若要肯定一台机器是否能思维，唯一的途径就是成为那台机器并且去感受自己的思维活动。”这当然这是不现实的事情，也使“人工智能不存在”这个观点很无力。人工智能感觉就像外星人一样，你没法否定它的存在的可能性，可是谁都没见到过~~~~~甚至我们连一个“声称见过”的人都没有……

       图灵在论文里描述的Learning Machine和现在机器学习的思路很类似，(也许这就是来源？我孤陋寡闻了？)，至于这样是否能创造出真正的人工智能，图灵举了这样一个例子，也就是说当原子堆很小时是不会产生链式反应的，但如果原子堆足够大了之后就会因为一个中子的轰击产生核裂变。图灵把一个想法比作中子，而人的思想比作原子堆，有一小部分思想处于超临界状态，进入其中的想法将会产生越来越多的想法，最终成为一个完整的"理论"，也就是智能，那么是否有一天这样一个“学习机器”也能进入超临界状态而产生人工智能呢？-----我想除了时间没谁知道答案

       人工智能，对于社会、经济、文化的影响我就不赘述了，各种科幻大片已经做了足够的渲染，现在的关键是在这个人工智能的瓶颈期，五花八门的想法随之而来，比如说对统计学方法批评的有，支持的也有。下面谈一点拙见：是不是我们应该像上面那句长长的英文说的那样“换位思考”一下，这样的换位应该不仅仅局限于“噢，电脑看到的图片是一个矩阵的数字”这样，而是尽量彻底地去换位，思考一下它能感觉到的数据是什么、它的方向感、它的位置感等等对于思考很重要的东西，(这只是我粗浅的想法=囧=，有点扯，见谅，跳过吧)

        就像图灵论文结尾时所说的

            We can only see a short distance ahead， 
            but we can see plenty there that needs to be done。

        很遗憾，我们似乎还在图灵的short distance里，真的希望有朝一日能有真正的人工智能诞生。