Ленивый образец случайных результатов в Python

Question

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

Другими словамиТеперь у меня есть

a = createHugeArray()
s = random.sample(a,len(a)*0.001)

, что довольно расточительно.Я предпочел бы что-нибудь более ленивое, как

a = createArrayGenerator()
s = random.sample(a,len(a)*0.001)

Я не знаю, работает ли это.Документация по random.sample не слишком ясна, хотя в ней упоминается, что xrange очень быстр, что заставляет меня верить, что это может сработать.Преобразование создания массива в генератор было бы небольшой работой (мои знания о генераторах очень ржавые), поэтому я хочу знать, работает ли это заранее.:)

Альтернатива, которую я вижу, состоит в том, чтобы сделать случайную выборку с помощью xrange и генерировать только те объекты, которые фактически выбраны по индексу.Это не очень понятно, потому что сгенерированные индексы являются произвольными и ненужными, и мне потребуется довольно хакерская логика для поддержки этого в моем методе generateHugeArray.

Для бонусных баллов: как на самом деле работает random.sample?Особенно, как это работает, если он не знает заранее численность населения, как с такими генераторами, как xrange?

Answer 1

Кажется, нет способа избежать выяснения того, как индексы соотносятся с вашими перестановками.Если вы этого не знаете, как бы вы создали случайный объект из вашего массива?Вы можете использовать трюк, используя предложенный вами xrange(), или реализовать класс, определяющий методы __getitem__() и __len__(), а также передать объект этого класса в качестве аргумента population для random.sample().

* 1007.* Некоторые дальнейшие комментарии:

• Преобразование createHugeArray () в генератор ничего не купит - random.sample() просто больше не будет работать.Ему нужен объект, поддерживающий len().

• Так что для нужно знать количество элементов в популяции с самого начала.

• Реализация имеет два разных алгоритма и выбирает тот, который будет использовать меньше памяти.Для относительно небольших k (то есть в данном случае) он просто сохранит индексы, уже выбранные в set, и сделает новый случайный выбор, если достигнет одного из них.

Редактировать: Совершенно другой подход состоит в том, чтобы перебрать все перестановки один раз и решить для каждой перестановки, должна ли она быть включена.Если общее число перестановок составляет n, и вы хотите выбрать k из них, вы можете написать

selected = []
for i in xrange(n):
    perm = nextPermutation()
    if random.random() < float(k-len(selected))/(n-i):
        selected.append(perm)

. Это будет точно выбирать k перестановок случайным образом.

Answer 2

Я предполагаю, что функция createHugeArray () содержит фрагмент кода, который повторяется один раз для каждого создаваемого объекта. И я предполагаю, что объекты генерируются из некоторого начального значения или семени, и в этом случае createHugeArray () выглядит примерно так:

def createHugeArray( list_of_seeds ):
  huge_array = []                  
  for i in list_of_seeds:
    my_object = makeObject( i )
    huge_array.append( my_object )           
  return huge_array

(я использовал списки, а не массивы, но вы поняли.)

Чтобы выполнить случайную выборку перед созданием объектов, просто добавьте строку, которая генерирует случайное число, а затем создайте объект, только если случайное число находится ниже определенного порога. Скажем, вы хотите только один объект из тысячи. random.randint (0,999) дает число от 0 до 999 - поэтому генерировать объект можно только в том случае, если вы получаете ноль. Код выше становится:

import random

def createHugeArray( list_of_seeds ):
  huge_array = [] 

  for i in list_of_seeds:
    die_roll = random.randint(0,999)

    if( die_roll == 0 ):
      my_object = makeObject( i )
      huge_array.append( my_object ) 
  return huge_array

Конечно, если мое предположение о том, как работает ваш код, неверно, то это бесполезно для вас, и в этом случае извините и удачи: -)

Answer 3

Объясняя, как работает random.sample,

random.sample(container, k) вернет k количество значений случайным образом из контейнера. Поскольку генератор является итеративным, как списки, кортежи и ключи или значения в dicts, он будет перебирать контейнер и затем принимать эти случайные элементы.

например. random.sample(xrange(111),4) вернет что-то вроде [33,52,111,1] как k = 4, что означает 4 случайных числа от генератора xrange до 111.

Answer 4

Вы можете создать список индексов массива с образцом, а затем сгенерировать объекты в соответствии с результатами:

def get_object(index):
    return MyClass(index)

или что-то в этом роде. Затем используйте sample для генерации нужных вам индексов и вызовите эту функцию с этими индексами:

objs = map(get_object, random.sample(range(length), 0.001 * length))

Это немного косвенно, так как он выбирает только из списка возможных индексов массива.