Code center > Darwinbots Program Source Code

Need fastest possible code to compare dna

(1/5) > >>

Botsareus:
I am currently using the original DNA structure:

--- Code: ---  DNA() As block            ' program array
...
Type block
  tipo As Integer
  value As Integer
End Type
--- End code ---

All my attempts to write a fast algorithm in vb6 to compare and calculate how different two DNAs are where futile.

I need a fast algorithm to compare two DNAs. If it has to be low level, that is fine. As long as I can call an API to it. This kind of DLL may be useful for DB3 as well, that is why I posted here.

Also, if Percentage to the nearest Whole Number is faster the Floating Point, please do Percentage. That is fine.

Thank you Numsgil, I hope you can pick your brain from your awesome video game programming experience and pull out something for me.

JRaccoon:
My first thought is some kind of modified two character Levenshtein distance. I can expand on this process if you tell me more about what you consider similar DNA.

1) Should the block be considered distinct if just the value is different and the tipo is the same.
2) Should the block be considered distinct if just the tipo is different and the value is the same.
3) Should the block be considered distinct if either the tipo or the value is the same edit: different.

The nice thing about the Levenshtein distance algorithm is you should be able to find a very efficient solution in almost any language.

Botsareus:
The block should be considered distinct if either the tipo or the value is different. A change in any of these data points constitutes a different dna statement. There could be runs of identical DNA and runs of different DNA. I attempted to port windiff logic as much as possible just by guessing.

JRaccoon:
Okay, that's what I would have guessed. Instead of Strings (which can be thought of as character arrays), you'll have the two complete DNA sequences as your strings. The only major modification you should have to make to the standard algorithm is instead of comparing a single character, you'll have to compare two Integers and only consider that block (character) equivalent if both tipo and value are the same.

Another option, if you have access to double-wide data types, would be to store both the tipo (What does this stand for?) and the value in a single Double (or whatever it might be called) and then you would only have to compare a single data point. This approach would likely be less efficient though.

I'd offer up some pseudo-code, but I don't really know Visual Basic which is the language of choice for DarwinBots if memory (and your code sample) serves. For the standard String comparison though, Rosetta Code has an example. http://rosettacode.org/wiki/Levenshtein_distance#Visual_Basic_.NET
I can't really comment on the efficiency of that implementation but it might be enough to get you started.

Botsareus:

--- Quote --- tipo (What does this stand for?)
--- End quote ---

We brake up dna into command types. Some examples are:

*.sysvar, .sysvar, basic command( add, subtract, etc.), advanced command (angle, distance, etc.)


I wonder if there is any low level tricks to make it faster though.
Also, the code returns a matrix of strings not a ratio.
Also, why are we doing "Math.Min" sounds like data modification to me.

Thanks for your help btw.

Navigation

[0] Message Index

[#] Next page