作者celestialgod (天)
看板MATLAB
标题Re: [讨论] 简单的计算 想不到暴力解之外的方法
时间Sat Sep 5 11:40:58 2015
%% function rle
% to comput the lengths and values along a vector
function [len, values] = rle(x)
i = [find(x(2:end) ~= x(1:end-1)); length(x)];
len = diff([0; i]);
if nargout > 1
values = x(i);
end
end
%% function inverse_rle
% produce a vector with lengths and coresponding values
function out = inverse_rle(len, values)
res = arrayfun(@(x, y) y*ones(x, 1), len, values, 'UniformOutput', false);
out = cat(1, res{:});
end
%% main
% data generation
N = 10000;
occurPoints = unique(randi(N, 100, 1));
if mod(length(occurPoints), 2) == 1
occurPoints = [occurPoints; N];
end
dat = zeros(N, 1);
for i = 1:2:length(occurPoints)
dat((occurPoints(i)+1):occurPoints(i+1)) = 1;
end
%% data generation - method 2
% len = diff([0; occurPoints; N]);
% values = repmat(0:1, 1, ceil(length(len)/2));
% values = values(1:length(len))';
% v = inverse_rle(len, values);
% isequal(v, dat) % 1
% part 1
[len, values] = rle(dat);
valuesCusum = cumsum(values);
values(values==1) = valuesCusum(values==1);
out_part1 = inverse_rle(len, values);
% part 2
[len, values] = rle(dat);
tmp = values(values == 0);
tmp(len(values==0) < 100) = 1;
values(values == 0) = tmp;
outTmp = inverse_rle(len, values);
[len2, values2] = rle(outTmp);
valuesCusum = cumsum(values2);
values2(values2==1) = valuesCusum(values2==1);
out_part2 = inverse_rle(len2, values2);
% part 2 - method 2 (faster, about 2 times)
[len, values] = rle(dat);
[valuesLen, valuesValues] = rle(values);
tmp = [0; cumsum(valuesLen)];
valuesLenNew = zeros(length(valuesValues), 1);
k = 1;
for i = 1:(length(tmp)-1)
valuesLenNew(i) = sum(len((tmp(i)+1):tmp(i+1)));
end
valuesCusum = cumsum(valuesValues);
valuesValues(valuesValues==1) = valuesCusum(valuesValues==1);
out_part2_2 = inverse_rle(valuesLenNew, valuesValues);
isequal(out_part2, out_part2_2) % 1
第三部分就利用类似第二部分的概念去写吧，当作练习吧XDD
※ 引述《JamesChen ( )》之铭言：
: 问题很简单，分两个部分
: 一串 0 1 数列
: 大致长得像是 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0
: 简单来说 1 代表 A 事件发生 0 代表没有 然後这是每个时间点的纪录
: 所以 A 一旦发生不会只发生 1 个点就结束 一定是一串
: 我想要做的是创一个新的数列 第 N 次 一串 1 变成一串 N
: 以上面的例子来说就是後面 4 个 1 都变成 2
: 我只想到 for loop + if 硬干的方法
: 但实际资料很长 又有好多受试者 感觉很耗时间
: 第二个部份是
: 如果两串 1 之前的 0 少於 200 个 需要把这两串 1 合并 (中间的 0 都当作 1)
: 我一样只想到硬解
: 我猜是小弟我不够熟 Matlab 平常都在用一些自己习惯的 function
: 没有做过类似的事情 但应该都有速解
: 希望高手可以帮个忙
: 甚至提点一下就好
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.205.27.107
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/MATLAB/M.1441424461.A.57D.html
1F：推 JamesChen: 回应超快 感谢... 好神 09/05 11:53
第二部分可以再加速，直接用values跟lens做新的lens跟values
不过这部分要再想一想怎麽做XD (已新增)
2F：推 profyang: 其实c大你这样写以演算法而言也算是暴力法就是...只是 09/05 13:36
3F：→ profyang: 你向量化得漂亮 09/05 13:36
4F：→ profyang: 不过我也想不到如何将演算法变成非暴力法就是...感觉 09/05 13:37
5F：→ profyang: 就ㄧ定要暴力法 09/05 13:37
对我来说这只是一种资料整理 我没有想过要用一个演算法去解决这个问题
资料整理只要有效率就好了拉XDD
况且这个方法 1e6笔、100个change点的资料也只要0.2秒
毕竟我是统计出身...我并不在意是不是暴力，只在乎是否能够整理成我要的资料
演算法就交给其他人做吧XDDDDDD
可能建议原PO标题改成如何加速这段程式，就不需要着眼在是不是暴力法这件事
另外就是原PO可能使用的方式是 如果资料有N笔，有M个change(0->1 or 1->0)的点
那麽for-loop + if 就是 O(N)，我这样计算就只是O(M)
(如果原PO不是一个个算就不是O(N))
就计算来说，我降低了计算的复杂度，而达到加速的功效
根据我自己读过的内容，广义而言，演算法就是一种降低计算复杂度的方法
因此，广义而言，我这也是在提供一种演算法XD
6F：推 profyang: 没啦 因为原原PO说他不会非暴力法 让我直觉他想改进演 09/05 13:55
7F：→ profyang: 算法 但看来他应该只是要比loop快的方法 那对matlab而 09/05 13:55
8F：→ profyang: 言当然就是向量化了 09/05 13:55
我觉得我太认真了 哈
9F：推 profyang: 不是喔~以part1来说 你的O(N)的部分等於是在cumsum中 09/05 14:24
cumsum那里也是O(M)才对
因为出来的值是change point的值
10F：→ profyang: 你指的O(M)是在後面的values(values==1)中对吧? 这个其 09/05 14:25
那里应该也是O(M)
11F：→ profyang: 实也还是matlab内建一个个元素去search吧...所以应该还 09/05 14:26
12F：→ profyang: 是O(N)才对? 09/05 14:26
你说的是rle的find吗？那部分确实是O(N)
13F：→ profyang: 等下我是搞错什麽 cumsum不就是把一个个元素叠加起来? 09/05 14:28
14F：→ profyang: 这样应该是O(N)阿~然後values(values==1)的部分也是一个 09/05 14:28
15F：→ profyang: 个元素去看你values是否=1 是的话就回传index给你 这样 09/05 14:29
可能有误会 cumsum确实是O(length(input))
但是我这里的values 只会有M个值 所以我写O(M)
N是指原本的资料长度
16F：→ profyang: 还是O(N)阿~ 也就是matlab内建这功能还是有扫个N次的for 09/05 14:29
17F：推 profyang: 确实有误会 你的O(N)应该在rle里面就做完了 09/05 14:32
对，我的O(N)在rle就做完了
18F：→ profyang: sorry我没细看XD 不过这样复杂度就还是O(N) 09/05 14:32
是阿(茶，我想错了
所以我还是没有降低计算的复杂度QQ
※ 编辑: celestialgod (123.205.27.107), 09/05/2015 14:35:47
19F：推 profyang: 没差 matlab就是向量化就快 09/05 15:23