Простое случайное распределение N элементов по n клеткам

Question

Я хочу просто распределить N элементов по n ячейкам, оба числа N и n могут быть большими, поэтому я не хотел бы зацикливаться на случайных значениях, как здесь:

import numpy as np

nitems = 100
ncells = 3
cells = np.zeros((ncells), dtype=np.int)
for _ in range(nitems):
    dest = np.random.randint(ncells)
    cells[dest] += 1
print(cells)

В этом случаевывод:

[31 34 35]

(сумма всегда N) Есть ли способ быстрее?

Answer 1

На моей машине ваш код с timeit занял 151 микросекунду.Следующее заняло 11 микросекунд:

import numpy as np
nitems = 100
ncells = 3
values = np.random.randint(0,ncells,nitems)
cells  = np.array_split(values,3)
lengths= [ len(cell) for cell in cells ]
print(lengths,np.sum(lengths))

Результат печати: [34, 33, 33] 100.

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

Если вы хотите, чтобы разбиение выполнялось случайным образом:

import numpy as np
nitems = 100
ncells = 3
values = np.random.randint(0,ncells,nitems)
ind_split = [ np.random.randint(0,nitems) ]
ind_split.append(np.random.randint(ind_split[-1],nitems))
cells  = np.array_split(values,ind_split)
lengths= [ len(cell) for cell in cells ]
print(lengths,np.sum(lengths))

Это использует преимущество numpy.array_split, взяв в качестве аргумента индексы того, где выполнять разбиение (а не количество почти равномерныхперегородки).

Answer 2

Ниже следует ответ на вопрос (я должен поблагодарить @pjs за его помощь).Я думаю, что это самый быстрый и, возможно, самый короткий и самый экономичный из возможных:

from numpy import *
from time import sleep

g_nitems =   10000
g_ncells =   10
g_nsamples = 10000

def genDist(nitems, ncells):
    r = sort(random.randint(0, nitems+1, ncells-1))
    return concatenate((r,[nitems])) - concatenate(([0],r))

# Some stats

test = zeros(g_ncells, dtype=int)
Max = zeros(g_ncells, dtype=int)
for _ in range(g_nsamples):
    tmp = genDist(g_nitems, g_ncells)
    print(tmp.sum(), tmp, end='\r')
    # print(_, end='\r')
    # sleep(0.5)
    test += tmp
    for i in range(g_ncells):
        if tmp[i] > Max[i]:
            Max[i] = tmp[i]

print("\n", Max)
print(test//g_nsamples)

Answer 3

Вы не указали, что счетчики должны иметь какое-то конкретное распределение, если они складываются в N, поэтому следующее будет работать в соответствии с запросом:

import numpy as np

nitems = 100
ncells = 3
range_array = [np.random.randint(nitems + 1) for _ in range(ncells - 1)] + [0, nitems]
range_array.sort()
cells = [range_array[i + 1] - range_array[i] for i in range(ncells)]
print(cells)

Он генерирует упорядоченный набор случайных чисел.значения между 0 и nitems, затем принимает последовательные разности для генерации желаемого количества ячеек.

Сложность O (ncells), а не O (nitems), поэтому она должна быть большеэффективен, когда предметов значительно больше, чем клеток.