Создание структур из элементов массива на основе индекса и значения

ProgramBox

Создание структур из элементов массива на основе индекса и значения

Post author:admin
Запись опубликована:25 февраля, 2023
Post category:Вопросы по программированию

#matlab

Вопрос:

Есть ли более элегантный способ выразить следующий код (например, без явного for-цикла)?

 P = [0.1 0.2 0.3 0.4];
% pre-allocate symbols array of struct
symbols = repmat(struct('probability', 0, 'indices', []), length(P), 1);
for i =1:length(P)
   symbols(i) = struct('probability', P(i), 'indices', i); 
end

PS: Я использую символы для реализации кодирования Хаффмана, если кому-то интересно.

Редактировать: вдохновленный одним из комментариев, я мог бы просто сделать это

 P = [0.1 0.2 0.3 0.4];
symbols = [
    [0.1 1];
    [0.2 2];
    [0.3 3];
    [0.4 4];
];
% access probability:
symbols(i)(1)
% access indices:
symbols(i)(2:end)

Итак

 symbols = [P(:) (1:length(P))']

Редактирование 2: для полноты, вот весь код, который я использую (код Хаффмана)

 function [c,h,w]=huffman(P)

assert(abs(sum(P) - 1) < 10e-6, "Probabilities must sum up to 100%");

% compute entropy
h = sum(P .* (-log2(P)));
% each row corresponds to the probability in P
c = cell(length(P), 1); % codes are represent as numerical vectors for bits

P = sort(P, 'descend');
% Preallocate 'symbols' for each probability
% A symbol is used to represent dummy "fused" probabilities as well
% size(symbols) == 1xlength(P) initially
% IMPORTANT: sort P first descending
symbols = struct('probability', num2cell(P), 'indices', num2cell(1:length(P)));
%symbols = repmat(struct('probability', 0, 'indices', []), length(P), 1);
%for i =1:length(P)
%   symbols(i) = struct('probability', P(i), 'indices', i); 
%end

while length(symbols) > 1
    % select the two lowest probabilities and add them
    % O(n) insert worst case vs log(n) binary search...
    last = symbols(end);
    preLast = symbols(end-1);
    % Build the code words by prepending bits
    c(last.indices) = cellfun(@(x)[0 x], c(last.indices), 'UniformOutput', false);
    c(preLast.indices) = cellfun(@(x)[1 x], c(preLast.indices), 'UniformOutput', false);
    % Insert dummy symbol representing combined probability of the two
    % lowest probabilities
    probSum = last.probability   preLast.probability;
    newSymbol = struct('probability', probSum, 'indices', [last.indices preLast.indices]);
    pos = find([symbols.probability] < probSum, 1);
    % insert dummy symbol and remove the two symbols which belong to it
    symbols = [symbols(1:pos-1) newSymbol symbols(pos:end-2)];
end
assert(length(symbols) == 1 amp;amp; abs(symbols(1).probability - 1) < 10e-6, "Probability of tree root must add up to 100%");
% compute average codeword length
w = sum(cellfun('length', c) .* P(:));

Я думаю, что использовать числовые массивы вместо структур и хранить 0 как «без индекса» — это больше работы, потому что я должен убедиться, что все индексные массивы правильно дополнены нулями, и вызвать find(индексы> 0) перед их использованием. Поэтому я пока это пропущу.

Это примерно в 3 раза быстрее, чем некоторый случайный код, который я нашел в Интернете, так что это не может быть ужасно.

Редактировать 3: на самом деле, это примерно на 40% быстрее, чем huffmandict из набора инструментов коммуникационных систем, так что да, вот так. Либо я что-то упускаю, либо они не заботятся о производительности.

1. Я бы просто придерживался использования P сам по себе. Использование подобной структуры в MATLAB неэффективно.

2. @CrisLuengo P недостаточно хорош, я создаю новые вероятности, добавляя элементы из P, но мне все равно нужно отслеживать исходные элементы из P, которые составляют суммарную вероятность. Вот почему я сохраняю индексы в P, которые делают um суммированной вероятностью. Также я не могу изменить P (чтобы индексы оставались действительными), поэтому я создаю новый массив с вероятностями. Я мог бы использовать массив, первый элемент = вероятность и (2: конец) == индексы.. хорошая идея

3. Я не знал, что массивы индексов должны были расти. Вы можете сделать (2:end) или просто сохранить два массива. Если ваши индексы для каждого элемента P растут с разной скоростью, вы можете использовать нули как «не используемые», или вы можете создать массив ячеек : indices{i}(:) . Но в этом последнем случае вы могли бы также использовать подход struct. В общем, числовые массивы намного эффективнее как по времени, которое требуется интерпретатору для извлечения элемента, так и по объему используемой памяти (поскольку каждый элемент в массиве struct является массивом со своими собственными накладными расходами на заголовок).

4. @CrisLuengo Ах, вы правы, я забыл о росте с разной скоростью, поэтому матрица неудобна. Я не могу передать 0 в качестве индексов, поэтому мне пришлось бы выбрать find(индексы> 0) или около того. Не уверен, что это быстрее. Я опубликую полный код, когда закончу…

Ответ №1:

Как насчет:

 symbols = struct('probability', num2cell(P), 'indices', num2cell(1:length(P)));

или (только Octave, не MATLAB):

 symbols = repmat(struct('probability', 0, 'indices', []), length(P), 1);
[symbols.probability] = num2cell(P){:};
[symbols.indices] = num2cell(1:length(P)){:};

1. Второй синтаксис работает в Octave, но не в MATLAB. Вы не можете этого сделать (){} .

2. Первый делает (почти, размеры меняются местами) то же самое, что и мой ручной цикл, поэтому я, скорее всего, приму его.