`
wsql
  • 浏览: 11715545 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
文章分类
社区版块
存档分类
最新评论

算法分析: 从N条成绩单信息选择M位不重复同学发奖

 
阅读更多
<?php
/**
 * author: selfimpr
 * blog: http://blog.csdn.net/lgg201
 * mail: lgg860911@yahoo.com.cn
 * copyright: 原创作品, 转载请附原始连接.
 *
 * 根据某种比较算法读取数据集中的最大N条数据, 并且, 数据有特征字段, 结果集中每条数据的特征字段必须唯一
 * 应用场景举例:
 * 		某班要发放单科成绩优秀奖, 共有N条单科成绩数据, 现要选取M名同学作为嘉奖对象, 但每人最多只能获奖一次.
 * 这里提供两种实现方式, 并加以比较其时间复杂度, 以便优选算法
 * 	算法1: 先对所有成绩排序, 然后从中选择
 * 	算法2: 不经过排序, 一遍扫描数据集选择数据
 * 时间复杂度比较结果:
 *  算法1时间消耗 : 算法2时间消耗 = log N : M
 */
define('WEIGHT',				'weight');
define('TIME',					'time');
define('UID',					'uid');
define('FEED_ID',				'feed_id');

define('FEED_ID_MIN',			10000);
define('WEIGHT_MIN',			20);
define('TIME_MIN',				1000);
define('UID_MIN',				1000);

#产生测试数据
function generate_datas() {
	#定义最大值
	if ( !defined(FEED_ID_MAX) ) {
		define('FEED_ID_MAX',			FEED_ID_MIN + FEED_ID_COUNT);
		define('WEIGHT_MAX',			WEIGHT_MIN + WEIGHT_COUNT);
		define('TIME_MAX',				TIME_MIN + TIME_COUNT);
		define('UID_MAX',				UID_MIN + UID_COUNT);
	}
	$feed_id	= FEED_ID_MIN;
	$datas		= array();
	while ( $feed_id ++ < FEED_ID_MAX ) {
		array_push($datas, array(
			FEED_ID		=> $feed_id, 
			TIME		=> rand(TIME_MIN, TIME_MAX), 
			UID			=> rand(UID_MIN, UID_MAX), 
			WEIGHT		=> rand(WEIGHT_MIN, WEIGHT_MAX), 
		));
	}
	return $datas;
}
#输出测试数据
function output_datas($datas, $fp) {
	foreach ( $datas as $data ) {
		fprintf($fp, "%d %d %d %d\n", $data[FEED_ID], $data[WEIGHT], $data[UID], $data[TIME]);
	}
}
#权重排序(先权重, 后时间)
function weight_sort($a, $b) {
	if ( $a[WEIGHT] != $b[WEIGHT] ) return $a[WEIGHT] - $b[WEIGHT];
	return $a[TIME] - $b[TIME];
}
#权重排序(先权重, 后时间), 倒序, 供先排序后选择算法使用
function weight_sort_reverse($a, $b) {
	if ( $b[WEIGHT] != $a[WEIGHT] ) return $b[WEIGHT] - $a[WEIGHT];
	return $b[TIME] - $a[TIME];
}
#权重选择(基于已排序数据集)
function weight_select($datas, $uniq_key, $count) {
	$result	= array();
	foreach ( $datas as $data ) {
		if ( array_key_exists($data[$uniq_key], $result) ) continue;
		$result[$data[$uniq_key]]	= $data;
		if ( -- $count <= 0 ) break;
	}
	return $result;
}

/**
 * compare_select_uniq_n 
 * 读取数据集$datas中的数据, 应用$compare比较函数, 选取$uniq_key数据项不重复的最大前$count条数据
 * 复杂度计算:
 * 	假设: 
 * 		1. 数据集$datas长度为N
 * 		2. 要获取的记录数$count为M
 * 	计算:
 * 		复杂度	= O( M * 2 ) + O( M * M * 1 ) + O( (N - M) * 1 ) + O( (N - M) * M * 2 ) + O( (N - M) * 1 )
 * 				= O( 2 * M * (M + 1) ) + O( 2 * (N - M) * (M + 1) )
 *				= O( 2 * (M + N - M) * (M + 1) )
 * 				= O( 2 * N * (M + 1) )
 * 				= O( N * M )	#忽略常数
 * @param mixed $datas 
 * @param mixed $uniq_key 
 * @param mixed $compare 
 * @param mixed $count 
 * @access public
 * @return void
 */
function compare_select_uniq_n($datas, $uniq_key, $compare, $count) {
	$tmp_datas	= array();			#结果集空间
	$tmp_length	= 0;				#结果集空间当前长度
	$index		= 0;				#遍历目标数据集$datas的下标
	$length		= count($datas);	#目标数据集$datas的长度
	#step 1: 构造初始的$count个临时数据
#复杂度: O(M * 2)
	while ( $count -- > 0 && $index < $length ) {
		$data	= $datas[$index];
		$index ++;

		#寻找唯一键相同的已有数据, 比较替换
#复杂度: O(M * M * 2)
		foreach ( $tmp_datas as $i => $ele ) {
			if ( $ele[$uniq_key] == $data[$uniq_key] ) {
				if ( $compare($data, $ele) > 0 ) 
					$tmp_datas[$i]	= $data;
				break;
			}
		}

		$tmp_datas[$count]	= $data;
	}
	#step2: 遍历剩余数据, 比较替换
#复杂度: O( (N - M) * 1 )
	while ( $index < $length ) {
		$data	= $datas[$index];
		$index ++;

		#寻找结果集中要替换的数据下标
		$cmp_i	= 0;
#复杂度: O( (N - M) * M * 2 )
		foreach ( $tmp_datas as $i => $ele ) {
			#优先选择唯一键相同的数据
			if ( $ele[$uniq_key] == $data[$uniq_key] ) {
				$cmp_i	= $i;
				break;
			#否则查找当前结果集中的最小记录
			} else if ( $compare($tmp_datas[$cmp_i], $ele) > 0 ) {
				$cmp_i	= $i;
			}
		}
		#检查要替换的目标数据, 如果符合替换条件则替换
#复杂度: O( (N - M) * 1 )
		if ( $compare($data, $tmp_datas[$cmp_i]) > 0 ) 
			$tmp_datas[$cmp_i]	= $data;
	}
	return $tmp_datas;
}
#基于排序然后选择的算法
function compare_select_uniq_n_sort($datas, $uniq_key, $compare, $count) {
	usort($datas, $compare);
	return weight_select($datas, $uniq_key, $count);
}
#测试入口封装
function test_wrap($datas, $uniq_key, $compare, $count, $func, $timefp, $outfp = NULL) {
	$begin	= microtime(true);
	$datas	= $func($datas, $uniq_key, $compare, $count);
	$end	= microtime(true);
	fprintf($timefp, "%s: %ss\n", strpos($func, 'sort') === FALSE ? '自建算法' : '排序算法', $end - $begin);
	if ( $outfp ) {
		#对结果数据排序以方便价差
		usort($datas, 'weight_sort');
		output_datas($datas, $outfp);
	}
}

define('FEED_ID_COUNT',			100000);		#产生的测试数据中FEED_ID个数
define('WEIGHT_COUNT',			100);		#产生的测试数据中的WEIGHT个数上限
define('TIME_COUNT',			5000);		#产生的测试数据中的TIME个数上限
define('UID_COUNT',				5000);		#产生的测试数据中的UID个数上限

#输出句柄
$stdout	= fopen('php://stdout', 'w');
$stderr	= fopen('php://stderr', 'w');

#产生测试数据
$datas	= generate_datas();

#输出排序的测试数据集供检查正确性
#$tmp_datas	= $datas;
#usort($tmp_datas, 'weight_sort');
#output_datas($tmp_datas, $stdout);

define('RETRIEVE_COUNT',		50);		#要取回的个数

test_wrap($datas, UID, 'weight_sort', RETRIEVE_COUNT, 'compare_select_uniq_n_sort', $stdout);
test_wrap($datas, UID, 'weight_sort_reverse', RETRIEVE_COUNT, 'compare_select_uniq_n', $stdout);
/*
 +------------------+--------------------------------------------------------------+
 |                                 测试结果                                        |
 +------------------+--------------------------------------------------------------+
 |     测试条件     |                           结果数据                           |
 +------------------+--------------------------------------------------------------+
 | N: 1000          | 排序算法: 0.030486106872559s                                 |
 | M: 50            | 自建算法: 0.18151593208313s                                  |
 +------------------+--------------------------------------------------------------+
 | N: 100000        | 排序算法: 6.3918650150299s                                   |
 | M: 50            | 自建算法: 19.431954860687s                                   |
 +------------------+--------------------------------------------------------------+
 | N: 1000          | 排序算法: 0.029729843139648s                                 |
 | M: 10            | 自建算法: 0.044672012329102s                                 |
 +------------------+--------------------------------------------------------------+
 | N: 100000        | 排序算法: 5.9424071311951s                                   |
 | M: 10            | 自建算法: 4.2767288684845s                                   |
 +------------------+--------------------------------------------------------------+
 |                               测试结果分析                                      |
 +------------------+--------------------------------------------------------------+
 | 1. 快速排序法时间复杂度为O( N * log N ), 权重选择时间忽略                       |
 | 2. 自建选择算法时间复杂度为O( N * M )                                           |
 | 根据以上两条, 期望为两种算法时间消耗比例为M : log N                             |
 | 1. 50 : log 1000 = 5 : 1, 测试结果符合期望                                      |
 | 2. 50 : log 100000 = 5 : 1.3, 测试结果符合期望                                   |
 | 3. 10 : log 1000 = 1 : 1, 测试结果略有偏差, 但整体数据量小, 此误差可接受        |
 | 4. 10 : log 100000 = 1 : 1.3, 测试结果符合期望                                   |
 +------------------+--------------------------------------------------------------+
 */


分享到:
评论

相关推荐

    小学数学数学故事数学童话北游记29悟空发奖

    小学数学数学故事数学童话北游记29悟空发奖

    网络安全小卫士[2].docx

    一、教材分析: 在信息社会中,丰富的信息资源为我们的学习和生活带来极大的方便,但是,丰富的信息资源在给我们带来便利的同时,也存在许多弊端,为此对小学生进行网安全教育显得尤为必要。 二、教学目标 1学会辨析...

    heybartender:选择你的毒药

    Hey Bartender Web 应用程序使用两个 API 从 Cocktail DB 调用鸡尾酒配方,并从 Love Calculator API 查找用户兼容性。 用户可以通过特定的酒精类型进行搜索,查找非酒精饮料列表或生成随机的饮料配方。 使用 Love ...

    奖学金程序

    学校学生奖学金大作业的程序,这是自己写的,不完善之处请见谅

    NJ 奖学金 C++

    这是NJ的奖学金一题的代码,相信能够为很多学生(特别是中大林老师的)带来便利。

    鑫达进销存适用于大、中、小超市,批发商,物流配送中心,商店等

    35.商品价格调整如通过“变价单”进行,则每天可以打印出相应的商品的调价、清退信息单,便于店面依此单检查商品的变价及清退情况。调价时的变价差价可入结算库并在月底结算时扣除。 36.软件的权限设置,可设置最高...

    用JAVA实现彩票管理系统

    用JAVA实现彩票管理系统 机体功能体现为 : 购买彩票、发奖,兑奖

    抽奖系统设计方案.pdf

    抽奖发布者可以发布抽奖,管理⾃⼰发布的抽奖信息和参加该抽奖的⽤户,获取系统返回的中奖⽤户并发奖;管理员可以通 过抽奖系统后端管理现有的抽奖及⽤户信息;抽奖执⾏模块则负责⾃动适时执⾏各类抽奖。 2,开发...

    lottery_system:iris + xorm + mysql + redis企业级抽奖系统

    go抽奖系统 分6个数据库表: ...中奖记录管理,可以根据用户id或奖品id或全部显示,后台可以将用户的中奖唱片删除或标记作弊(修改状态位)奖品管理:显示名称数量更新时间等信息,可以修改奖品库存,中奖概率等

    随机获取oracle数据库中的任意一行数据(rownum)示例介绍

    最近看oracle资料的时候,了解rownum的概念,以前只知道对数据库表进行...获取出该条奖品,这样获取出来的值,在一定的并发量的时候,发生拿到同一条数据的概率就比较小啦,为了支持高并发的情况,可以在考虑为奖品表增

    TokenGenerator_java:生成令牌的代码

    Token Generator 使用SDK访问好视通云通信平台服务需要使用Token,该项目提供生成Token的Java语言代码。 关于Token鉴权的具体细节,参考 使用方式 你应该在服务器程序中使用对应的代码生成Token,将Token下发给...

    员工抽奖工具(附源代码和文档说明)

    适用于给员工幸运抽奖并发奖的场所.没有抽奖人员数量的限定,没有使用次数的限定。如果需要增值开发,可以与我联系 Email: yyazygr@163.com

    领奖台PPT模板下载

    颁奖 颁奖会 颁奖典礼 奖项 发奖 嘉奖 奖品 公司颁奖 PPT模板下载

    魔众刮刮卡抽奖系统 v1.0.0

    同时高级刮刮卡可以实现由商家自行控制出奖概率,也可以由商家直接在中奖者粉丝的手机端完全整个发奖验证流程。操作系统:Linux/Unix 或 Windows软件环境:Laravel 5.1的运行环境Apache/Nginx , ...

    墨子刮刮卡抽奖系统 v1.0.0.zip

    同时高级刮刮卡可以实现由商家自行控制出奖概率,也可以由商家直接在中奖者粉丝的手机端完全整个发奖验证流程。 墨子刮刮卡抽奖系统前台截图 墨子刮刮卡抽奖系统后台截图 相关阅读 同类推荐:站长常用源码

    我校二十一项科研成果荣获1982年北京市科技成果奖 (1983年)

    1983年2月22日北京市举行1982年优秀科技成果发奖大会,我校21项科研成果荣获奖励,其中:一等奖1项(全市共5项),二等奖6项,三等奖11项,优秀论文奖3项。获奖项目有:1.紫外曝光铬版精缩机...

    魔众大转盘抽奖系统 v1.0.0

    魔众高级大转盘功能可以在公众号内...同时高级大转盘可以实现由商家自行控制出奖概率,也可以由商家直接在中奖者粉丝的手机端完全整个发奖验证流程。您可以通过微信扫描右上角二维码来体验公众号第三方平台微信应用。

    魔众刮刮卡抽奖系统源代码

    魔众高级刮刮卡功能可以在公众号内实现刮奖活动,粉丝可以通过刮奖获得...同时高级刮刮卡可以实现由商家自行控制出奖概率,也可以由商家直接在中奖者粉丝的手机端完全整个发奖验证流程。 操作系统: Linux/Unix 或 Wi

    魔众大转盘抽奖系统源代码

    魔众高级大转盘功能可以在公众号内实现转盘活动,粉丝可以通过幸运大转盘获得...同时高级大转盘可以实现由商家自行控制出奖概率,也可以由商家直接在中奖者粉丝的手机端完全整个发奖验证流程。 您可以通过微信扫描右

Global site tag (gtag.js) - Google Analytics