MATLAB中的哈希表

93

Matlab是否支持哈希表?


一些背景

我正在解决一个在Matlab中需要对图像进行尺度空间表示的问题。为了做到这一点,我创建一个方差为sigma*s^k的二维高斯滤波器,其中k在某个范围内,然后我依次使用每个滤波器来过滤图像。现在,我想要一些从k到过滤图像的映射。

如果k总是整数,我只需创建一个三维数组,使之成立:

arr[k] = <image filtered with k-th guassian>

然而k并不一定是整数,所以我不能这样做。我的想法是保留一个k数组,使其满足以下条件:

arr[find(array_of_ks_ = k)] = <image filtered with k-th guassian>

一开始看起来这很好,但我可能要使用约20或30个k的值进行数千次查找,我担心这会影响性能。

我想知道是否最好使用某种哈希表进行此操作,以便我具有O(1)的查找时间,而不是O(n)。


现在,我知道我不应该过早地进行优化,而且我可能根本没有这个问题,但请记住,这只是背景,可能存在情况下,这确实是最好的解决方案,无论它是否是针对我的问题的最佳解决方案。

7个回答

121
考虑使用MATLAB的map类:containers.Map。以下是简要概述:
  • 创建:

    >> keys = {'Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun', ...
      'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec', 'Annual'};
    
    >> values = {327.2, 368.2, 197.6, 178.4, 100.0,  69.9, ...
      32.3,  37.3,  19.0,  37.0,  73.2, 110.9, 1551.0};
    
    >> rainfallMap = containers.Map(keys, values)
    
    rainfallMap = 
      containers.Map handle
      Package: containers
    
      Properties:
            Count: 13
          KeyType: 'char'
        ValueType: 'double'
      Methods, Events, Superclasses
    
  • 查找:

    x = rainfallMap('Jan');
    
  • 赋值:

    rainfallMap('Jan') = 0;
    
  • 添加:

    rainfallMap('Total') = 999;
    
  • 移除:

    rainfallMap.remove('Total')
    
  • 检查:

    values = rainfallMap.values;
    keys = rainfallMap.keys;
    sz = rainfallMap.size;
    
  • 检查键:

  • if rainfallMap.isKey('Today')
        ...
    end
    

7
哇,我不知道!+1。你知道它们是否比逻辑索引快很多吗? - Jonas
3
MATLAB 7.7(R2008b)中添加了Containers.Map,详见http://www.mathworks.com/access/helpdesk/help/techdoc/rn/brqyzax-1.html。在R2010a中新增了一个构造器,可以指定键类型和值类型。 M = containers.Map('KeyType',kType,'ValueType',vType) - zellus
9
@zellus,@amro:Matlab 中没有命令历史记录,这不是很烦人吗? - Jonas
4
查询:rainfallMap('Jan'); 赋值:rainfallMap('Jan') = 'zero'; 查看:rainfallMap.values; rainfallMap.keys; rainfallMap.size; 检查键:rainfallMap.isKey('Today'); - Evgeni Sergeev
1
从MATLAB R2022b开始,dictionary现在被推荐使用,而不是containers.Map。我在下面的答案中添加了一个链接,说明如何使用dictionary - undefined
显示剩余3条评论

26

Matlab R2008b (7.7)的新containers.Map类是一个缩小版的Matlab版本java.util.Map接口。它具有与所有Matlab类型(例如Java Maps无法处理Matlab结构体)无缝集成的附加功能,以及自Matlab 7.10 (R2010a)起指定数据类型的能力。

需要使用键值映射/字典的严肃Matlab实现应仍然使用Java的Map类 (java.util.EnumMap, HashMap, TreeMap, LinkedHashMapHashtable),以获得更大的功能性和性能。在任何情况下,早于R2008b版本的Matlab没有真正的替代方案,必须使用Java类。

使用Java集合的潜在限制是无法包含结构体等非原始Matlab类型。为了克服这个问题,可以将类型降级(例如使用struct2cell或编程方式),或创建一个单独的Java对象来保存您的信息并将此对象存储在Java Collection中。

你可能也会对一个纯Matlab面向对象(基于类)的Hashtable实现感兴趣,这个实现可以在File Exchange中找到。


1
今天又发布了另一个基于Matlab类的实现:http://www.mathworks.com/matlabcentral/fileexchange/28586 - Yair Altman

19

您可以使用Java来完成此操作。

在Matlab中:

dict = java.util.Hashtable;
dict.put('a', 1);
dict.put('b', 2);
dict.put('c', 3);
dict.get('b')

但我想你需要进行一些分析,以确定它是否能够带来速度提升...


14

Matlab不支持哈希表。 编辑 直到r2010a版本为止,参见@Amro的回答。

为了加快查找速度,您可以省略find并使用逻辑索引

arr{array_of_ks==k} = <image filtered with k-th Gaussian>
或者
arr(:,:,array_of_ks==k) = <image filtered with k-th Gaussian>

然而,根据我对Matlab的所有经验,我从未遇到过查找成为瓶颈的情况。


为了加速您的特定问题,我建议使用增量过滤。

arr{i} = GaussFilter(arr{i-1},sigma*s^(array_of_ks(i)) - sigma*s^(array_of_ks(i-1)))
假设 array_of_ks 按升序排列,而GaussFilter则根据方差计算滤波器掩模的大小(当然还使用2个1D滤波器),或者您可以在Fourier空间中进行过滤,这对于大图像特别有用,如果方差间隔均匀(不幸的是它们很可能不会是)。

12

虽然有点笨重,但我很惊讶没有人建议使用结构体。您可以通过变量名struct.(var)访问任何结构体字段,其中var可以是任何变量,并将适当地解析。

dict.a = 1;
dict.b = 2;

