Как создать случайный раздел из итератора в Python

Question

Учитывая желаемое количество разделов, разделы должны быть почти равными по размеру. Этот вопрос решает проблему для списка.Они не имеют случайного свойства, но это легко добавляется .Моя проблема в том, что у меня есть итератор в качестве входных данных, поэтому shuffle не применяется.Причина в том, что я хочу случайным образом разделить узлы графа.График может быть очень большим, поэтому я ищу решение, которое не просто создает промежуточный список.

Моей первой идеей было использование compress() с функцией случайного числаселектор.Но это работает только для двух разделов.

Answer 1

Вы можете просто создать k список.Когда вы получите значение, выберите случайное целое число x в диапазоне от 0 до k-1 и поместите это значение в x-й список.

В среднем каждый список будет содержать N / k элементов, но со стандартным отклонением √ (N * 1 / k * (1-1 / k)).

def random_partition(k, iterable):
  results = [[] for i in range(k)]
  for value in iterable:
    x = random.randrange(k)
    results[x].append(value)
  return results

Answer 2

Вы просто имеете дело с различными разделами, верно?

def dealer( iterator, size ):
    for item in iterator
        yield random.randrange( size ), item

Разве это не поможет вам начать с назначения каждого элемента на раздел?

Тогда вы можете сделать что-то вродеэто сделать списки.Может быть, не очень хорошая вещь, но это показывает, как использовать функцию.

def make_lists( iterator, size ):
    the_lists = []*size
    for partition, item in dealer( iterator, size ):
        the_lists[partition].append(item)
    return the_lists

Answer 3

Вы можете сделать длину списков более равномерной, настроив веса в зависимости от количества сгенерированных узлов в каждом разделе.Они будут примерно равной длины, если вы выберете функцию так, чтобы вес был равен 0, когда (количество узлов в разделе n)> (количество узлов) / (количество разбиений), то есть

weight [i] = max (numNodes / numPartitions - nodeSoFar [i], 0)

(max () - остановка отрицательных весов, что может произойти, если у вас 4 узла и 3 раздела.)

Затем выберите случайное число от 1 до суммы (веса) (или от 0 до суммы (веса) -1) и выберите соответствующий раздел.

compress() работает, если вы используете другой селектор для раздела;что-то вроде (x == n for x in random_partition_numbers), где random_partition_numbers - это генератор.Конечно, вам нужно будет скопировать random_partition_numbers для каждого раздела.Этот дизайн по своей сути медленнее, так как он должен перебирать список узлов для каждого раздела.