Повторите копии элементов массива:Декодирование длин серий в MATLAB
-
21-09-2019 - |
Вопрос
Я пытаюсь вставить несколько значений в массив, используя массив «значений» и массив «счетчик».Например, если:
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
.
Решение
Постановка задачи
У нас есть множество ценностей, 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
И, следовательно, заметное ускорение с этим новым подходом!
Другие советы
Тесты
Обновлено для R2015b.: repelem
теперь самый быстрый для всех размеров данных.
Протестированные функции:
- Встроенный MATLAB
repelem
функция, добавленная в R2015a - Гновице
cumsum
решение (rld_cumsum
) - Дивакара
cumsum
+diff
решение (rld_cumsum_diff
) - Кнедлсепп
accumarray
решение (knedlsepp5cumsumaccumarray
) от эта почта - Наивная реализация на основе цикла (
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
решение выше
Я знаю встроенной функции, но вот одно решение:
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{:}];
Наконец -то есть (как 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
Проблемы с производительностью в встроенном Matlab repelem
были исправлены с R2015B. Я запустил test_rld.m
Программа из Post ChappJC в R2015B, и repelem
теперь быстрее, чем другие алгоритмы примерно к фактору 2: