2
\$\begingroup\$

The exercise i am working on requires me to read a binary sequence stored in a text file. The objective is to find the occurrences of all subsequences of length between a and b (their values are given in the function parameters) and put them in a list of tuples.

For example: If the following binary sequence is given as input and the length of each subsequence should be between 2 and 4:

a = 2 
b = 4 

01010010010001000111101100001010011001111000010010011110010000000

I should write a program to generate the following output:

[(1, ["1011", "1101"]), 
 (2, ["0101", "0110", "1010"]), 
 (3, ["0111", "101", "1110", "1111"]), 
 (4, ["0001", "0011", "1100"]), 
 (5, ["011", "1000", "110"]), 
 (6, ["0000", "111"]), 
 (7, ["0010", "1001"]), 
 (8, ["0100"]), 
 (10, ["010"]), 
 (11, ["000", "001", "11"]), 
 (12, ["100"]),            
 (15, ["01", "10"]), 
 (23, ["00"] )]

You will notice that each tuple in the list has two elements. The first element is the number of times a subsequence appears in the given sequence whilst the second element is the list containing the corresponding subsequences.

E.g. the first tuple indicates that the subsequences "1011" and "1101" appear only once in the given sequence.

The solution i have written does solve the problem (it passes all correctness tests), but it is slow and doesn't pass the performance tests (it only passes 5 out of 22 tests) in which the maximum timeout is set to 1 second. How could i make this solution faster?

I am not allowed to import any external libraries.

def ex1(ftesto,a,b,n):
    with open(ftesto,encoding='utf8') as f: 
        S = f.read().replace('\n','')
    N = len(S)
    D = {} 
    subsequences = {} 
    for i in range(N+1):
        for j in range(i+1,N+1): 
            if a <= len(S[i:j]) <= b: 
                if S[i:j] not in D:
                    D[S[i:j]] = 1   
                else:
                    D[S[i:j]] += 1                     
    for k,v in D.items(): 
        subsequences.setdefault(v,[]).append(k)
    result = sorted([(k,sorted(v)) for k,v in subsequences.items()])   
    return result[:n] 

if __name__ == '__main__':
    
   ftesto = 'ft1.txt'
   a = 2
   b = 4
   n = 20

The amount of elements in the list must be equal or less than "n". That explains why i am using the slicing at the end of the function.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ from which range are the values a, b, n and the length of the 01-string \$\endgroup\$
    – miracle173
    Feb 18 at 9:27
  • \$\begingroup\$ read the post please \$\endgroup\$
    – alex108
    Feb 18 at 10:54
  • 1
    \$\begingroup\$ so a=2, b=4 and the string is 01010010010001000111101100001010011001111000010010011110010000000 and this takes more than one second to calculate the result? \$\endgroup\$
    – miracle173
    Feb 18 at 12:42
  • \$\begingroup\$ @miracle173 It takes much longer time if a very long sequence is given as input. That's why i need to improve efficiency \$\endgroup\$
    – alex108
    Feb 19 at 10:27
  • \$\begingroup\$ that's why I want to know how long the sequence can be \$\endgroup\$
    – miracle173
    Feb 19 at 13:32
3
\$\begingroup\$

PEP 8

You are violating several Style Guide for Python Code rules:

  • commas should be followed by a space,
  • variables should be snake_case,
  • always surround binary operators with one space

Never called

ex1() is never called by your mainline.

Declare variables closer to where they are used

subsequences is declared 7 lines earlier than it needs to be.

Separate I/O from processing

ex1() cannot be called with test data, unless that test data is in a file. Use two functions. One that solves the problem with an in-memory string, and a second that reads the string from a file for processing.

Avoid dict.setdefault(...)

subsequences.setdefault(v, []).append(k) will create a new list ([]) every time it is executed. Many times this default will never be used, and must be garbage collected. This is just wasting time.

Instead, use collections.defaultdict. Note that collections is not an external library; it is internal, built into Python.

Counter

Similarly, use collections.Counter for counting objects. Again, built into Python; not an external library.

Reworked Code


from collections import Counter, defaultdict

def binary_sequence_counts(sequence, shortest, longest, limit):
    n = len(sequence)

    sequence_counter = Counter()
    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            if shortest <= len(sequence[i:j]) <= longest:
                sequence_counter[sequence[i:j]] += 1

    subsequences = defaultdict(list)
    for subsequence, count in sequence_counter.items():
        subsequences[count].append(subsequence)

    result = sorted((count, sorted(subseqs)) for count, subseqs in subsequences.items())
    return result[:limit]

def ex1(ftesto, a, b, n):
    with open(ftesto, encoding='utf8') as f:
        sequence = f.read().replace('\n', '')

    return binary_sequence_counts(sequence, a, b, n)

