嵌入式Linux平台下随机序列算法的设计
开篇：润墨网以专业的文秘视角，为您筛选了一篇嵌入式Linux平台下随机序列算法的设计范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
【摘 要】本文以多媒体播放器的随机不重复播放机能为切入点，针对嵌入式平台实时性要求高，处理速度不够快，但系统存储歌曲量大的特点，进行随机序列产生算法的设计和实现，并在ARM linux平台下进行算法的设计检证。
0 背景
随着近几年嵌入式系统总体能力的提升，嵌入式多媒体应用越来越丰富。从低端的MP3播放器，中端的workman，到高端的智能手机，音乐播放功能已经成为系统默认具备的功能。
嵌入式系统的存储能力已经跨入G时代。随身可携带的歌曲数量从几十首，已经上升至几百首，甚至上万首。
随机播放机能存在一种需求，要将播放列表中的歌曲随机播放一遍，在所有歌曲都播放一遍之前，不能出现有重复播放的情况。
1 嵌入式系统的特点
嵌入式系统的能力现在虽然已经提升不少，但和个人计算机相比较，运算能力仍然无法匹敌个人计算机。并且还存在以下几种嵌入式系统特有的特点：
*运算数据通常不能被交换到外部存储设备上，程序可以使用的内存无法超过物理内存容量。
*人机交互需要快速的实时响应，耗时过长的程序给用户较差的性能体验。
*外部存储器多为FLASH设备，写入寿命有限制，程序设计需要尽可能减少FLASH的写操作。
因此，在嵌入式系统中，随机播放的算法需要在时间以及空间的设计中，获得一个平衡，这样才能让用户有最好的体验。
2 算法的目标
*需要随机播放的总数是可变化。
*在总数给定的情况下，随机产生的序列不能出现重复。
*时间和空间使用是平衡的，满足嵌入式系统的特点。
3 解决方案
为了能够达成上述目标，主要采用下面几种技术方案：
*将随机序列的产生，分配到每一次歌曲切换的时候，而不是在初始化的过程中全部生成。
*将随机序列中某一个随机数的产生，分解为按照16进制数位分别产生，避免因为歌曲总量的提高导致时间出现指数级别的增长，尽可能控制为线性增长。
*采用bitmap标示已经产生的随机数。
*采用用时申请的方式动态申请内存。
*记录随机序列产生的结果，并提供回溯查询功能。
基于上面的技术方案，在本设计中将整体算法划分为两个部分：
*随机数列产生器，用于产生不重复的随机数列。
*随机数列记录器，用于记录已经随机数列，并向外部提供访问接口。
4 数据结构设计
4.1 顶层数据结构
顶层数据结构（shuffle_t）包含随机数列产生器和随机数列记录器。
下面是数据结构定义：
typedef struct _shuffle_t {
/* 随机数列的最大值 */
int max；
/* 随机数列产生器 */
random_t *random；
/* 随机数列记录器 */
sequence_t *sequence；
}shuffle_t；
在内存中的数据关系如图1所示。
图1 顶级数据结构示意图
4.2 随机数列产生器数据结构
随机数列产生器的数据结构（random_t）包含三个部分：
*动态增长的bitmap池。
*优化的16以内的随机数产生器。
*按数位顺序产生，代有检测功能的随机数列控制器。
下面是数据结构定义：
/*双向循环链表 */
typedef struct _chain_t {
/* 前一个链表 */
struct _chain_t *prev；
/* 后一个链表 */
struct _chain_t *next；
}chain_t；
/* digit池的描述头 */
typedef struct _pool_head_t {
/* 双向循环链表 */
chain_t chain；
/* 当前digit池的总数 */
int total；
/* 当前digit池已使用个数 */
int used；
/* digit池首地址 */
char *data；
}pool_head_t；
/* digit池总入口 */
typedef struct _pool_t {
/* bitmap池中，一个bitmap单位的大小 */
int block_size；
/* bitmap池双向链表的表头 */
chain_t chain；
}pool_t；
/* 16以内随机数产生器 */
typedef struct _hex_random_t {
/* /dev/urandom 文件描述符 */
int fd；
/* 16以内随机数缓存： 128个 */
int seed[16]；
/* 16以内随机数缓存使用位置 */
int position；
}hex_random_t；
/* 16进制数位点阵图 */
typedef struct _digit_t {
/* 当前数位在16进制数位的位置 */
int offset；
/* 点阵图 */
int bitmap；
/* 低阶数位的digit首地址 */
struct _digit_t *lower_digit[ 16 ]；
}digit_t；
/* 随机数列产生器 */
typedef struct _random_t {
/* 随机数最大值 */
int max；
/* digit池总入口 */
pool_t pool；
/* 16以内随机数产生器 */
hex_random_t hex_random；
/* 随机数最大值的16进制位数 */
int digit_total；
/* 最高阶digit首地址 */
digit_t *digit_root；
}random_t；
在内存中的数据关系如图2所示。
图2 随机数列产生器数据结构示意图
当随机数列最大值为255，并且32至255已经都产生时，随机数列产生器数据结构信息如图3所示。
图3 随机数列产生器数据结构示意图（特例）
4.3 随机数列记录器数据结构
随机数列记录器的数据结构（sequence_t）包含两个部分：
* 动态增长的记录数组
* 游标
下面是数据结构定义：
/* 随机数列记录器 */
typedef struct _sequence_t {
/* 记录器的最大值 */
int index_max；
/* 记录器的当前值 */
int index_current；
/* 记录块中的条目数 */
int index_per_block；
/* 记录块的总数 */
int block_total；
/* 记录块首地址的数组 */
int **block_vector；
}sequence_t；
在内存中的数据关系如图4所示。
图4 随机数列记录器数据结构示意图
5 关键算法流程图
某一个随机数的产生，是按照数位从高到低产生的，只有在最大数值范围内的随机数，并且是新的随机数才是合法的随机数。
因此，即使是32位范围的随机数，也只有8个数位，采取递归调用的方式并不会因为函数层次太深而占用太多的堆栈，并且代码实现比较方便。
图5至图7，采用软件设计中通用的PAD图，直观的展示了随机数列中某一个随机数的产生流程。
图5 某一个随机数产生函数PAD图
6 测试结果
在 S5PV210 开发板上进行测试，（CPU为cortex-A8 1G ARM单核处理器， 内存为200Mhz 512M的DDR2），重复产生最大值分别为15，255，4095和65535的随机数列1000次，并记录下随机数列的总体消耗时间、平均消耗时间以及某一个随机数产生的最大消耗时间。
表1和表2是测试结果。单位是微秒。
表1 测试结果1
表2 测试结果2
7 结束语
从测试结果可以看到，总体耗时和随机数列的最大值成正比；而平均耗时和数位的个数成正比；最大耗时不固定，基本上也体现出和随着数位个数增加。
平均产生一个随机数为几个纳秒，最大可能为几个毫秒。在嵌入式Linux平台下，已经基本达成算法的目标。
【参考文献】
[1]严蔚敏，吴伟民.数据结构：C语言版[M].北京：清华大学出版社，1996.
[2]韦东山.嵌入式Linux应用开发完全手册[M].北京：人民邮电出版社，2008.
[3]谭浩强.C程序设计[M].2版.北京：清华大学出版社，1999.