셔플 된 목록을 복사하는 것이 왜 훨씬 느린가요?
셔플 된 range(10**6)목록을 10 번 복사하는 데 약 0.18 초가 붙여. (5 번 실행됩니다)
0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451
셔플되지 않은 목록을 10 번 복사하는 데 약 0.05 초가 있습니다.
0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184
내 테스트 코드는 다음과 가변적입니다.
from timeit import timeit
import random
a = range(10**6)
random.shuffle(a) # Remove this for the second test.
a = list(a) # Just an attempt to "normalize" the list.
for _ in range(5):
print timeit(lambda: list(a), number=10)
나는 또한 복사를 시도한 a[:]결과가 발생했습니다 (즉, 큰 속도 차이)
속도 차이가 큰 이유는 무엇입니까? 나는 유명한 배열 의 속도 차이를 알고 있습니다. 정렬되지 않은 배열보다 정렬 된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까? 예,하지만 여기서 내 처리에는 결정이 없습니다. 목록에있는 참조를 맹목적으로 복사하는 것입니다.
Windows 10에서 Python 2.7.12를 사용하고 있습니다.
편집 : Python 3.5.2도 시도했지만 결과는 거의 동일했습니다 (일관되게 약 0.17 초 셔플되고 약 0.05 초에 계속 셔플되지 않았습니다). 이에 대한 코드는 다음과 가변합니다.
a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
print(timeit(lambda: list(a), number=10))
흥미로운 점은 정수가 처음 생성 되는 순서에 달려있는 것 입니다. 예를 들어 대신 shuffle임의의 순서를 사용하여 만든 random.randint:
from timeit import timeit
import random
a = [random.randint(0, 10**6) for _ in range(10**6)]
for _ in range(5):
print(timeit(lambda: list(a), number=10))
이것은 귀하의 list(range(10**6))(첫 번째 및 빠른 예) 복사만큼 빠 사용 .
그러나 셔플하면 정수가 더 이상 처음 생성 된 순서가 아니기 때문에 속도가 느려집니다.
빠른 인터메조 :
- 모든 Python 객체는 힙에 있으므로 모든 객체는 포인터입니다.
- 목록 복사는 단순 작업입니다.
- 파이썬은 참조 그러나 카운트를 사용하므로 object-가 새 컨테이너 에 들어갈 때 참조 카운트가 증가해야 우리합니다 (
Py_INCREF에서list_slice). 즉, 객체가있는 곳에서 이동해야합니다. 참조를 복사 할 수 없습니다.
따라서 목록을 복사 할 때 해당 목록의 각 항목을 가져 오기 새 목록에 "있는 그대로"넣습니다. 다음 항목이 현재 항목에 저장 생성 가능성이 있습니다.
컴퓨터가 캐시에 항목을로드 할 때마다 x다음 메모리 항목 ( 캐시 지역) 도로 드 가정 해 보겠습니다 . 그러면 컴퓨터가 x+1동일한 캐시에있는 항목에 대한 참조 횟수 증가를 수행 할 수 있습니다 !
셔플 된 시퀀스를 사용하여 여전히 다음 메모리 항목을로드하지만 목록에 다음 항목이 없습니다. 따라서 다음 항목을 "정말"찾지 않고는 참조 횟수 증가를 수행 할 수 없습니다.
요약 : 실제 속도는 효율적이고 상황에 따라 달라지기 전에. 순서가 무엇인지에 따라 순서가 생성됩니다.
다음을보고이를 확인할 수 있습니다 .id
CPython 구현 세부 사항 :이 메모리에있는 오브젝트의 주소입니다.
a = list(range(10**6, 10**6+100))
for item in a:
print(id(item))
짧은 발췌를 보여주기 위해 :
1496489995888
1496489995920 # +32
1496489995952 # +32
1496489995984 # +32
1496489996016 # +32
1496489996048 # +32
1496489996080 # +32
1496489996112
1496489996144
1496489996176
1496489996208
1496489996240
1496507297840
1496507297872
1496507297904
1496507297936
1496507297968
1496507298000
1496507298032
1496507298064
1496507298096
1496507298128
1496507298160
1496507298192
따라서 실제로는 "힙에서 서로 옆에"있습니다. 함께 사용 shuffle하지 않습니다 :
import random
a = list(range(10**6, 100+10**6))
random.shuffle(a)
last = None
for item in a:
if last is not None:
print('diff', id(item) - id(last))
last = item
이 메모리에서 실제로 서로 옆에 있지 않은 것을 보여줍니다.
diff 736
diff -64
diff -17291008
diff -128
diff 288
diff -224
diff 17292032
diff -1312
diff 1088
diff -17292384
diff 17291072
diff 608
diff -17290848
diff 17289856
diff 928
diff -672
diff 864
diff -17290816
diff -128
diff -96
diff 17291552
diff -192
diff 96
diff -17291904
diff 17291680
diff -1152
diff 896
diff -17290528
diff 17290816
diff -992
diff 448
중요 사항 :
나는 이것을 스스로 생각하지 않았다. 대부분의 정보는 Ricky Stewart 의 블로그 게시물 에서 찾을 수 있습니다 .
이 답변은 Python의 "공식"CPython 구현을 기반으로합니다. 다른 구현 (Jython, PyPy, IronPython, ...)의 세부 사항은 다를 수 있습니다. 이것을 지적 해 주신 @ JörgWMittag 에게 감사드립니다 .
목록 항목을 섞으면 참조 위치가 더 나빠져서 캐시 성능이 저하됩니다.
목록을 복사하면 객체가 아닌 참조 만 복사되므로 힙에서의 위치는 중요하지 않습니다. 그러나 복사에는 refcount를 수정하기 위해 각 객체에 액세스하는 것이 포함됩니다.
다른 사람들이 설명했듯이 참조를 복사하는 것뿐만 아니라 객체 내부의 참조 수가 증가하므로 객체 에 액세스하고 캐시가 역할을합니다.
여기에 더 많은 실험을 추가하고 싶습니다. 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 초로 유지됩니다. 캐시가 더 이상 반복되는 요소에 도움이되지 않기 때문입니다.
셔플 전에 힙에 할당되면 인접한 인덱스 개체가 메모리에 인접 해 있고 액세스 할 때 메모리 적중률이 높습니다. 셔플 후 새 목록의 인접 인덱스 개체는 메모리에 없습니다. 인접하면 적중률이 매우 낮습니다.
참고 URL : https://stackoverflow.com/questions/42107442/why-is-copying-a-shuffled-list-much-slower
'IT' 카테고리의 다른 글
| Umbraco, 그것은 나입니까 아니면 사용하기가 정말 어렵습니까? (0) | 2020.09.12 |
|---|---|
| Sieve of Eratosthenes 알고리즘의 시간 (0) | 2020.09.12 |
| CSS3 애니메이션 완료시 있습니까? (0) | 2020.09.12 |
| 자바의 큰 숫자 (0) | 2020.09.11 |
| 로컬 SQL Server 인스턴스에 대한 관리자 액세스 권한을 어떻게 부여합니까? (0) | 2020.09.11 |