Loop erasing random walk

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.

[Jan]

What do you want as output for v=[1, 2, 3, 2, 3]?

It would be much easier to find an equivalent vectorized solution, if you post your working FOR-loop approach - then we have a chance to knwo, what "equivalent" exactly means.

[Mehmet Candemir]

I just forgot to mention that loops should be erased in chronological order, i.e first loop is be removed first. So I need to have v=[1,2,3] sinc the first loop is "2-3-2"

[Jan]

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]

My mistake it should contain one of the 1's and one of the 35's. so [3 1 22 87 33 35 34]

Answer 1

[Andrei Bobrov]

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

[Mehmet Candemir]

I just tried with the example v=[3 1 4 6 7 9 1 22 87 33 35 36 37 35 34] and it does not seem to work. V remains the same.

[Mehmet Candemir]

the cell idx{:} is empty

[Mehmet Candemir]

It gave me v=[3 22 87 33 34] but i need [3 1 22 87 33 35 34] I keep one of the repeated integers. 1-*-*-*-*1=1 or x*****x=x. Thanks

[Andrei Bobrov]

corrected

[Mehmet Candemir]

seems to work. I'l just perform extensive tests :)

Thanks

[Mehmet Candemir]

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]

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.

Answer 2

[Jan]

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);

[Mehmet Candemir]

I'll just try it and report back

[Mehmet Candemir]

It's strange that I can't accept two answers. Thank you very much for your time and concern.

[Mehmet Candemir]

I've just seen that loops don't return the same answer. I used 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]

And the first solution , [98 17 21 57 1 49 80 49 99 40 48 96 52] (wrong, twice 49)

while the second [ 98 17 21 57 1 49 99 54 62 76 85 68 66](wrong 80 should be there)

[Jan]

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]

Yeah it worked this time. I should make a stupid error somwhere..Thanks...