1

I have an array with different numbers, and i have to find minimum, maximum and all the differences of those numbers. I have tried this:

# list of numbers from which we want to find differences. 
list_of_nums = [1, 9, 7, 13, 56, 5]


def find_differences(list_of_nums):
    list_of_nums = list(dict.fromkeys(list_of_nums)) # remove duplicates
    differences = [] # list to keep differences

    for i in list_of_nums:
        for j in list_of_nums:
            if i > j:
                differences.append(i - j)
            elif j > i:
                differences.append(j - i)
            else:
                continue

    differences = list(dict.fromkeys(differences)) # remove duplicates
    return sorted(differences)


differences = find_differences(list_of_nums)


print("All differences: ", differences)
print("Maximum difference: ", max(differences))
print("Minimum difference: ", differences[0])

Everything here works, but lot of time is wasted for sorting, removing duplicates and looping through lists. So the bigger is the list, the slower program works. I tried to replace the build in sorted function by a sorting algorithm, but it made worse. Here what i get:

All differences:  [2, 4, 6, 8, 12, 43, 47, 49, 51, 55]
Maximum difference:  55
Minimum difference:  2

If anyone knows better way to solve this, i would be grateful!

Michael
  • 657
  • 4
  • 29

2 Answers2

1

Create a function that calculates a set of all differences and returns both minimum and maximum difference.

import itertools

def get_min_max_dif(numbers):
    diffs = {abs(a - b) for a, b in itertools.product(numbers, numbers) if a != b}
    return min(diffs), max(diffs)

Then use this function to evaluate your list of numbers.

print(get_min_max_dif([1, 9, 7, 13, 56, 5]))

Update:

If you want to avoid the itertools library you can do that:

def get_min_max_dif(numbers):
    diffs = {abs(a - b) for a in numbers for b in numbers if a != b}
    return min(diffs), max(diffs)
dlask
  • 8,776
  • 1
  • 26
  • 30
  • But i think using external libraries compensates the things on which we wasted time earlier. Doesn't it slow down the program? – Michael May 10 '20 at 01:02
  • Don't guess, measure it in your specific environment. – dlask May 10 '20 at 01:04
  • Fortunately it does have a positive impact on time. 0.00012933099787915125 is time for my code and 0.00012530700041679665 is for your code. The difference is not so big but it works. – Michael May 10 '20 at 01:20
  • Itertools is not an external library. – Peter Wood May 10 '20 at 13:41
1

Building on answer from Calculate difference between all elements in a set of integers

Code

from itertools import combinations

def find_differences(lst):
  " Find all differences, min & max difference "
  d = [abs(i - j) for i, j in combinations(set(lst), 2)]

  return min(d), max(d), d

Test

list_of_nums = [1, 9, 7, 13, 56, 5]
min_, max_, diff_ = find_differences(list_of_nums)
print(f'All differences: {diff_}\nMaximum difference: {max_}\nMinimun difference: {min_}')

Output

All differences: [4, 6, 8, 12, 55, 2, 4, 8, 51, 2, 6, 49, 4, 47, 43]
Maximum difference: 55
Minimun difference: 2

Performance

Summary - current approach ~2X faster than original post

Test on Posted List

from timeit import timeit

list_of_nums = [1, 9, 7, 13, 56, 5]
count = 10000
print(timeit(lambda:find_differences(list_of_nums), number=count))
print(timeit(lambda:find_differences_orig(list_of_nums), number=count))

Result

0.108 seconds  # using combinations
0.274 seconds  # original post (using sort)

Testing Random List (10, 000 elements)

list_of_nums = [randint(1,30) for _ in range(10000)]
count = 1000
print(timeit(lambda:find_differences(list_of_nums), number=count))
print(timeit(lambda:find_differences_old(list_of_nums), number=count))

Result

0.481 seconds  # this post (using combinations)
1.032 seconds  # original post (using sort)
DarrylG
  • 16,732
  • 2
  • 17
  • 23