나를 잃지 말자

빠른 이유로는 3가지 이유가 있다.

1. numpy.ndarray는 a collection of similar data-types that are densely packed in memory.

(반면, list는 different data-types을 가질 수 있고 computation하는 데에 있어서 몇가지 과정을 더 타야한다.)

(이 부분은 하단의 설명을 다시 보자.)

2. numpy는 한 task를 subtask로 알아서 나눠서 parallely하게 작동하기도 한다.

(예를 들면, np.dot()을 수행할 때, argument의 size가 크면 cpu core 전부를 쓰는 것을 확인할 수 있다.)

3. numpy는 C언어로 구현되어 있어서 더 빠르게 작동한다.

하늘색이 실제 저장된 값

ndarray는 element조회시 "data"에 접근 후, 모든 데이터를 쭉 접근 가능

쭉이란, 각 값들이 메모리에 연속적으로 저장되어 있음

게다가 각 element가 같은 dtype이라, +N byte형태로 빠른 element 연속 접근이 가능

list의 경우 각 파란색 값이 메모리에 연속적으로 존재하지 않음

ob_item 내에 각 element의 reference(메모리 주소)를 갖고 있다.

그 reference를 타고 가더라도, 객체 자체가 있고, 그 객체 내에 ob_digit(객체가 int라면)로 가야 element에 접근

즉, 접근단계가 ndarray(1)에 비해 list(3)가 접근 단계가 많다.

그리고 next element에 접근할 때도 ndarray(1)인데 list(3)이므로 접근 방식 자체에서 느린 구조이다.

결론

ndarray는

dtype이 similar한 녀석들로 만들면 고속 접근이 가능

list는

dtype이 different하더라도 담을 수가 있음, 따라서 무한한 정수가 가능(담긴 element int가 아무리 커져도 int32 형태로 제한이 걸릴 일은 없다는 것)

참고자료:

towardsdatascience.com/how-fast-numpy-really-is-e9111df44347

spyhce.com/blog/cpython-data-structures

www.youtube.com/watch?v=fiYD0yCou4k

set/dictionary는

hash table

hash collision을 막는 방법으로는 closed hashing(open addressing, 같은 의미인데 하나는 closed, 하나는 open...)

따라서, 특정 element가 set/dictionary에 존재하냐는

element의 hash값을 구하고 그 위치만 따지면 되므로 O(1)

참고자료:

stackoverflow.com/questions/327311/how-are-pythons-built-in-dictionaries-implemented

jinyes-tistory.tistory.com/10

jinyes-tistory.tistory.com/11

jinyes-tistory.tistory.com/12