竹磬网-邵珠庆の日记 生命只有一次，你可以用它来做些更多伟大的事情–Make the world a little better and easier


261月/150

北京市小汽车摇号程序的反编译、算法及存在的问题浅析-不重复随机数列生成算法

发布在 邵珠庆

给定一个正整数n，需要输出一个长度为n的数组，数组元素是随机数，范围为0 – n-1，且元素不能重复。比如 n = 3 时，需要获取一个长度为3的数组，元素范围为0-2，

比如 0,2,1。

这个问题的通常解决方案就是设计一个 hashtable ，然后循环获取随机数，再到 hashtable 中找，如果hashtable 中没有这个数，则输出。下面给出这种算法的代码

        public static int[] GetRandomSequence0(int total)
        {
            int[] hashtable = new int[total];
            int[] output = new int[total];
 
            Random random = new Random();
            for (int i = 0; i < total; i++)
            {
                int num = random.Next(0, total);
                while (hashtable[num] > 0)
                {
                    num = random.Next(0, total);
                }
 
                output[i] = num;
                hashtable[num] = 1;
            }
 
            return output;
        }

 

代码很简单，从 0 到 total - 1 循环获取随机数，再去hashtable 中尝试匹配，如果这个数在hashtable中不存在，则输出，并把这个数在hashtable 中置1，否则循环尝试获取随机数，直到找到一个不在hashtable 中的数为止。这个算法的问题在于需要不断尝试获取随机数，在hashtable 接近满时，这个尝试失败的概率会越来越高。

 

那么有没有什么算法，不需要这样反复尝试吗？答案是肯定的。

 

image

如上图所示，我们设计一个顺序的数组，假设n = 4

第一轮，我们取 0 – 3 之间的随机数，假设为2，这时，我们把数组位置为2的数取出来输出，并把这个数从数组中删除，这时这个数组变成了

image

第二轮，我们再取 0-2 之间的随机数，假设为1，并把这个位置的数输出，同时把这个数从数组删除，以此类推，直到这个数组的长度为0。这时我们就可以得到一个随机的不重复的序列。

这个算法的好处是不需要用一个hashtable 来存储已获取的数字，不需要反复尝试。算法代码如下：

        public static int[] GetRandomSequence1(int total)
        {
            List<int> input = new List<int>();
            for (int i = 0; i < total; i++)
            {
                input.Add(i);
            }
 
            List<int> output = new List<int>();
 
            Random random = new Random();
            int end = total;
            for (int i = 0; i < total; i++)
            {
                int num = random.Next(0, end);
                output.Add(input[num]);
                input.RemoveAt(num);
                end--;
            }
 
            return output.ToArray();
        }

 

这个算法把两个循环改成了一个循环，算法复杂度大大降低了，按说速度应该比第一个算法要快才对，然而现实往往超出我们的想象，当total = 100000 时，测试下来，第一个算法用时 44ms, 第二个用时 1038 ms ，慢了很多！这是为什么呢？问题的关键就在这个 input.RemoveAt 上了，我们知道如果要删除一个数组元素，我们需要把这个数组元素后面的所有元素都向前移动1，这个移动操作是非常耗时的，这个算法慢就慢在这里。到这里，可能有人要说了，那我们不用数组，用链表，那删除不就很快了吗？没错，链表是能解决删除元素的效率问题，但查找的速度又大大降低了，无法像数组那样根据数组元素下标直接定位到元素。所以用链表也是不行的。到这里似乎我们已经走到了死胡同，难道我们只能用hashtable  反复尝试来做吗？在看下面内容之前，请各位读者先思考5分钟。

…… 思考5分钟

算法就像一层窗户纸，隔着窗户纸，你永远无法知道里面是什么，一旦捅穿，又觉得非常简单。这个算法对于我，只用了2分钟时间想出来，因为我经常实现算法，脑子里有一些模式，如果你的大脑还没有完成这种经验的积累，也许你要花比我长很多的时间来考虑这个问题，也许永远也找不到捅穿它的方法。不过不要紧，我把这个方法公布出来，有了这个方法，你只需轻轻一动，一个完全不同的世界便出现在你的眼前。原来就这么简单……。

 

还是上面那个例子，假设 n = 4

image

 

