Welcome to the most active Linux Forum on the web.
 LinuxQuestions.org good sequence comparsion algorithm?
 User Name Remember Me? Password
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

 10-12-2004, 06:21 PM #1 feetyouwell Member   Registered: Dec 2003 Location: NC, US Distribution: Novell Linux Eval (2.6.5) Posts: 240 Rep: good sequence comparsion algorithm? this one might be a bit off the topic here I am looking for a good generic algorithms that does two sequence comparison I will have sequence A which contain n items (think them as doubles) and sequence B which contain m items I need to comparsion item1 in A to all items in B, and do the same for all items in B therefore, there should be n*m comparison. there might not be any quicker way to do this, but if you know, please let me know, thanks.
 10-12-2004, 06:48 PM #2 CroMagnon Member   Registered: Sep 2004 Location: New Zealand Distribution: Debian Posts: 900 Rep: I guess it depends on what you're doing, and what comparison you need to make. For example, if you need to compare every item in A with every item in B to find out whether the item in B is less than, equal to, or greater than an A item, you could sort B first, and reduce the number of comparisons (either to n log m by doing a sort of binary search, or just simply iterating through B until you find a value that is larger - all subsequent items in B would be larger). How much this would speed things up depends on the data and the speed of the sort.
 10-14-2004, 05:58 AM #3 ta0kira Senior Member   Registered: Sep 2004 Distribution: FreeBSD 9.1, Kubuntu 12.10 Posts: 3,078 Rep: If it is a magnitude comparison as stated above, you can simplify by sorting each first. Unless you can relate the elements of A to others in A and likewise with B, I think you are stuck with an m*n algorithm. If you keep it 2 lists; sort first, then have 2 positional references; one for the position on A and one for B. Then you can compare and increment the appropriate position accordingly, and base your analysis on a comparison of the current list positions. If they are the same type, you can use an associative structure that has one member as the list value and the name/pointer/etc. of the list as another value: A: 1 2 3 4 5 B: 6 7 8 9 0 --> <1, A> <2, A> ... <6, B> <7, B> ... Then combine the lists and sort by list value, then extract your info based on the distribution of A and B elements. The bottom line is m*n is basically the least efficient algorithm you can have because the sets do not intersect, but if you can somehow combine/internally relate the 2 lists you can end up with something like log(m+n) complexity with something like a merge sort (very fast and 'stable'; like elements retain relational order.) Sorry it is so vague, but I don't know what you are comparing, or even what language you intend to use. I generally write my algorithms in C++, then when I get them working I extract the substance of the algorithm and make it into something generic. ta0kira Last edited by ta0kira; 10-15-2004 at 01:14 AM.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Linux.tar.gz Linux - Security 19 05-02-2006 08:54 PM kaon *BSD 3 02-08-2005 11:19 AM mcshen Programming 3 03-12-2004 02:00 PM lamiczka Linux - Hardware 1 02-17-2004 11:59 AM mandrake_linux Programming 3 07-27-2001 04:03 AM

LinuxQuestions.org

All times are GMT -5. The time now is 10:45 PM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -