I'm trying to search doubled occurrences of numbers in a list. But for big arrays (like >1000 items this taking quite a long time). Is there any method for speeding it up?
lis = [1, 6, 9, 3, 27, 50, 12, 2]
def isAnyThere (lis):
for m in lis:
for m in lis:
if m == 2 * k:
return m
return 0
CodePudding user response：
It wasn't super clear from the question but I think you want to check if there are any pairs of numbers in the list such that one is double the other?
If you sort the list first, you would only need to check each pair of elements once so that immediately halves the number of comparisons.
Also work on the set of list elements to remove duplicated values in large lists.
def isAnyThere (lis):
lis = sorted(set(lis))
for i in range(len(lis)):
for j in range(i 1, len(lis)):
if lis[j] == 2*lis[i]:
return lis[j]
else:
return 0
CodePudding user response：
Python's set type provides O(1) lookup and insert performance unless the set becomes spectacularly large. The following algorithm:
- insert the elements of the list into a set
- for each even element x of the list check to see if x // 2 is in the set
takes 2*n steps for a list of length n.
from typing import Sequence
def find_doubled(seq: Sequence[int]) -> Sequence[tuple[int, int]]:
return [(x, x // 2) for x in seq if x % 2 == 0 and x // 2 in set(seq)]
if __name__ == '__main__':
l = find_doubled([1, 6, 9, 3, 27, 50, 12, 2])
print(l)
# prints [(6, 3), (12, 6), (2, 1)]
Duplicates are dealt with by ignoring them.