0

What is the fastest way to search a list whether or not it has an element that begins with a specified string, and then return the index of the element if it's found.

Something like:

mylist=['one','two','three','four']
mystring='thr'

It should return 2.

David
  • 1
  • 3
  • 1
    The fastest way is to not use Python for this task. So would reasonably fast and readable be enough? – timgeb Mar 15 '18 at 21:32
  • How many times will you be searching vs. how often the list is changed? – Mark Ransom Mar 15 '18 at 21:34
  • 1
    Show what you have and we'll tell you if it can be improved. Better yet: if you have working code, ask on [codereview.se] as they specialize in improving working code, not fixing broken code as is done here. – Jongware Mar 15 '18 at 21:34
  • @timget et all, only 1 time search, the list won't be changed, i would like the best method for python, i dont use other languages, so the reasonably fastest method that is available for python3.x would satisfy, thanks! – David Mar 16 '18 at 19:03

5 Answers5

2

You can't get better than O(n) complexity here, but generally speaking if you are after pure speed then don't even use Python.

The canonical Python solution I would propose is to use a memory efficient generator and call next on it once.

>>> mylist = ['one','two','three','four']
>>> mystring = 'thr'
>>> next(index for index, item in enumerate(mylist) if item.startswith('thr'))
2

By default, this will give you a StopIteration exception if the condition is never satisfied. You can provide a second argument to next if you want a fallback-value.

timgeb
  • 76,762
  • 20
  • 123
  • 145
0

indices = [i for i, s in enumerate(mylist) if s.startswith('thr')]
Enumerate is slightly faster

Sagar Ruchandani
  • 95
  • 6
0

If you are going to do more than a single search, you can organize the list in a way to get better than O(n) execution time for each search. Obviously if you're only doing a single search the overhead of reorganizing the list will be prohibitive.

import bisect
mylist.sort()
n = bisect.bisect_left(mylist, mystring)
if n >= len(mylist) or not mylist[n].startswith(mystring):
    print('not found')

If you need to preserve the original order it's only a little more complicated.

mysorted = sorted((s,i) for i,s in enumerate(mylist))
n = bisect.bisect_left(mysorted, (mystring, 0))
if n >= len(mysorted) or not mysorted[n][0].startswith(mystring):
    print('not found')
else:
    n = mysorted[n][1]
Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
0

Just running a counter should do you fine

i = 0
mylist = ['one','two','three','four']
mystring = 'thr'
for x in mylist:
    if mystring in x:
       i = i + 1
       print (i)
    else:
       i = i + 1

Although this will print '3' and not '2'.

I hope this helps.

Vishvas Chalishazar
  • 1
  • 1
  • Try changing `mystring = 'hr'`. It does not need to begin with for using `in` function. – niraj Mar 15 '18 at 22:30
-1
mystring='thr'
[n for (n,item) in enumerate(mylist) if item.startswith(mystring)][0]
Out: 2
PythonCA
  • 7
  • 4