| 最近遇到这样一个问题：生成 1 - N 的随机排列。这是一个比较常见的问题，生成一个有限集合的随机排列的时候就要用到。一种 naive 的算法是： for i = 1..n do r = 1..n 之间的随机数 while (r 已经被选择) do r = 1..n 之间的随机数 end ar[i] = r 将 r 标记为已被选择 end 这种算法的问题是，当可供选择的数很少的时候（极端情况是只剩最后一个），大量的时间都浪费在 while 循环上了，理论上平均时间复杂度达到 O(n2) ，而且还需要额外空间记录是否已经使用。 实际上，前人早已研究过这个问题。Random Shuffle 算法可以在 O(n) 的时间内随机打乱一个数组，所以只需要把 1..N 保存在一个数组中，再 shuffle 这个数组即可。实现方法参见维基百科 Fisher–Yates shuffle 。正确性证明参见 Knuth 的《计算机程序设计艺术（第二卷）：半数值算法》。 不少语言已经在标准库中包含了这个函数： Python import random random.shuffle(ar) Java import java.util.Collections; Collections.shuffle(List<?> list); C++ #include <algorithm> const int N = 8; int ar[] = {1, 2, 3, 4, 5, 6, 7, 8}; random_shuffle(ar, ar + N); Lua 标准库中没有这个函数，我的实现： -- random shuffle a table in place function shuffle(t) f |
2012-2-3 17:01
随机混洗（Random Shuffle）算法
遥远的街市 | henix | RSS
2012-2-1 17:12
这一年，2011 （图片版）
| 【一月】 冰雪中的湘南。 【二月】 回到北京，不置可否。 【三月】 朝南的窗，花花草草，写写画画。 【四月】 北方的春天，确比南方要耀眼得多。 【五月】 安静的转变。 【六月】 温暖，陪伴。最好的爱，是不是就是这个样子？ 【七月】 你是否也向往这样一个葱郁的小院子，不管在哪里。 【八月】 忙碌中，不忘读书。在粉红色小屋。 【九月】 与自我对话。杂乱中找到主线。 【十月】 对于湘西的情感，已扎根于心中。湿漉漉的温情。 【十一】 阿加罗，一切都会顺利。 【十二】 一切由心而生。 |
天使出走 | kidonly | RSS
2012-1-31 22:15
线段树小结
| 线段树（Segment Trees）主要用来解决跟区间有关的问题。比如，给你一个数组，要求支持以下操作： 更新：将某个区间的所有数加上一个数 查询：查询某个区间的所有数的和 普通的做法时间复杂度为 O(n) ，每次需要遍历区间内所有的数，但用线段树可以做到 O(log n) 。 其基本思想就是把区间信息先预处理出来。如果根节点保存 [l, r) 的信息（可以是和，或者最大值、最大值等等），其左右孩子节点则分别保存 [l, (l+r)/2) 和 [(l+r)/2, r) 的信息，然后依次类推。 查询的时候，只需要选取其中部分节点就可以“拼凑”出要查的区间。所以，线段树只适用于那些总结果可以由子区间的结果合成的问题，比如区间求和、区间最值。 由于线段树除最后一层外，前面每一层的节点都是满的，因此深度为 O(log n) 。 关于线段树，黑书上说有这样一个性质：线段树建立好后，其范围内的任何一个区间，都可以用线段树上的不超过 2 log n 条线段表示。 证明的方法主要是先证每一层最多会被选取两个节点，然后由于高度为 log n 可得。 为什么每层最多会选取两个呢？试证如下： 首先，任何一个区间进入线段树，这个区间总会在某个地方被分成两半，除非这个区间的长度为 1 ，那就不用讨论了。分成两半后，前一半由于必须包含 mid 这块区间，它“落下”的时候，每一层最多选取一个节点。后一半同理。 (svg) 如上图，在线段树中查询线段①，被分成②③两个部分。对于每个部分，可以分两种情况：一种是像②那样，没有达到下一层的一半，此时不会选择 C ；另一种是像③那样，超过下一层的一半，此时会选取 D 。后面的类似。于是一层中最多有两个节点被选取。 实现方法：一般是像堆那样实现成数组，然后可以用 2 * i 和 2 * i + 1 作为下标分别访 |
遥远的街市 | henix | RSS
2012-1-30 21:03
树状数组小结
| 树状数组（Binary Indexed Trees）适用于单点更新、区间查询的问题，更新和查询的复杂度都是 O(log n) 。可以求前缀和（sum(a[1]..a[n])），用两个前缀和相减就可以求任意区间和。更新的时候只能是对某位的一个 delta ，而不是设置某一位。经过变形可以解决区间更新、单点查询的问题。 使用的时候需要注意，树状数组的下标必须从 1 开始，下标 0 是错误的。如果遇到题目中有下标 0 的情况，可以把所有的下标都加 1 。 我的实现： #include <cassert> inline int lowbit(int x) { return (x & (-x)); } class Bit { private: int size; int *reduced; public: Bit(int size) { assert(size > 0); this->size = size; reduced = new int[size + 1]; for (int i = 0; i <= size; i++) { reduced[i] = 0; } } int query(int idx) const { assert(idx > 0 && idx <= size); int res = 0; while (idx > 0) { res += reduced[idx]; idx &= (idx - 1); } return res; } void update(int idx, int delta) { assert(idx > 0 && idx <= size) |
遥远的街市 | henix | RSS
2012-1-22 00:30
这一年，2011 （文字版）
| 本来是要在2012还没有到来之前写下这些的。我习惯对于过去的一年回顾一下，这样对自己会有更清晰的认知。可是一直都忙得焦头烂额，没有功夫静下心来。 于是，一直到农历年的末尾。终于有这么一个晚上，能安安静静地坐在台灯前，翻翻过去。 过去是由什么组成的呢？ 走过的路，经历过的事，遇见过的人，看过的书，写过的字，拍过的照片，画过的画，拍过的照片，住过的房子，梦过的梦。 这些就是全部吗？ 我想不是。 其实很多东西都已经忘了。那些藏在记忆的角落里的点点滴滴，那些思绪里的细枝末节，也许早就忘了。它们的存在只是一瞬，而我们却是由这么多个一瞬连接而成的。情绪过去，便不再留痕迹。接下来的是下一个情绪，而下一个情绪也会走。 真的不会有痕迹吗？如今我整理的，是痕迹，还是它们的结果？ 我也不知道。我也不想思考这个问题。就容我将它们，一个个记叙。 今年博客写得少了。其实有好多东西想写，有太多太多东西想写。这些年积累的太多，却未有道来。渐渐地，也不去道了。因为一旦道，就是排山倒海。 【一月】 一月的湖南冰冷到极点。 先是期盼雪，后来是被雪折腾得够呛。由湘西转战湘南，依然是冰冻天气。我喜欢郴州，这种有树的小城我都喜欢。再加上板梁小河上蒸腾的雾气，便是更多了些欢喜。衡山没有雾凇，但莽山有。被吹出毛茸茸的形状，朝一个方向歪着，大雾一来，又什么也看不清。真想不到这竟是广东的第一峰。 在衡山我有特别的亲切感。在半山住着的几日，白天爬山，傍晚回来。我总会记得傍晚深绿色的树林中，飘散着大山特有的气味。我甚至会感觉自己是在喜马拉雅脚下的那个小山村。它们是相似的，亲切的，令人愉悦的，让人从上到下每一块筋骨都舒展开来，每一个毛孔都在顺畅呼吸。 在之后的日子里，我常常会向人提起小东江旁那个废旧的隧道，那个有着温润清凉的江水的拉拉渡。隧道口传来的狗吠，还有小羊咩咩的叫，越来越远，最后全无。无尽的黑暗，前后都是黑暗。但我选择了继 |
天使出走 | kidonly | RSS
2012-1-19 07:59
专注
| 当一个人专注地做ta热爱的事情的时候，身上一定是放着光的。周围的人能“看”到ta的光，被ta，或者不只是ta，被这光中的ta所吸引。 英语里面个短语叫be into something，我觉得表达得更形象。专注地去做一件事情，把整个人投入了进去。你好像是不存在的，你和你正在做的事情是一体的。 你有过这样的时候吗？ 在这样的时候，你是在做什么事情？ 这件事情也许就是你要去做的，让你天性舒展，让你放光的事情。 |
天使出走 | kidonly | RSS
2012-1-10 17:39
POJ 2823 单调队列 + IO 优化
| 最近继续补算法……学习一下单调队列。据说 POJ 2823 是道经典题目。 给出一个数组和一个固定长度的窗口，这个窗口从左滑到右，要求依次输出每个区间的最大值。 用单调队列求解：滑动窗口每往右边移动一步，就有一个元素出队，另一个元素进队。考虑队列中有两个元素依次是 a b（b 在 a 后面），如果 b > a ，那么 a 在任何时刻都不可能作为最大值输出，所以在这种情况下就可以直接忽略掉 a 。于是我们可以保证队列是单调递减的，这样每次输出的时候就输出队首就可以了。 不过这道题直接提交就超时了，看了下网上其他人都说要加上 IO 优化，也就是不要用 printf 输出，改用自己写的输出函数以实现更快速的输出一个整数。参见 putint() 函数，什么 register 都出来了，再优化下去就汇编了。这样做了之后果然 AC 。 代码（gcc）： #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <errno.h> #include <stdbool.h> #include <limits.h> struct monoq_t { int *head, *end; int *q; int size; }; typedef struct monoq_t monoq_t; int monoq_init(monoq_t *self, int size) { if (size < 0) { return EINVAL; } self->q = malloc(size * sizeof(int)); if (self->q == NULL) { return ENO |
遥远的街市 | henix | RSS
2012-1-10 17:05
最长上升子序列的 nlogn 算法
| 最长上升子序列（Longest increasing subsequence, LIS）是个经典的动态规划问题，用动态规划可以在 \(O(n^2)\) 的时间内解决。 问题描述参见 POJ 2533 。 但还有另外一种利用决策的单调性的算法，可以在 \(O(n\log n)\) 的时间解决。 设 min[i] 为长度为 i 的最长子序列的最后一个元素最小可以是多少。每次将原序列的一个元素 a 插入到 min 数组中，并更新数组 min ，每次只需找到 min 中第一个比 a 大的数，并用 a 替换那个数。在查找的时候可以用二分查找，于是时间复杂度是 \(O(n\log n)\) 。 代码： #include <stdio.h> #include <stdbool.h> int main(int argc, char *argv[]) { int n; scanf("%d", &n); int ar[n]; int i; for (i = 0; i < n; i++) { scanf("%d", ar + i); } int min[n]; int len = 0; for (i = 0; i < n; i++) { /* insert ar[i] into min */ int l = 0, r = len; int mid; bool found = false; while (l < r) { mid = (l + r) / 2; if (ar[i] < min[mid]) { r = mid; } else if (ar[i] > min[mid]) { l = mid + 1; } else { |
遥远的街市 | henix | RSS
2012-1-8 23:12
失而复得
| 2011年的末尾，接二连三遇到一系列的狗血事件，虽然过程很麻烦，但最后大部分都以一个不错的结果而告终。大约是我能欣然接受各种变化，每天还乐呵呵地傻高兴。唯一有点小失落的是，丢了一张SD卡。其实也没什么，只不过丢了些照片，一些记忆的凭证罢了。 但你越不失落，生活就越不会让你失落。昨天同事递给我一张卡，问我是不是看它很面熟。顿时大喜。至今我也没有弄清楚这张卡经历了怎样的过程最后到了她的手上，但失而复得感觉实在太棒。至此，年末所有事件最后都完满画上句号。 你说呢。只要你去相信，相信好的就会有好的。相信顺利，最终总是会顺利。 本来以为弄丢了的照片。小乖和小卡同学，在夕阳里。 |
天使出走 | kidonly | RSS
2012-1-4 17:49
社交游戏广告投入与收回天数模型
| 社交游戏方兴未艾，我不相信未来就一定是发行商的天下。于是，打算抛砖引玉，利用自家产品积累的一些数据，建立一个模型（非常不完善，所以期待大家各种板砖）。模型要解决的问题是：给出一个预算（Budget），计算多久能够收回预算。地址： http://www.magnetjoy.com/budget.html 目前的思路是，用预算，除以CPC（install，而非click，我们自己计算，在FB台湾，大概是0.3美金左右，FB自己的Ads CPC要考虑到Developer Dashboards中的Auth通过率），得到预算带来的直接安装用户数。结合我们自己的经验，发现一个普通的社交游戏，一般一个外界用户会带来X倍的自增长。姑且称为Organic Growth Users，把每天的自增长用户数，除以外界带来的用户数，得到的一个比例，姑且称为Organic Growth Rate，简称OGR。这个值加一，即是每一个外界用户带来的新用户总数。我自己算了一下，手头某个游戏，在台湾FB市场的OGR是2.12（广告）～0.70（互推），如果有其他渠道，肯定也有不同的比例。这个数值跟游戏的病毒性也有一定关系。 于是通过Budget/CPC*(OGR+1)可得知投入预算能带来的相应安装数。再乘以“安装转化DAU比率”，即可得到大概带来的均值DAU。这个比例根据我们的经验，一般在5%-15%左右。 拿到DAU之后，输入对应的ARPU，再考虑相应的成本（比如平台分成、服务器），就能估算收入。再用预算除以收入，即可得到『多久能够收回预算』。 以上模型，存在非常多不完善的地方，譬如没有考虑DAU随游戏生命周期的衰减；譬如没有考虑OGR会随着用户积累而有些许上扬。这两者优于对结果分别有正面和负面的影响，所以我姑且认为他们可以『抵消』。但一个人的思维是局限的，还希望更多同行参与交流，可以添加我的微博：@awg |
