Повторите копии элементов массива:Декодирование длин серий в MATLAB

Question

Я пытаюсь вставить несколько значений в массив, используя массив «значений» и массив «счетчик».Например, если:

a=[1,3,2,5]
b=[2,2,1,3]

Мне нужен вывод какой-то функции

c=somefunction(a,b)

быть

c=[1,1,3,3,2,5,5,5]

Где a(1) повторяется b(1) количество раз, a(2) повторяется b(2) раз и т.д.

Есть ли в MATLAB встроенная функция, которая делает это?Я бы хотел избежать использования цикла for, если это возможно.Я пробовал варианты «repmat()» и «kron()», но безрезультатно.

Это в основном Run-length encoding.

Answer 1

Постановка задачи

У нас есть множество ценностей, vals и runlengths, runlens:

vals     = [1,3,2,5]
runlens  = [2,2,1,3]

Нам нужно повторить каждый элемент в vals раз каждый соответствующий элемент в runlens. Анкет Таким образом, окончательный результат будет:

output = [1,1,3,3,2,5,5,5]

Проспективный подход

Одним из самых быстрых инструментов с Matlab является cumsum и очень полезен при работе с векторизационными проблемами, которые работают над нерегулярными моделями. В заявленной проблеме нерегулярность сопровождается различными элементами в runlens.

Теперь, чтобы использовать cumsum, нам нужно сделать две вещи здесь: инициализировать массив zeros и поместите «соответствующие» значения в «ключевых» позициях на массиве нулей, так что после »cumsum"Применяется, мы получим окончательный набор повторяющихся vals из runlens времена

Шаги: Давайте по числу вышеупомянутых шагов, чтобы дать проспективному подходу более легкую перспективу:

1) Инициализировать массив нулей: какая должна быть длина? Поскольку мы повторяем runlens раз длина массива нулей должна быть суммированием всех runlens.

2) Найти позиции/индексы ключей: теперь эти ключевые положения являются местами вдоль массива нулей, где каждый элемент из vals начать повторять. Таким образом, для runlens = [2,2,1,3], ключевые позиции, нанесенные на массив нулей, будут:

[X 0 X 0 X X 0 0] % where X's are those key positions.

3) Найти соответствующие значения: последний гвоздь, который должен быть забит перед использованием cumsum было бы помещать «соответствующие» значения в эти ключевые позиции. Теперь, так как мы будем делать cumsum Вскоре, если вы думаете внимательно, вам понадобится differentiated версия values с diff, чтобы cumsum На тех, которые будут вернуть наше values. Анкет Поскольку эти дифференцированные значения будут размещены на массиве нулей в местах, разделенных runlens расстояния, после использования cumsum У нас будет каждый vals Элемент повторяется runlens раз как конечный результат.

Код решения

Вот реализация, сшивая все вышеперечисленные шаги -

% Calculate cumsumed values of runLengths. 
% We would need this to initialize zeros array and find key positions later on.
clens = cumsum(runlens)

% Initalize zeros array
array = zeros(1,(clens(end)))

% Find key positions/indices
key_pos = [1 clens(1:end-1)+1]

% Find appropriate values
app_vals = diff([0 vals])

% Map app_values at key_pos on array
array(pos) = app_vals

% cumsum array for final output
output = cumsum(array)

Предварительное распределение взлома

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

array(clens(end)) = 0; % instead of array = zeros(1,(clens(end)))

Завершение: код функции

Чтобы завершить все, у нас будет компактный функциональный код для достижения этой декодировании длины длиной, как это -

function out = rle_cumsum_diff(vals,runlens)
clens = cumsum(runlens);
idx(clens(end))=0;
idx([1 clens(1:end-1)+1]) = diff([0 vals]);
out = cumsum(idx);
return;

Сравнительный анализ

Код сравнительного анализа

Следующим перечислен код сравнения времени выполнения и ускорения для указанного cumsum+diff подход в этом посте к Другой cumsum-only Основанный подход на MATLAB 2014B-

