Arrays Are So Often A Bad Choice

반응형

저는 오랫동안 물리학 연구소에서 일하다가 마침내 과학 소프트웨어 산업으로 전환했습니다. 연구소의 많은 과학자들은 데이터 분석이나 실험실 하드웨어를 제어하기 위해 자신만의 소프트웨어를 개발해야 했다. 그러나 그곳의 물리학자들과 엔지니어들은 훌륭한 과학자들임에도 불구하고 일반적으로 전문적인 소프트웨어 개발에 대한 경험이 거의 없었다. 그들 대부분은 프로그래밍을 스스로 배웠고, 종종 온라인 신병 훈련소에서 배웠다. 하지만 분명히, 그것은 그들을 여기까지 데려왔을 뿐이다. 대부분의 사람들이 생성한 코드는 대부분 유지보수가 불가능하고 읽을 수 없으며 종종 성능 문제로 어려움을 겪는다. 어느 순간부터 저는 박사과정 학생들이 가장 흔한 실수를 피할 수 있도록 실습 강좌를 개설하기 시작했습니다. 제가 세계에서 가장 위대한 소프트웨어 개발자라고 주장하는 것도 아니고, 일반적으로 사람들이 어떤 신뢰할 수 있는 코드를 만들기 위해 전문가가 될 필요는 없지만, 소프트웨어를 쓰는 모든 사람들(전문 소프트웨어 개발자들뿐만 아니라)이 알아야 할 것들이 정말 있습니다. 그리고 그런 것들 중 일부는 전형적인 신병 훈련소의 기본을 넘어선 것 같다. 한 가지 예로, 이 글의 주제는 데이터 구조의 올바른 선택입니다. 제 수업에서 제가 발견한 것은 학생들이 사물 모음을 다룰 때마다 항상 배열을 사용하길 원한다는 것입니다. 많은 사람들은 다른 용기 종류가 존재한다는 것을 몰랐고, 그 존재를 알고 있던 사람들조차도 그것을 고려하지 않았다. 그들은 항상 반사적으로 배열을 사용했다. 하지만 어레이는 종종 잘못된 선택입니다! 그래서 저는 그들에게 전형적인 기본 용기 타입의 장단점을 소개하고 사용법을 교육했습니다. 그것이 그들에게 유용했기 때문에, 적어도 여러분 중 일부에게도 유용할 수 있습니다. 언어로는 파이썬과 표준 라이브러리를 선택하지만 다른 프로그래밍 언어도 마찬가지입니다.

배열

프로그래밍 언어를 배우는 모든 사람이 접하는 가장 기본적인 컨테이너 유형은 배열이다. 메모리에서 배열은 메모리의 연결된 블록으로, 한 항목씩 내부에 저장한다. 그리고 각각의 아이템은 메모리 배열 블록 안에서 같은 크기를 가지고 있습니다.

 

따라서 컴퓨터는 배열 시작의 메모리 주소를 알고 있으므로 시작 주소에 단일 항목 크기의 k배를 추가하기만 하면 k번째 항목의 위치를 알 수 있습니다. 좋은 생각이고, 사실 그렇긴 한데, 단점도 있어요. 어레이 구조를 자주 변경해야 하는 경우 어레이를 선택하는 것이 좋지 않을 수 있습니다. 배열의 시작 부분에 항목을 삽입할 때 발생하는 상황을 고려합니다. 컴퓨터는 배열 앞에 있는 메모리를 단순히 사용할 수 없습니다. 대부분의 메모리는 다른 데이터에 이미 사용되고 있기 때문입니다. 따라서 어레이의 메모리 블록을 항목 크기의 한 배만큼 늘린 다음 모든 항목을 한 단계 더 이동시키는 방법밖에 없으므로 복사 작업이 많이 필요합니다. 그러면 공간은 새로운 0번째 요소를 쓸 수 있는 여유 공간이 됩니다. 코드 관점에서 요소를 삽입하는 것은 메서드 호출에 불과하다. 하지만 여러분은 항상 무대 뒤에서 공연을 갉아먹을 수 있는 많은 일들이 일어나고 있다는 것을 명심해야 합니다.

한 가지 더 고려해야 할 것은 가독성이다. 컨테이너에 저장하려는 객체의 순서가 시간 순서이고 가장 이른 객체나 최신 객체를 원하는 경우 배열 표기법이 정상입니다. 그러나 RGB 색 코드를 저장하는 것과 같이 자연스러운 순서가 없다면, color_code[3]라고 말하면 배열에서 4번째 색상을 얻을 수 없다. color_codes를 쓸 수 있다면 훨씬 가독성이 있지 않을까요?RED`] 대신에요? 음, 할 수 있지만, 배열로는 안 돼요 그게 우리가 다음 단계로 넘어가는 거야.

사전

두 번째 기본 컨테이너 타입은 파이썬이 "사전"이라고 부르는 것이다. 이 데이터 구조는 다양한 이름으로 실행됩니다. 자바에서는 해시맵, 다른 곳에서는 키 값 테이블이라고 하며, 일반적으로 연관된 데이터 구조체라고 부르기도 한다. 그러나 원칙적으로, 그것은 사용자에게 모두 동일합니다. 일반적인 기능은 인덱스가 아니라 이름(키)으로 데이터 항목(값)에 액세스하고 저장하는 것입니다. 파이썬에서, 당신은 이렇게 말할 것이다.

color_codes = {
      'RED': '#FF0000',
      'GREEN': '#00FF00',
      'BLUE': '#0000FF'
}

 

따라서 color_codes[와 같은 단일 항목에 액세스할 수 있습니다.RED] 항목에 자연적인 순서가 없는 경우, 훨씬 더 읽기 쉬운 코드로 이어지는 경우가 많습니다. 컴퓨터는 키에서 요청된 항목의 메모리 위치를 계산할 수 있습니다(구현에 따라 달라짐). 그래서 그것은 사전이라고 불립니다. 항목 키를 기준으로 메모리 위치를 "조회"합니다. 사전 자체에 있는 개체들은 연속된 메모리 묶음에 저장되지 않지만 일반적으로 메모리 전체에 분산되어 있습니다. 이 접근 방식의 장점은 새 항목을 삽입할 때 컴퓨터는 새 항목의 키에 해당하는 위치에 새 메모리를 예약해야 한다는 것입니다. 다른 모든 항목은 현재 위치에 유지되며 복사 작업이 포함되지 않습니다. 반면에 여기에는 단점도 있습니다. 언제나 그렇듯이, 케이크도 먹을 수 없고 먹을 수도 없습니다. 사전의 단일 항목에 액세스하는 속도는 빠르지만 많은 항목에 액세스하는 속도는 다소 느릴 수 있습니다. 그게 무슨 뜻이죠? 특히 수치 계산의 경우 많은 데이터를 처리하는 경우가 많으며 데이터를 CPU의 레지스터로 최대한 빨리 가져오는 것이 매우 중요합니다. 배열의 단일 항목에 액세스하면 시스템이 이를 레지스터에 로드하고 캐시에 저장합니다. 그러나 요청한 항목뿐만 아니라 인접 항목도 필요하지 않더라도 캐시에 저장됩니다! 중요한 것은, 많은 경우 하나의 항목뿐만 아니라 다른 항목에도 작업을 해야 한다는 것입니다. 그리고 다음 항목이 이미 캐시에 저장되어 있다면(램 메모리에 비해 번개처럼 빠름), 컴퓨터는 캐시에서 직접 다음 항목을 레지스터에 로드할 수 있으며(캐시 적중이라고 함) 느린 RAM 메모리에서 로드할 필요가 없다. 하지만 사전의 경우, 그러한 속임수는 효과가 없습니다! 사전의 다양한 항목이 메모리 전체에 분산되어 있으므로 단일 항목에 액세스하면 항목 자체가 캐시에 저장되지만 요청된 항목에 근접하지 않기 때문에 다른 항목은 캐시에 저장되지 않을 수 있습니다. 그러므로 당신이 당신의 코드에서 다음 항목에 접근할 때, 컴퓨터는 캐시에서 그것을 찾지 못할 것이고 느린 RAM 메모리에서 그것을 강제로 로드해야 할 것이다. 일반적인 비즈니스 애플리케이션에서는 이 방법이 문제가 되지 않는 경우가 많지만, 컴퓨팅 집약적인 경우에는 이 방법이 엄청난 차이를 만들어 낼 수 있습니다!

놓다

배열과 사전 모두 일부 개체의 여러 복사본을 동일한 컨테이너에 저장할 수 있습니다. 원하는 경우도 많지만 컨테이너에 있는 개체의 고유성을 적용하려는 경우도 있습니다. 후자의 경우 데이터 구조로 원하는 것이 세트입니다. 수학 집합처럼 집합에 요소를 두 번 추가하려고 해도 변경되지 않습니다. 따라서 고유성 제약 없이 세트에 간단히 추가할 수 있습니다. 예를 들어, 파이썬에서 우리는 다음과 같이 말할 수 있다.

s = set()
s.add('Apple')
s.add('Orange')
s.add('Apple')
s.add('Orange')
print(s)
Out:
{'Orange', 'Apple'}

집합은 합집합, 교차점, 차이 등과 같은 일반적인 수학 집합 연산을 허용합니다. 사전의 경우 집합 순서가 지정되지 않습니다. 따라서 집합 요소를 반복할 때 요소가 추가된 순서와 반복이 동일하다는 보장은 없습니다. 상세 내역은 세트 구조의 구현에 따라 달라지지만, 이에 대해 어떠한 가정도 해서는 안 됩니다. 그냥 무질서하다고 생각해. 현재로서는, 우리는

 

for el in s:
    print(el)
Out:
Orange
Apple

또한 사전과 마찬가지로 요소가 메모리 어디에 저장되는지도 보장하지 않습니다. 따라서 요소가 메모리 전체에 분산되어 있으며 사전과 마찬가지로 고속 액세스에도 영향을 미친다고 가정해야 합니다.

연결된 목록

그러나 파이썬 표준 라이브러리에 포함되지 않은 또 다른 공통 데이터 구조는 링크 리스트이다. 파이썬으로 목록을 만들면

a = list()
a.extend([1, 2, 3])
print(a)
Out:
[1, 2, 3]

 

연결된 목록이 아니라 동적 배열입니다! 그 이름 짓기는 매우 유감스럽다. 그렇다면 진정한 링크드 리스트란 무엇일까요? 즉, 모든 요소가 두 부분으로 구성되어 있는 데이터 컨테이너입니다. 첫째, 데이터 자체와 둘째, 다음 요소가 저장되는 위치에 대한 포인터입니다.

링크된 목록의 중간쯤에 있는 특정 요소에 액세스하려는 경우 컴퓨터는 목록의 시작 부분에서 시작하여 원하는 요소가 발견될 때까지 목록의 모든 요소를 따라 포인터를 따릅니다. 따라서 정확한 위치를 달리 계산할 수 없기 때문에 컨테이너의 일부가 통과되어야 하기 때문에 요소 접근이 느립니다. 반면에 복사 작업이 필요하지 않기 때문에 요소를 어딘가에 삽입하는 것은 빠릅니다. 새 요소는 메모리의 아무 곳에나 생성되고 선행 요소의 포인터는 새 요소를 삽입하기 위해 리디렉션됩니다. 링크 리스트는 유행이 지난 것처럼 보이며, 파이썬과 같은 일부 프로그래밍 언어들은 기본적으로 더 이상 링크 리스트를 지원하지 않는다. 네, 특별한 사유가 없는 한 사용하지 않는 것을 추천합니다. 하지만 자연스레 좋은 이유가 떠오르지 않는다. 대부분의 경우 링크된 목록의 장점은 링크된 목록의 느린 요소 접근이라는 단점이 없이 사전에서 더 잘 다루어진다.

트리, 대기열, 스택 등

더 중요한 컨테이너 데이터 구조가 많이 있으며, 이 구조들은 모두 특정한 강점과 약점을 가지고 있다. 예를 들어, 트리는 빠른 검색을 수행하거나 요소를 특정 순서로 가져올 때 특히 유용합니다. 나는 이 기사의 후속으로 그 구조들 중 몇 가지를 설명할 것이다. 관심이 있으시다면 채널 고정해 주세요. 읽어주셔서 감사합니다!