第一轮，我们随机获得2时，我们不将 2 从数组中移除，而是将数组的最后一个元素移动到2的位置

image

这时数组变成了

image

第二轮我们对 0-2 取随机数，这时数组可用的最后一个元素位置已经变成了2，而不是3。假设这时取到随机数为1

我们再把下标为2 的元素移动到下标1，这时数组变成了

image

以此类推，直到取出n个元素为止。

这个算法的优点是不需要用一个hashtable 来存储已获取的数字，不需要反复尝试，也不用像上一个算法那样删除数组元素，要做的只是每次把数组有效位置的最后一个元素移动到当前位置就可以了，这样算法的复杂度就降低为 O(n) ，速度大大提高。

经测试，在 n= 100000 时，这个算法的用时仅为7ms。

下面给出这个算法的实现代码

        /// <summary>
        /// Designed by eaglet
        /// </summary>
        /// <param name="total"></param>
        /// <returns></returns>
        public static int[] GetRandomSequence2(int total)
        {
 
            int[] sequence = new int[total];
            int[] output = new int[total];
 
            for (int i = 0; i < total; i++)
            {
                sequence[i] = i;
            }
 
            Random random = new Random();
 
            int end = total - 1;
 
            for (int i = 0; i < total; i++)
            {
                int num = random.Next(0, end + 1);
                output[i] = sequence[num];
                sequence[num] = sequence[end];
                end--;
            }
 
            return output;
        }

 

下面是n 等于1万，10万和100万时的测试数据，时间单位为毫秒。从测试数据看GetRandomSequence2的用时和n基本成正比，线性增长的，这个和理论上的算法复杂度O(n)也是一致的，另外两个算法则随着n的增大，用时超过了线性增长。在1百万时，我的算法比用hashtable的算法要快10倍以上。

 

  10000 100000 1000000
GetRandomSequence0 5 44 1075
GetRandomSequence1 11 1038 124205
GetRandomSequence2 1 7 82

 

现在摇号的程序及数据都可以在官网中查看，目的就是通过信息的透明度来堵住那些说摇号系统有猫腻之类的传言，我做为一个程序员，下意识的就想看看到底是否有猫腻。

通过下载程序，导入数据，将种子数写入后，的确没有什么猫腻，但还是不死心，想研究一下算法，结果发现了惊人的事情。
此算法使用的是伪随机，简单点将就是当种子数一定，摇号数据一定，每次随机结果都是一样的。举个例子，借用某申请编码2245102443992，摇号基数序号500015，取种子数范围在100000至120000之间能中签的种子数，结果显示共132个种子数，其概率为0.66%。随机找了一个种子数100575进行计算，得出结果在左侧表中，查询2245102443992是否中签，结果显示中签，在第15916行摇中；所以大家都应该知道怎么回事了吧，只要摇号池数据确定，查询出摇号基数序号，就能算出中签的种子数都有哪些，所以公布的数据和程序又有何用？关键在于种子数的确定。

 

 

标签: , , , , , , 没有评论
278月/130

浅析优惠券模式–如何应对商家违规

发布在 邵珠庆

团购之后，优惠券又遍地开花，早在互联网兴起之前，优惠券就是许多商家的促销手段。而这种立足于本地生活服务，同时捆绑着移动互联网、二维码概念的优惠券模式，会让消费者和商家产生怎样的反应呢？某日与人聊天后，仅以我所知的一种模式为例：消费者前往餐厅就餐时，以手机扫描菜单上的二维码，或者展示手机二维码，由餐厅扫描，就可以享受一定程度的优惠，而运营这种优惠券模式的互联网企业则从中收取佣金，虽然很少，但这明显是长尾市场，积少成多也是非常可观的。

商家扫描用户，还是用户扫描商家？

先说一个有意思的问题：到底该由谁出示二维码比较合理？又由谁来扫描比较划算呢？这种成本永远不要指望用户去承担，因为他们可以拒绝消费。

如果是商家扫描用户：针对用户提供的任何二维码载体，商家都需要使用自有的扫描终端，在现有餐厅点菜系统的基础上改进，只需要一次性的固定投入成本。更现实一点，服务员使用自有的智能手机都可以完成扫描。

