MATLAB 高級數據結構連載 4 containers.Map

02-01

All comments and opinions expressed on Zhihu are mine alone and do not necessarily reflect those of my employers, past or present.

本文內容所有內容僅代表本人觀點，和Mathworks無關

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

containers.Map簡介

MATLAB中最具代表性的高級數據類型是containers.Map，我們可以把它叫做映射表。它和函數映射有些類似，比如函數映射的定義是：

F(x) = Yn

針對每一個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 電話號碼簿姓名電話號碼

先討論數組，因為電話號碼簿中既含有數字，又含有字元串，而數組中只能存放Double類型的數據，所以沒有辦法用數組直接記錄電話號碼薄中的內容。

再試試元胞數組，我們在第1行預先聲明一個 3 X 3 的元胞數組，然後在2-4行按順序填放號碼簿的內容。

% 元胞數組初始化naddressBook = cell(3,1); % 預分配大小是MATLAB編程的好習慣 naddressBook{1} = {Abby, 5086470001};naddressBook{2} = {Bob , 5086470002};naddressBook{3} = {Charlie, 5086470003}; n

需要的時候，可以通過for循環訪問其中的內容，比如：

for iter = 1:length(addressBook) % 元胞數組的遍歷n addressBook{iter} 　　　　　　　　 % 通過Index訪問元胞中的內容nendn

但是按照順序遍歷電話號碼簿沒有什麼實際用處，號碼簿的主要功能應該是提供查找的功能才是。比如要想查詢Charlie的電話號碼，我們希望程序最好可以寫成如下這樣：

CharlieNum = addressBook{Charlie} % 提示：這是錯誤的寫法n

或者

CharlieNum = addressBook.Charlie % 提示：這是錯誤的寫法n

但是元胞數組的值只能通過Index去訪問內容，不支持如上的訪問方式。所以為了找到Charlie的電話號碼，程序不得不遍曆元胞中的所有內容，取出每一個元胞元素的第一列的字元串做比較，如果名字等於Charlie，則輸出電話號碼：

% 使用for循環查找nfor iter = 1:length(addressBook)n if strcmp(addressBook{iter}{1},Charlie)n addressBook{iter}{2} % 如找到則輸出電話號碼n　　　　　 break;n endnendn

當然還有其他的方式來盛放電話號碼簿，比如把電話和名字分別存到到兩個元胞數組中去

names = {Abby,Bob,Charlie}; % 用元胞放號碼nnumbers = {5086470001,5086470002,5086470001}; % 用元胞放名字nind = find(strcmp(names,Charlie)); % strcmp接受向量的輸入返回Logical數組 n % find緊接著找出邏輯數組中非零元素的Indexnnumbers{ind} n

其中第3行strcmp接受元胞作為輸入，在其中尋找Charlie，find函數將返回Charlie所在的位置，這樣的方式比使用for循環要快，但無一例外的是，兩種方法都要從頭開始遍歷一個數組，終究來說是慢的。

除查找性能慢外，使用元胞盛放電話號碼簿類型的數據還有其它缺點：

無法方便的驗證重複數據。電話號碼簿要求每一個人的名字都是獨一無二的，所以在數據錄入的時候要防止姓名的重複，但是我們沒有其它辦法知道某名字是否已經被使用過了，除非在每次輸入的時候都對整個元胞里的內容做遍歷比較。
無法方便地添加內容。如果電話號碼簿中的記錄需要不斷地增長，但是我們沒有辦法在一開始就估計出其大概的數量，於是無法有效的預先分配內存，所以添加數據時，一旦超過預先分配的量，MATLAB就要重新分配內存了。
無法方便地刪除內容。如果我們要從元胞中去掉某一記錄，可以找到該記錄，並把該位置的元胞內容置空，但這並不會自動減小元胞數組的長度，如果
這樣的刪減操作多了，元胞中會留下很多沒有利用的空餘位置。
不方便作為函數的參數，具體原因見struct的局限性.

最後我們再嘗試一下用結構體盛放電話號碼簿數據類型，struct的賦值很簡單，比如可以直接賦值：

% 賦值方法1naddressBook.Abby = 5086470001;naddressBook.Bob = 5086470002;naddressBook.Charlie = 5086470003;n

或者：

% 賦值方法2naddressBook = struct(Abby,5086470001,Bob,5086470002,Charlie,5086470003)n

方法1和方法2是等價的。

struct數據類型的查找很方便，比如要查詢Charlie的電話號碼，直接訪問struct中的同名的field即可以了。

