← Сtrl

doza_and · Июль 18, 2015 13:54:28

Мне кажется вы со своими мудрствованиями запутаете коллег.

py.user.next
А randint() требует вычисления длины - операция по времени такая же, как и поиск

Для большинства последовательностей это очевидно не так.

import time
L=1000000
li=list(range(L))
########
t0=time.clock()
a=len(li)
t1=time.clock()
print("len")
print(t1-t0)
########
t0=time.clock()
a=li[L/2]
t1=time.clock()
print("index")
print(t1-t0)
########
t0=time.clock()
a=li.index(L/2)
t1=time.clock()
print("linear search")
print (t1-t0)
########
t0=time.clock()
for i,v in enumerate(li):
    pass
t1=time.clock()
print("enumerate")
print (t1-t0)import time

len
3.2163095698e-06
index
2.03719608012e-06
linear search
0.0106376918778
enumerate
0.104751248308

py.user.next
А у некоторых последовательностей вообще длина не вычисляется

Да, запросто можно представить такую последовательность (которые конечно не имеют отношения к тому что спрашивал ТС, поскольку у него явно указан tuple).

Например интересно как ваш алгоритм будет работать с такой последовательностью:

from itertools import cycle
tuple(enumerate(cycle("123")))

enumerate работает потому что длину считает перебором элементов, при этом вы отказываетесь от возможно реализованных авторами контейнера более эффективных способов определения длины.

Отредактировано doza_and (Июль 18, 2015 13:55:36)

py.user.next · Июль 19, 2015 02:08:20

doza_and
Мне кажется вы со своими мудрствованиями запутаете коллег.

Я ему говорю, как оно будет дальше развиваться. А дальше он будет делать функцию, которая всё это инкапсулирует. А когда делаешь функцию, нужно оставлять как можно меньше ограничений у формальных параметров.

А если функцию не делать, рано или поздно столкнёшься с нехваткой имён. Функция действует как пространство имён - даёт возможность не выдумывать имена, потому что удобные заняты.

doza_and
Для большинства последовательностей это очевидно не так.

Алгоритмически равно O(n) как вычисление длины, так и поиск элемента. Получается двухпроходный алгоритм O(2n). А если ещё и операцию сравнения при поиске учитывать - то O(3n).

enumerate - это быстрее, чем len + index. Допустим, там миллион слов; пока ты будешь длину вычислять, потом выбирать случайное слово, а потом искать индекс этого слова (который не совпадёт ещё с выбранным, если там одинаковые слова есть), enumerate уже даст ответ - слово и его правильный индекс.

doza_and

len
3.2163095698e-06
index
2.03719608012e-06
linear search
0.0106376918778
enumerate
0.104751248308

Там это время ушло на цикл for, который неявно вызывает ещё функции.

Вот сравнение:

#!/usr/bin/env python3
 
import timeit
 
 
def f1():
    import random
 
    WORDS = ("питон", "мышь", "кислород", "карандаш", "ответ", "стакан")
    index, word = random.choice(tuple(enumerate(WORDS)))
 
def f2():
    import random
 
    WORDS = ("питон", "мышь", "кислород", "карандаш", "ответ", "стакан")
    iword = random.randint(0, len(WORDS) - 1)
    word = WORDS[iword]
    iword, word
 
 
def main():
    t1 = timeit.Timer('f1()', 'from __main__ import f1')
    t2 = timeit.Timer('f2()', 'from __main__ import f2')
 
    for t in t1, t2:
        print(t.repeat(3, 10000))
 
if __name__ == '__main__':
    main()

[guest@localhost py]$ ./timecmp.py 
[0.07288823899943964, 0.06414823500017519, 0.06307941100021708]
[0.05327650500021264, 0.051950771000520035, 0.05130656600067596]
[guest@localhost py]$

Так что то якобы десятикратное преимущество над enumerate - это просто for.

doza_and
Да, запросто можно представить такую последовательность (которые конечно не имеют отношения к тому что спрашивал ТС

Ну, типа функции ему писать не надо, пусть это остаётся на уровне кода новичка.

doza_and
поскольку у него явно указан tuple

Функция должна быть общей, то есть быть применимой в как можно большем числе случаев. Это ослабление предусловия.

Допустим, туда подаётся множество. Да, у которого нет .index() ;)
Мой enumerate сработает, твой len + index - нет.

