Tabelas de hash no MATLAB

92

O MATLAB tem suporte para tabelas de hash?


Alguns antecedentes

Estou trabalhando em um problema no Matlab que requer uma representação de escala no espaço de uma imagem. Para fazer isso eu criar um filtro 2-D Gaussian com variância sigma*s^kpara kem algum intervalo., E então eu uso um de cada vez para filtrar a imagem. Agora, quero algum tipo de mapeamento da kimagem filtrada.

Se kfosse sempre um número inteiro, eu simplesmente criaria uma matriz 3D de modo que:

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

No entanto, knão é necessariamente um número inteiro, então não posso fazer isso. O que pensei em fazer foi manter uma série de ks tais que:

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

O que parece muito bom à primeira vista, exceto que estarei fazendo essa pesquisa potencialmente alguns milhares de vezes com cerca de 20 ou 30 valores de k, e temo que isso prejudique o desempenho.

Eu me pergunto se eu não ficaria melhor fazendo isso com uma tabela de hash de algum tipo, de modo que eu teria um tempo de pesquisa que é O (1) em vez de O (n).


Bem, eu sei que não devo otimizar prematuramente e posso não ter esse problema, mas lembre-se, isso é apenas o pano de fundo, e pode haver casos em que esta é realmente a melhor solução, independentemente de ser o melhor solução para o meu problema.

Nathan Fellman
fonte

Respostas:

14

O Matlab não oferece suporte para hashtables. EDITAR Até r2010a, isto é; veja a resposta de @Amro .

Para agilizar suas pesquisas, você pode descartar o finde usar INDEXAÇÃO LÓGICA .

arr{array_of_ks==k} = <image filtered with k-th Gaussian>

ou

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

No entanto, em toda a minha experiência com o Matlab, nunca vi uma pesquisa ser um gargalo.


Para acelerar seu problema específico, sugiro usar a filtragem incremental

arr{i} = GaussFilter(arr{i-1},sigma*s^(array_of_ks(i)) - sigma*s^(array_of_ks(i-1)))

assumindo que array_of_ksestá classificado em ordem crescente, e GaussFilter calcula o tamanho da máscara de filtro com base na variância (e usa, 2 filtros 1D, é claro), ou você pode filtrar no Espaço de Fourier, que é especialmente útil para imagens grandes e se as variações são espaçados uniformemente (o que provavelmente não são).

Jonas
fonte
120

Considere o uso da classe de mapa do MATLAB: containers.Map . Aqui está uma breve visão geral:

  • Criação:

    >> 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
  • Olho para cima:

    x = rainfallMap('Jan');
  • Atribuir:

    rainfallMap('Jan') = 0;
  • Adicionar:

    rainfallMap('Total') = 999;
  • Remover:

    rainfallMap.remove('Total')
  • Inspecionar:

    values = rainfallMap.values;
    keys = rainfallMap.keys;
    sz = rainfallMap.size;
  • Verificar chave:

    if rainfallMap.isKey('Today')
        ...
    end
Amro
fonte
7
Nossa, eu não sabia disso! +1. Você sabe se eles são muito mais rápidos do que a indexação lógica?
Jonas
3
Containers.Map foi adicionado no MATLAB 7.7 (R2008b) consulte mathworks.com/access/helpdesk/help/techdoc/rn/brqyzax-1.html . Uma novidade no R2010a é um construtor para especificar o tipo de chave, bem como o tipo de valor. M = containers.Map ('KeyType', kType, 'ValueType', vType)
zellus
@Jonas: Eu não os usei extensivamente, seria interessante ver como eles se comparam ao uso de indexação lógica para pesquisa.
Amro
9
@ zellus, @ amro: Não é irritante como não há histórico dos comandos no Matlab?
Jonas
4
Lookup: rainMap ('Jan'); Atribuir: rainMap ('Jan') = 'zero'; Inspecione: rainMap.values; rainMap.keys; rainMap.size; Verifique a chave: chuvaMap.isKey ('Hoje');
Evgeni Sergeev
26

A nova classe containers.Map do Matlab R2008b (7.7) é uma versão reduzida do Matlab da interface java.util.Map . Ele tem o benefício adicional de integração contínua com todos os tipos de Matlab ( Java Maps não pode lidar com structs Matlab, por exemplo), bem como a capacidade desde o Matlab 7.10 (R2010a) de especificar tipos de dados .

Implementações sério Matlab que requerem mapas de valor-chave / dicionários ainda deve usar classes Mapa de Java ( java.util.EnumMap , HashMap , TreeMap , LinkedHashMap ou Hashtable ) para ter acesso à sua funcionalidade maior não se desempenho. As versões do Matlab anteriores ao R2008b não têm alternativa real em nenhum caso e devem usar as classes Java.

Uma limitação potencial do uso de coleções Java é sua incapacidade de conter tipos Matlab não primitivos, como structs. Para superar isso, faça down-converter dos tipos (por exemplo, usando struct2cell ou programaticamente) ou crie um objeto Java separado que manterá suas informações e armazenará esse objeto na coleção Java.

Você também pode estar interessado em examinar uma implementação de Hashtable orientada a objeto puro do Matlab (baseada em classe), que está disponível no File Exchange .

Yair Altman
fonte
1
Outra implementação baseada em classe Matlab postada hoje: mathworks.com/matlabcentral/fileexchange/28586
Yair Altman
19

Você pode usar java para isso.

No matlab:

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

Mas você teria que fazer alguns perfis para ver se isso lhe dá um ganho de velocidade, eu acho ...

taurano
fonte
12

É um pouco complicado, mas estou surpreso que ninguém tenha sugerido o uso de structs. Você pode acessar qualquer campo de estrutura por nome de variável, como struct.(var)onde varpode ser qualquer variável e resolverá de forma apropriada.

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

var = 'a';

display( dict.(var) ); % prints 1
Mark Elliot
fonte
1
Seria interrompido se você usasse um número como nome de campo dict.('2'):: mathworks.com/access/helpdesk/help/techdoc/matlab_prog/…
Amro
Além disso, as variáveis ​​devem ser inteiros: dict.(['k',num2str(1)])funciona, mas dict.(['k',num2str(1.1)])falha, e se os valores forem inteiros, você pode usá-los para indexar diretamente. Caso contrário, é uma boa ideia.
Jonas
@Amro, @Jonas, pontos justos, se as chaves fossem inteiras você não precisaria usar este truque (um array faria mais sentido) ... se as chaves são flutuantes arbitrários, isso é um pouco mais desafiador, mas eu prefixaria com uma letra e substituiria .por um _.
Mark Elliot
6
Os problemas acima com o uso de estruturas podem ser evitados variabilizando as strings antes de adicionar como nomes de campo:dict.(genvarname(['k',num2str(1.1)]))
foglerit
1

Você também pode aproveitar as vantagens do novo tipo "Mesa". Você pode armazenar diferentes tipos de dados e obter estatísticas com facilidade. Consulte http://www.mathworks.com/help/matlab/tables.html para obter mais informações.

Lei Zhang
fonte