Повторяющиеся числа MATLAB на основе вектора длин

Существует ли векторный способ сделать следующее? (показано на примере):

input_lengths = [ 1 1 1 4       3     2   1 ]
result =        [ 1 2 3 4 4 4 4 5 5 5 6 6 7 ]

Я выделил длину ввода, поэтому легко понять, как получается результат.

Результирующий вектор имеет длину: sum(lengths). В настоящее время я вычисляю result с помощью следующего цикла:

result = ones(1, sum(input_lengths ));
counter = 1;
for i = 1:length(input_lengths)
    start_index = counter;
    end_index = counter + input_lengths (i) - 1;

    result(start_index:end_index) = i;
    counter = end_index + 1;
end

EDIT:

Я также могу сделать это с помощью arrayfun (хотя это не совсем векторная функция)

cell_result = arrayfun(@(x) repmat(x, 1, input_lengths(x)), 1:length(input_lengths), 'UniformOutput', false);
cell_result : {[1], [2], [3], [4 4 4 4], [5 5 5], [6 6], [7]}

result = [cell_result{:}];
result : [ 1 2 3 4 4 4 4 5 5 5 6 6 7 ]

Ответ 1

result = zeros(1,sum(input_lengths));
result(cumsum([1 input_lengths(1:end-1)])) = 1;
result = cumsum(result);

Это должно быть довольно быстро. И использование памяти минимально возможно.

Оптимизированная версия вышеуказанного кода, благодаря Bentoy13 (см. его очень подробный бенчмаркинг):

result = zeros(1,sum(input_lengths));
result(1) = 1;
result(1+cumsum(input_lengths(1:end-1))) = 1;
result = cumsum(result);

Ответ 2

Полностью векторизованная версия:

selector=bsxfun(@le,[1:max(input_lengths)]',input_lengths);
V=repmat([1:size(selector,2)],size(selector,1),1);
result=V(selector);

Нижняя сторона - это использование памяти O (numel (input_lengths) * max (input_lengths))

Ответ 3

Больше комментариев, чем что-либо, но я сделал несколько тестов. Я пробовал цикл for и arrayfun, и я проверил ваш цикл for и arrayfun. Ваш цикл for был самым быстрым. Я думаю, это потому, что это просто и позволяет компиляции JIT максимально оптимизировать. Я использую Matlab, октава может отличаться.

И время:

Solution:     With JIT   Without JIT  
Sam for       0.74       1.22    
Sam arrayfun  2.85       2.85    
My for        0.62       2.57    
My arrayfun   1.27       3.81    
Divakar       0.26       0.28    
Bentoy        0.07       0.06    
Daniel        0.15       0.16
Luis Mendo    0.07       0.06

Итак, код Bentoy очень быстрый, а Луис Мендо - почти точно такая же скорость. И я слишком полагаюсь на JIT!

И код для моих попыток

clc,clear
input_lengths = randi(20,[1 10000]);

% My for loop
tic()
C=cumsum(input_lengths);
D=diff(C);
results=zeros(1,C(end));
results(1,1:C(1))=1;
for i=2:length(input_lengths)
    results(1,C(i-1)+1:C(i))=i*ones(1,D(i-1));
end
toc()

tic()
A=arrayfun(@(i) i*ones(1,input_lengths(i)),1:length(input_lengths),'UniformOutput',false);
R=[A{:}];
toc()

Ответ 4

Контрольный показатель всех решений

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

Я не буду публиковать код script здесь, это довольно длинный и очень неинтересный. Процедура эталонного теста состоит в том, чтобы запускать каждое решение для набора различных длин входных векторов: 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000, 100000, 200000, 500000, 1000000. Для каждой входной длины я создал случайный входной вектор, основанный на законе Пуассона с параметром 0.8 (чтобы избежать больших значений):

input_lengths = round(-log(1-rand(1,ILen(i)))/poisson_alpha)+1;

Наконец, я усредняю время вычисления более 100 прогонов на длину ввода.

Я запустил script на своем ноутбуке (ядро I7) с помощью Matlab R2013b; JIT активирован.

И вот графические результаты (извините, цветные строки), в шкале логарифмической шкалы (ось x: длина ввода, ось y: время вычисления в секундах):

Итак, Луис Мендо - явный победитель, поздравляю!

Для тех, кто хочет получить числовые результаты и/или хочет их переустановить, здесь они (вырезают таблицу на 2 части и приближаются к 3 цифрам для лучшего отображения):

N                   10          20          50          100         200         500         1e+03       2e+03
-------------------------------------------------------------------------------------------------------------
OP for-loop       8.02e-05    0.000133    0.00029     0.00036     0.000581    0.00137     0.00248     0.00542 
OP arrayfun       0.00072     0.00117     0.00255     0.00326     0.00514     0.0124      0.0222      0.047
Daniel              0.000132    0.000132    0.000148    0.000118    0.000126    0.000325    0.000397    0.000651
Divakar             0.00012     0.000114    0.000132    0.000106    0.000115    0.000292    0.000367    0.000641
David for-loop    9.15e-05    0.000149    0.000322    0.00041     0.000654    0.00157     0.00275     0.00622
David arrayfun    0.00052     0.000761    0.00152     0.00188     0.0029      0.00689     0.0122      0.0272
Luis Mendo          4.15e-05    4.37e-05    4.66e-05    3.49e-05    3.36e-05    4.37e-05    5.87e-05    0.000108
Bentoy13 cumsum   0.000104    0.000107    0.000111    7.9e-05     7.19e-05    8.69e-05    0.000102    0.000165
Bentoy13 sparse   8.9e-05     8.82e-05    9.23e-05    6.78e-05    6.44e-05    8.61e-05    0.000114    0.0002
Luis Mendo optim. 3.99e-05    3.96e-05    4.08e-05    4.3e-05     4.61e-05    5.86e-05    7.66e-05    0.000111

N                   5e+03       1e+04       2e+04       5e+04       1e+05       2e+05       5e+05       1e+06
-------------------------------------------------------------------------------------------------------------
OP for-loop       0.0138      0.0278      0.0588      0.16        0.264       0.525       1.35        2.73
OP arrayfun       0.118       0.239       0.533       1.46        2.42        4.83        12.2        24.8
Daniel              0.00105     0.0021      0.00461     0.0138      0.0242      0.0504      0.126       0.264
Divakar             0.00127     0.00284     0.00655     0.0203      0.0335      0.0684      0.185       0.396
David for-loop    0.015       0.0286      0.065       0.175       0.3         0.605       1.56        3.16
David arrayfun    0.0668      0.129       0.299       0.803       1.33        2.64        6.76        13.6
Luis Mendo          0.000236    0.000446    0.000863    0.00221     0.0049      0.0118      0.0299      0.0637
Bentoy13 cumsum   0.000318    0.000638    0.00107     0.00261     0.00498     0.0114      0.0283      0.0526
Bentoy13 sparse   0.000414    0.000774    0.00148     0.00451     0.00814     0.0191      0.0441      0.0877
Luis Mendo optim. 0.000224    0.000413    0.000754    0.00207     0.00353     0.00832     0.0216      0.0441

Хорошо, я добавил еще одно решение в список... Я не мог помешать оптимизации оптимального решения Luis Mendo. Нет никаких оснований для этого, это всего лишь вариант от Луиса Мендо, я объясню это позже.

Очевидно, что решения с использованием arrayfun очень трудоемки. Решения, использующие явный цикл for, являются более быстрыми, но все же медленными по сравнению с другими решениями. Итак, да, векторизация по-прежнему является основным вариантом для оптимизации Matlab script.

Так как я видел большую дисперсию в вычислительные времена самых быстрых решений, особенно при длинах входных данных от 100 до 10000, я решил более точно провести сравнение. Таким образом, я поставил самые медленные друг от друга (извините) и переделал контрольный показатель по 6 другим решениям, которые работают намного быстрее. Второй контрольный ориентир по этому сокращенному списку решений идентичен, за исключением того, что у меня в среднем более 1000 прогонов.

(Нет таблицы здесь, если вы действительно этого не хотите, это те же номера, что и раньше)

Как было отмечено, решение Daniel немного быстрее, чем Divavar, потому что кажется, что использование bsxfun с @times медленнее, чем с использованием repmat. Тем не менее, они в 10 раз быстрее, чем решения для петли: ясно, что векторизация в Matlab - это хорошо.

Решения Bentoy13 и Luis Mendo очень близки; первый использует больше инструкций, но второй использует дополнительное выделение при конкатенации 1 в cumsum(input_lengths(1:end-1)). И поэтому мы видим, что решение Bentoy13 имеет тенденцию быть немного быстрее при больших входных длинах (выше 5.10 ^ 5), потому что нет дополнительного распределения. Исходя из этого соображения, я сделал оптимизированное решение, в котором нет дополнительного распределения; вот код (Луис Мендо может поставить это в свой ответ, если он хочет:)):

result = zeros(1,sum(input_lengths));
result(1) = 1;
result(1+cumsum(input_lengths(1:end-1))) = 1;
result = cumsum(result);

Любые комментарии для улучшения приветствуются.

Ответ 5

Это небольшой вариант ответа @Daniel . Суть этого решения основана на этом решении. Теперь этот метод избегает repmat, поэтому, таким образом, он может быть немного "более векторным". Здесь код -

selector=bsxfun(@le,[1:max(input_lengths)]',input_lengths); %//'
V = bsxfun(@times,selector,1:numel(input_lengths)); 
result = V(V~=0)

Для всех отчаянных однострочных для поиска людей

result = nonzeros(bsxfun(@times,bsxfun(@le,[1:max(input_lengths)]',input_lengths),1:numel(input_lengths)))

Ответ 6

Я ищу элегантное решение, и я думаю, решение David - хорошее начало. Что я имею в виду, так это то, что можно сгенерировать индексы, где добавить один из предыдущего элемента.

Для этого, если мы вычислим cumsum входного вектора, получим:

cumsum(input_lengths)
ans = 1     2     3     7    10    12    13

Это индексы концов последовательностей одинаковых чисел. Это не то, что мы хотим, поэтому мы дважды переводим вектор, чтобы получить начало:

fliplr(sum(input_lengths)+1-cumsum(fliplr(input_lengths)))
ans = 1     2     3     4     8    11    13

Вот трюк. Вы переворачиваете вектор, копируете его, чтобы получить концы перевернутого вектора, а затем откидывайте назад; но вы должны вычесть вектор из общей длины выходного вектора (+1, потому что индекс начинается с 1), потому что на перевернутом векторе применяется cumsum.

Как только вы это сделали, это очень просто, вам просто нужно положить 1 на вычисленные индексы и 0 в другом месте и cumsum it:

idx_begs = fliplr(sum(input_lengths)+1-cumsum(fliplr(input_lengths)));
result = zeros(1,sum(input_lengths));
result(idx_begs) = 1;
result = cumsum(result);

ИЗМЕНИТЬ

Во-первых, пожалуйста, взгляните на решение Luis Mendo, оно очень близко к моему, но более простое и немного быстрее (я не буду редактировать мои даже это очень близко). Я думаю, что в этот день это самое быстрое решение из всех.

Во-вторых, глядя на другие решения, я составил еще один лайнер, немного отличающийся от моего первоначального решения и от другого однострочного изображения. Хорошо, это будет не очень читаемо, поэтому сделайте вдох:

result = cumsum( full(sparse(cumsum([1,input_lengths(1:end-1)]), ...
ones(1,length(input_lengths)), 1, sum(input_lengths),1)) );

Я разрезал его на две строки. Хорошо, теперь объясните это.

Аналогичная часть состоит в том, чтобы построить массив индексов, где нужно увеличить значение текущего элемента. Для этого я использую решение Луиса Мендо. Чтобы построить в одной строке вектор решения, я использую здесь тот факт, что на самом деле это редкое представление двоичного вектора, то, что мы будем кончать в самом конце. Этот разреженный вектор строится с использованием нашего вычисленного вектора индекса в виде позиций x, вектора 1 в виде y-позиций и 1 в качестве значения для размещения в этих местах. Четвертый аргумент дается для точного общего размера вектора (важно, если последний элемент input_lengths не равен 1). Затем мы получаем полное представление этого разреженного вектора (иначе результат будет разреженным вектором без пустого элемента), и мы можем cumsum.

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