python - 如何提取 Python 列表中一定比例的均匀分布的元素？

Question

我有一个数据点列表。为了程序的完整运行，我将使用所有数据点，但为了测试代码，我只想使用其中的一小部分，以便程序在短时间内运行。不过，我不想简单地获取列表的前 n 个元素；我想从列表中选择均匀分布的元素。因此，如果我使用了 50% 的数据点，我可能希望每秒从数据点列表中选择一个数据点。

基本上，我想要一个函数，它将一个列表和一个百分比作为参数，并返回一个列表，该列表由输入列表中均匀分布的元素组成，其数量尽可能接近所请求的百分比。

执行此操作的好方法是什么？

Answer 1

为了完整性，请考虑以下内容。

这个问题可以分为两部分:

1. 在给定特定百分比或分数的情况下，确定要选取的元素数量。

2. 选择应从列表中选择的元素。

第一点很简单。如果您想要 percentage = 35.#% 的列表，最好选择 round(len(my_list) * (percentage/100.)) 元素.请注意，只有当 len(my_list) 是 (percentage/100.) 的倍数时，您才能获得完全正确的百分比。这种不准确是不可避免的，因为连续测量值(百分比)被转换为离散测量值(元素数量)。

第二点将取决于您对应该返回哪个元素的特殊要求。选择尽可能均匀分布的元素是可行的，但肯定不是最简单的方法。

从概念上讲，您将如何执行此操作(请参阅下面的实现):

如果您有一个长度为 l 的列表，您希望其中的某个均匀分布的分数 f(f = percentage/100。 ) 您必须将列表的索引分箱到大小为 l/round(l * f) 的 round(l * f) 分箱中。您想要的是包含每个 bin 最中心元素的列表。

为什么会这样？

对于第一点，请注意，如果我们制作大小为 l/round(l * f) 的 bin，我们将得到 l/l/round(l * f) = round (l * f) 垃圾箱在最后。这是理想的数量(见上文第 1 点)。如果对于这些大小相同的容器中的每一个，然后我们选择最中心的元素，我们将得到一个尽可能均匀分布的元素列表。

这是一个简单的(既没有优化速度也没有非常漂亮)的实现:

from bisect import bisect_left
def equal_dist_els(my_list, fraction):
    """
    Chose a fraction of equally distributed elements.
    :param my_list: The list to draw from
    :param fraction: The ideal fraction of elements
    :return: Elements of the list with the best match
    """
    length = len(my_list)
    list_indexes = range(length)
    nbr_bins = int(round(length * fraction))
    step = length / float(nbr_bins)  # the size of a single bin
    bins = [step * i for i in xrange(nbr_bins)]  # list of bin ends
    # distribute indexes into the bins
    splits = [bisect_left(list_indexes, wall) for wall in bins]
    splits.append(length)  # add the end for the last bin
    # get a list of (start, stop) indexes for each bin
    bin_limits = [(splits[i], splits[i + 1]) for i in xrange(len(splits) - 1)]
    out = []
    for bin_lim in bin_limits:
        f, t = bin_lim
        in_bin = my_list[f:t]  # choose the elements in my_list belonging in this bin
        out.append(in_bin[int(0.5 * len(in_bin))])  # choose the most central element
    return out

我们现在可以将这种理想算法 (equal_dist_els) 与@jonrsharpe 的切片方法进行比较:

请参阅下面的代码。

沿 x 轴是要返回的元素的期望分数，在 y 轴上是期望分数与两种方法返回的分数之间的绝对差值。我们看到对于大约 0.7 (~70%) 的分数，切片方法的偏差是显着的，即如果你要求~70%，切片方法返回所有元素 (100%)，这几乎是 45% 的偏差。

总而言之，我们可以说@jonrsharpe 的切片方法适用于小分数 (>>0.1)，但在选择较大分数时变得越来越不准确。另请注意，不准确性与列表的长度无关。分箱算法的实现当然稍微复杂一些，而且很可能也慢得多。然而，它的不准确性只是由上面提到的不可避免的不准确性给出的，随着列表长度的增加而减少。

绘图代码:

from matplotlib import pyplot as plt
# def of equal_dist_els see above
def select_els(seq, perc):
    """Select a defined percentage of the elements of seq."""
    return seq[::int(round(1./perc if perc != 0 else 0))]
list_length = 50
my_list = range(list_length)
percentages = range(1, 101)
fracts = map(lambda x: x * 0.01, percentages)

equal_dist = map(lambda x: abs(len(equal_dist_els(my_list, x)) / float(len(my_list)) - x), fracts)
slicing = map(lambda x: abs(len(select_els(my_list, x)) / float(len(my_list)) - x), fracts)

plt.plot(fracts, equal_dist, color='blue', alpha=0.8, linewidth=2, label=r'equal_dist_elements')
plt.plot(fracts, slicing, color='red', alpha=0.8, linewidth=2, label=r'select_elements by @jonrsharpe')
plt.title('Choosing equally dist. fraction of els from a list of length %s' % str(list_length))
plt.xlabel('requested fraction')
plt.ylabel('absolute deviation')
plt.legend(loc='upper left')
plt.show()