MATLAB映射表數據結構

2019-3-10 15:59| 發布者: ilovematlab| 查看: 49424| 評論: 11|原作者: oopmatlab

摘要: 除了常用的基本數據類型,MATLAB還有很多其它實用的數據類型不為人熟悉,例如映射表containers.Map,常用的MATLAB高級數據類型。它最大的特點使用方便的索引方式進行快速的查找。本篇介紹為什么需要這種數據結構,以 ...

文章PDF瀏覽下載鏈接

目錄:

MATLAB常用基本數據類型有:整型,浮點型,字符型,函數句柄,元胞數組和結構體數組。除了這些基本數據類型,MATLAB還有很多其它的數據類型不為人熟悉,這些數據類型在編程中也非常有用。MATLAB高級數據類型系列旨在向大家介紹它們:比如 containers.Maptablesenumeration和time series等等,它們為什么有用,用來解決什么問題,并且怎樣在科學工程計算使用。本篇首先介紹 containers.Map 數據類型。

containers.Map簡介

MATLAB中最具代表性的高級數據類型是containers.Map,我們可以把它叫做映射表。它和函數映射有些類似,比如函數映射的定義是:
F(x) = Y
針對每一個X,都有一個唯一的Y與之對應,反之不一定。如圖Fig.1所示。和函數映射相似,映射表用來形容鍵(Key)和鍵值(Key Value)之間的一一對應關系。每個Key都是獨一無二的,且只能對一個Key Value。如圖Fig.2所示。
Fig.1 函數映射關系
Fig.2 containers.Map類的映射示意圖

數組,元胞和結構體的局限性

開始我們先介紹一下數組,元胞數組和結構體的局限性,為什么有的時候這些基本的數據類型無法滿足程序的要求,換句話說,我們為什么需要 containers.Map 數據結構。假設要用MATLAB來記錄電話號碼簿中數據,比如表Table.1所示:
Table.1 電話號碼簿
姓名 電話號碼
Abby 5086470001
Bob 5086470002
Charlie 5086470003
先討論數組,因為電話號碼簿中既含有數字,又含有字符串,而數組中只能存放Double類型的數據,所以沒有辦法用數組直接記錄電話號碼薄中的內容。 再試試元胞數組,我們在第1行預先聲明一個 3 X 3 的元胞數組,然后在2-4行按順序填放號碼簿的內容。
% 元胞數組初始化
addressBook    = cell(3,1);    % 預分配大小是MATLAB編程的好習慣 
addressBook{1} = {'Abby',     '5086470001'};
addressBook{2} = {'Bob' ,     '5086470002'};
addressBook{3} = {'Charlie',  '5086470003'};      
需要的時候,可以通過for循環訪問其中的內容,比如:
for iter = 1:length(addressBook)         % 元胞數組的遍歷
   addressBook{iter}               % 通過Index訪問元胞中的內容
end
但是按照順序遍歷電話號碼簿沒有什么實際用處,號碼簿的主要功能應該是提供查找的功能才是。比如要想查詢Charlie的電話號碼,我們希望程序最好可以寫成如下這樣:
CharlieNum = addressBook{'Charlie'}     % 提示:這是錯誤的寫法
或者
CharlieNum = addressBook.Charlie        % 提示:這是錯誤的寫法
但是元胞數組的值只能通過Index去訪問內容,不支持如上的訪問方式。所以為了找到Charlie的電話號碼,程序不得不遍歷元胞中的所有內容,取出每一個元胞元素的第一列的字符串做比較,如果名字等于Charlie,則輸出電話號碼:
% 使用for循環查找
for iter = 1:length(addressBook)
   if strcmp(addressBook{iter}{1},'Charlie')
        addressBook{iter}{2}              % 如找到則輸出電話號碼
      break;
   end
end
當然還有其他的方式來盛放電話號碼簿,比如把電話和名字分別存到到兩個元胞數組中去
names   = {'Abby','Bob','Charlie'};                 % 用元胞放號碼
numbers = {'5086470001','5086470002','5086470001'}; % 用元胞放名字
ind = find(strcmp(names,'Charlie'));  % strcmp接受向量的輸入 返回Logical數組 
                                      % find緊接著找出邏輯數組中非零元素的Index
numbers{ind}  
其中第3行strcmp接受元胞作為輸入,在其中尋找Charlie,find函數將返回Charlie所在的位置,這樣的方式比使用for循環要快,但無一例外的是,兩種方法都要從頭開始遍歷一個數組,終究來說是慢的。 除查找性能慢外,使用元胞盛放電話號碼簿類型的數據還有其它缺點:
  • 無法方便的驗證重復數據。電話號碼簿要求每一個人的名字都是獨一無二的,所以在數據錄入的時候要防止姓名的重復,但是我們沒有其它辦法知道某名字是否已經被使用過了,除非在每次輸入的時候都對整個元胞里的內容做遍歷比較。
  • 無法方便地添加內容。如果電話號碼簿中的記錄需要不斷地增長,但是我們沒有辦法在一開始就估計出其大概的數量,于是無法有效的預先分配內存,所以添加數據時,一旦超過預先分配的量,MATLAB就要重新分配內存了。
  • 無法方便地刪除內容。如果我們要從元胞中去掉某一記錄,可以找到該記錄,并把該位置的元胞內容置空,但這并不會自動減小元胞數組的長度,如果 這樣的刪減操作多了,元胞中會留下很多沒有利用的空余位置。
  • 不方便作為函數的參數,具體原因見struct的局限性.
最后我們再嘗試一下用結構體盛放電話號碼簿數據類型,struct的賦值很簡單,比如可以直接賦值:
% 賦值方法1
addressBook.Abby   = '5086470001';
addressBook.Bob  = '5086470002';
addressBook.Charlie  = '5086470003';
或者:
% 賦值方法2
addressBook = struct('Abby','5086470001','Bob','5086470002','Charlie','5086470003')
方法1和方法2是等價的。 struct數據類型的查找很方便,比如要查詢Charlie的電話號碼,直接訪問struct中的同名的field即可以了。
num = addressBook.Charlie  
如果要查詢的人名是一個變量, 我們可以使用getfield函數:
num = getfield(addressBook,name)  % 其中name是變量   
struct盛放電話號碼簿類型的數據,查詢起來確實比元胞進步了不少,但還是有些不方便的地方。 因為struct的field的名字要求必須是以字母開頭,這是一個很大的局限,并不是所有的類似電話號碼簿的結構都可以用人名做索引,比如賬戶號碼簿,股票代碼等等,他們通常是用數字開頭的,比如圖Table.2中的數據:
Table.2 深證股票代碼
股票代碼 股票名稱
000001 深發展
000002 萬科
000004 ST國農
如果我們要求通過股票的代碼來查找股票的具體信息,struct無法簡單的直接做到。 使用struct的另一個不方便之處在于,當把struct當做函數參數,并且在函數內部需要對該struct做一定的修改時,為了要把修改后的結果返回,我們需要對原來的struct做完全的拷貝,顯然如果struct中的數據很多的話,這樣做是低效的。比如下面的函數中,addressBook被當做函數的參數傳入,在函數中添加了一個新的field, 為了返回更新后的結構,函數內部必須重新構造一個新的struct,也就是s返回給該函數的調用者。
% 把struct當做函數的參數    
function s = modifystruct(s)
    s.Dave =  '5086470004';
end

用containers.Map來記錄電話號碼簿

