This is my current code:def search(word,source):    places = []    for x in range(0,len(source)):        if source[x] == word[0]:            if source[x:x+len(word)] == word:                places.append(x)    return places    How would I optimize this without using regular expressions?
Searching text for a string
python;algorithm;strings;regex;search
Using timeit to time the function running over 1000 iterations, as follows:import timeitdef search(word=None,source=None):    word = is    source = Lorem Ipsum is simply dummy text    places = []    for x in range(0, len(source)):        if source[x] == word[0]:            if source[x:x + len(word)] == word:                places.append(x)    return placesprint timeit.timeit(search, number=1000)This code gives us the following results (over 4 runs):0.2590000629430.122999906540.1749999523160.0520000457764So, we'll use that as our baseline for improvement (further runs stay constant around .052/1000). Let's grab the low hanging fruit - caching the len calls:import timeitdef search(word=None,source=None):    word = is    source = Lorem Ipsum is simply dummy text    places = []    len_word = len(word)    len_source = len(source)    for x in range(0, len_source):        if source[x] == word[0]:            if source[x:x + len_word] == word:                places.append(x)    return placesprint timeit.timeit(search, number=1000)Improvement:0.05199984931950.0470001697540.04999995231630.0490000247955Now, what happens if we get rid of places and just return once we find the string, as follows:import timeitdef search(word=None,source=None):    word = is    source = Lorem Ipsum is simply dummy text    len_word = len(word)    len_source = len(source)    for x in range(0, len_source):        if source[x] == word[0]:            if source[x:x + len_word] == word:                return xprint timeit.timeit(search, number=1000)Well, this happened:0.03499984741210.02999997138980.02799987792970.0279998779297Nice! But wait, there's more! We can just use Python built ins:import timeitdef search(word=None,source=None):    word = is    source = Lorem Ipsum is simply dummy text    return source.lower().find(word.lower())print timeit.timeit(search, number=1000)to halve the time it took us with the brute force approach:0.01400017738340.01499995994570.01200008392330.0110000114441These are the two final products, one brute force, and one using built ins, and both return the same int value when a word is found:def search(word,source):    len_word = len(word)    len_source = len(source)    for x in range(0, len_source):        if source[x] == word[0]:            if source[x:x + len_word] == word:                return xdef search(word,source):    return source.lower().find(word.lower())::EDIT::In regards to the comment (not same as OPs code), turn the function into an iterator rather than returning a list. This will give you the speed boost of the prior code, and still give you all the places of occurrence:def search(word,source):    len_word = len(word)    len_source = len(source)    for x in range(0, len_source):        if source[x] == word[0]:            if source[x:x + len_word] == word:                yield xfor occurrence in search():    print occurrence EDIT::: Getting rid of if source[x] == word[0] also gives us a nice speedup:def search(word,source):    len_word = len(word)    len_source = len(source)    for x in range(0, len_source):        if source[x:x + len_word] == word:                yield xEDIT:::Another quick win, caching the first chars:def search(word,source):    places = []    len_word = len(word)    len_source = len(source)    first_char = word[0]    for x in range(0, len_source):        if source[x] == first_char:            if source[x:x + len_word] == word:                places.append(x)    return places