Exclusion of undesirable segments of splitted series

[altenbach]

Well, my search algorithm was pretty quick& dirty and not optimized at all. For fun I made a few modifications, and it finds now all solutions in well under one hour (still only running on one CPU core, but 5x+ faster). I think it should be easily possible to solve it in under 20 minutes using both cores. (just guessing). 🙂

Let me know if anything is not clear in my code.

[dan07]

Hello...

The only thing that I was able to do was apply the sequence to the graphs to verify if its the correct one, as you said "You can pick any search result with the slider on the right and everything will update accordingly"

Thanks

Daniel

[dan07]

Sorry Altenbach, I maked a mistake in the last message

The correct sentence is: The only thing that I was not able to do was apply the sequence to the graphs to verify if its the correct one, as you said "You can pick any search result with the slider on the right and everything will update accordingly"


Thanks

Dan07

[altenbach]

1. Run program
2. Move slider to zero or a positive value.
3. anything happening?

[altenbach]

Just for completeness, here's the fast version. It takes about 47 minutes to find all 291 matches with the default settings. If you set the minimum bits to 26, it is much faster since it uses a LUT for the bit counting, and finds the 3 matches in about 8 minutes. Pretty impressive for 2^34 possibilities! 🙂

Further reasons for the speed improvements:

• It actually only counts with U32 for the first 32 bits, but at each iteration it checks all four corresponding patterns with the two extra bits.
• The search code is flat to avoid the subVI calling overhead, which makes it a bit ugly.
• LUT for bit counting.

Maybe you can implement some of the ideas.

I am sure many things could be improved, and there are probably little bugs. I only spend very little time on this. The search should run in parallel to the main loop so the search results can be inspected during the search. It should also be split to run on multiple cores.

[dan07]

Hello Altenbach....

This VI is very fast and works properly with my data. The only problem is that I have numbers without decimal places, which could increase the number of possibilities, but in my next files I will take note of the numbers with at least 3 decimal places.

What is the reason for the 32 bits combination runs much more fast? It's related with the 32 bit of the operation system?

What is LUT?

I would like to thank you again. Some easy operations to you are quite difficult and sometimes impossible to me....

My problem is now solved.

All the best to you

Dan07

[altenbach]

If you want to search for more significant digits, you probably should multiply it up like we currently do for the ratio part and do the comparison on whole numbers. Otherwise you probably will not get a match because the real number is slighly different.

There are probably still a few small bugs in my code (I already found a few). maybe I have time to do some more tweaks over the weekend.

Yes, 32 bit operations are definitely faster than 64 bit operations, but there are also a few other optimizations.

LUT: lookup table. I create an array outside the main loop (at the start of the program)  that contains the number of set bits for all 16bit numbers. Indexing into the array with any number up to 2^16-1 will return the number of set bits. To count the number of true bits for any given 32 bit numbers, we just split it in two 16 bit parts and index each into the array and add the two resulting elements. This is faster than creating a boolean array, converting to 0,1, and adding the array elements at each of the 2^32 iterations of the loop. Calculating the lookup table is very fast (only 2^16 iterations) and is done only once. (We could of course also use a tiny 8bit lookup table and split the number fourways. OTOH, a single 32bit lookup table would be too big for todays computers and OSs. ;))

This is especially important if we filter based on a large "min segments" value, because then we can reject many numbers right away and we don't even need to do the detailed calculations for those.

[altenbach]

---

altenbach wrote:

Just for completeness, here's the fast version. It takes about 47 minutes to find all 291 matches with the default settings. If you set the minimum bits to 26, it is much faster since it uses a LUT for the bit counting, and finds the 3 matches in about 8 minutes. Pretty impressive for 2^34 possibilities! 🙂

---

Over the weekend, I was testing out some ideas for a similar problem, and I have now a version that does the same in 24minutes (2x faster) (default settings) and under a minute with min=26 (8x faster). Still only running on one core. There is probably still quite a bit of slack left. 😄 

If you want, I can clean ip up a bit next time I have some spare time and post it later.

[dan07]

Hello... how are you?

Sorry for the delayed answer...

Last week I was using your VI to search for some values and show me the possible sequences that matches the results. But the whole search is taking about 1 hour. If you could send me the faster VI I will be very glad.

We always learn the things by the worst way , in my next analysis I will not make the same mistake, I will take note of the results with at least 2 decimal places.

Thanks for attention

Dan07

[dan07]

One more question...

I need to append to the VI a control for the graphs scale. In other VIs I used to use a property node for the graph, with Maximum and Minimum... But I was working in the first VI that you sent me (that with the size of a Post Card, not the large and monster like that I sent first to you...) and I don't know where I should link the scale control.

Attached is a picture with what I want to do.

Thanks again

Dan07

Message Edited by dan07 on 06-29-2008 01:02 AM