[python] 셔플 된 목록을 복사하는 것이 훨씬 느린 이유는 무엇입니까?

다른 사람들이 설명했듯이 참조를 복사하는 것뿐만 아니라 객체 내부의 참조 수가 증가하므로 객체 에 액세스하고 캐시가 역할을 수행합니다.

여기에 더 많은 실험을 추가하고 싶습니다. shuffled와 unshuffled에 대해서는 그다지 중요하지 않습니다 (하나의 요소에 액세스하면 캐시를 놓칠 수 있지만 다음 요소를 캐시에 가져 와서 적중합니다). 그러나 요소가 여전히 캐시에 있기 때문에 나중에 동일한 요소에 액세스하면 캐시에 도달 할 수있는 반복 요소에 대해.

정상 범위 테스트 :

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

크기는 같지만 하나의 요소 만 반복해서 반복되는 목록은 항상 캐시에 도달하기 때문에 더 빠릅니다.

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

그리고 그것이 어떤 숫자인지는 중요하지 않은 것 같습니다.

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

흥미롭게도 같은 두 개 또는 네 개의 요소를 대신 반복하면 더 빨라집니다.

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

항상 같은 카운터가 증가하는 것을 좋아하지 않는 것 같아요. 각 증가가 이전 증가의 결과를 기다려야하기 때문에 파이프 라인이 멈출 수도 있지만 이것은 거친 추측입니다.

어쨌든 더 많은 수의 반복 요소에 대해 이것을 시도하십시오.

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

출력 (첫 번째 열은 서로 다른 요소의 수이며 각 요소에 대해 세 번 테스트 한 다음 평균을 취합니다) :

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

따라서 단일 (반복) 요소에 대해 약 2.8 초에서 2, 4, 8, 16, … 다른 요소에 대해 약 2.2 초로 떨어지고 수십만 개까지 약 2.2 초에 유지됩니다. 나는 이것이 내 L2 캐시를 사용한다고 생각합니다 (4 × 256 KB, 나는 i7-6700 ).

그런 다음 몇 단계를 거치면 시간이 최대 3.5 초가됩니다. 나는 이것이 “소진”될 때까지 내 L2 캐시와 내 L3 캐시 (8MB)를 혼합하여 사용한다고 생각합니다.

마지막에는 약 3.5 초로 유지됩니다. 캐시가 더 이상 반복되는 요소에 도움이되지 않기 때문입니다.