选择随机元素的最快方法 [英] fastest method to choose a random element

问题描述

您好，

这是一个关于最佳方法的问题（在性能方面仅为
）从列表中选择满足
a某些财产。


这是设置：我需要从列表中选择一个满足给定属性的随机元素

。所有元素都可能具有

属性。大多数情况下，许多元素都会满足

属性，而且评估属性有点贵。元素之间具有属性的
的机会。


一个简单的方法是：


导入随机

def random_pick（a_list，property）：

''''''从列表中返回一个具有属性的随机元素


如果没有元素属性，则返回None

''''''

random.shuffle（a_list）

for a in a_list ：

如果属性（i）：返回我


，但这需要每次洗牌。


第二种方法，如果我们知道列表中至少有一个元素（b / b $ b）具有该属性，则有效：


随机导入

def random_pick（a_list，property）：

''''''从列表中返回一个具有属性的随机元素


循环永远如果没有元素有财产

'''''

而1：

i = random.choice（a_list）

if property（i ）：返回i


如果列表中的许多元素具有

属性并且效率较低（如果只有少数元素），则效率更高（平均）列表有

属性（如果没有元素属性，就会发疯）


还有一个：


随机导入

def random_pick（a_list，property）：

''''''从列表中返回一个具有属性的随机元素

''''''

b_list = [如果属性（x），则x在a_list中为x）

尝试：

返回随机.choice（b_list）

终于：返回没有


但是这个检查了所有元素的属性，这是没有

好。


我不需要强大的随机数，所以一个简单的解决方案如下：

随机导入

globalRNG = random.Random（）


def random_pick（a_list，property）：

''''''从列表中返回一个随机元素该物业


仅当len（a_list）+1为素数时才有效：使用费马的小定理

'''''
a = globalRNG（1，len（a_list））

ind = a
$ x $ b for x in xrange（len（a_list））：

x = a_list [a-1]

如果属性（x）：返回x

ind * = a


但这只有在len（a_list）+1为素数时才有效！现在，如果有一种有效的方法可以找到一个素数给予

而不是一个数字但是不是很大的话，这个可以保存
...


还有其他想法吗？谢谢大家

解决方案

1月4日下午7:55，c ... @ mailinator.com写道：

您好，

这是一个关于从列表中选择随机元素的最佳方法（在性能方面仅为b $ b）的问题那些满足

a某些财产。


这是设置：我需要从列表中选择一个随机元素

满足给定的财产。所有元素都可能具有

属性。大多数情况下，许多元素都会满足

属性，而且评估属性有点贵。元素之间具有属性的
的机会。


一个简单的方法是：


导入随机

def random_pick（a_list，property）：

''''''从列表中返回一个具有属性的随机元素


如果没有元素属性，则返回None

''''''

random.shuffle（a_list）

for a in a_list ：

如果属性（i）：返回我


，但这需要每次洗牌。


第二种方法，如果我们知道列表中至少有一个元素（b / b $ b）具有该属性，则有效：


随机导入

def random_pick（a_list，property）：

''''''从列表中返回一个具有属性的随机元素


循环永远如果没有元素有财产

'''''

而1：

i = random.choice（a_list）

if property（i）：return i


如果列表中的许多元素更有效（平均）如果只有列表中的少数元素具有

属性（并且如果没有元素具有属性则会变得疯狂）


又一个：


随机导入

def random_pick（a_list，property）：

''' '''从包含属性的列表中返回一个随机元素

''''''

b_list = [如果属性（x），则a_list中的x为x]

试试：

返回random.choice（b_list）

终于：返回无


但是这一个检查了所有元素的属性，这不是好的。
好​​。


我不需要强大的随机数，所以一个简单的解决方案就像：

随机导入

globalRNG = random.Random（）


def random_pick（a_list，property y）：

''''''从具有属性的列表中返回一个随机元素


仅当len（a_list）+1是素数：使用费马的小定理

'''''

a = globalRNG（1，len（a_list））

ind = a
$ x $ b for x in xrange（len（a_list））：

x = a_list [a-1]

if property（x）：返回x

ind * = a


但这只适用于len（a_list）+1是素数!!!现在，如果有一种有效的方法可以找到一个素数给予

而不是一个数字但是不是很大的话，这个可以保存
...


还有其他想法吗？谢谢大家

缓存可能会有所帮助。


如果使用相同的列表多次调用random_pick，那么

对a_list缓存

[a_list中i的属性（i）]的结果。


如果随机调用random_pick多次列表多个

列表项的实例然后缓存

属性（i）对于我在a_list中的i。


你可以做到这两点。


你可能会调查更好的属性（i）可以使用一个更快的算法来实现，可能是表查找，或者是从初始插值