如果是用户扫描商家：用户通常手持智能手机，提供二维码扫描的软件则很多。目前来看，商家需要在菜单等载体上印刷二维码，而且陆续和不同的网站合作，就要加印不同的二维码，这是长期的投入，管理上也很繁琐。除非，商家的信息化程度很高，有一套能即时生成相应二维码的电子系统，这也需要开发。

综上来看，好像两种方式都可行，但是仔细一想，网站要从中提取佣金，自然需要记录每一次有效的扫描。如果由商家扫描用户，交易完成后商家完全可以否认（如果不借助其他手段的话）；如果由用户扫描商家，多次扫描如果只形成一次交易，商家也觉得吃亏。所以，需要借助一个确定的交易行为标志来辅助记录，付款就是一个比较显然的交易行为标志。

于是，不论双方谁扫描谁，都要通过手机支付来完成交易，一旦涉及钱财交易就会牵涉交易安全等问题，看起来没多少技术含量的优惠券模式就变得不再简单。当然，这仍然存在交易漏洞，扫描完成之后，双方已经互相确认身份，但是不通过手机支付的话，网站仍然无法抽取本次交易的佣金，在当前手机支付远未主流的现实条件下，手机账户上没钱，吃一顿饭掏钱包一点也不稀奇。即使通过网站与商家的合同限定，也无法完全杜绝这种行为。

不求精确，但求模糊，手机支付未必能达成目标却徒增风险和成本，接下来怎么办？重回原点：

扫描和交易现场只有商家和用户双方，漏报交易次数符合商家的利益，所以网站不能指望他们，那只有指望用户，给予用户某种激励，使其监督与商家的交易，这种方式看起来更加简单，但是激励策略的制定却会很有讲究。这需要对用户的心理做出足够的研究分析，使用户在“网站激励”与“商家摒除网站能给予更大优惠”之间选择时，能显著地偏向于网站。

这种激励可能为：积分奖励，荣誉奖励，举报收益等等。

商家与用户的博弈

商家与用户的交易过程可能是什么样的？从用户使用优惠券的角度出发，先来看看商家与用户的博弈（其实为网站借助用户与商家的博弈）：

由图中可见，红色的分支是优惠券模式下，最正常的分支，也是网站获益最大的分支；蓝色分支则是商家获益最大的分支，但是对于网站而言，蓝色分支要么不可控，要么在与商家正常合作的背景下不太可能出现。所以，只有紫色的分支最有可能影响网站的收益，从而影响优惠券模式的存在。

紫色的分支主要分为两种：

  • 1.当用户与商家接触后，出于对自身更大优惠的争取，用户是有某种激励可能与商家达成某种私下交易。
  • 2.当用户与商家熟悉后，熟客的往来更有可能催生用户与商家绕开网站直接交易。

以上两种，尤其是当商家给出的优惠券的优惠幅度远小于商家自行给用户的优惠幅度时。

所以，作为网站，可以尝试采取如下应对措施：

  • 1.向商家争取足够的优惠，维持商家合理利润的前提下，争取让商家在正常经营情况下，不愿再多拿出哪怕一分钱来让利。（优惠券网站的激烈竞争、商家明降暗升的优惠等，都会削弱网站的议价能力。）
  • 2.通过与商家的合同约束，鼓励用户监督、派遣神秘抽查顾客等，提高商家漏报、私下交易的违规成本。
  • 3.其他方式，肯定还有其他更好的方式，但是我暂时没有想到，以后可能补充。
标签: , , , , 没有评论
248月/1120

Memcache的使用与浅析

发布在 邵珠庆

[ 测试代码 ]
现在我们开始一段测试代码：

<?php
//连接
$mem = new Memcache;
$mem->connect("192.168.0.200", 12000);

//保存数据
$mem->set('key1', 'This is first value', 0, 60);
$val = $mem->get('key1');
echo "Get key1 value: " . $val ."<br>";

//替换数据
$mem->replace('key1', 'This is replace value', 0, 60);
$val = $mem->get('key1');
echo "Get key1 value: " . $val . "<br>";

//保存数组
$arr = array('aaa', 'bbb', 'ccc', 'ddd');
$mem->set('key2', $arr, 0, 60);
$val2 = $mem->get('key2');
echo "Get key2 value: ";
print_r($val2);
echo "<br>";

//删除数据
$mem->delete('key1');
$val = $mem->get('key1');
echo "Get key1 value: " . $val . "<br>";

