随机混洗(Random Shuffle)算法

  最近遇到这样一个问题:生成 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

这一年,2011 (图片版)

【一月】 冰雪中的湘南。 【二月】 回到北京,不置可否。 【三月】 朝南的窗,花花草草,写写画画。 【四月】 北方的春天,确比南方要耀眼得多。 【五月】 安静的转变。 【六月】 温暖,陪伴。最好的爱,是不是就是这个样子? 【七月】 你是否也向往这样一个葱郁的小院子,不管在哪里。 【八月】 忙碌中,不忘读书。在粉红色小屋。 【九月】 与自我对话。杂乱中找到主线。 【十月】 对于湘西的情感,已扎根于心中。湿漉漉的温情。 【十一】 阿加罗,一切都会顺利。 【十二】 一切由心而生。

线段树小结

  线段树(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 作为下标分别访

树状数组小结

  树状数组(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)

这一年,2011 (文字版)

本来是要在2012还没有到来之前写下这些的。我习惯对于过去的一年回顾一下,这样对自己会有更清晰的认知。可是一直都忙得焦头烂额,没有功夫静下心来。 于是,一直到农历年的末尾。终于有这么一个晚上,能安安静静地坐在台灯前,翻翻过去。 过去是由什么组成的呢? 走过的路,经历过的事,遇见过的人,看过的书,写过的字,拍过的照片,画过的画,拍过的照片,住过的房子,梦过的梦。 这些就是全部吗? 我想不是。 其实很多东西都已经忘了。那些藏在记忆的角落里的点点滴滴,那些思绪里的细枝末节,也许早就忘了。它们的存在只是一瞬,而我们却是由这么多个一瞬连接而成的。情绪过去,便不再留痕迹。接下来的是下一个情绪,而下一个情绪也会走。 真的不会有痕迹吗?如今我整理的,是痕迹,还是它们的结果? 我也不知道。我也不想思考这个问题。就容我将它们,一个个记叙。 今年博客写得少了。其实有好多东西想写,有太多太多东西想写。这些年积累的太多,却未有道来。渐渐地,也不去道了。因为一旦道,就是排山倒海。 【一月】 一月的湖南冰冷到极点。 先是期盼雪,后来是被雪折腾得够呛。由湘西转战湘南,依然是冰冻天气。我喜欢郴州,这种有树的小城我都喜欢。再加上板梁小河上蒸腾的雾气,便是更多了些欢喜。衡山没有雾凇,但莽山有。被吹出毛茸茸的形状,朝一个方向歪着,大雾一来,又什么也看不清。真想不到这竟是广东的第一峰。 在衡山我有特别的亲切感。在半山住着的几日,白天爬山,傍晚回来。我总会记得傍晚深绿色的树林中,飘散着大山特有的气味。我甚至会感觉自己是在喜马拉雅脚下的那个小山村。它们是相似的,亲切的,令人愉悦的,让人从上到下每一块筋骨都舒展开来,每一个毛孔都在顺畅呼吸。 在之后的日子里,我常常会向人提起小东江旁那个废旧的隧道,那个有着温润清凉的江水的拉拉渡。隧道口传来的狗吠,还有小羊咩咩的叫,越来越远,最后全无。无尽的黑暗,前后都是黑暗。但我选择了继

专注

当一个人专注地做ta热爱的事情的时候,身上一定是放着光的。周围的人能“看”到ta的光,被ta,或者不只是ta,被这光中的ta所吸引。 英语里面个短语叫be into something,我觉得表达得更形象。专注地去做一件事情,把整个人投入了进去。你好像是不存在的,你和你正在做的事情是一体的。 你有过这样的时候吗? 在这样的时候,你是在做什么事情? 这件事情也许就是你要去做的,让你天性舒展,让你放光的事情。

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

最长上升子序列的 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 {

失而复得

2011年的末尾,接二连三遇到一系列的狗血事件,虽然过程很麻烦,但最后大部分都以一个不错的结果而告终。大约是我能欣然接受各种变化,每天还乐呵呵地傻高兴。唯一有点小失落的是,丢了一张SD卡。其实也没什么,只不过丢了些照片,一些记忆的凭证罢了。 但你越不失落,生活就越不会让你失落。昨天同事递给我一张卡,问我是不是看它很面熟。顿时大喜。至今我也没有弄清楚这张卡经历了怎样的过程最后到了她的手上,但失而复得感觉实在太棒。至此,年末所有事件最后都完满画上句号。 你说呢。只要你去相信,相信好的就会有好的。相信顺利,最终总是会顺利。 本来以为弄丢了的照片。小乖和小卡同学,在夕阳里。

社交游戏广告投入与收回天数模型

社交游戏方兴未艾,我不相信未来就一定是发行商的天下。于是,打算抛砖引玉,利用自家产品积累的一些数据,建立一个模型(非常不完善,所以期待大家各种板砖)。模型要解决的问题是:给出一个预算(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
分页: [<<] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [>>]

目录

搜索

高级搜索>>

统计信息

网站管理员

图标

  • 本站支持 WAP 访问
  • 订阅本站的 RSS 2.0 新闻聚合

Powered By SXNA 1.7

Copyright Sipo XNA. Some Rights Reserved.