Loop erasing random walk

10 次查看（过去 30 天）
Mehmet Candemir
Mehmet Candemir 2011-5-25
Hi, I'm trying to find a fast way to detect loops in a vector. By loop I mean repetition of an integer and by loop erasing remove all integers between two occurrence of any integer For instance,
v=[3 1 4 6 7 9 1 22 87 33 35 36 37 35 34] should be equal to [3 1 22 87 33 35 34]
basically these are the nodes that I'm visiting in a graph and there may be loops. I just want to obtain a simple path (without loops). I found solutions but require "for" loops and I need this to be performant since it will be applied to every walk (100'000 walk of length up to 2'000 ). If anyone could help it will be greatly appreciated.
  4 个评论
显示 2更早的评论
Jan
Jan 2011-5-25
In the example in the question, the both 1's are deleted. Here you keep the first (or last) value of the loop. Which behaviour is wanted?
Mehmet Candemir
Mehmet Candemir 2011-5-25
My mistake it should contain one of the 1's and one of the 35's. so [3 1 22 87 33 35 34]

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Andrei Bobrov
Andrei Bobrov 2011-5-25
EDIT
V = v(:);
[a b n] = unique(V,'first');
[~, bl, nl] = unique(V,'last');
v1 = [b bl];
v1(abs(diff(v1,[],2)) < 100*eps,:) = [];
vv = min(v1(:)):max(v1(:));
idx = arrayfun(@(x)vv(vv>=v1(x,1) & vv<v1(x,2)),1:size(v1,1),'un',0);
V([idx{:}]) = []
removed typo
  7 个评论
显示 5更早的评论
Mehmet Candemir
Mehmet Candemir 2011-5-25
I jsut tried with this vector
v=[98 17 21 57 1 49 80 49 99 40 48 96 52 96 18 41 30 83 69 19 240 242 280 273 291 248 209 249 270 293 270 210 299 261 286 261 268 296 270 272 204 266 285 260 282 266 282 204 220 255 208 246 259 231 281 289 205 253 271 291 240 206 218 201 274 287 252 220 251 224 241 298 220 204 221 251 207 231 268 296 270 249 275 267 246 267 275 249 220 296 270 293 277 228 238 230 270 296 279 267 275 22 52 64 99 54 62 14 62 92 8 33 59 44 51 70 92 47 44 51 20 55 67 97 69 31 69 83 26 83 15 70 95 65 59 82 59 58 5 19 29 71 66 25 67 27 91 66 46 67 3 73 0 26 59 82 79 65 79 4 52 69 16 84 62 76 85 68 66]
It returned me [98 17 21 57 1 49 66] I think that there is still one error.
Jan
Jan 2011-5-25
UNIQUE calls SORT implicitely. If you inline the UNIQUE function, one of ther sortings could be omitted. But the complexity of the function would grow again.

请先登录，再进行评论。

更多回答（1 个）

Jan
Jan 2011-5-25
A FOR-loop approach, which might be fast already due to Matlab's JIT acceleration:
v = [3 1 4 6 7 9 1 22 87 33 35 36 37 35 34];
off = false; % Faster to call function FALSE once
n = length(v);
use = true(1, n);
for i = 1:n
if use(i)
multi = find(v((i + 1):n) == v(i), 1, 'last');
if isempty(multi) == 0
use((i + 1):(i + multi)) = off;
end
end
end
v = v(use);
If you expect long loops, a WHILE method can be faster:
off = false; % Faster to call function FALSE once
n = length(v);
use = true(1, n);
i = 1;
while i <= n
multi = find(v((i + 1):n) == v(i), 1, 'last');
if isempty(multi)
i = i + 1;
else
use((i + 1):(i + multi)) = off;
i = i + multi + 1;
end
end
v = v(use);
Using the smallest possible integer type for v will reduce the processing time:
v = int16(v);
  5 个评论
显示 3更早的评论
Jan
Jan 2011-5-25
I get the same [98 17 21 57 1 49 99 54 62 76 85 68 66] with both versions. And 80 appears inside [49 80 49], such that it should *not* be there. Please check this again.
For your small test-vector of length 169 I get these timings (Matlab 2009a, 1.5GHz PentiumM):
tic; for i=1:20000, r = Andrei(v); end, toc % 4.39 sec
tic; for i=1:20000, r = JanFor(v); end, toc % 1.50 sec
tic; for i=1:20000, r = JanWhile(v); end, toc % 0.85 sec
I've constructed a longer testvector by [v,v+500,v+1000,...]. For a vector of length 13520 the WHILE method is 5 times faster than the 2*UNIQUE method.
Mehmet Candemir
Mehmet Candemir 2011-5-25
Yeah it worked this time. I should make a stupid error somwhere..Thanks...

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by