Implementation of PELT pruning

[sensille]

Hi,

while trying to understand active_arraylist I stumbled upon the fact that the pruning loop only removes every second element when multiple consecutive elements should be pruned. Currently the implementation is

iter = active_arrlist_endidx;
while active_arrlist(iter) > 1
    lb = active_arrlist(iter);
    if F(lb-1) + state_cell{lb, 1} > F(rb)
         active_arrlist(iter) = active_arrlist(lb);
    end
    iter = lb;
end

while it should be

iter = active_arrlist_endidx;
while active_arrlist(iter) > 1
    lb = active_arrlist(iter);
    if F(lb-1) + state_cell{lb, 1} > F(rb)
         active_arrlist(iter) = active_arrlist(lb);
    else
         iter = lb;
    end
end

Not sure if it changes the result of the calculation, but at least it wastes cycles.

What do you think?

[sensille]

Another point: you initialize active_arrlist_endix to 2. The comment above that suggests that you intend to add 2 to the list. But active_arrlist(2) is 1, so the loop is not visited on the first run, and the arrlist is always one element too short.
Initializing the endix to 3 and extending the arrlist to N instead of N-1 changes the result of the calculation.

[mstorath]

Thanks for the comments. You may be right with both points but I have to take a closer look in the next days. In the meantime, you might resort to the FPVI pruning which uses a different iteration.

[mstorath]

There was indeed a problem with the loop. I just committed a fix which hopefully fixes the issue. I added a testcase that compares the two prunings which now gives the same results. I would appreciate if you briefly checked it with the test signals you have used. Thanks again for the feedback!

[sensille]

Thanks for looking into this. I see that just replacing active_arrlist_endix extends the list to the right by one, that part looks good. But I'm not so sure about the loop:

while lb > 1
    next = active_arrlist(lb);
    if F(lb-1) + state_cell{lb, 1} > F(rb)
        active_arrlist(lb) = next;
    end
    lb = next;
end

Now your loop does nothing. You just assign with next the value to active_arrlist you read 2 lines before.
Also it might be that you have to start the loop with lb = rb and not lb = active_arrlist(rb) to be able to prune the second to last list element, but I haven't thought that through yet.

[mstorath]

Yes, that fixed nothing indeed.
The issue is in the array list structure I used which probably needs me more than a couple of minutes to fix and test.
For the moment I reverted the PELT pruning to a previous version that worked with lists from the Java Collections Framework
and which should circumvent to problem with the custom list.

[sensille]

Btw, I think my proposed fix above (the added else) fixes the delete-issue with the loop.