生成不重复随机数

今天碰到一个生成不重复随机数题目, 题目类似如下:
在一个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之间的随机值替换上面的1024, 将能保证tmp的值一定小于等于1M, 由于递增的特性也可保证每个循环tmp的值是在0~1M中的惟一值.更改后代码如下:

int buff[1024];
int tmp = 0;
for (i = 0; i < 1024; i++) { tmp += srand() % 1024; buff[i] = tmp; }

从代码中可以看到tmp由上一次tmp的值和这一次的随机值决定. 因此生成的值一定是随机的.

虽然生成的数是随机的, 但是在数组中的布局却是从小到大来分布的, 因为我们在赋数组时同样需要随机分布. 修改代码如下:

int buff[1024];
int tmp = 0;
int buff_index = 0;

memset(buff, 0xff, sizeof(buff[0]) * 1024);
for (i = 0; i < 1024; i++) { tmp += srand() % 1024; buff_index += rand(); buff_index %= 1024; while (buff[buff_index] != -1) { buff_index++; buff_index %= 1024; } buff[buff_index] = tmp; }

在写入数组时采用随机生成索引号的方法来决定要写到数值的哪一个位置, 如果这个位置被写过, 那么顺序向下查找空间数组位置, 因为数组共有1024个, 因为不管怎么样每次总能找到一个没有被写过的数组位置, 这样写入1024次之后一定会生成内存分布随机的1024个不重复的随机数.

btw: 清风同学说这个算法有个bug, 就是我第一个随机数一定会生成0~1024之间的数, 暂时还没有想到办法.

闭包的好处

今天看了swift中的闭包一节, 看到最后值捕获时我才明白闭包的便利性. 如果没有值捕获, 那么支持闭包的特性跟C语言的函数指针比除了可以创建匿名函数与函数嵌套定义外恐怕没有什么优势. 但是有了值捕获这一功能闭包可以大大增加写代码的便利性.
下面是swift的一个闭包的例子:

func testclouser(t1 : Int) -> () -> Int {
var tst = 3;
func inc() -> Int {
tst += t1;
return tst;
}

return inc;
}

let fun = testclouser(9);
let fun2 = testclouser(3);

println(fun());
println(fun());

println(fun2());
println(fun2());

其输出结果如下:

12
21
6
9

可以看到从现像上看fun将tst, t1包了一份进入自己的闭包中作为全局变量, 但是这个全局变量并不能被其他函数或闭包访问, 而且fun与fun2虽然是由同一个函数体生成并且都包入了tst与t1变量, 但是fun与fun2算是两个独立的闭包, 所以fun与fun2都会有自己的全局tst, t1变量, 所以才会导致如上结果. 这种特性用C语言其实并没有太好的方法去模拟. 只能和类似的方法去实现.
下面是C语言的类似实现:

#include
#include

struct testclouser {
int tst;
int t1;
};

void testclouser_capture(struct testclouser *clouser, int t1)
{
assert(clouser);
clouser->tst = 3;
clouser->t1 = t1;
}

int testclouser_do(struct testclouser *clouser)
{
assert(clouser);
return clouser->tst += clouser->t1;
}

int main()
{
struct testclouser tc1;
struct testclouser tc2;

testclouser_capture(&tc1, 9);
testclouser_capture(&tc2, 3);

printf("%dn", testclouser_do(&tc1));
printf("%dn", testclouser_do(&tc1));
printf("%dn", testclouser_do(&tc2));
printf("%dn", testclouser_do(&tc2));

return 0;
}

这里只是对栈来模拟闭包, 可以类似这里的实现来对堆模拟闭包.

从代码上比较可以看出, 当我们需要实现类似上面的需求时, 虽然C可以实现, 但是会增加代码量而且看上去会很繁琐, 而在支持闭包的语言中, testclouser_capture的操作会被编译器做掉, 写出来的代码可以更简洁, 更清晰.

多线程调DLL

最近写代码一不小心又着了多线程的道, 背景如下:
前不久写了这样一个DLL:

const wchar_t *a = L"xxxx";
const wchar_t *b = L"xxxx";

int do_something_a(struct axx *param_a)
{
...
}
int do_something_b(struct bxx *param_b)
{
...
}


在do_something_a与do_something_b中分别用到了字符串a, b.本来这样相安无事, 可是很多地方会用到这个DLL的代码, 但是字符串a, b并不一样, 而字符中a, b可以根据param_a, param_b中的信息来生成, 本着代码正交性的原则, 将DLL重构如下:

wchar_t a[..];
wchar_t b[..];

int do_something_a(struct axx *param_a)
{
gen_a(param_a, a);
...
}
int do_something_b(struct bxx *param_b)
{
gen_b(param_b, b);
...
}

这样咋一看是没什么问题, 代码简洁了, 程序完美了. 可是我忽略了两个问题, 一个进程中不管调LoadLibrary多少次, DLL只会被加载一次. 而我这个DLL是会在多个线程同时加载使用的.
这样一来, 问题就来了, 由于全局数组a与b的存在, 所有的函数都不是线程安全的, 在低并发量的线程中冲突并不严重, 所以问题很难发现, 但是在高并发的线程中两个函数就会大量执行失败.

找到问题了后将代码重构如下:

int do_something_a(struct axx *param_a)
{
wchar_t a[..];
gen_a(param_a, a);
...
}
int do_something_b(struct bxx *param_b)
{
wchar_t b[..];
gen_b(param_b, b);
...
}

这次bug再次给我提了醒, 多线程代码要处处小心, 一不小心就会掉坑里.