Finding sequential recurrences in a list of numbers

Question

I have a list like this:

seq = [-2,3,-2,3,5,3,7,1,4,-5,1,4,-5,1,4,-5]

I want to get all the sequential recurrences and where it happens, I feel the way I'm doing its too brute force and in reality I want this for several lists each with length of about 300.

dic = {}
for p1 in range(len(seq)):
    for p2 in range(p1+1,len(seq)):
        dic.setdefault(tuple(seq[p1:p2]), []).append((p1,p2))

which results in all unique sequences of numbers as keys and their positions as values, for example:

#-2,3: [(0,2),(2,4)]

But also results in a lot of entries that occur only once that don't interest me, I'm 'cleaning' these after by taking only values that have more than 1 entry:

def clean(dic):
    cleandic = {}
    for key, value in dic.items():
        if len(value) > 1:
            cleandic.setdefault(key,value)
    return cleandic

cleandic = clean(dic)

Now for the last step I'm trying to get rid of the occurrences that happens inside the bigger ones, so I sorted the dict by reverse len of keys (bigger keys comes first), for example:

#(1,4,-5,1,4,-5) : ([7,13),(10,16)]
#...
#(1,4,-5) : [(7,10),(10,13)]

The best I came up with to take out the small ones:

sorteddic = dict(sorted(cleandic.items(), key=lambda item: len(item[0]), reverse=True))

onlybigs = {}
while len(sorteddic) > 0:
    for key1, values1 in sorteddic.items():
        for key2, values2 in sorteddic.copy().items():
            if len(key2) == len(key1):
                continue
            for value1 in values1:     #ex: (7,13)
                for value2 in values2: #ex: (7,10)
                    if value2[0] >= value1[0] and value2[1] <= value1[1]:
                        sorteddic[key2].pop(sorteddic[key2].index(value2))
        onlybigs.setdefault(key1, sorteddic.pop(key1))
        break

#and a second clean in the end
readydic = clean(onlybigs)

This last step especially is taking too long because it compares each value for each key and my guess is the whole process can be done more efficiently somehow.

Any insights?

Answer 1

You're doing things the hard way.

dic = {}
for p1 in range(len(seq)):
    for p2 in range(p1+1,len(seq)):
        dic.setdefault(tuple(seq[p1:p2]), []).append((p1,p2))

For each range, you are calling .setdefault(). You should just use a default dictionary, which can automatically create a list for any unseen keys:

from collections import defaultdict

dic = defaultdict(list)

for p1 in range(len(seq)):
    for p2 in range(p1 + 1, len(seq)):
        dic[tuple(seq[p1:p2])].append((p1, p2))

---

Next, you're filtering the dictionary the hard way.

cleandic = {}
for key, value in dic.items():
    if len(value) > 1:
        cleandic.setdefault(key,value)

This can be expressed in one line, using list comprehension:

cleandic = { key: val for key, val in dic.items() if len(val) > 1 }

---

The next improvement comes from noting that the key portion of (-2, 3): [(0, 2), (2, 4)]} is completely recoverable from the value portion; using (0, 2) or (2, 4) as a slice of seq will return the appropriate sequence. You do not need to maintain a dictionary; a list of lists is sufficient and less complex. Instead of cleandic, you can have:

groups = [ val for val in dic.values() if len(val) > 1 ]

Instead of removing the second of these two dictionary values:

#(1,4,-5,1,4,-5) : [(7,13),(10,16)]
#(1,4,-5) : [(7,10),(10,13)]

You now just need to remove the second of these two list entries:

[(7,13),(10,16)]
[(7,10),(10,13)]

---

You can still sort this by noting that (7,13) represents a sequence of length 6.

groups = sorted(groups, key=lambda item: item[0][1] - item[0][0], reverse=True)

---

Any time you have to .copy() is good time to stop and think if there is another way to solve the problem.

    for key2, values2 in sorteddic.copy().items():
        ...
                  sorteddic[key2].pop(sorteddic[key2].index(value2))

Here, you are modifying sorteddic inside the loop, so you clearly can't loop on the sorteddic itself, which explains the need to copy the dictionary first. Since the copy is itself in another loop, you are doing a lot of copies!

