MATLAB映射表数据结构

2019-3-10 15:59| 发布者: ilovematlab| 查看: 45065| 评论: 6|原作者: 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++软件工程师。业余兴趣包括如何把软件工程中的现代手段,应用到科学和工程计算当中去,来更好的解决复杂的问题。包括如何从整体上设计科学计算程序的结构;如何让程序便于扩展和修改;在改进和开发算法的时候,如何保证程序已有的功能没有收到影响;如何让算法开发和测试系统的建立齐头并进。

声明:
本文内容所有内容仅代表个人观点,如有任何问题,请联系作者。
本版块所有文章版权归作者个人所有,未经允许,不得作为出版物出版。如需转载,请联系论坛管理员

23

鲜花

握手

雷人

路过

鸡蛋

刚表态过的朋友 (23 人)

发表评论

最新评论

引用 1342199147 2019-3-18 20:36
不明觉厉
引用 永定赤子 2019-1-9 15:11
看了这篇文章,很受启发.不过我有一个问题,比如我们有列向量A->列向量B的查找表M,现在我有一个数组C,通过查找表M查找得到数组D,因为containers.Map只支持单一变量输入,除了循环,即有没有一种方法实现D=M(C)。
引用 1391569671 2018-11-13 10:16
很好用,不过相对不怎么熟悉
引用 zhangqinghao 2017-9-7 10:40
关于映射表结构,能否请教一个问题,如何才能快速映射一个矩阵?
我试过用
mapping = @(x)(map_table(x));
Y = arrayfun(mapping,X);
的形式,但是运行非常慢,还不如直接用for循环快,还是说映射表现在只适合单值映 ...
引用 zhizhou450 2017-2-22 14:12
先mark一记,最近在接触金融数据,对于cell和struct型的数据真是深恶痛绝,是时候再学一波新知识了~
引用 admin 2016-5-19 17:38
MATLAB table是R2013b中引入的一个新的数据结构,虽然不像常用的基本数据类型为人熟悉,但是在编程中非常有用。
引用 mengzhihu2 2016-4-30 11:42
很强大,很实用,受教了!
另外,请问matlab是从哪个版本开始支持这一类型的呢?

查看全部评论(6)

MATLAB table数据结构 首篇

MATLAB table是R2013b中引入的一个新的数据结构,虽然不像常用的基本数据类型为人熟悉,但是在编程中非常有用。它用来存放表状类型的数据结构,并且支持常见的表和表之间的运算。 ... ... ... ... ... ... ...

MATLAB映射表数据结构

除了常用的基本数据类型,MATLAB还有很多其它实用的数据类型不为人熟悉,例如映射表containers.Map,常用的MATLAB高级数据类型。它最大的特点使用方便的索引方式进行快速的查找。本篇介绍为什么需要这种数据结构,以 ...

MATLAB table数据结构 再篇

MATLAB table是R2013b中引入的一个新的数据结构,虽然不像常用的基本数据类型为人熟悉,但是在编程中非常有用。它用来存放表状类型的数据结构,并且支持常见的表和表之间的运算。 ... ... ... ... ... ... ...

对函数的输入进行检查和解析

在工程计算中,如果函数的输入有错误,我们总是希望能尽早捕捉到这些错误,并及时终止程序。在MATLAB 中,可以使用validateattributes,validatestring和inputParser 类来对输入进行检查。它们提供全面的检查功能和清 ...

MATLAB单元测试

本篇是把现代软件工程思想应用到MATLAB工程开发中的精髓,希望高级MATLAB用户仔细研读。作者用实际的例子解释在开发和逐渐改进算法的时候,如何保证程序已有的功能没有收到影响,步步为营,让算法开发和测试系统的建 ...

MATLAB映射表数据结构

除了常用的基本数据类型,MATLAB还有很多其它实用的数据类型不为人熟悉,例如映射表containers.Map,常用的MATLAB高级数据类型。它最大的特点使用方便的索引方式进行快速的查找。本篇介绍为什么需要这种数据结构,以 ...

对函数的输入进行检查和解析

在工程计算中,如果函数的输入有错误,我们总是希望能尽早捕捉到这些错误,并及时终止程序。在MATLAB 中,可以使用validateattributes,validatestring和inputParser 类来对输入进行检查。它们提供全面的检查功能和清 ...

MATLAB性能测试框架

MATLAB Performance Test 框架是Mathworks 在MATLAB R2016a 中推出的⼀个新的框架,该框架⽤来获得代码性能在统计意义上的数据,还可以⽤来⽐较算法的性能,并且给出详细完整的报告。 ... ... ... ... ... ... ... ...
关闭

站长推荐上一条 /4 下一条

返回顶部