查表。


- Paddy。

缓存可能会有所帮助。


如果使用相同的列表多次调用random_pick，则

缓存
$的结果b $ b [a_list中i的属性（i）]对a_list。


如果调用random_pick几个tim es列表中包含多个

列表项的实例然后缓存

property（i）对于我在a_list中的i。


你可以同时做这两件事。


你可能会调查更好的属性（i）可以用一个更快的算法来实现，可能是表格查找或插值从最初的

表查询。


- Paddy。

谢谢，Paddy。这些是对一般

问题的有趣的一般性评论。

顺便说一下，我注意到两件事：


我忘记了在第三种方法中写randint：

A = globalRNG.randint（1，LEN（的a_list））

警告您要发布到的组是Usenet组。发布到此论坛的消息

将使您的电子邮件地址对互联网上的任何人都可见。意思是一个人，但不是机器人，可能会看到我的电子邮件

地址，所以下次使用我的真实地址是安全的...

1月4日，7：55 * pm，c ... @ mailinator.com写道：

*你好，

*这是一个关于最佳方法的问题（在性能方面仅为
）从列表中选择一个随机元素来满足某些属性的价值。


*这是设置：我需要从列表中选择一个满足给定属性的随机元素

。所有元素都可能具有

属性。大多数情况下，许多元素都会满足

属性，而且评估属性有点贵。

拥有该属性的机会在元素之间是统一的。

这里有一些使用列表的缓存随机排序的代码。它b / b $ b假设你需要多个随机元素。它永远不会在同一元素上两次调用
''prop''，即使元素

通过''prop''也是O（n）很稀疏。我希望这对你有用！


随机导入


类RandomPicker（对象）：

def __init__ （self，seq，prop = lambda x：True）：

seq = list（seq）

random.shuffle（seq）

＃存储项目是否我们已经计算了道具

已经。

self.random_list = [（x，False）for x in seq]

self.prop = prop

def pick（self）：

for i，（x，p）枚举（self.random_list）：

如果p或self.prop（x）：

如果不是p：

＃记录self.prop通过的事实。

self.random_list [i] =（x，True）

＃砍掉道具失败的物品。

self.random_list = self.random_list [i ：]

r = self.random_list

＃而不是再次洗牌整个列表，只需

插入

＃ x随机回到列表中。由于剩下的

元素

＃已经随机排序，这没关系。

n = random.randint（0，len（r） - 1）

r [0]，r [n] = r [n]，r [0]

返回x

＃没有list传递''prop''测试。

返回无


＃示例：从0到1000选择100个奇数整数。

a = RandomPicker（xrange（1000），lambda x：x％2 == 1）

print [a.pick（）for x in xrange（100）]

>
-

Paul Hankin

Hello,
This is a question for the best method (in terms of performance
only) to choose a random element from a list among those that satisfy
a certain property.

This is the setting: I need to pick from a list a random element
that satisfies a given property. All or none of the elements may have
the property. Most of the time, many of the elements will satisfy the
property, and the property is a bit expensive to evaluate. Chance of
having the property are uniform among elements.

A simple approach is:

import random
def random_pick(a_list,property):
''''''Returns a random element from a list that has the property

Returns None if no element has the property
''''''
random.shuffle(a_list)
for i in a_list:
if property(i): return i

but that requires to shuffle the list every time.

A second approach, that works if we know that at least one element of
the list has the property, is:

import random
def random_pick(a_list,property):
''''''Returns a random element from a list that has the property

Loops forever if no element has the property
''''''
while 1:
i=random.choice(a_list)
if property(i): return i

which is more efficient (on average) if many elements of the list have
the property and less efficient if only few elements of the list has
the property (and goes crazy if no element has the property)

Yet another one:

import random
def random_pick(a_list,property):
''''''Returns a random element from a list that has the property
''''''
b_list=[x for x in a_list if property(x)]
try:
return random.choice(b_list)
finally: return None

but this one checks the property on all the elements, which is no
good.

I don''t need strong random numbers, so a simple solution like:
import random
globalRNG=random.Random()

def random_pick(a_list,property):
''''''Returns a random element from a list that has the property

Works only if len(a_list)+1 is prime: uses Fermat''s little theorem
''''''
a=globalRNG(1,len(a_list))
ind=a
for i in xrange(len(a_list)):
x=a_list[a-1]
if property(x):return x
ind*=a

but this works only if len(a_list)+1 is prime!!! Now this one could be
saved if there were an efficient method to find a prime number given
than a number n but not very much greater...

Any other ideas? Thanks everybody

解决方案

On Jan 4, 7:55 pm, [e-mail] wrote:

Hello,
This is a question for the best method (in terms of performance
only) to choose a random element from a list among those that satisfy
a certain property.

This is the setting: I need to pick from a list a random element
that satisfies a given property. All or none of the elements may have
the property. Most of the time, many of the elements will satisfy the
property, and the property is a bit expensive to evaluate. Chance of
having the property are uniform among elements.

A simple approach is:

import random
def random_pick(a_list,property):
''''''Returns a random element from a list that has the property

Returns None if no element has the property
''''''
random.shuffle(a_list)
for i in a_list:
if property(i): return i

but that requires to shuffle the list every time.

A second approach, that works if we know that at least one element of
the list has the property, is:

import random
def random_pick(a_list,property):
''''''Returns a random element from a list that has the property

Loops forever if no element has the property
''''''
while 1:
i=random.choice(a_list)
if property(i): return i

which is more efficient (on average) if many elements of the list have
the property and less efficient if only few elements of the list has
the property (and goes crazy if no element has the property)

Yet another one:

import random
def random_pick(a_list,property):
''''''Returns a random element from a list that has the property
''''''
b_list=[x for x in a_list if property(x)]
try:
return random.choice(b_list)
finally: return None

but this one checks the property on all the elements, which is no
good.

I don''t need strong random numbers, so a simple solution like:
import random
globalRNG=random.Random()

def random_pick(a_list,property):
''''''Returns a random element from a list that has the property

Works only if len(a_list)+1 is prime: uses Fermat''s little theorem
''''''
a=globalRNG(1,len(a_list))
ind=a
for i in xrange(len(a_list)):
x=a_list[a-1]
if property(x):return x
ind*=a

but this works only if len(a_list)+1 is prime!!! Now this one could be
saved if there were an efficient method to find a prime number given
than a number n but not very much greater...

Any other ideas? Thanks everybody

Caching might help.

If random_pick is called several times with the same list(s) then
cache the result of
[property(i) for i in a_list] against a_list.

If random_pick is called several times with list(s) whith multiple
instances of list items then cache
property(i) against i for i in a_list .

You could do both.

You might investigate wether property(i) could be implemented using a
faster algorithm, maybe table lookup, or interpolation from initial
table lookup.

- Paddy.

Caching might help.

If random_pick is called several times with the same list(s) then
cache the result of
[property(i) for i in a_list] against a_list.

If random_pick is called several times with list(s) with multiple
instances of list items then cache
property(i) against i for i in a_list .

You could do both.

You might investigate wether property(i) could be implemented using a
faster algorithm, maybe table lookup, or interpolation from initial
table lookup.

- Paddy.

Thanks, Paddy. Those are interesting general comments for the general
problem.
By the way, I noticed two things:

I forgot to write randint in the third approach:

a=globalRNG.randint(1,len(a_list))

The warning "The group you are posting to is a Usenet group. Messages
posted to this group will make your email address visible to anyone on
the Internet." means a person, but not a bot, may see my email
address, so it is safe to use my real address next time...

On Jan 4, 7:55*pm, [e-mail] wrote:

* Hello,
* This is a question for the best method (in terms of performance
only) to choose a random element from a list among those that satisfy
a certain property.

* This is the setting: I need to pick from a list a random element
that satisfies a given property. All or none of the elements may have
the property. Most of the time, many of the elements will satisfy the
property, and the property is a bit expensive to evaluate. Chance of
having the property are uniform among elements.

Here''s some code that uses a cached random sorting of the list. It
assumes you''ll want more than one random element. It never calls
''prop'' on the same element twice, and it''s O(n) even when the elements
that pass ''prop'' are sparse. I hope this is useful to you!

import random

class RandomPicker(object):
def __init__(self, seq, prop=lambda x:True):
seq = list(seq)
random.shuffle(seq)
# Store with the item whether we''ve computed prop on it
already.
self.random_list = [(x, False) for x in seq]
self.prop = prop
def pick(self):
for i, (x, p) in enumerate(self.random_list):
if p or self.prop(x):
if not p:
# Record the fact that self.prop passed.
self.random_list[i] = (x, True)
# Chop off the items that prop failed on.
self.random_list = self.random_list[i:]
r = self.random_list
# Instead of shuffling the whole list again, just
insert
# x back in the list randomly. Since the remaining
elements
# are randomly sorted already, this is ok.
n = random.randint(0, len(r) - 1)
r[0], r[n] = r[n], r[0]
return x
# Nothing in the list passes the ''prop'' test.
return None

# Example: pick 100 odd integers from 0 to 1000.
a = RandomPicker(xrange(1000), lambda x: x % 2 == 1)
print [a.pick() for i in xrange(100)]

--
Paul Hankin

这篇关于选择随机元素的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！