|
|
|
| Pathologically Eclectic Rubbish Lister | |
| PerlMonks |
Re: Algorithm Showdown: (A litany of failures)by BrowserUk (Patriarch) |
| on Dec 11, 2004 at 07:40 UTC ( [id://414076]=note: print w/replies, xml ) | Need Help?? |
|
Okay. You, and a few others seem to think that my attempt to walk away from this implies concession and sour grapes. It doesn't. I should have known (myself) better than to think I could anyway. Here are a few (more) reasons that I reject this second round of "pissing contest": Failure 1 - a really simple test.My code works. Ysth's code works. Your's fails, but it does it really fast!
Failure 2 -- use a slightly different alphabet.My code works and finds no matches. Ysth's code works and finds no matches. Your's produces fiftytwo thousand errors, really fast.
Failure 3 -- verify the number of matches found is correct.For this I use the set of all 2701 possible, 25-char, 2-mismatch fuzzy matches for the subsequence 'A' x 25. By making the test sequence(s) all 'A's, then every key will match at every offset in the sequence, in every sequence. This allows me to verify that all possible positions are checked, all possible fuzzy matches are matched and allows a simple calculation to verify the total match count from an implementation. For an 'A'x1000-char sequence, and 25-char x 2-mismatch keys = (1000-25+1) * 2701 = 2636176 matches.
Yep! Your code sure is quick, but look at the memory consumption! What happens if
Mine handles it--slowly. ysth's handles it--slowly. Yours, churns and churns, and fails-- really, really slowly. Eventually being terminated by the system due to lack of virtual memory. I have 1GB available.
And I do hope that all those that disapproved of my attempt to walk away from this intensely frustrating waste of effort will notice that last test alone required nearly 5 hours of my time--at 99% cpu usage making doing anything else productive impossible. I wonder how many of those that have demonstrated their disapproval have even bothered to read the crufty code I'm having to pick apart and debunk? Unlike demerphq, I don't abandon a test after less than two minutes just cos it's inconvenient! Failure 4 -- mixed length fragmentsThis is harder to demonstrate convincingly, and easily dismissed by reference back to the OP with it's description of 25-char sequences. However, every description I have found of the processes (Digestion and Shredding) that biochemists use in the Cloning, Mapping and Sequencing of DNA, produces large sets of fragments, of variable length. Every version of my algorithm published, and my latest, most effcient version which is one or two orders of magnitude more efficient than the best so far published, happily deals with every key having a different length. Indeed, the -KEYLEN=25 parameter shown in the examples above is internally overridden and only used on my versions for consistancy. As I stated elsewhere, I can make my code run much more quickly, by making the same assumption as both yours, and ysth's code (which he openly noted) make. I have avoided doing this because I want a generally applicable algorithm, whether for genome work or fuzzy name matching, or looking for postcodes or any other type of fuzzy match where the search keys can be any mixed bag of words. You mentioned somewhere that your algorithm could be adapted to do this, but as it relies heavily for at least part of its performance upon ysth's multi-indexing mechanism, and he has stated that his algorthm would be affected, I can only assume that your implementation would be also. The ethics of comparative studiesBefore any comparsions are made, and results are published, it is pretty standard practice to ensure that the algorithms under test:
Ie. If your going to fairly and accurately compare different algorithms, then you agree these criteria, or variancies from it before you published huge, dramatic sets of statistics. And when you do, you note those assumptions and variencies. I brought this to your attention well in advance of your act of "publish and be damned", and you chose to ignore it. So, you got damned. And given that we have been here before, I have no intention of withdrawing one syllable of that condemnation, even if it does go against my stated "don't be rude" philosophy. It is clear from the record of those posts, that your's was a knowing, deliberate act, and I called it as such. SummationSo, let me sum up. You create an Inline-C implementation of a Trie, use it as a faster replacement for the standard hash in ysth's implementation of his brilliant, innovative algorithm, which itself relies on my xor technique to determine the fuzz factor. What part did your original algorithm play in this? Zero! Nada! Not - a - jot!. You then wrap it up in a crufty, over-engineered test harness that serves to guarantee that only idiot's like me are ever going to download, install and run it; to produce a big table of impressive looking statistics comparing this 2-week, 3-man extravagaza, with a peice of code knocked up on the spot, in under an hour, and use it "claim victory"? However, your Trie implementation--as used for those tests--is so domain specific in it's contruction, that it is severly limited in it's application. Any single change--an extra character in the alphabet (ACGTX); or lowercase letters; a fuzz factor higher than 4 in combination with any number of pathalogical testcases--causes it to variously: produce no output; or produce reams of errors and no matches; or exhaust all available memory before ever producing a single match. And the kicker. Your code does not yet produce the required information. As tested and lauded, your code outputs:
But what is missing? The value or index position of the key that was matched. So now you have a file full of sub-sequences that match a key--which if you'd bothered to record the sequence number, as well as the offset, would be redundant anyway--all of which matched one of the (100,000 or 500,000 or 1,000,000) keys in the keys file. But which one? Sure, you can post process the two together to determine the information, but that's damn nearly as big a job as the original problem. And what will you use to fuzzy-match those fuzzy-matched sub-sequences back to the keys they matched? The xor method of course! Yes. If used within the very specific domain of inputs, your combination of ysth's multi-indexing, a fast Inline-C Trie implementation, and the xor method does result in a very fast solution to the original problem. But maybe your module should be named: Fuzzy(not greater than 4)::Matcher(if you don't need mixed case)::DFA(+multi-index+xor)::charset(ACGT).pm There is nothing wrong with cross-fertilisation. Indeed, I congratulated ysth on his innovation the moment I understood how clever it is. I'm in the processes of nicking a few ideas myself. It probably still won't (quite) match your performance on sparse datasets, but it will
But for you to post that table of meaningless drivel under the heading "Algorithm shootout", when 90% of it isn't even your algorithm and bears almost no relationship to your original "proof-of-concept" code; compare it against my off-the-cuff implementation--which still works!; Eggs with bananas! Gah! Words finally fail me. Nothing I want to add at this point is publishable. Addendum: And my detailed analysis of both your original algorithm, and this implementation of an entirely different one, has shown me nothing that would cause me to recind any of the fundamental points of my original analysis on the applicability of Tries this class of problem. Some of the projected numbers change, sometimes by an order of magnitude or two, but the underlying basic difficiencies remain. Without using ysth's innovation to allow you to avoid a brute force linear search of every sub-sequences, using a Trie would be a linear O(nm) process. And without the use of the xor algorithm to determine the fuzz factor, you would need to be storing this information in the Trie. But for the same reasons as you cannot related the fuzzy-matched subsequence back to the key that it matched, you also cannot determine the fuzz-factor without the xor method. This is as I identified, the simple reality that Tries work by uniquifying their keys. The process of producing all the fuzzy match possibility for each of the 100,000 keys will produce many duplicates and these will all be folded down to a single path in the Trie. Yes, you can associate a value with that path, but which value? An array of input-key/fuzz-factor-that-produced-this-path pairs? But then how do you determine which of those pairings was responsible for this match? And what will attaching all that extra information in the Trie do for your memory consumption? Boom after 50 keys like your "proof-of-concept"! Examine what is said, not who speaks.
The end of an era!
"But you should never overestimate the ingenuity of the sceptics to come up with a counter-argument." -Myles Allen"Think for yourself!" - Abigail "Time is a poor substitute for thought"--theorbtwo "Efficiency is intelligent laziness." -David Dunham "Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon
In Section
Meditations
|
|
||||||||||||||||||||||||||||||