UPDATED: (larger test lists)
The issue is that you are doing an index search for every element. This means the complexity of your algorithm is O(n2).
The set and dict solutions are better because they trade off memory to gain speed. Here is a very crude quick script for comparing the performance:
import sys
from timeit import timeit
def generate_list(size: int) -> list:
return list(range(-size//2, size//2))
def original_solution(counter: list, slope: list) -> list:
filter_count = [i for i, j in zip(counter, slope) if i-1 == slope.index(slope[int(i-1)]) and j <= -1]
return filter_count
def using_dictionary(counter: list, slope: list) -> list:
"""Inspired by Mechanic Pig"""
mapping = {}
for i, elem in zip(counter, slope):
mapping.setdefault(elem, i)
filter_count = [i for elem, i in mapping.items() if elem < -1]
return filter_count
def using_set(counter: list, slope: list) -> list:
"""Inspired by Алексей Р"""
s = set()
filter_count = []
for i, e in zip(counter, slope):
if e not in s and e < 0:
s.add(e)
filter_count.append(i)
return filter_count
def main():
size, n = sys.argv[1:]
print(f"List size: {size}, n: {n}")
print("Time in seconds:")
for func in [original_solution, using_dictionary, using_set]:
name = func.__name__
t = timeit(
f'counter = slope = generate_list({size}); '
f'{name}(counter, slope)',
setup=f'from __main__ import generate_list, {name}',
number=int(n)
)
print(f'{name:<18}', round(t, 4))
if __name__ == '__main__':
main()
You can call the script providing the desired list size and number or repetitions.
python test_script.py 10000 10
The results:
List size: 10000, n: 10
Time in seconds:
original_solution 3.5511
using_dictionary 0.0122
using_set 0.0093
I would speculate that the set solution is slightly better because both adding and lookup are O(1) in complexity and there is only one loop, making the entire algorithm O(n).
While the dict solution is technically also O(n), it has to do two loops, meaning 2 * n iterations in practice. So in the limit it is the same as the set solution, but in practice it will probably always be a bit slower.