//清除所有数据
$mem->flush();
$val2 = $mem->get('key2');
echo "Get key2 value: ";
print_r($val2);
echo "<br>";

//关闭连接
$mem->close();
?>

如果正常的话，浏览器将输出：
Get key1 value: This is first value
Get key1 value: This is replace value
Get key2 value: Array ( [0] => aaa [1] => bbb [2] => ccc [3] => ddd )
Get key1 value:
Get key2 value:

 

[ 程序分析 ]

初始化一个Memcache的对象：
$mem = new Memcache;

连接到我们的Memcache服务器端，第一个参数是服务器的IP地址，也可以是主机名，第二个参数是Memcache的开放的端口：
$mem->connect("192.168.0.200", 12000);

保存一个数据到Memcache服务器上，第一个参数是数据的key，用来定位一个数据，第二个参数是需要保存的数据内容，这里是一个字符串，第三 个参数是一个标记，一般设置为0或者MEMCACHE_COMPRESSED就行了，第四个参数是数据的有效期，就是说数据在这个时间内是有效的，如果过 去这个时间，那么会被Memcache服务器端清除掉这个数据，单位是秒，如果设置为0，则是永远有效，我们这里设置了60，就是一分钟有效时间：
$mem->set('key1', 'This is first value', 0, 60);

从Memcache服务器端获取一条数据，它只有一个参数，就是需要获取数据的key，我们这里是上一步设置的key1，现在获取这个数据后输出输出：
$val = $mem->get('key1');
echo "Get key1 value: " . $val;

现在是使用replace方法来替换掉上面key1的值，replace方法的参数跟set是一样的，不过第一个参数key1是必须是要替换数据内容的key，最后输出了：
$mem->replace('key1', 'This is replace value', 0, 60);
$val = $mem->get('key1');
echo "Get key1 value: " . $val;

同样的，Memcache也是可以保存数组的，下面是在Memcache上面保存了一个数组，然后获取回来并输出
$arr = array('aaa', 'bbb', 'ccc', 'ddd');
$mem->set('key2', $arr, 0, 60);
$val2 = $mem->get('key2');
print_r($val2);

现在删除一个数据，使用delte接口，参数就是一个key，然后就能够把Memcache服务器这个key的数据删除，最后输出的时候没有结果
$mem->delete('key1');
$val = $mem->get('key1');
echo "Get key1 value: " . $val . "<br>";

最后我们把所有的保存在Memcache服务器上的数据都清除，会发现数据都没有了，最后输出key2的数据为空，最后关闭连接
$mem->flush();
$val2 = $mem->get('key2');
echo "Get key2 value: ";
print_r($val2);
echo "<br>";

 

【Memcache协议分析】

如果你不喜欢 php_memcache.dll 扩展或者服务器器目前不支持这个扩展，那么就可以考虑自己构建，需要构建Memcahe的客户端，要先了解Memcache协议的交互，这样才能开发自己的客户端，我这里就简单的分析以下Memcache的协议。
（更详细的协议内容请在Memcache服务器端的源码的 doc/protocol.txt 文件中，本文基本来源于此）

Memcache既支持TCP协议，也支持UDP协议，不过我们这里是以TCP协议的协议作为主要考虑对象，想了解UDP协议的过程，请参考 doc/protocol.txt 文件。

[ 错误指令]
Memcache的协议的错误部分主要是三个错误提示之提示指令：
普通错误信息，比如指令错误之类的
ERROR\r\n

客户端错误
CLIENT_ERROR <错误信息>\r\n

服务器端错误
SERVER_ERROR <错误信息>\r\n

[ 数据保存指令]
数据保存是基本的功能，就是客户端通过命令把数据返回过来，服务器端接收后进行处理。
指令格式：
<命令> <键> <标记> <有效期> <数据长度>\r\n

<命令> - command name
主要是三个储存数据的三个命令， set, add, replace
set 命令是保存一个叫做key的数据到服务器上
add 命令是添加一个数据到服务器，但是服务器必须这个key是不存在的，能够保证数据不会被覆盖
replace 命令是替换一个已经存在的数据，如果数据不存在，就是类似set功能