var = 'a';

display( dict.(var) ); % prints 1

1
如果您将数字用作字段名称,代码就会出现错误:dict.('2'):http://www.mathworks.com/access/helpdesk/help/techdoc/matlab_prog/br04bw6-38.html#br1v5bu-1 - Amro
此外,变量必须是整数:dict.(['k',num2str(1)]) 可以运行,但 dict.(['k',num2str(1.1)]) 会失败,如果值是整数,可以直接使用它们进行索引。否则这个想法很好。 - Jonas
@Amro,@Jonas,你们说得很有道理。如果键是整数,那么您就不需要使用这个技巧(数组更合适)......如果键是任意浮点数,则会更具挑战性,但我会在前缀中加上一个字母,并将“.”替换为“_”。 - Mark Elliot
6
在将字符串添加为字段名称之前,可以通过将其变量化来避免使用结构时出现的问题:dict.(genvarname(['k',num2str(1.1)])) - foglerit

2
MATLAB 2022b新增了dictionary对象。在MATLAB文档中可以找到完整的使用指南,具体位置在语言基础 > 数据类型 > 字典
现在推荐使用dictionary而不是旧的containers.Map。引用containers.Map的文档:

dictionary推荐使用,因为它接受更多的数据类型作为键和值,并提供更好的性能。(自R2022b起)

来自R2022b版本说明
在几乎所有的使用情况下,`dictionary` 的性能比 `containers.Map` 更快。
关于 `containers.Map` 的使用方法,请参考Amro's answer
构建字典可以通过传递具有相同数量条目的键和值数组来实现初始条目的集合:
% From key and value arrays
>> d = dictionary(["a", "b", "c"], [1, 2, 3])
d = 
  dictionary (string ⟼ double) with 3 entries:

    "a" ⟼ 1
    "b" ⟼ 2
    "c" ⟼ 3

或者,初始条目可以作为键值对提供:
% Using Name=Value syntax (string keys only)
>> d = dictionary(a=1, b=2, c=3)  
d = 
  dictionary (string ⟼ double) with 3 entries:

    "a" ⟼ 1
    "b" ⟼ 2
    "c" ⟼ 3

>> squares = dictionary(2, 4, 3, 9, 4, 16)
squares =
  dictionary (double ⟼ double) with 3 entries:
    2 ⟼ 4
    3 ⟼ 9
    4 ⟼ 16

创建一个未配置的字典,您可以使用没有任何输入的dictionary
>> d_unconfigured = dictionary
d_unconfigured =
  dictionary with unset key and value types.

字典将在您分配一个条目后进行配置。
要构建一个具有预配置键和值类型的空字典,您可以使用configureDictionary(R2023b或更高版本):
>> d_empty = configureDictionary("string", "double")
d_empty =
  dictionary (string ⟼ double) with no entries.

查找

单个键:

>> d("a")
ans =
     1

同时查找一个键数组:
>> k = [ "a" "b"
         "b" "c" ];
>> d(k)
ans =
     1     2
     2     3

无效的键查找错误。
>> d("bad key")
Error using  () 
Key not found. 

>> d(123)
Error using  () 
Key not found. 

MATLAB R2023b 引入了lookup函数,它允许您指定一个备用值:
>> d.lookup("a", FallbackValue=nan)
ans =
     1

>> d.lookup("missing", FallbackValue=nan)
ans =
   NaN

任务

>> d("new") = 10
d =
  dictionary (string ⟼ double) with 4 entries:
    "a"   ⟼ 1
    "b"   ⟼ 2
    "c"   ⟼ 3
    "new" ⟼ 10

如果可以进行转换,值将自动转换为值类型。如果无法进行转换,则会发出错误提示。
d("new") = "123"  % Note: string instead of double
d =
  dictionary (string ⟼ double) with 4 entries:
    "a"   ⟼ 1
    "b"   ⟼ 2
    "c"   ⟼ 3
    "new" ⟼ 123

>> d("new") = @sum
Error using  () 
Unable to use 'function_handle' as value for dictionary with 'double' value type.
Caused by:
    Conversion to double from function_handle is not possible

删除

可以通过将一个空数组[]赋值给键来删除它们:

>> d("a") = []
d =
  dictionary (string ⟼ double) with 2 entries:
    "b" ⟼ 2
    "c" ⟼ 3

键的数组也可以在左侧使用,就像在上面的赋值中所看到的那样。

MATLAB 2023b引入了remove函数,其行为与赋值[]完全相同。

>> d.remove("a")
ans =
  dictionary (string ⟼ double) with 2 entries:
    "b" ⟼ 2
    "c" ⟼ 3

尺寸

条目数量:

>> d.numEntries
ans =
     3

提取键/值集合

键和值数组:

>> d.keys
ans = 
  3×1 string array
    "a"
    "b"
    "c"

>> d.values
ans =
     1
     2
     3

条目 表格

>> d.entries
ans =
  3×2 table
    Key    Value
    ___    _____
    "a"      1  
    "b"      2  
    "c"      3  

查询类型配置
查询键和值的类型:
>> [kt, vt] = d.types
kt = 
    "string"
vt = 
    "double"

检查字典是否配置了键和值的类型:
>> d.isConfigured
ans =
  logical
   1

没有任何初始条目的构建的词典是未配置的。
>> d2 = dictionary
d2 =
  dictionary with unset key and value types.

>> d2.isConfigured
ans =
  logical
   0

>> [kt, vt] = d2.types
kt = 
    <missing>
vt = 
    <missing>

未配置的字典在分配条目后立即配置完成。
>> d2("key") = "value"
d2 =
  dictionary (stringstring) with 1 entry:
    "key""value"

>> d2.isConfigured
ans =
  logical
   1

1

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接