1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Algorithm Optimization [Python]

  1. Jun 11, 2017 #1
    1. The problem statement, all variables and given/known data
    Given a list of integers and a single sum value, return the first two values (parse from the left please) in order of appearance that add up to form the sum.
    Code (Python):
    sum_pairs([11, 3, 7, 5],         10)
    #              ^--^      3 + 7 = 10
    == [3, 7]

    sum_pairs([4, 3, 2, 3, 4],         6)
    #          ^-----^         4 + 2 = 6, indices: 0, 2 *
    #             ^-----^      3 + 3 = 6, indices: 1, 3
    #                ^-----^   2 + 4 = 6, indices: 2, 4
    #  * entire pair is earlier, and therefore is the correct answer
    == [4, 2]

    sum_pairs([0, 0, -2, 3], 2)
    #  there are no pairs of values that can be added to produce 2.
    == None/nil/undefined (Based on the language)

    sum_pairs([10, 5, 2, 3, 7, 5],         10)
    #              ^-----------^   5 + 5 = 10, indices: 1, 5
    #                    ^--^      3 + 7 = 10, indices: 3, 4 *
    #  * entire pair is earlier, and therefore is the correct answer
    == [3, 7]
    Negative numbers and duplicate numbers can and will appear.

    NOTE: There will also be lists tested of lengths upwards of 10,000,000 elements. Be sure your code doesn't time out.


    This is a problem off of codewars.com. I have made two versions that satisfy the eight examples but there is a 12000ms time restraint that I need to overcome. I am not versed in CS so I don't know much about algorithms or how to optimize them.

    2. Relevant equations

    The examples are:
    Code (Python):
    l1= [1, 4, 8, 7, 3, 15]
    l2= [1, -2, 3, 0, -6, 1]
    l3= [20, -13, 40]
    l4= [1, 2, 3, 4, 1, 0]
    l5= [10, 5, 2, 3, 7, 5]
    l6= [4, -2, 3, 3, 4]
    l7= [0, 2, 0]
    l8= [5, 9, 13, -3]

    print(sum_pairs(l1, 8) == [1, 7]) #"Basic: %s should return [1, 7] for sum = 8" % l1)
    print(sum_pairs(l2, -6) == [0, -6]) #"Negatives: %s should return [0, -6] for sum = -6" % l2)
    print(sum_pairs(l3, -7) == None) #"No Match: %s should return None for sum = -7" % l3)
    print(sum_pairs(l4, 2) == [1, 1]) #"First Match From Left: %s should return [1, 1] for sum = 2 " % l4)
    print(sum_pairs(l5, 10) == [3, 7]) #"First Match From Left REDUX!: %s should return [3, 7] for sum = 10 " % l5)
    print(sum_pairs(l6, 8) == [4, 4]) #"Duplicates: %s should return [4, 4] for sum = 8" % l6)
    print(sum_pairs(l7, 0) == [0, 0]) #"Zeroes: %s should return [0, 0] for sum = 0" % l7)
    print(sum_pairs(l8, 10) == [13, -3]) #"Subtraction: %s should return [13, -3] for sum = 10" % l8)
     
    They should all return True
    3. The attempt at a solution
    My first attempt is simple and straight forward:
    Code (Python):
    def sum_pairs(ints, s):
        prev_list = []
        for num in ints:
            for test in prev_list:
                if num+test == s:
                    return ([test, num])
            prev_list += [num]
    My second attempt is the same structure however I store and organize previous test numbers by either positive or negative:
    Code (Python):
    def sum_pairs(ints, s):
        neg_list = []
        pos_list = []
        for num in ints:
            if num > s:
                for neg in neg_list:
                    if neg == s - num:
                        return [neg,num]
            else:
                for pos in pos_list:
                    if pos == s - num:
                        return [pos,num]
            if num < 0:
                neg_list += [num]
            else:
                pos_list += [num]
    With this new method, I went from 50 total possible returns to 31. I am not sure if this is the right direction to go. It very well may be I'm doing more work by organizing than I am saving.

    From here, my plan was to make four lists: two negatives with one where abs(number) >= abs(s) and the other abs(number) < abs(s) with a similar pattern for positive numbers. I think it might be helpful to find the sign of 's' at the very beginning but I haven't figured out how to use that to my advantage..
     
    Last edited: Jun 11, 2017
  2. jcsd
  3. Jun 11, 2017 #2
    You just need to look at all the numbers once, and store them is such a way while doing this, you can immediately look up if the new number forms a pair with any number that you have already seen.
    This can be done in a lot of ways: keeping the list sorted, storing the list as a hashtable or tree, or use an array of all the possible values that can occur.
     
  4. Jun 11, 2017 #3
    Ahhh I think I was trying to do this intuitively but lacked the programming experience. I think I will try to sort the list first:
    Code (Text):
    if prev_num not in prev_list:
        prev_list += [prev_num]
        prev_list = sorted(prev_list)
     
    After that, I will be able search the list backwards or forwards until (s-(num+test)) changes signs.

    If that doesn't do the trick, I will try hashtables. The book I used to learn python briefly mentioned how fast hashtables were but didn't go over them in-depth.
    Thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Algorithm Optimization [Python]
  1. Python question (Replies: 1)

Loading...