生成随机且唯一的索引，其范围为n个组合

Question

我想做一个随机的参数搜索器，但我不知道如何在一个范围内生成一个随机但唯一的索引组合。例如，我有以下参数：

    hyperparams  = {
        'size': [200, 300, 400],
        'min_count': [1, 2, 3, 4, 5],
        'iter': [50, 100],
        'window': [4, 5, 7, 10],
        'alpha': [0.025, 0.01],
        'min_alpha': [0.025, 1e-4],
    }

我想生成它们的唯一组合，并且每个索引都有一个n次的范围。 假设它将产生500种可能的组合。我只想随机抽取100个，但在这100个样本中，任何一个都是重复的。 i、 e

^{pr2}$

哪个。。。在

Index 0 is the size.

Index 1 is min_count.

Index 2 is iter.

and so on...

所以以后我用

::
size = hyperparams['size'][1]
min_count = hyperparams['min_count'][3]
iter = hyperparams['iter'][2]
::
::

Answer 1

如果我理解正确的话，你需要一个在一定范围内的不重复的元组序列。在

编辑0：

我相信你最好的办法是先创造所有可能的组合，然后再洗牌：

import itertools
import random


def random_unique_combinations_k0(items, k):
    # generate all possible combinations
    combinations = list(itertools.product(*[item for item in items]))
    # shuffle them
    random.shuffle(combinations)
    for combination in itertools.islice(combinations, k):
        yield combination

编辑1：

如果生成所有组合的内存开销太大，您可能需要反复尝试并拒绝非唯一的组合。 一种方法是：

^{pr2}$

（这也只能在添加combination之前使用列表和检查唯一性来实现，这也会呈现random.shuffle()多余的内容，但从我的测试来看，这比使用sets慢得多。）

编辑2：

可能最不需要内存的方法是实际洗牌生成器，然后在它们上使用itertools.product()。在

import random
import itertools


def pseudo_random_unique_combinations_k(items, k):
    # randomize generators
    comb_gens = list(items)
    for i, comb_gen in enumerate(comb_gens):
        random.shuffle(list(comb_gens[i]))
    # get the first `num` combinations
    combinations = list(itertools.islice(itertools.product(*comb_gens), k))
    random.shuffle(combinations)
    for combination in itertools.islice(combinations, k):
        yield tuple(combination)

这显然会牺牲一些随机性。在

编辑3：

继@Divakar方法之后，我又编写了另一个版本，它似乎相对高效，但它很可能会受到random.sample()功能的限制。在

import random
import functools


def prod(items):
    return functools.reduce(lambda x, y: x * y, items)


def random_unique_combinations_k3(items, k):
    max_lens = [len(list(item)) for item in items]
    max_num_combinations = prod(max_lens)
    for i in random.sample(range(max_num_combinations), k):
        index_combination = []
        for max_len in max_lens:
            index_combination.append(i % max_len)
            i = i // max_len
        yield tuple(item[i] for i, item in zip(index_combination, items))

测试

在请求的输入上，它们执行得相当快，0方法是最快的（甚至比2或{}方法更快），而{}方法是最慢的，3方法介于两者之间。 sklearn.model_selection.ParameterSampler方法的速度与1方法相当。在

items = [v for k, v in hyperparams.items()]
num = 100

%timeit list(random_unique_combinations_k0(items, num))
615 µs ± 4.87 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit list(random_unique_combinations_k1(items, num))
2.51 ms ± 33.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit list(pseudo_random_unique_combinations_k(items, num))
179 µs ± 1.41 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit list(random_unique_combinations_k3(items, num))
570 µs ± 35.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# the `sklearn` method which is slightly different in that it is
# also accessing the underling dictiornary    
import from sklearn.model_selection import ParameterSampler
%timeit list(ParameterSampler(hyperparams, n_iter=num))
2.86 ms ± 171 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

作为补充说明，我将确保您hyperparams是一个collections.OrderedDict，因为{}不能保证跨不同版本的Python排序。在

对于稍微大一点的物体，我们开始看到极限：

items = [range(50)] * 5
num = 1000

%timeit list(random_unique_combinations_k0(items, num))
# Memory Error

%timeit list(random_unique_combinations_k1(items, num))
19.3 ms ± 273 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit list(pseudo_random_unique_combinations_k(items, num))
1.82 ms ± 14.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit list(random_unique_combinations_k3(items, num))
2.31 ms ± 28.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

更大的物体更是如此：

items = [range(50)] * 50
num = 1000

%timeit list(random_unique_combinations_k0(items, num))
# Memory Error

%timeit list(random_unique_combinations_k1(items, num))
149 ms ± 3.45 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit list(pseudo_random_unique_combinations_k(items, num))
4.92 ms ± 20.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit list(random_unique_combinations_k3(items, num))
# OverflowError

摘要：

方法0可能不适合内存，方法1最慢，但可能更健壮，方法{}如果不遇到溢出问题，它的性能最好，而方法2（pseudo）是最快和内存消耗较少的方法，但它会产生一些“较少随机”的组合。在

Answer 2

这里有一个基于哈希的方法来生成唯一的组合，而不是生成所有的组合，只生成所需的组合数量-

num_comb = 100 # number of combinations needed

# We need ordered keys to maintain the indexing needed :
# Index 0 is the size, Index 1 is min_count, Index 2 is iter...
ordered_keys = ['size', 'min_count', 'iter', 'window', 'alpha','min_alpha']
lens = np.array([len(hyperparams[i]) for i in ordered_keys])

prod_lens = lens.cumprod()
idx = np.random.choice(prod_lens[-1], num_comb, replace=0)

N = len(lens)
out = np.zeros((num_comb,N),dtype=int)
r = idx
for i in range(2,N+1):
    d = r//prod_lens[-i]
    r = r - d*prod_lens[-i]
    out[:,-i+1] = d
out[:,0] = r

运行时测试

目前发布的三种方法解决了无法生成所有组合的问题，而且这些方法是真正随机的-@norok2-Edit1，@scnerd，还有一种方法在这篇文章中发布了三组输出长度-

^{pr2}$

Answer 3

scikit-learn需要准确地解决这个问题来实现RandomizedSearchCV，它们有一个独立的类ParameterSampler，您可以使用这个类：

In [1]: from sklearn.model_selection import ParameterSampler

In [2]: list(ParameterSampler({'a': [1,2,3], 'b': ['x', 'y', 'z'], 'c': [0.1, 0.2, 0.3]}, n_iter=5))
Out[2]:
[{'a': 3, 'b': 'z', 'c': 0.2},
 {'a': 3, 'b': 'y', 'c': 0.1},
 {'a': 3, 'b': 'z', 'c': 0.1},
 {'a': 3, 'b': 'x', 'c': 0.2},
 {'a': 1, 'b': 'y', 'c': 0.3}]

这不是索引，但是您可以通过用索引列表替换值列表来轻松解决这个小问题：

^{pr2}$

而且according to the documentation，你不会得到任何重复：

If all parameters are presented as a list, sampling without replacement is performed.

快速浏览一下current source code可以看到，当所有参数都以列表形式给出时，它会生成所有可能的选项，并从中随机抽样。在大多数情况下这不是问题，但是如果你有大量的超参数选项，它可能会占用相当多的内存。在