DC3算法

最近做了一个差量更新工具， 实质就是一个Diff工具。这个Diff工具在本地生成一个patch文件。客户端通过网络下载到本地后，根据本地文件和patch文件来生成最新版本文件。 与传统patch不同的是，为了尽可能的减少网络传输，patch文件需要尽可能的小，并且不需要逆向patch(从版a到版本b生成的patch, 版本b使用这个patch可以还原到版本a). 基于以上考虑，我重新设计了一个二进制patch格式，整个patch文件中有两种Action（分别是COPY， INSERT)，大致数据结构如下： [c] struct COPY { ……

如何恢复全局INDEX

一般来说，当需要分配全局惟一id时，一般都会有一个变量来记录当前最新的id值，比如叫INDEX变量。 每次需要分配id时，只要简单的自增一下INDEX变量，然后INDEX的值即为当前分配出去的ID的值。 为了最大可能的延迟复用已经分配过的id，一般来说不会去特殊处理INDEX变量，即每次自增INDEX，并允许回绕情况的发生。 但是最近碰到问题就是，我有一堆分配过的id，如何重新恢复出INDEX的值。具体场景如下： [c] struct obj { unsigned int id; time_t createtime; ……

为什么要使用算法

在接触算法之初, 我为诸如快速排序, 二分查找效率感到惊讶. 随着代码量的增加, 对于如动态规划之类以空间换取时间的算法, 我还能理解. 但是我始终不明白如二分查找这类需要前置条件算法为什么能提高程序效率, 虽然查找快了, 但是开销浪费在了排序上, 使用二分查找的一次读写的开销和, 甚至很可能比不使用算法还要慢. 最近在阅读了一些开源代码之后, 终于有点明白为什么如二分查找这类需要前置条件算法可以提高程序效率了. 在程序设计中, 使用如二分查找这类需要前置条件的算法之所以……

生成不重复随机数

今天碰到一个生成不重复随机数题目, 题目类似如下: 在一个1K的数组中生成1~1M之间的随机数, 1K中的随机数不能重复. 第一反应就是暴力查询, 每生成一次就去已有的数据查询, 时间复杂度为O(n2). 效率极差. 仔细思考后发现这样一种特性, 数值空间为1~1M, 需要取出1K个数据, 1M = 1K * 1K 类似下面代码: int buff[1024]; int tmp = 0; for (i = 0; i < 1024; i++) { tmp += 1024; buff[i] = tmp; } 上面的代码如果执行完毕那么tmp的结果会成为1M. 将一个0~1023之间的……

CheckSum计算的优化

　　最近在纠结于大数据的checksum的计算，算法如下： 1 unsigned long cs_cal(const unsigned char *buff, unsigned long size) 2 { 3 unsigned long cs; 4 5 cs = 0; 6 while (size--) 7 cs += buff[size]; 8 9 return cs; 10 } 　　当文件大于4G后这种计算的龟速就很明显了，在网上看到大牛说MMX指令对于数据计算相当不俗，于是改成下面代码（bug:不对齐部分没有处理，这部分消耗很小,对于效率影响不大）： 1 unsigned long cs_cal(const……

32位系统使用文件作为媒介来模拟大于4G内存访问

代码一篇，暂时没发现bug: 1 // vm_mgr.cpp : Defines the exported functions for the DLL application. 2 // 3 4 #include "stdafx.h" 5 6 #include <Windows.h> 7 #include <vector> 8 #include <assert.h> 9 #include <tchar.h> 10 #include "../common/assist.h" 11 #include"../error_no/error_no.h" 12 #include "../Log/log.h" 13 #include "vm_mgr.h" 14 15 #define VM_ADDR_GEN(addr, index) (assert……