datasizes = [reshape(linspace(10,70,4).'*10.^(0:4),1,[]) 10^6 2*10^6]; %
fcns = {'rld_cumsum','rld_cumsum_diff'}; % approaches to be benchmarked

for k1 = 1:numel(datasizes)
    n = datasizes(k1); % Create random inputs
    vals = randi(200,1,n);
    runs = [5000 randi(200,1,n-1)]; % 5000 acts as an aberration
    for k2 = 1:numel(fcns) % Time approaches  
        tsec(k2,k1) = timeit(@() feval(fcns{k2}, vals,runs), 1);
    end
end

figure,      % Plot runtimes
loglog(datasizes,tsec(1,:),'-bo'), hold on
loglog(datasizes,tsec(2,:),'-k+')
set(gca,'xgrid','on'),set(gca,'ygrid','on'),
xlabel('Datasize ->'), ylabel('Runtimes (s)')
legend(upper(strrep(fcns,'_',' '))),title('Runtime Plot')

figure,      % Plot speedups
semilogx(datasizes,tsec(1,:)./tsec(2,:),'-rx')        
set(gca,'ygrid','on'), xlabel('Datasize ->')
legend('Speedup(x) with cumsum+diff over cumsum-only'),title('Speedup Plot')

Связанный код функции для rld_cumsum.m:

function out = rld_cumsum(vals,runlens)
index = zeros(1,sum(runlens));
index([1 cumsum(runlens(1:end-1))+1]) = 1;
out = vals(cumsum(index));
return;

Участки времени выполнения и ускорения

Выводы

Предлагаемый подход, похоже, дает нам заметное ускорение над cumsum-only подход, о котором о 3X!

Почему этот новый cumsum+diff Основанный на основе подхода лучше, чем в предыдущем cumsum-only подход?

Ну, суть причины заключается на последнем этапе cumsum-only подход, который должен составить карту «смягченных» значений в vals. Анкет В новом cumsum+diff На основе подход мы делаем diff(vals) вместо этого Matlab только обрабатывает n Элементы (где n - количество длиной пробега) по сравнению с отображением sum(runLengths) количество элементов для cumsum-only подход и это число должно быть во много раз больше, чем n И, следовательно, заметное ускорение с этим новым подходом!

Answer 2

Тесты

Обновлено для R2015b.: repelem теперь самый быстрый для всех размеров данных.

---

Протестированные функции:

1. Встроенный MATLAB repelem функция, добавленная в R2015a
2. Гновице cumsum решение (rld_cumsum)
3. Дивакара cumsum+diff решение (rld_cumsum_diff)
4. Кнедлсепп accumarray решение (knedlsepp5cumsumaccumarray) от эта почта
5. Наивная реализация на основе цикла (naive_jit_test.m), чтобы протестировать JIT-компилятор

Результаты test_rld.m на R2015б:

Старый временной график с использованием R2015а здесь.

Выводы:

• repelem всегда самый быстрый примерно в 2 раза.
• rld_cumsum_diff постоянно быстрее, чем rld_cumsum.
• repelem самый быстрый для небольших размеров данных (менее 300-500 элементов)
• rld_cumsum_diff становится значительно быстрее, чем repelem около 5 000 элементов
• repelem становится медленнее, чем rld_cumsum где-то между 30 000 и 300 000 элементов
• rld_cumsum имеет примерно такую ​​же производительность, как и knedlsepp5cumsumaccumarray
• naive_jit_test.m имеет почти постоянную скорость и находится на одном уровне с rld_cumsum и knedlsepp5cumsumaccumarray для меньших размеров, немного быстрее для больших размеров

График старой ставки с использованием R2015а здесь.

Заключение

Использовать repelem ниже примерно 5 000 элементов и cumsum+diff решение выше.

Answer 3

Я знаю встроенной функции, но вот одно решение:

index = zeros(1,sum(b));
index([1 cumsum(b(1:end-1))+1]) = 1;
c = a(cumsum(index));

Объяснение:

Вектор нулей сначала создан из той же длины, что и выходной массив (т.е. сумма всех репликаций в b) Затем в первом элементе помещаются в первый элемент, и каждый последующий элемент, представляющий, где начало новой последовательности значений будет в выходе. Кумулятивная сумма вектора index затем можно использовать для индексации в a, воспроизводить каждое значение желаемое количество раз.

Ради ясности, это то, на что выглядят различные векторы для ценностей a а также b дано в вопросе:

        index = [1 0 1 0 1 1 0 0]
cumsum(index) = [1 1 2 2 3 4 4 4]
            c = [1 1 3 3 2 5 5 5]

---

РЕДАКТИРОВАТЬ: Ради полноты, там является Еще одна альтернатива с использованием Arrayfun, но, похоже, это займет от 20 до 100 раз, чем приведенное выше решение с векторами до 10 000 элементов длиной:

c = arrayfun(@(x,y) x.*ones(1,y),a,b,'UniformOutput',false);
c = [c{:}];

Answer 4

Наконец -то есть (как R2015A) встроенная и задокументированная функция для этого, repelem. Анкет Следующий синтаксис, где второй аргумент - вектор, здесь актуален:

W = repelem(V,N), с вектором V и вектор N, создает вектор W где элемент V(i) повторяется N(i) времена

Или повернуть другим способом, «каждый элемент N указывает количество раз, чтобы повторить соответствующий элемент V."

Пример:

>> a=[1,3,2,5]
a =
     1     3     2     5
>> b=[2,2,1,3]
b =
     2     2     1     3
>> repelem(a,b)
ans =
     1     1     3     3     2     5     5     5

Answer 5

Проблемы с производительностью в встроенном Matlab repelem были исправлены с R2015B. Я запустил test_rld.m Программа из Post ChappJC в R2015B, и repelem теперь быстрее, чем другие алгоритмы примерно к фактору 2: