DjangoBB LoFi version

Найти - Пользователи

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

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

1 2 3

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 работает потому что длину считает перебором элементов, при этом вы отказываетесь от возможно реализованных авторами контейнера более эффективных способов определения длины.

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'

py.user.next

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

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

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

Manu_Vilks.Py

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

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

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