5

Given a string, typically a sentence, I want to extract all substrings of lengths 3, 4, 5, 6. How can I achieve this efficiently using only Python's standard library? Here is my approach, I am looking for one which is faster. To me it seems the three outer loops are inevitable either way, but maybe there is a low-level optimized solution with itertools or so.

import time

def naive(test_sentence, start, end):
    grams = []
    for word in test_sentence:
        for size in range(start, end):
            for i in range(len(word)):
                k = word[i:i+size]
                if len(k)==size:
                    grams.append(k)
    return grams

n = 10**6
start, end = 3, 7
test_sentence = "Hi this is a wonderful test sentence".split(" ")

start_time = time.time()
for _ in range(n):
    naive(test_sentence, start, end)
end_time = time.time()

print(f"{end-start} seconds for naive approach")

Output of naive():

['thi', 'his', 'this', 'won', 'ond', 'nde', 'der', 'erf', 'rfu', 'ful', 'wond', 'onde', 'nder', 'derf', 'erfu', 'rful', 'wonde', 'onder', 'nderf', 'derfu', 'erful', 'wonder', 'onderf', 'nderfu', 'derful', 'tes', 'est', 'test', 'sen', 'ent', 'nte', 'ten', 'enc', 'nce', 'sent', 'ente', 'nten', 'tenc', 'ence', 'sente', 'enten', 'ntenc', 'tence', 'senten', 'entenc', 'ntence']

Second version:

def naive2(test_sentence,start,end):
    grams = []
    for word in test_sentence:
        if len(word) >= start:
            for size in range(start,end):
                for i in range(len(word)-size+1):
                    grams.append(word[i:i+size])
    return grams
Improve this question
5
  • What's the expected output for your example string? Commented Dec 9, 2021 at 20:29
  • 1
    The len(k)==size check can be eliminated - the only way that can fail is if you start your slice at a point too close to the end of the sentence, but that could be better handled by reducing the range of the for i loop. Also, do you really need all of the substrings to exist at the same time, in a list? Memory usage could be vastly reduced by yielding them one at a time in a generator function. Commented Dec 9, 2021 at 20:34
  • Memory is not a problem for me, time is. Hmm okay thinking about the boundaries .. Commented Dec 9, 2021 at 20:36
  • Woah, I eliminated the length check and moved it to word level and looked for right boundaries. It's twice as fast. Changing the code. Commented Dec 9, 2021 at 20:48
  • Um, {end-start} seconds is not right. Could you fix that and also show your times for the two solutions? Commented Dec 10, 2021 at 21:27

2 Answers 2

Reset to default
4

Well, I think this is not possible to improve the algorithm, but you can micro-optimize the function:

def naive3(test_sentence,start,end):
    rng = range(start,end)
    return [word[i:i+size] for word in test_sentence
                           if len(word) >= start
                           for size in rng
                           for i in range(len(word)+1-size)]

Python 3.8 introduces assignment Expressions that are quite useful for performance. Thus if you can use a recent version, then you can write:

def naive4(test_sentence,start,end):
    rng = range(start,end)
    return [word[i:i+size] for word in test_sentence 
                           if (lenWord := len(word)+1) > start
                           for size in rng
                           for i in range(lenWord-size)]

Here are performance results:

naive2: 8.28 µs ±  55 ns per call
naive3: 7.28 µs ± 124 ns per call
naive4: 6.86 µs ±  48 ns per call    (20% faster than naive2)

Note that half of the time of naive4 is spent in creating the word[i:i+size] string objects and the rest is mainly spent in the CPython interpreter (mainly due to the creation/reference-counting/deletion of variable-sized integer objects).

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

Image
Very nice, I always hated that you can't declare variables in a list comprehension. I like this approach + 20% is really good for my application.
Image
@MarcelB Not sure what you mean, but sounds wrong. You "declare" variables in pretty much every list comprehension. For example word, size and i in the first one here.
Image
@KellyBundy I mean constants which you can reuse as in the example above ...
Image
@MarcelB What constants? And I'd define constants before (i.e., outside of) the list comprehension.
Image
Yeah, I can agree it's opinion-based. For me it also depends on the case. In this case, the whole (lenWord := len(word)+1) > start looks ok (except that the variable name lies about its value). In other cases, I prefer to separate setting the variable from using it. Also, one advantage of the "list" idiom, and the reason it did get optimized after all, is that it doesn't leak the variable to outside the comprehension. Btw, a micro-optimization that I think could have a larger effect is to prepare a list of slice objects for each word length, instead of recreating them all the time.
|
0

I believe this will do it:

test_sentence = "Hi this is a wonderful test sentence".split()

lengths = [3, 4, 5, 6]

result = []
for t in test_sentence:
    for l in lengths:
        if len(t) >= l:
            start = 0
            while start + l <= len(t):
                result.append(t[start:start+l])
                start += 1
Improve this answer

4 Comments

Image
Can you please show that this is indeed faster than the OPs method? It looks similar and would have the same Big O value of n^3
Image
It is exactly as fast as my second approach (tried 10 runs and the values differ marginally every time).
Image
@MatthewBarlowe from theoretical perspective I'm not sure there is too much to optimize. It might be more of a library thing here.
Image
If you're really looking for performance, you're probably best of writing it in C and just using Python as a wrapper.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.