<键> - key
就是保存在服务器上唯一的一个表示符，必须是跟其他的key不冲突，否则会覆盖掉原来的数据，这个key是为了能够准确的存取一个数据项目

<标记> - flag
标记是一个16位的无符号整形数据，用来设置服务器端跟客户端一些交互的操作

<有效期> - expiration time
是数据在服务器上的有效期限，如果是0，则数据永远有效，单位是秒，Memcache服务器端会把一个数据的有效期设置为当前Unix时间+设置的有效时间

<数据长度> - bytes
数据的长度，block data 块数据的长度，一般在这个个长度结束以后下一行跟着block data数据内容，发送完数据以后，客户端一般等待服务器端的返回，服务器端的返回：

数据保存成功
STORED

数据保存失败，一般是因为服务器端这个数据key已经存在了
NOT_STORED

[ 数据提取命令]
从服务器端提取数据主要是使用get指令，格式是：
get <键>*

<键>* - key
key是是一个不为空的字符串组合，发送这个指令以后，等待服务器的返回。如果服务器端没有任何数据，则是返回：
END\r\n

证明没有不存在这个key，没有任何数据，如果存在数据，则返回指定格式：
VALUE <键> <标记> <数据长度>\r\n
<数据块>

返回的数据是以VALUE开始的，后面跟着key和flags，以及数据长度，第二行跟着数据块。

<键> -key
是发送过来指令的key内容

<标记> - flags
是调用set指令保存数据时候的flags标记

<数据长度> - bytes
是保存数据时候定位的长度

<数据块> - data block
数据长度下一行就是提取的数据块内容

 

[ 数据删除指令]
数据删除指令也是比较简单的，使用get指令，格式是：
delete <键> <超时时间>

<键> - key
key是你希望在服务器上删除数据的key键

<超时时间> - timeout
按照秒为单位，这个是个可选项，如果你没有指定这个值，那么服务器上key数据将马上被删除，如果设置了这个值，那么数据将在超时时间后把数据清除，该项缺省值是0，就是马上被删除

删除数据后，服务器端会返回：
DELETED
删除数据成功
NOT_FOUND
这个key没有在服务器上找到

如果要删除所有服务器上的数据，可以使用flash_all指令，格式：
flush_all

这个指令执行后，服务器上所有缓存的数据都被删除，并且返回：
OK

这个指令一般不要轻易使，除非你却是想把所有数据都干掉，删除完以后可以无法恢复的。

[其他指令]
如果想了解当前Memcache服务器的状态和版本等信息，可以使用状态查询指令和版本查询指令。

如果想了解当前所有Memcache服务器运行的状态信息，可以使用stats指令，格式
stats
服务器将返回每行按照 STAT 开始的状态信息，包括20行，20项左右的信息，包括守护进程的pid、版本、保存的项目数量、内存占用、最大内存限制等等信息。

如果只是想获取部分项目的信息，可以指定参数，格式：
stats <参数>
这个指令将只返回指定参数的项目状态信息。

如果只是想单独了解当前版本信息，可以使用version指令，格式：
version
将返回以 VERSION 开头的版本信息

如果想结束当前连接，使用quit指令，格式：
quit

将断开当前连接

另外还有其他指令，包括incr, decr 等，我也不太了解作用，就不做介绍了，如果感兴趣，可以自己去研究。

 

【Memcache在中型网站的使用】

使用Memcache的网站一般流量都是比较大的，为了缓解数据库的压力，让Memcache作为一个缓存区域，把部分信息保存在内存中，在前端能 够迅速的进行存取。那么一般的焦点就是集中在如何分担数据库压力和进行分布式，毕竟单台Memcache的内存容量的有限的。我这里简单提出我的个人看 法，未经实践，权当参考。

[ 分布式应用]
Memcache本来支持分布式，我们客户端稍加改造，更好的支持。我们的key可以适当进行有规律的封装，比如以user为主的网站来说，每个用户都有 User ID，那么可以按照固定的ID来进行提取和存取，比如1开头的用户保存在第一台Memcache服务器上，以2开头的用户的数据保存在第二胎 Mecache服务器上，存取数据都先按照User ID来进行相应的转换和存取。

但是这个有缺点，就是需要对User ID进行判断，如果业务不一致，或者其他类型的应用，可能不是那么合适，那么可以根据自己的实际业务来进行考虑，或者去想更合适的方法。

[ 减少数据库压力]
这个算是比较重要的，所有的数据基本上都是保存在数据库当中的，每次频繁的存取数据库，导致数据库性能极具下降，无法同时服务更多的用户，比如 MySQL，特别频繁的锁表，那么让Memcache来分担数据库的压力吧。我们需要一种改动比较小，并且能够不会大规模改变前端的方式来进行改变目前的 架构。

我考虑的一种简单方法：
后端的数据库操作模块，把所有的Select操作提取出来（update/delete/insert不管），然后把对应的SQL进行相应的hash算法 计算得出一个hash数据key（比如MD5或者SHA），然后把这个key去Memcache中查找数据，如果这个数据不存在，说明还没写入到缓存中， 那么从数据库把数据提取出来，一个是数组类格式，然后把数据在set到Memcache中，key就是这个SQL的hash值，然后相应的设置一个失效时 间，比如一个小时，那么一个小时中的数据都是从缓存中提取的，有效减少数据库的压力。

缺点是数据不实时，当数据做了修改以后，无法实时到前端显示，并且还有可能对内存占用比较大，毕竟每次select出来的数据数量可能比较巨大，这个是需要考虑的因素。

上面只是我两点没有经过深思熟虑的简单想法，也许有用，那就最好了。

 

【Memcache的安全】

我们上面的Memcache服务器端都是直接通过客户端连接后直接操作，没有任何的验证过程，这样如果服务器是直接暴露在互联网上的话是比较危险， 轻则数据泄露被其他无关人员查看，重则服务器被入侵，因为Mecache是以root权限运行的，况且里面可能存在一些我们未知的bug或者是缓冲区溢出 的情况，这些都是我们未知的，所以危险性是可以预见的。

为了安全起见，我做两点建议，能够稍微的防止黑客的入侵或者数据的泄露。

[ 内网访问]
最好把两台服务器之间的访问是内网形态的，一般是Web服务器跟Memcache服务器之间。普遍的服务器都是有两块网卡，一块指向互联网，一块指向内 网，那么就让Web服务器通过内网的网卡来访问Memcache服务器，我们Memcache的服务器上启动的时候就监听内网的IP地址和端口，内网间的 访问能够有效阻止其他非法的访问。

# memcached -d -m 1024 -u root -l 192.168.0.200 -p 11211 -c 1024 -P /tmp/memcached.pid

Memcache服务器端设置监听通过内网的192.168.0.200的ip的11211端口，占用1024MB内存，并且允许最大1024个并发连接

[ 设置防火墙]
防火墙是简单有效的方式，如果却是两台服务器都是挂在网的，并且需要通过外网IP来访问Memcache的话，那么可以考虑使用防火墙或者代理程序来过滤非法访问。
一般我们在Linux下可以使用iptables或者FreeBSD下的ipfw来指定一些规则防止一些非法的访问，比如我们可以设置只允许我们的Web服务器来访问我们Memcache服务器，同时阻止其他的访问。

# iptables -F
# iptables -P INPUT DROP
# iptables -A INPUT -p tcp -s 192.168.0.2 --dport 11211 -j ACCEPT
# iptables -A INPUT -p udp -s 192.168.0.2 --dport 11211 -j ACCEPT

上面的iptables规则就是只允许192.168.0.2这台Web服务器对Memcache服务器的访问，能够有效的阻止一些非法访问，相应的也可以增加一些其他的规则来加强安全性，这个可以根据自己的需要来做。

标签: , , 20 评论
   

支持博主

了解慈善捐款计划

关于邵珠庆博客

文章标签

API GA Git Google Analytics HTML5 jquery JS Linux MySQL nginx PHP SaaS web 互联网 代码 使用 分析 创业 原理 命令 好东西 如何 工具 常用 开发 总结 技巧 技术 插件 数据 文件 方法 时间 架构 框架 汇总 百度 管理 系统 网站 网站分析 设计 详解 问题 阿里云

记事邵珠庆博客

1、Web前端网址导航
2、邵珠庆极客筛站
3、识别移动设备访问代码


最近文章

最近评论

博客日历

2024年7月
一 二 三 四 五 六 日
« 8月    
1234567
891011121314
15161718192021
22232425262728
293031  

目录分类

文章归档

博客功能