Хеш-таблицы в MATLAB

92

Поддерживает ли MATLAB хеш-таблицы?


Некоторый фон

Я работаю над проблемой в Matlab, которая требует представления изображения в масштабном пространстве. Для этого я создаю фильтр 2-D Gaussian с дисперсией sigma*s^kдля kв некотором диапазоне., А затем я использую каждый в свою очередь , для фильтрации изображения. Теперь мне нужно какое-то отображение kотфильтрованного изображения.

Если бы kвсегда было целое число, я бы просто создал трехмерный массив, такой что:

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

Однако kэто не обязательно целое число, поэтому я не могу этого сделать. Я думал о том, чтобы сохранить такой массив ks, чтобы:

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

На первый взгляд это кажется довольно хорошим, за исключением того, что я буду выполнять этот поиск несколько тысяч раз примерно с 20 или 30 значениями k, и я боюсь, что это повредит производительности.

Интересно, не лучше ли мне было бы делать это с какой-то хэш-таблицей, чтобы у меня было время поиска, равное O (1) вместо O (n).


Теперь я знаю, что мне не следует проводить оптимизацию преждевременно, и у меня может вообще не быть этой проблемы, но помните, что это всего лишь фон, и могут быть случаи, когда это действительно лучшее решение, независимо от того, лучшее решение моей проблемы.

Натан Феллман
источник

Ответы:

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 одномерных фильтра), или вы можете фильтровать в пространстве Фурье, что особенно полезно для больших изображений и если дисперсии равномерно (что, к сожалению, не так).

Йонас
источник
120

Рассмотрите возможность использования класса карты MATLAB: container.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
Containers.Map был добавлен в MATLAB 7.7 (R2008b), см. Mathworks.com/access/helpdesk/help/techdoc/rn/brqyzax-1.html . Новым в R2010a является конструктор для указания типа ключа, а также типа значения. M = контейнеры.Map ('KeyType', kType, 'ValueType', vType)
zellus
@Jonas: Я не использовал их широко, было бы интересно посмотреть, как они сравниваются с использованием логической индексации для поиска ..
Амро
9
@ zellus, @ amro: Разве не раздражает отсутствие истории команд в Matlab?
Джонас
4
Поиск: rainfallMap («Янв»); Назначьте: rainfallMap ('Jan') = 'ноль'; Проверьте: rainfallMap.values; rainfallMap.keys; rainfallMap.size; Проверить ключ: rainfallMap.isKey ('Сегодня');
Евгений Сергеев
26

Новый класс container.Map в Matlab R2008b (7.7) - это уменьшенная версия интерфейса java.util.Map для Matlab . Он имеет дополнительное преимущество - бесшовную интеграцию со всеми типами Matlab (например, Java Maps не может обрабатывать структуры Matlab ), а также возможность, начиная с Matlab 7.10 (R2010a), указывать типы данных .

Серьезные реализации Matlab, требующие карт / словарей «ключ-значение», должны по-прежнему использовать классы Java Map ( java.util.EnumMap , HashMap , TreeMap , LinkedHashMap или Hashtable ), чтобы получить доступ к их более широким функциям, если не к производительности. Версии Matlab до R2008b в любом случае не имеют реальной альтернативы и должны использовать классы Java.

Потенциальным ограничением использования коллекций Java является их неспособность содержать непримитивные типы Matlab, такие как структуры. Чтобы преодолеть это, либо преобразуйте типы с понижением (например, используя struct2cell или программно), либо создайте отдельный объект Java, который будет содержать вашу информацию и хранить этот объект в коллекции Java.

Вам также может быть интересно изучить объектно-ориентированную (основанную на классах) реализацию Hashtable на чистом Matlab, которая доступна в File Exchange .

Яир Альтман
источник
1
Еще одна реализация на основе классов Matlab, опубликованная сегодня: mathworks.com/matlabcentral/fileexchange/28586
Яир Альтман,
19

Вы можете использовать для этого java.

В Matlab:

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

Но вам нужно будет провести некоторое профилирование, чтобы увидеть, дает ли он вам прирост скорости, я думаю ...

тауран
источник
12

Это немного запутанно, но я удивлен, что никто не предложил использовать структуры. Вы можете получить доступ к любому полю структуры по имени переменной, так как struct.(var)where varможет быть любой переменной и будет разрешено соответствующим образом.

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

var = 'a';

display( dict.(var) ); % prints 1
Марк Эллиот
источник
1
Он сломается, если вы используете число в качестве имени поляdict.('2') :: mathworks.com/access/helpdesk/help/techdoc/matlab_prog/…
Амро
Кроме того, переменные должны быть целыми числами: dict.(['k',num2str(1)])работает, но dict.(['k',num2str(1.1)])не работает, и если значения являются целыми числами, вы можете использовать их для непосредственного индексирования. В противном случае это хорошая идея.
Jonas
@Amro, @Jonas, справедливо, если бы ключи были целыми числами, вам не нужно было бы использовать этот трюк (массив будет иметь больше смысла) ... если ключи являются произвольными числами с плавающей запятой, это немного сложнее, но я «d префикс с буквой и заменить .с _.
Марк Эллиот,
6
Вышеупомянутых проблем с использованием структур можно избежать, dict.(genvarname(['k',num2str(1.1)]))
варьируя
1

Вы также можете воспользоваться новым типом «Таблица». Вы можете хранить разные типы данных и очень легко получать из них статистику. См. Http://www.mathworks.com/help/matlab/tables.html для получения дополнительной информации.

Лэй Чжан
источник