Sweet Snippet系列 之 随机选择

  1. 引子:

  平日工作学习时总会遇到一些令人欣喜的代码段子(Snippet),虽然都很短小,但是其间所含的道理都颇有意味,遂而觉得应该不时的将她们记下,一来算作复习整理,二来也给有兴趣的朋友做些参考,虽然题目说成了一个系列,但自己也不知道能写多少,大概准则估计也就是写到哪算哪了,今天算是第一篇,瞎扯扯随机选择 :)

  2. 问题:

  题目很简单,如何等概率的选取一个集合中的元素,譬如我们现在有一个vector(C++):

vector<int> v = { 1, 2, 3, 4, 5 };
int selected = random_select(v);

  如何实现这个random_select 函数呢?其实有个很简单的方法,便是随机选取一个范围在[0, v.size()) 中的整数即可,代码大抵是这个样子:

int random_number(int max) {
    return rand() % max;
}

int random_select(const vector<int>& v) {
    return v[random_number(v.size())];
}

  当然,我们还可以继续优化上述代码,譬如将random_select泛化等等,在此就不赘述了,仅从功能性角度来看,上面代码确实完成了我们的期望:“等概率”的随机选取了vector集合中的某个元素。(这里“等概率”之所以加上引号,是因为真实的选取结果其实并不是绝对等概率的,问题在于我们使用了rand()取余来获取随机数,而这种方法所产生的随机数大部分情况下都不是均匀分布的,S.T.L(注意是个人名:))对于此有个非常精彩的讨论

  但在现实生活中,很多情况下我们未必一开始就知道集合的长度,譬如我们目前只有begin和end两个前向迭代器:

ForwardIterator begin = some_func_get_begin();
ForwardIterator end = some_func_get_end();
ForwardIterator iter = random_select(begin, end);

  那么这里的random_select应该如何实现才能保证等概率的选取这个集合中的元素呢?有个方法大概可以算是归约吧,就是首先使用迭代器遍历一遍集合,然后我们便可以知道集合的长度了,然后问题也就归约到之前的随机选取问题了。不管怎么说,这是一个可行的办法,但是明眼人一看就知道这种方法不是很简洁,甚至可以说有些坏味道,但是如果马上让我来实现一下random_select的话,我估摸着可能也会采取这种方法,尽管心里觉得别扭,幸而前些日子在这里看到了一个更简单的方法,很有意思:)如果用代码实现的话,大概是这个样子:   使用C++的一个完整示例:

#include <iostream>
#include <random>
#include <list>

using namespace std;

namespace {

class Random {
public:
    int Next(int min, int max) {
        uniform_int_distribution<> distribution(min, max);
        return distribution(m_engine);
    }

    int Next(int max) {
        return Next(0, max);
    }

private:
    mt19937 m_engine;
} random;

template<typename ForwardIterator>
ForwardIterator random_select(ForwardIterator begin, ForwardIterator end) {
    int count = 0;
    auto selected = end;

    for (auto iter = begin; iter != end; ++iter) {
        if (random.Next(count++) == 0) {
            selected = iter;
        }
    }

    return selected;
}

}

int main() {
    list<int> l = { 1, 2, 3, 4, 5 };

    int testCount = 32;
    for (int i = 0; i < testCount; ++i) {
        cout << *random_select(std::begin(l), std::end(l)) << " ";
        if ((i + 1) % 10 == 0) {
            cout << "\n";
        }
    }

    return 0;
}

  另有一个C#的完整示例,原理是一致的,也顺道贴一下:

using System;
using System.Collections.Generic;

namespace RandomSelect {
	
	class Program {
		
		static Random random = new Random();
		
		public static T RandomSelect<T>(IEnumerable<T> enumerable) {
			int count = 0;
			T selected = default(T);
			
			var enumerator = enumerable.GetEnumerator();
			while (enumerator.MoveNext()) {
				if (random.Next(++count) == 0) {
					selected = enumerator.Current;
				}
			}
			
			return selected;
		}
		
		public static void Main(string[] args) {
			var list = new List<int> { 1, 2, 3, 4, 5 };
			int testCount = 32;
			for (int i = 0; i < testCount; ++i) {
				Console.Write(RandomSelect(list));
				Console.Write(" ");
				if ((i + 1) % 10 == 0) {
					Console.WriteLine();
				}
			}
			Console.WriteLine();
			
			Console.Write("Press any key to continue . . .");
			Console.ReadKey(true);
		}
	
	}

}

3. 道理:

  不知你看懂了多少代码,其实上面代码砍头去尾之后,真正有趣的大概就是这么一段:

for (auto iter = begin; iter != end; ++iter) {
        if (random.Next(count++) == 0) {
            selected = iter;
        }
    }

  可就这么几句代码,到底是如何保证等概率选取集合元素的呢?让我们来细究一下:

  不妨假设集合有n的元素,考虑第 i 个元素的最终选取概率 p(i),不难看出以下关系:

  a. p(i) 与 p(1)、p(2) ... p(i-1) 没有依赖关系,即无论前i - 1元素的单次选取情况如何,都不影响第i个元素的最终选取。

  b. p(i) 依赖于 p(i+1)、p(i+2) ... p(n),即如果第i个元素被最终选取,那么就意味着i+1、i+2 ... n 等元素都没有被单次选取。

  考虑到元素的单次选取概率都与元素位置有关,第i个元素单次选取概率为 1 / i,自然的,其单次不被选取的概率便是 1 - 1/i = (i - 1)/i

  则有p(i) = 1 / i * i/(i+1) * (i+1)/(i+2) ... (n-1)/n = 1/n

  于是我们有对于任意集合元素,其被最终选取的概率皆为 1/n !Nice!

  好了,我的废话就这么多了,如果有机会的话继续瞎扯扯,希望吧 :)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

17730
来自专栏章鱼的慢慢技术路

笔试常考题型之时间复杂度

57260
来自专栏数据结构与算法

BZOJ4872: [Shoi2017]分手是祝愿

Description Zeit und Raum trennen dich und mich. 时空将你我分开。B 君在玩一个游戏,这个游戏由 n 个灯和 n...

30550
来自专栏有趣的Python和你

Python数据分析之锁具装箱问题问题重述问题分析建模与求解

12630
来自专栏大数据风控

R中如何用ifelse进行数据分组

数据分组,根据数据分析对象的特征,按照一定的数值指标,把数据分析对象划分为不同的区间部分来研究,以揭示内在的联系和规律性; 在R中,我们常用ifelse函数来进...

38480
来自专栏专注数据中心高性能网络技术研发

[LeetCode]Array主题系列{1,11,15,16,18,26,27,31,33,34题}

1.内容介绍 开一篇文章记录在leetcode中array主题下面的题目和自己的思考以及优化过程,具体内容层次按照{题目,分析,初解,初解结果,优化解,优化解结...

35360
来自专栏智能算法

程序员必须知道的十大基础实用算法及其讲解

出自博客园 原文地址:http://kb.cnblogs.com/page/210687/ 算法一:快速排序算法   快速排序是由东尼·霍尔所发展的一种排序算法...

39280
来自专栏CDA数据分析师

数据分析师不可不知的10大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较...

22480
来自专栏CSDN技术头条

程序员必须知道的十大基础实用算法及其讲解

算法一:快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较...

21850
来自专栏ml

由判断三一点是否在三角形内部而引发的思考.....

判断一个点是否在三角形里面(包括边界上),这个问题对于许多初学者来说,可谓是一头雾水,如何判断呢? 假如有四个点A(x0,y0),B(x1,y1),C(x2,y...

31380

扫码关注云+社区

领取腾讯云代金券