Welcome to the most active Linux Forum on the web.
Go Back > Forums > Non-*NIX Forums > Programming
User Name
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.


  Search this Thread
Old 10-12-2004, 06:21 PM   #1
Registered: Dec 2003
Location: NC, US
Distribution: Novell Linux Eval (2.6.5)
Posts: 240

Rep: Reputation: 30
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.
Old 10-12-2004, 06:48 PM   #2
Registered: Sep 2004
Location: New Zealand
Distribution: Debian
Posts: 900

Rep: Reputation: 33
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.
Old 10-14-2004, 05:58 AM   #3
Senior Member
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
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.

Last edited by ta0kira; 10-15-2004 at 01:14 AM.


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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

Similar Threads
Thread Thread Starter Forum Replies Last Post
What is the best cryptographic algorithm? Linux.tar.gz Linux - Security 19 05-02-2006 08:54 PM
Open/Net/FreeBSD Comparsion kaon *BSD 3 02-08-2005 11:19 AM
huffman algorithm mcshen Programming 3 03-12-2004 02:00 PM
Is there any comparsion chart available for graphic cards? lamiczka Linux - Hardware 1 02-17-2004 11:59 AM
assistance with an algorithm mandrake_linux Programming 3 07-27-2001 04:03 AM > Forums > Non-*NIX Forums > Programming

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

Main Menu
Write for LQ is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration