Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Suppose I have two lists of N 3 by 3 vectors of integers.

I need to find a quick way (say of running time at most N^(1+epsilon)) to find the vectors of the first list that have the same 1st coordinate with a vector of the second list.

Of course, I could do the following naive copmarison:

for u in list_1 do
for v in list_2
if u[1] equals v[1] then
print u;print v;
end if;end for; end for;

This, however, would require N^2 loops.

I feel that sorting the two lists according to their first coordinate and then look up for collisions is perhaps a fast way. Bubbleshort, etc., would probably take logN time, but I can't really see how to code the search for collision between the sorted lists.

Any help would be appreciated.

share|improve this question
    
Should rather be on StackOverflow.com, I think. –  haylem Jun 2 '11 at 12:29
1  
You can do it in O(n) without using hash tables, sets or any other data structures that are not simple arrays or linked lists. The fact that the lists are sorted helps you - inside of a while loop (not for loop) you would move a pointer to left list and a right list conditionally. The exact details can be somewhat messy, but because both lists are sorted, you only need to traverse each one once, going in one direction only. In fact, you do not need to be able to access them by index at all. The step is similar to a merge step of the merge sort algorithm. –  Job Mar 14 '13 at 17:07
add comment

2 Answers

Here is a quick and dirty O(N) Python answer for you that uses only the given lists. This only works if both lists are SORTED. I need to clean this up, but it does illustrate what you need to get done. I have chosen bad names for the variables; I will clean this up later.

def test():
    sorted_full = [1,3,5,7,9,11,15,17]
    sorted_sub = [5,11,17]

    full_ix = 0
    sub_ix = 0

    while full_ix < len(sorted_full) and sub_ix < len(sorted_sub):
        curr_full = sorted_full[full_ix]
        curr_sub = sorted_sub[sub_ix]
        if curr_full == curr_sub:
            print('Common id ' + str(curr_full) + ' at index ' + str(full_ix))
            full_ix +=1
            sub_ix +=1
            continue
        if curr_full < curr_sub:
            full_ix +=1
        else:
            sub_ix+=1


test()
share|improve this answer
    
This is not an O(1) solution . . . –  Chewy Gumball Mar 15 '13 at 0:04
    
@Chewy Gumball, duh, thanks, changed to O(n). –  Job Mar 15 '13 at 0:08
add comment

The naive way requires O(N^2) time, correct. Sorting the lists first takes O(N log N) time, assuming you use a good algorithm (bubblesort is O(N^2)), and the rest is O(N), so total time is O(N log N).

If you can use a hash table that allows multiple entries (C++0x's std::unordered_multimap would be ideal) you can get normal performance down to O(N). Just enter the elements of one vector into the hash table, first coordinate as the key and entire vector as the value, then go through the other vector, looking up first coordinate values.

share|improve this answer
    
Thanks for your suggestion. Since I am using MAGMA could you please provide some details (or a link?) on how unordered_multimap is implemented ? –  manenir Jun 1 '11 at 21:48
1  
+1 Spot on with the hash table implementation. –  Ed Woodcock Jun 2 '11 at 8:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.