上面一節我們介紹了數組,元胞數組和結構體在模擬電話號碼簿這種數據結構時的局限性,這節我們來看怎么用 containers.Map 來盛放電話號碼簿中的內容:
addressMap = containers.Map;             % 首先聲明一個映射表對象變量
addressMap('Abby')    = '5086470001';
addressMap('Bob')     = '5086470002';
addressMap('Charlie') = '5086470003';  
第一行我們聲明一個containers.Map的變量(其實是containers.Map類的對象)叫做addressMap,2,3,4行通過提供Key Key Value的方式來給對象賦值,其中單引號內部的值叫做鍵(Key),等式右邊的叫做鍵值(Key Value)。通過這個結構,我們在MATLAB內存中,建立起了如圖Fig.3的映射關系數據結構。
Fig.3 電話號碼簿映射表
Fig.4 Map類的UML
查找addressMap對象中的內容極其方便,比如查找我們想知道Charlie的電話號碼,只需:
% 查找  
num  = addressMap('Charlie')  
如果我們要修改Charlie的電話號碼,只需 :
% 賦值
addressMap('Charlie') = newNum;  

什么是containers.Map

containers.Map是一個MATLAB的內置類(類是面向對象編程中的一個基本概念,在這里可以把類暫時理解成一種數據類型),所謂內置,就是MATLAB內部實現的,通常這種類的性能更加的優秀。containers.Map其中containers是Package的名稱,Map是該Package中的一個類,Map是它的類名。用UML(Unified Modeling Language)的語法把該類表示出來,它的屬性包括Count, KeyType,ValueType。它的常用方法包括keys,values,isKey,remove。如圖Fig.4所示。

containers.Map的屬性和成員方法

這節我們介紹containers.Map的屬性和成員方法,假設我們這樣初始化一個containers.Map對象:
% 初始化一個Map對象
addressMap = containers.Map;
addressMap('Abby')    = '5086470001';
addressMap('Bob')     = '5086470002';
addressMap('Charlie') = '5086470003';
在命令行中鍵入該對象的名稱,MATLAB會顯示該對象屬性的基本信息:
>> addressMap
addressMap =
  Map with properties:
        Count: 3          % MAP 中映射對的數目
      KeyType: char       % MAP 中鍵的類型 
    ValueType: any        % MAP 中鍵值的類型   
其中Count 表示Map對象中映射對的數目。按照規定,鍵的類型一定要是字符類型,不能是其它數據類型,而鍵值的類型可以是MATLAB中的任意類型:數組,元胞,結構體,MATLAB對象,甚至JAVA對象等等。因為鍵值的類型可以是任何MATLAB類型,所以 containers.Map 是MATLAB中極其靈活的數據類型。 成員方法keys 用來返回對象中所有的鍵:
>> addressMap.keys
ans =
    'Charlie'    'Abby'    'Bob'  
成員方法values用來返回對象中的所有鍵值
>> addressMap.values
ans = 
    '5086470003'    '5086470001'    '5086470002'  
remove用來移除對象中的一個鍵-鍵值對,經過下面的操作之后,該對象中的Count的值變成了2。
>> addressMap.remove('Charlie')
ans = 
  Map with properties:
        Count: 2          % 映射對數目減少
      KeyType: char
    ValueType: any
  
isKey成員方法用來判斷一個map對象中是否已經含有一個鍵值,比如:
>> addressMap.isKey('Abby')
ans =
     1
>> addressMap.isKey('abby')    % 鍵是大小寫敏感的
ans =
     0  
isKey的功能是查詢,類似之前提到的find和strcmp函數合起來使用的例子。

containers.Map的特點

containers.Map可以不斷地擴張不需預分配

使用數組和元胞數組作為數據容器,通常要預先分配容器的大小。否則每次擴充容器,MATLAB都會重新分配內存,并且拷貝原來數組中的數據到新分配的內存中去。映射表是一個可以靈活擴充的容器,并且不需要預分配,每次往里面添加內容不會引起MATLAB重新分配內存。 我們可以通過提供兩個元胞來構造映射表對象,比如下面我們構造一個機票簿數據結構:
% 映射表的初始化方法1
ticketMap = containers.Map( {'2R175', 'B7398', 'A479GY'}, ...
                            {'Abby', 'Bob, 'Charlie'});
  
也可以在程序的一開始,先聲明一個對象:
% 映射表的初始化方法2  
>> ticketMap = containers.Map 
然后在計算的過程中慢慢的向表中插入數據:
% 映射表的初始化方法2  
>> ticketMap['2R175'] = 'Abby';
...
>> ticketMap['A479GY'] = 'Charlie;  

containers.Map可以作為參數在函數內部直接修改

因為containers.Map是handle類(handle類的介紹參見《MATLAB面向對象編程-從入門到設計模式》第三章:MATLAB的句柄類和實值類),我們還可以方便的將這個對象傳給任何MATLAB的函數,并且在函數內部直接修改對象內部的數據,并且不用把它當做返回值輸出,比如:
>> modifyMap(ticketMap);  
modifyMap函數可以寫成:
function modifyMap(ticketMap)   % 該函數沒有返回值
   .....
   ticketMap(NewKey) = newID 
end  
注意這里沒有把修改的ticketMap當做返回值,在函數中我們直接修改了Map中的數據,這是MATLAB面向對象語言中handle類的特性。

containers.Map可以增強程序的可讀性

映射表內部可以存儲各種類型的數據,并且給它們起一些有意義的名字。具體的例子見元素周期表的例子。 訪問和修改這些數據的時候,可以直接使用這些有意義的名字,從而增加程序的可讀性。而如果用元胞數組存儲這些數據,在訪問和修改這些數據的時候, 需要使用整數的Index,程序可讀性不夠好。

containers.Map提供對數據的快速查找

映射表查找的復雜度是常數O(C)的,而傳統的數組和元胞數組查找的復雜度是線性O(N)的。如果不熟悉算法中復雜度的概念,可以這樣理解:如果使用數組或者元胞來存儲數據,當我們要在該數據結構中搜索一個值時,只能做線性搜索,平均下來,搜索的時間和該數據結構中的元素的數目N成正比,即元胞和數組中的元素越多,找到一個值所用的時間就越長,這叫做線性的復雜度 O(N)。而映射表采取的底層實現是哈希表(Hash Map),搜索時間是常數C,理論上來說搜索速度和集合中元素的個數沒有關系。所以當容器中元素數量眾多的時候,要想查找得快,可以使用containers.Map結構。具體例子見快速查找的例子。 下面通過對假想的數據集合進行查找,來比較一下數組和container.Map的性能。我們第一行先構造一個含有1000000(10^7)個整數的數組(這是數組中元素的個數很多,如果只有少量元素,線性查找的效率會高一些),按順序填充從1到(10^7)的整數;作為比較,第二行再構造一個containers.Map對象,往內部填充從1到(10^7)的整數,Key和KeyValue都相同。
a = 1:1000000;
m = containers.Map(1:1000000,ones(1,1000000));  
數組數據結構,使用find函數依次查找從1到(10^7)的整數,在筆者的機器上,耗時28.331901秒
% array的查找
tic
for i=1:100000, 
    find(b==i);
end; 
toc  
% command line結果




Elapsed time is 28.331901 seconds.  
containers.Map數據結構,使用鍵值1到(10^7)進行訪問, 在筆者的機器上,耗時只需1.323007秒, 結論是:如果有大量的數據,并且要頻繁的進行查找操作,可以考慮使用containers.Map數據結構。(讀者可以試試減少容器中元素的個數,觀察一下什么情況下,數組的查找會更快一些。)
% 映射表的查找
tic
for i=1:100000, 
    m(i);
end; 
toc
% command line結果      




Elapsed time is 1.323007 seconds.
談到在MATLAB中使用高級數據結構,另一種常見的做法是直接使用Java和Python對象,這里順便比較一下在MATLAB中使用Java的哈希表的效率。再筆者的機器上,耗時3.072889秒.
% JAVA哈希表的查找
s = java.util.HashSet();
for i=1:100000, s.add(i); end   
tic; 
for i=1:100000, 
    s.contains(i); 
end; 
toc
% command line結果      






Elapsed time is 3.072889 seconds.

containers.Map的使用實例

用來盛放元素周期表

工程計算中可以使用這種鍵-鍵值的例子有很多。比如物理化學計算中可以用映射表來盛放元素周期表中的內容:
>> ptable = containers.Map;
>> ptable('H')  = 1 ;
>> ptable('He') = 2 ;  
其中鍵是原子符號,而鍵值是原子量。因為鍵值的類型不限,所以鍵值本身還可以是對象,比如Atom類對象,其中包涵更多有用的內容:
% 類文件Atom.m
classdef Atom < handle
  properties
      atomicNumber
      fullName
  end
  methods
    function obj = Atom(num,name)
       obj.atomicNumber = num ;
       obj.fullName = name
    end
  end
end  
\end{Verbatim} 于是:
% 鍵值可以是Atom對象 		  
>> ptable('H') = Atom(1,'hydrogen');
>> ptable('H') = Atom(2,'helium');  

用來實現快速地檢索

這個問題來自ilovematlab一個網友的提問:
大家好,最近遇到一個問題,要構建20000次以上的三元素向量,且保證每次不重復構建,該向量元素值在2000―3000之間不定數,目前采用的方法是建立一歷史檔案矩陣A,構建一個存儲一行,A大小行數持續增加。每次在構建出一新的向量時對該向量與歷史檔案矩陣每行進行對比,最終確定是否構建過,若沒構建過,重新構建。算法顯示該檢查程序運算時間在執行20000次以上時,會超過200S的運行時間。想力爭減小該時間,求方法。 多謝!
這位網友的問題不在于如何構建這些向量,而是如何保證每次不重復的構建。他一開始想出的解決方法是用矩陣A來存儲歷史檔案,每建立一個新的向量,和該歷史檔案已有的內容做比較,如果在檔案中沒有存檔,則構建。這樣設計的問題是,如他所述,當A中存儲的向量變多之后,每次檢查該向量是否之前被創建過的時間加長。 這是一個典型的可以用映射表來解決的問題,把線性的復雜度轉成常數的復雜度。他可以給每個向量設計一個獨立無二的ID,比如直接轉數字成id : num2str(vector)
% 構建
mydictionary = containers.Map

% 插入數據
id = num2str(vector) ; % 比如vector = [1 2 3];
mydictionary('some_id') = vector ;  
之后的檢索也是通過vector得到獨一無二的ID,然后通過isKey來判斷該鍵值是否已經被加入到MAP中去了。
some_otherID = some_other_vector ;
% 驗證是否已經構建給過
if mydictinary.isKey('some_otherID')
      % 做要做的工作
end  


關于作者

oopmatlab,計算物理博士,計算機碩士,《MATLAB面向對象編程-從入門到設計模式》作者,現就職一家科學工程計算公司的任架構組C++軟件工程師。業余興趣包括如何把軟件工程中的現代手段,應用到科學和工程計算當中去,來更好的解決復雜的問題。包括如何從整體上設計科學計算程序的結構;如何讓程序便于擴展和修改;在改進和開發算法的時候,如何保證程序已有的功能沒有收到影響;如何讓算法開發和測試系統的建立齊頭并進。

聲明:
本文內容所有內容僅代表個人觀點,如有任何問題,請聯系作者。
本版塊所有文章版權歸作者個人所有,未經允許,不得作為出版物出版。如需轉載,請聯系論壇管理員

32

鮮花

握手

雷人

路過

雞蛋

剛表態過的朋友 (32 人)

發表評論

最新評論

引用 Violet96 2019-10-27 16:13
總是能看到新的用途
引用 昔我往矣3838438 2019-10-13 10:09
很實用,謝謝樓主,這樣算參加了討論嗎?
引用 張卷卷 2019-9-29 14:20
受教了
引用 2827164381 2019-9-21 09:43
引用 rozall 2019-9-7 11:57
學到了
引用 玖攸 2019-8-23 19:04
學習了
引用 liuminghuan 2019-8-22 12:11
感謝樓主分享~~
引用 WZYang 2019-8-21 16:11
內容很豐富
引用 yangxiaoxiang 2019-8-21 11:05
學習了
引用 xanaduzb 2019-7-18 18:57
水平有點不足,看不懂啊
引用 wx_NqPG2gPU 2019-7-13 17:34
受益匪淺
引用 nhuwhusuhf 2019-7-11 09:23
fighting
引用 kcv—— 2019-7-9 18:05
學習了
引用 kcv—— 2019-7-9 18:05
學習了
引用 lizhihao118110 2019-7-9 08:14
學習了大神
引用 十里楓葉如雨 2019-7-1 10:41
很棒
引用 比熊妮妮 2019-6-19 16:39
牛人,matlab還能這么用啊
引用 a_polar_bear 2019-6-14 16:52
學習了
引用 ffggrt6 2019-6-13 15:59
厲害
引用 zhongze2014 2019-6-13 13:28
很有用,很強大

查看全部評論(11)

MATLAB table數據結構 首篇

MATLAB table是R2013b中引入的一個新的數據結構,雖然不像常用的基本數據類型為人熟悉,但是在編程中非常有用。它用來存放表狀類型的數據結構,并且支持常見的表和表之間的運算。 ... ... ... ... ... ... ...

MATLAB映射表數據結構

除了常用的基本數據類型,MATLAB還有很多其它實用的數據類型不為人熟悉,例如映射表containers.Map,常用的MATLAB高級數據類型。它最大的特點使用方便的索引方式進行快速的查找。本篇介紹為什么需要這種數據結構,以 ...

MATLAB table數據結構 再篇

MATLAB table是R2013b中引入的一個新的數據結構,雖然不像常用的基本數據類型為人熟悉,但是在編程中非常有用。它用來存放表狀類型的數據結構,并且支持常見的表和表之間的運算。 ... ... ... ... ... ... ...

MATLAB單元測試

本篇是把現代軟件工程思想應用到MATLAB工程開發中的精髓,希望高級MATLAB用戶仔細研讀。作者用實際的例子解釋在開發和逐漸改進算法的時候,如何保證程序已有的功能沒有收到影響,步步為營,讓算法開發和測試系統的建 ...

對函數的輸入進行檢查和解析

在工程計算中,如果函數的輸入有錯誤,我們總是希望能盡早捕捉到這些錯誤,并及時終止程序。在MATLAB 中,可以使用validateattributes,validatestring和inputParser 類來對輸入進行檢查。它們提供全面的檢查功能和清 ...

MATLAB映射表數據結構

除了常用的基本數據類型,MATLAB還有很多其它實用的數據類型不為人熟悉,例如映射表containers.Map,常用的MATLAB高級數據類型。它最大的特點使用方便的索引方式進行快速的查找。本篇介紹為什么需要這種數據結構,以 ...

對函數的輸入進行檢查和解析

在工程計算中,如果函數的輸入有錯誤,我們總是希望能盡早捕捉到這些錯誤,并及時終止程序。在MATLAB 中,可以使用validateattributes,validatestring和inputParser 類來對輸入進行檢查。它們提供全面的檢查功能和清 ...

MATLAB性能測試框架

MATLAB Performance Test 框架是Mathworks 在MATLAB R2016a 中推出的?個新的框架,該框架?來獲得代碼性能在統計意義上的數據,還可以?來?較算法的性能,并且給出詳細完整的報告。 ... ... ... ... ... ... ... ...
關閉

站長推薦上一條 /3 下一條

返回頂部
哪一款德州扑克还能玩