>>> import random
>>> 
>>> def f1():
...     WORDS = {"питон", "мышь", "кислород", "карандаш", "ответ", "стакан"}
...     index, word = random.choice(tuple(enumerate(WORDS)))
...     return index, word
... 
>>> def f2():
...     WORDS = {"питон", "мышь", "кислород", "карандаш", "ответ", "стакан"}
...     iword = random.randint(0, len(WORDS) - 1)
...     word = WORDS[iword]
...     return iword, word
... 
>>> f1()
(3, 'кислород')
>>> f2()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in f2
TypeError: 'set' object does not support indexing
>>>

Кажется, я с помощью своей функции смог найти случайное слово, а индекс можно только отбросить. Хоть это и можно было бы сделать через random(), а вдруг там бы была другая функция, аналога которой в библиотеке нет?

doza_and
enumerate работает потому что длину считает перебором элементов

Не, он вообще длину не ищёт, это просто зипование чисел с элементами последовательности.

doza_and
Например интересно как ваш алгоритм будет работать с такой последовательностью:

А в таком случае оба не будут подходить, потому что невозможно вернуть последний элемент (если он случайный) бесконечной последовательности и его индекс. Индекс равен бесконечности.

doza_and · Июль 19, 2015 09:11:10

py.user.next
Функция должна быть общей, то есть быть применимой в как можно большем числе случаев.

Да это сложный архитектурный выбор. Приходится или ограничивать общность или жертвовать быстродействием. Редко когда удается совместить оба варианта.

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import timeit
def f1():
    import random
    WORDS = ("питон", "мышь", "кислород", "карандаш", "ответ", "стакан")*1000
    index, word = random.choice(tuple(enumerate(WORDS)))
def f2():
    import random
    WORDS = ("питон", "мышь", "кислород", "карандаш", "ответ", "стакан")*1000
    iword = random.randint(0, len(WORDS) - 1)
    word = WORDS[iword]
    iword, word
def main():
    t1 = timeit.Timer('f1()', 'from __main__ import f1')
    t2 = timeit.Timer('f2()', 'from __main__ import f2')
 
    for t in t1, t2:
        print(t.repeat(3, 10000))
 
if __name__ == '__main__':
    main()

[6.969264377437743, 7.330539255925593, 6.922474260426043]
[0.38192501650165056, 0.38119296129612934, 0.3821524152415243]

Да я усилил ограничения на применимость. Требуется __getitem__ и __len__ . Но это операции которые обычно имеют трудоемкость O. А enumerate и, наверное, tuple имеют трудоемкость О где N Длина последовательности. В вашем примере основное время тратится на вызовы функций. Поэтому разницы нет.

py.user.next
Так что то якобы десятикратное преимущество над enumerate - это просто for.

Кстати замечу что в моем посте разница не 10 а 10000 раз. Поскольку последовательность размером в миллион элементов.

Какой вариант выбрать зависит от того что собирается делать пользователь. Если будут последовательности длинной до сотни элементов, то enumerate пойдет.

:) Объект Монстр

import random
class Tx:
    def __init__(self,m):
        self.m=m
    def __getitem__(self,i):
        return str(i*self.m)
obj = Tx(3)
def get_randelm(obj):
    try:
        L=obj.len()
    except:
        L = 0xffffffff # :( Хак
    return obj[random.randint(0, L)]
obj = Tx(3)
>>> get_randelm(obj)
'11432516094'

Отредактировано doza_and (Июль 19, 2015 09:47:37)

py.user.next · Июль 20, 2015 05:58:24

doza_and
и, наверное, tuple имеют трудоемкость О где N Длина последовательности

Основное замедление происходит из-за tuple. Это повторное создание входного списка.
Похоже, что enumerate здесь не подходит, потому что choice всегда выполняет внутреннее вычисление длины, а у итератора она неизвестна.

Отредактировано py.user.next (Июль 20, 2015 05:58:58)

Manu_Vilks.Py · Авг. 30, 2015 15:09:31

import random
WORDS = (“питон”, “мышь”, “кислород”, “карандаш”, “ответ”, “стакан”)
print(“Индекс случайно выбранного элемента:”,WORDS.index(random.choice(WORDS)))

Вот так просто будет

Отредактировано Manu_Vilks.Py (Авг. 30, 2015 15:17:43)

Python-сообщество

Уведомления

#1 Июль 18, 2015 13:54:28

Как узнать индекс случайно выбранного элемента последовательности?

#2 Июль 19, 2015 02:08:20

Как узнать индекс случайно выбранного элемента последовательности?

#3 Июль 19, 2015 09:11:10

Как узнать индекс случайно выбранного элемента последовательности?

#4 Июль 20, 2015 05:58:24

Как узнать индекс случайно выбранного элемента последовательности?

#5 Авг. 30, 2015 15:09:31

Как узнать индекс случайно выбранного элемента последовательности?

Board footer