Moreover, this isn't even a loop! It is just a way to extract the first item from the dictionary.

for key1, values1 in sorteddic.items():
    ...
    break

Rework the algorithm to not modify the container you're looping over:

def subset_of(long_groups, group):
    return any(lg[0] <= g[0] and g[1] <= lg[1] for long_group in long_groups
               for lg in long_group for g in group)

...

longest_groups = []
for group in groups:
    if not subset_of(longest_groups, group):
        longest_group.append(group)

Finally, you can rebuild your dictionary with the sequence tuples as keys:

readydic = { tuple(seq[group[0][0]:group[0][1]]): group for group in longest_groups }

Since all the dictionary copying has been removed, this should be significantly faster.

Answer 2

Optimized version

The crucial function can be thought through 3 phases:

Aggregating dictionary of sequential recurrences

As was correctly mentioned defaultdict(list) is a more performant alternative to dic.setdefault.
Besides of that, as you've mentioned, input list could be of length 300. In that case the initial approach will evaluate len(seq) 44850 times.
To optimize that we'll store the size of the input sequence in a separate variable seq_size = len(seq) and refer it in subsequent loops.

---

Filtering out entries that weren't recurred (occurred once) with ordering

Instead of defining clean inner function and generating a redundant dictionary cleandic - both filtering and sorting can be performed in one pass:

d = dict(sorted(((k, v) for k, v in d.items() if len(v) > 1),
                key=lambda x: len(x[0]), reverse=True))

---

Filtering out entries that are part (included) of other longer sequences

Instead of falling into a numerous noisy loops - a string membership trick can be applied. It's based on the idea of presenting string representations of short and long sequences as a "needle" and "haystack".
It looks as: " 1 4 -5 " in " 1 4 -5 1 4 -5 ".
Trailing spaces prevent incorrect matches like "1 4 -5" in "1 4 -55 11 4 -5" (which would be truthy)

---

The new implementation is placed into a function called find_recurrences.
(I've moved the old implementation into function find_recurrences_old for comparison)

from collections import defaultdict


def find_recurrences(seq):
    seq_size = len(seq)
    d = defaultdict(list)

    for i in range(0, seq_size):
        for j in range(i + 1, seq_size):
            d[tuple(seq[i:j])].append((i, j))

    d = dict(sorted(((k, v) for k, v in d.items() if len(v) > 1),
                    key=lambda x: len(x[0]), reverse=True))
    d_copy = d.copy()

    for k, v in d_copy.items():
        if k not in d:
            continue
        k_str = f" {' '.join(map(str, k))} "
        for k_ in d.keys() - set([k]):
            if f" {' '.join(map(str, k_))} " in k_str:
                del d[k_]

    return d

---

Ensuring that both functions return the same result:

In [79]: seq = [-2, 3, -2, 3, 5, 3, 7, 1, 4, -5, 1, 4, -5, 1, 4, -5]                                                         

In [80]: find_recurrences_old(seq)                                                                                           
Out[80]: {(1, 4, -5, 1, 4): [(7, 12), (10, 15)], (-2, 3): [(0, 2), (2, 4)]}

In [81]: find_recurrences(seq)                                                                                               
Out[81]: {(1, 4, -5, 1, 4): [(7, 12), (10, 15)], (-2, 3): [(0, 2), (2, 4)]}

---

But the new version has time performance advantage:

In [84]: %timeit find_recurrences_old(seq)                                                                                   
97.3 µs ± 212 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [85]: %timeit find_recurrences(seq)                                                                                       
80.5 µs ± 154 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 3

Use collections.defaultdict() rather than dict.setdefault().

Instead of nested loops to find subsequence, keep a dict mapping items to their positions. For each item in the sequence check if that item was in the sequence before. If it is, only check for subsequences starting at those positions. I think on average, this will do better than the nest loops:

seen_items = defaultdict(list)

for pos, item in enumerate(sequence):
    if item in seen_items:
        for other_pos in seen_items[item]:
            ...check for matching subsequences starting at pos and other_pos
            ...and add them to the dict of sequences...

    seen_items[item].append(pos)