num = addressBook.Charlie n

如果要查詢的人名是一個變數, 我們可以使用getfield函數：

num = getfield(addressBook,name) % 其中name是變數 n

struct盛放電話號碼簿類型的數據，查詢起來確實比元胞進步了不少，但還是有些不方便的地方。

因為struct的field的名字要求必須是以字母開頭，這是一個很大的局限，並不是所有的類似電話號碼簿的結構都可以用人名做索引，比如賬戶號碼簿，股票代碼等等，他們通常是用數字開頭的，比如圖Table.2中的數據：

Table.2 深證股票代碼

如果我們要求通過股票的代碼來查找股票的具體信息，struct無法簡單的直接做到。

使用struct的另一個不方便之處在於，當把struct當做函數參數，並且在函數內部需要對該struct做一定的修改時，為了要把修改後的結果返回，我們需要對原來的struct做完全的拷貝，顯然如果struct中的數據很多的話，這樣做是低效的。比如下面的函數中，addressBook被當做函數的參數傳入，在函數中添加了一個新的field，為了返回更新後的結構，函數內部必須重新構造一個新的struct，也就是s返回給該函數的調用者。

% 把struct當做函數的參數 nfunction s = modifystruct(s)n s.Dave = 5086470004;nendn

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

上面一節我們介紹了數組，元胞數組和結構體在模擬電話號碼簿這種數據結構時的局限性，這節我們來看怎麼用 containers.Map 來盛放電話號碼簿中的內容：

addressMap = containers.Map; % 首先聲明一個映射表對象變數naddressMap(Abby) = 5086470001;naddressMap(Bob) = 5086470002;naddressMap(Charlie) = 5086470003; n

第一行我們聲明一個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的電話號碼，只需：

% 查找 nnum = addressMap(Charlie) n

如果我們要修改Charlie的電話號碼，只需：

% 賦值naddressMap(Charlie) = newNum; n

什麼是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對象naddressMap = containers.Map;naddressMap(Abby) = 5086470001;naddressMap(Bob) = 5086470002;naddressMap(Charlie) = 5086470003;n

在命令行中鍵入該對象的名稱，MATLAB會顯示該對象屬性的基本信息：

>> addressMapnaddressMap =n Map with properties:n Count: 3 % MAP 中映射對的數目n KeyType: char % MAP 中鍵的類型 n ValueType: any % MAP 中鍵值的類型 n

其中Count 表示Map對象中映射對的數目。按照規定，鍵的類型一定要是字元類型，不能是其它數據類型，而鍵值的類型可以是MATLAB中的任意類型：數組，元胞，結構體，MATLAB對象，甚至JAVA對象等等。因為鍵值的類型可以是任何MATLAB類型，所以 containers.Map 是MATLAB中極其靈活的數據類型。

成員方法keys 用來返回對象中所有的鍵：

>> addressMap.keysnans =n Charlie Abby Bob n

成員方法values用來返回對象中的所有鍵值

>> addressMap.valuesnans = n 5086470003 5086470001 5086470002 n

remove用來移除對象中的一個鍵-鍵值對，經過下面的操作之後，該對象中的Count的值變成了2。

>> addressMap.remove(Charlie)nans = n Map with properties:n Count: 2 % 映射對數目減少n KeyType: charn ValueType: anyn n

isKey成員方法用來判斷一個map對象中是否已經含有一個鍵值，比如：

>> addressMap.isKey(Abby)nans =n 1n>> addressMap.isKey(abby) % 鍵是大小寫敏感的nans =n 0 n

isKey的功能是查詢，類似之前提到的find和strcmp函數合起來使用的例子。

containers.Map的特點

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

使用數組和元胞數組作為數據容器，通常要預先分配容器的大小。否則每次擴充容器，MATLAB都會重新分配內存，並且拷貝原來數組中的數據到新分配的內存中去。映射表是一個可以靈活擴充的容器，並且不需要預分配，每次往裡面添加內容不會引起MATLAB重新分配內存。

我們可以通過提供兩個元胞來構造映射表對象，比如下面我們構造一個機票簿數據結構：

% 映射表的初始化方法1nticketMap = containers.Map( {2R175, B7398, A479GY}, ...n {Abby, Bob, Charlie});n n

也可以在程序的一開始，先聲明一個對象：

% 映射表的初始化方法2 n>> ticketMap = containers.Map n

然後在計算的過程中慢慢的向表中插入數據：

% 映射表的初始化方法2 n>> ticketMap[2R175] = Abby;n...n>> ticketMap[A479GY] = Charlie; n

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

因為containers.Map是handle類(handle類的介紹參見《MATLAB面向對象編程-從入門到設計模式》第三章：MATLAB的句柄類和實值類)，我們還可以方便的將這個對象傳給任何MATLAB的函數，並且在函數內部直接修改對象內部的數據，並且不用把它當做返回值輸出，比如：

>> modifyMap(ticketMap); n

modifyMap函數可以寫成：

function modifyMap(ticketMap) % 該函數沒有返回值n .....n ticketMap(NewKey) = newID nend n

注意這裡沒有把修改的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;nm = containers.Map(1:1000000,ones(1,1000000)); n

數組數據結構，使用find函數依次查找從1到(10^7)的整數，在筆者的機器上，耗時28.331901秒

% array的查找nticnfor i=1:100000, n find(b==i);nend; ntoc n

% command line結果nnnnnElapsed time is 28.331901 seconds. n

containers.Map數據結構，使用鍵值1到(10^7)進行訪問，

在筆者的機器上，耗時只需1.323007秒，

結論是：如果有大量的數據，並且要頻繁的進行查找操作，可以考慮使用containers.Map數據結構。(讀者可以試試減少容器中元素的個數，觀察一下什麼情況下，數組的查找會更快一些。)

% 映射表的查找nticnfor i=1:100000, n m(i);nend; ntocn

% command line結果 nnElapsed time is 1.323007 seconds.n

談到在MATLAB中使用高級數據結構，另一種常見的做法是直接使用Java和Python對象，這裡順便比較一下在MATLAB中使用Java的哈希表的效率。再筆者的機器上，耗時3.072889秒.

% JAVA哈希表的查找ns = java.util.HashSet();nfor i=1:100000, s.add(i); end ntic; nfor i=1:100000, n s.contains(i); nend; ntocn

% command line結果 nnnnnnnElapsed time is 3.072889 seconds.n

containers.Map的使用實例

用來盛放元素周期表

工程計算中可以使用這種鍵-鍵值的例子有很多。比如物理化學計算中可以用映射表來盛放元素周期表中的內容：

>> ptable = containers.Map;n>> ptable(H) = 1 ;n>> ptable(He) = 2 ; n

其中鍵是原子符號，而鍵值是原子量。因為鍵值的類型不限，所以鍵值本身還可以是對象，比如Atom類對象，其中包涵更多有用的內容：

% 類文件Atom.mnclassdef Atom < handlen propertiesn atomicNumbern fullNamen endn methodsn function obj = Atom(num,name)n obj.atomicNumber = num ;n obj.fullName = namen endn endnend nn 於是：n

% 鍵值可以是Atom對象 tt n>> ptable(H) = Atom(1,hydrogen);n>> ptable(H) = Atom(2,helium); n

用來實現快速地檢索

這個問題來自論壇一個網友的提問：

大家好，最近遇到一個問題，要構建20000次以上的三元素向量，且保證每次不重複構建，該向量元素值在2000―3000之間不定數，目前採用的方法是建立一歷史檔案矩陣A，構建一個存儲一行，A大小行數持續增加。每次在構建出一新的向量時對該向量與歷史檔案矩陣每行進行對比，最終確定是否構建過，若沒構建過，重新構建。演算法顯示該檢查程序運算時間在執行20000次以上時，會超過200S的運行時間。想力爭減小該時間，求方法。
多謝！

這位網友的問題不在於如何構建這些向量，而是如何保證每次不重複的構建。他一開始想出的解決方法是用矩陣A來存儲歷史檔案，每建立一個新的向量，和該歷史檔案已有的內容做比較，如果在檔案中沒有存檔，則構建。這樣設計的問題是，如他所述，當A中存儲的向量變多之後，每次檢查該向量是否之前被創建過的時間加長。

這是一個典型的可以用映射表來解決的問題，把線性的複雜度轉成常數的複雜度。他可以給每個向量設計一個獨立無二的ID，比如直接轉數字成id ：num2str(vector)

% 構建nmydictionary = containers.Mapnn%　插入數據nid = num2str(vector) ; % 比如vector = [1 2 3];nmydictionary(some_id) = vector ; n

之後的檢索也是通過vector得到獨一無二的ID，然後通過isKey來判斷該鍵值是否已經被加入到MAP中去了。

some_otherID = some_other_vector ;n% 驗證是否已經構建給過nif mydictinary.isKey(some_otherID)n %　做要做的工作nend n