DjangoBB LoFi version

Полная версия: есть ли более быстрый вариант поиска по массиву с туплами?

Начало » Python для новичков » есть ли более быстрый вариант поиска по массиву с туплами?

test157

Авг. 13, 2009 06:30:07

всем привет у меня вот такого вида массив:

arr = [(1,2,3), (4,5,6), (8,9,10)]

как мне проверить быстро - содержит ли второй столбец нужное мне значение или нет? сейчас делаю вот так:

if [v for v in arr if v[1] == 5]:
    do_here_something()

но почемуто запали сомнения что есть более элегантное решение, или это нормальная практика? вот так проверять?

поидее ведь это не очень эффективно, если элементов много нам достаточно выходит на первом а он будет постоянно весь лист сканировать - ну и както длинно это ИМХО.

т.е. желательно аналог .index() или .find() - только который умеет работать вот с такими данными, а сейчас у меня получается почти аналог count() тока длинный и некрасивый, и вместо кол-ва сами элементы )

Андрей Светлов

Авг. 13, 2009 10:16:22

нет. Быстро не сделать, линейного времени поиска для списка не избежать. Мелкие ухищрения по крупному не помогут.
.index и .find - тоже имеют линейную алгоритмическую сложность
Возможно, лучше использовать другой тип данных?

Прямой ответ:

if 5 in (i[1] for i in lst):
    do()

pasaranax

Авг. 13, 2009 12:29:50

А если классически, вот так, то это не быстрее будет?

for v in arr:
    if v[1] == 5: 
        do_here_something()

Эти встроенные в списки циклы одинаковы по скорости с такими многословными (не pythonic?) вариантами?

Андрей Светлов

Авг. 13, 2009 14:03:46

так - медленнее. И довольно ощутимо.
Но все же, как я говорил: если необходим поиск, используйте set или dict.
Кстати, в collections от Python 3.1 появился OrderedDict. Поскольку класс реализован на Питоне - можно его выдернуть и для более старых версий.

>>> from timeit import Timer
>>> import random
>>> l = [(str(i), i) for i in xrange(10000)]
>>> random.shuffle(l)
>>> s1 = 'if 5 in (i[1] for i in l): pass'
>>> t1 = Timer(s1, 'from __main__ import l')
>>> t1.timeit(1000)
0.59166409417957766
>>> s2 = 'if 5 in (i[1] for i in l): break'
>>> t2 = Timer(s2, 'from __main__ import l')
>>> t2.timeit(1000)
0.0012608446045305755
>>> s3 = '''
... for v in l: 
... 	if 5 == v[1]: 
... 		pass
... 	'''
... 
>>> t3 = Timer(s3, 'from __main__ import l')
>>> t3.timeit(1000)
0.91812171658693842
>>> s4 = '''
... for v in l: 
... 	if 5 == v[1]: 
... 		break
... 	'''
>>> t4 = Timer(s4, 'from __main__ import l')
>>> t4.timeit(1000)
0.49133507191561421
>>>

test157

Авг. 13, 2009 20:34:27

а как это БРЕЙК в ифе? у меня на такую конструкцию питон 2.5 ругается

if 5 in (i[1] for i in l): break

Андрей Светлов

Авг. 14, 2009 15:27:49

Эт я слегка глюканул - так можно было писать только в контексте timeit. По хорошему Timer должен был дать мне по рукам - но не дал.

bazooka

Авг. 14, 2009 17:03:19

походу break выкидывает из цикла таймера

    >>> s2 = 'if 5 in (i[1] for i in l): break'
    >>> s22 = 'if 5 in (i[1] for i in l): pass'
    >>> t2 = Timer(s2, 'from __main__ import l')
    >>> t2.timeit(1000)
    0.0017299652099609375
    >>> t2.timeit(1000000000)
    0.0017070770263671875
    >>> t2 = Timer(s22, 'from __main__ import l')
    >>> t2.timeit(1000)
    1.6248788833618164