嵌入式Linux平臺下隨機序列算法設計

嵌入式Linux平臺下隨機序列算法設計

【摘 要】本文以多媒體播放器的隨機不重復播放機能為切入點，針對嵌入式平臺實時性要求高，處理速度不夠快，但系統存儲歌曲量大的特點，進行隨機序列產生算法的設計和實現，并在ARM Linux平臺下進行算法的設計檢證。

【關鍵詞】嵌入式；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 {

總結

以上是生活随笔為你收集整理的linux算法设计,嵌入式Linux平台下随机序列算法设计.doc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。