4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ You have 3-2 in your seq list. Is this a subtraction, or are you missing a comma? \$\endgroup\$ – AJNeufeld Nov 22 '19 at 5:34
  • \$\begingroup\$ corrected it and some other mistakes in the code \$\endgroup\$ – Thiago Luiz Nov 22 '19 at 5:42
  • \$\begingroup\$ @ThiagoLuiz, the final readydict have lost indexes for the most items {(1, 4, -5, 1, 4): [(7, 12), (10, 15)], (1, 4, -5, 1): [], (4, -5, 1, 4): [], (1, 4, -5): [], (4, -5, 1): [], (-5, 1, 4): [], (-2, 3): [(0, 2), (2, 4)], (1, 4): [(13, 15)], (4, -5): [], (-5, 1): [], (-2,): [], (3,): [(5, 6)], (1,): [], (4,): [], (-5,): []} <-- empty lists. Is it not working as expected yet? \$\endgroup\$ – RomanPerekhrest Nov 22 '19 at 6:06
  • \$\begingroup\$ sorry, i just did cleandic = {} for key, value in dic.items(): if len(value) > 1: cleandic.setdefault(key,value) again at the end \$\endgroup\$ – Thiago Luiz Nov 22 '19 at 6:09
  • \$\begingroup\$ @ThiagoLuiz, but you have readydic, not dic at the end. Please fix and update your code \$\endgroup\$ – RomanPerekhrest Nov 22 '19 at 6:10
4
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I don't think my example seq was great, because I have to keep smallers that happens outsite the biggers even if they same the same numbers. So here seq = [1,2,3,4,5,6,0,1,2,3,4,5,6,1,2,3,1,2,3,0] the (1,2,3) in the end has to be in readydic. I adapted your code to do this, is it ok if I answer my question with that? And one more question, turning values to list and back do dict doesn't become a time problem with biggers dicts? \$\endgroup\$ – Thiago Luiz Nov 23 '19 at 15:25
  • \$\begingroup\$ From What should I do when someone answers my question?, in particular the Posting a self-answer section, you are allowed to post a self answer, but it "must meet the standards of a Code Review answer, just like any other answer. Describe what you changed, and why. Code-only answers that don't actually review the code are insufficient and are subject to deletion". Alternately, you could post a new follow-up question, cross-linking one to the other, showing what you've done and why, inviting addition code review feedback. \$\endgroup\$ – AJNeufeld Nov 23 '19 at 20:50
  • \$\begingroup\$ There is a performance impact with converting dictionary values to a list, and later turning the list back into a dictionary. However, there is a much, much larger impact repeatedly copying the dictionary once for every entry in the dictionary. A dictionary is a more complex data structure than a list; if you are merely iterating over all entries in the container, using a list instead of a dictionary will not be slower and might be slightly faster. If you want to leave the container as a dictionary, that can work; the important aspect is removing the repeated copies. \$\endgroup\$ – AJNeufeld Nov 23 '19 at 21:06
3
\$\begingroup\$

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)
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ checking your answer I found a +1 mistake in my code that got into yours. Edit was to short, in the first loop should be for j in range(i + 1, seq_size+1): Your code is a big improvement on mine but it gives a different result, the list i gave as exemple just doesn't show it. Try this: seq2 = [1,2,3,4,5,6,0,1,2,3,4,5,6,1,2,3,1,2,3] my code results: {(1, 2, 3, 4, 5, 6): [(0, 6), (7, 13)], (1, 2, 3): [(13, 16), (16, 19)]} your code results: {(1, 2, 3, 4, 5, 6): [(0, 6), (7, 13)]} The cause is the "needle" and "haystack" part. Again, big improvement \$\endgroup\$ – Thiago Luiz Nov 23 '19 at 2:16
0
\$\begingroup\$

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)
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.