How efficient is list.index(value, start, end)?
<p>Today I realized that python's <code>list.index</code> can also take an optional <code>start</code> (and even <code>end</code>) parameter.</p>

<p>I was wondering whether or not this is efficiently implemented and which of these two is better:</p>

<pre><code>pattern = "qwertyuytresdftyuioknn"
words_list = ['queen', 'quoin']
for word in words_list:
    i = 1
    for character in word:
        try:
            i += pattern[i:].index(character)
        except ValueError:
            break
        else:
            yield word
</code></pre>

<p>or</p>

<pre><code>pattern = "qwertyuytresdftyuioknn"
words_list = ['queen', 'quoin']
for word in words_list:
    i = 1
    for character in word:
        try:
            i = pattern.index(character, i)
        except ValueError:
            break
        else:
            yield word
</code></pre>

<p>So basically <code>i += pattern[i:].index(character)</code> vs <code>i = pattern.index(character, i)</code>. </p>

<p>Searching for this on <em>generic_search_machine</em> returns nothing helpful, except a lot of beginner tutorials trying to teach me what a list is.</p>

<p><strong>Background:</strong>
This code tries to find all words from <code>words_list</code> which match <code>pattern</code>. <code>pattern</code> is a list of characters a user entered by swiping over the keyboard, like on most modern mobile device's keyboards. </p>

<p>In the actual implementation there is the additional requirement that the returned word should be longer than 5 characters and the first and last character have to exactly match. These lines are omitted here for brevity, since they are trivial to implement.</p>

<p>This calls a built-in function implemented in C:</p>

<pre><code>i = pattern.index(character, i)
</code></pre>

<p>Even without looking at the <a href="https://hg.python.org/cpython/file/v3.5.2/Objects/listobject.c#l2147" rel="nofollow">source code</a>, you can always assume that the underlying implementation is smart enough to implement that efficiently, i.e. that it does not look at the first <code>i</code> values in the list.</p>

<p>As a rule of thumb, using a built-in functionality is <em>always</em> faster than (or at least as fast as) the best thing you can implement yourself.</p>

<p><strong>The attempt to make it better:</strong></p>

<pre><code>i += pattern[i:].index(character)
</code></pre>

<p>This is deffinitely worse. It makes a <strong>copy of</strong> <code>pattern[i:]</code> and then looks for <code>character</code> in it.</p>

<p>So, in the worst case, if you have a <code>pattern</code> of 1 GB and <code>i=1</code>, this copies 1 GB of data in memory in attempt to skip the first element (which whould have been skipped anyway).</p>

python list indexof