def testcase():
    seq = "01010010010001000111101100001010011001111000010010011110010000000"
    result = binary_sequence_counts(seq, 2, 4, 20)
    # print result, or
    # check if result is correct

The above code is way more readable than the original.

Efficiency

This code is just plain awful:

    for i in range(n + 1):
        for j in range(i + 1, n + 1):
            if shortest <= len(sequence[i:j]) <= longest:
                ...

If your sequence is 100,000 digits long, the inner loop will execute about 5,000,000,000 times! That's a lot! Especially if you're only concerned with subsequences between 2 and 4 digits long, in which case you only need about 300,000 iterations.

A simple modification of the range(...) limits would dramatically improve your speed. If you do it correctly, you can even get rid of the a <= len(...) <= b test, because with the correct ranges you will not be able to generate sequences that are the incorrect length.

In fact, with the correct limits, you could even use the counter to do the counting entirely for you:

sequence_counts = Counter(sequence[i:j]
                          for i in range(...)
                          for j in range(...))

Proper range limits left as exercise to student.

min heap

You are sorting a potentially huge list of values, and then returning only the n-smallest results. sorted(iterable)[:n] This can be a potentially huge waste of time!

Using the heapq.nsmallest(n, iterable) (again, built-in, not an external library), you can reduce the amount of space used, and possibly the amount of time. Note that this is faster only for smaller values of n. If n is big, it can be faster to use sorted(iterable)[:n]. Always profile!

Roll Your Own

The question has been updated to disallow any imports. No problem. We'll just have to implement our own defaultdict and Counter. Assuming your are allowed to create your own class ...

object.__missing__

When a dict.__getitem__ is called, but the dictionary does not contain that key, object.__missing__(self, key) is called. We can use this method to change the behaviour.

Counter

To implement a simple "counter" dictionary, we just need 0 to be returned for any missing key.

class Counter(dict):
    def __missing__(self, key):
        return 0

If the key is missing, 0 is returned. If you "add 1" to a missing key, 0 is returned, 1 is added to the returned value, and the resulting 1 is stored back under that key:

>>> c = Counter()
>>> c['foo']
0
>>> c['bar'] += 1
>>> c['bar'] += 1
>>> c
{'bar': 2}

Notice that the 'foo' key still does not exist; only the 'bar' key exists because values were actually written to it.

defaultdict

You don't actually need a full defaultdict here. You just need a dictionary which returns an empty list when an unknown key is retrieved. Unlike the Counter class above, we need to remember the list that was returned for the key, because we'll be appending items to the list, which (unlike the += operator) won't write the result back into the dictionary.

class DictOfLists(dict):
    def __missing__(self, key):
        self[key] = []
        return self[key]

Unlike the Counter, referencing an unknown key will create the key in the dictionary, filling it with an empty list:

>>> dol = DictOfLists()
>>> dol['foo']
[]
>>> dol['bar'].append("baz")
>>> dol
{'foo': [], 'bar': ['baz']}
>>> 

The actual defaultdict allows you to specify a factory function in the constructor, to create values for the missing keys. That isn't too much more complicated. Feel free to research this.

\$\endgroup\$
6
  • \$\begingroup\$ i really appreciate your answer. I am sorry. I just realized i made a mistake in the description of the exercise. The college teacher has forbidden us to use any libraries which means that we are not even allowed to type import in our code. Hence, the task becomes more difficult. The idea of limiting the range sounds very good. I will try it \$\endgroup\$
    – alex108
    Feb 18 at 8:09
  • \$\begingroup\$ You changed "not allowed to import any external libraries" to "not allowed to import any libraries" which technically is changing the question and invalidates my answer. I will allow the change to stand, but I've added the word "external" back into the question post, but formatted with strikethrough to indicate it was there, and is now removed. \$\endgroup\$
    – AJNeufeld
    Feb 18 at 15:55
  • \$\begingroup\$ Thank you for your answer, but how should i modify the range limits with the counter in order to improve efficiency? \$\endgroup\$
    – alex108
    Feb 18 at 23:26
  • \$\begingroup\$ Hint: If your binary sequence is 10 characters long, and you are looking for subsequences between 2 and 4 characters in length, what is the largest starting index you can possibly use? How did you determine that? What can you say about the ending index when you are at any given starting index. Are there special cases you might have to worry about? Do you have to handle them with separate code, or can you prevent them from occurring somehow? \$\endgroup\$
    – AJNeufeld
    Feb 19 at 1:16
  • \$\begingroup\$ I tried this: sequence_counts = Counter(sequence[i:i+j] for i in range(n-shortest) for j in range(shortest,longest+1)) But i get errors, how do i solve this? \$\endgroup\$
    – alex108
    Feb 19 at 11:16

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.