就地重组列表的一部分 [英] Shuffling part of a list in-place

问题描述

我有一个list，我想就地 对其一部分进行洗牌.

I have a list and I want to shuffle a portion of it in-place.

我知道random.shuffle()并且它可以就地工作，但是如果我对列表进行切片，它将对原始输入的切片副本进行混洗，而使原始list保持不变:

I am aware of random.shuffle() and that it works in-place, but if I slice the list, it shuffles the sliced copy of the original input, leaving the original list untouched:

import random

l = list(range(20))
print(l)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

random.shuffle(l[:10])  # I wish it was shuffling the first half
print(l)  # but does nothing to `l`
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

我有什么选择?

编辑:这并不是

EDIT: This is not truly a duplicate of this question, since there was no requirement for it to be in-place. Eventually, it seems that it would be possible to shuffle in-place a portion of a list only manually (which is exactly what I was trying to avoid), as suggested by one of the answers posted there.

推荐答案

一个人可以使用 random.shuffle() 接受first和last索引作为参数，例如:

One could use Fisher-Yates shuffle to fundamentally re-implement random.shuffle() to accept a first and last index as arguments, e.g.:

import random


def valid_index(i, n):
    assert(-n <= i < n)
    return i % n


def shuffle(seq, first=0, last=-1, rand_int_gen=None):
    n = len(seq)
    first = valid_index(first, n)
    last = valid_index(last, n)
    # use Fisher-Yates shuffle (Durstenfeld method)
    if callable(rand_int_gen):
        for i in range(first, last):
            j = rand_int_gen(i, last)
            seq[i], seq[j] = seq[j], seq[i]
    else:
        getrandbits = random.getrandbits
        for i in range(first, last + 1):
            size = last - i + 1
            j = getrandbits(size.bit_length()) % size + i
            seq[i], seq[j] = seq[j], seq[i]
    return seq

用法如下:

l = list(range(20))
print(l)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

random.seed(0)  # just to show reproducible results
shuffle(l, 0, 9)
print(l)
# [6, 7, 2, 5, 8, 4, 9, 3, 0, 1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

就时间而言，这实际上比对整个序列进行混排的速度要比random.shuffle()快百分之几.

Time-wise this is actually even a few percent faster than random.shuffle() for shuffling the whole sequence.

这实际上是更快的，因为它直接从random.getrandbits()获取随机值，而random.getrandbits()是random公开的用于生成随机整数的最接近方法，其他方法例如. randint()和randrange()最终简化为此. 最后两个最后在内部使用_getrandbelow()，这可能会更频繁地调用getrandbits().

This is faster essentially because it gets the random values directly from random.getrandbits() which is the closest method exposed by random for random integer generation, the others, e.g. randint() and randrange() eventually reducing to this. These last two eventually use internally _getrandbelow() which could be calling getrandbits() more often the necessary.

for k in range(1, 7): 
    n = 10 ** k 
    print(n) 
    %timeit l = list(range(n)); random.shuffle(l) 
    %timeit l = list(range(n)); shuffle(l) 
    print() 

10
100000 loops, best of 3: 6.16 µs per loop
100000 loops, best of 3: 3.85 µs per loop

100
10000 loops, best of 3: 54.3 µs per loop
10000 loops, best of 3: 28 µs per loop

1000
1000 loops, best of 3: 585 µs per loop
1000 loops, best of 3: 341 µs per loop

10000
100 loops, best of 3: 6.01 ms per loop
100 loops, best of 3: 3.56 ms per loop

100000
10 loops, best of 3: 71.7 ms per loop
10 loops, best of 3: 44.1 ms per loop

1000000
1 loop, best of 3: 815 ms per loop
1 loop, best of 3: 582 ms per loop

也建议使用此方法，如@ usr2564301所指出的那样此处. 不幸的是，我认为没有更好的方法可以就地执行此操作.

This approach was also suggested here, as pointed out by @usr2564301. Unfortunately, I think there is no better approach for doing this operation in-place.

这篇关于就地重组列表的一部分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！