정의되지 않은 인덱스의 기본값이있는 가장 빠른 데이터 구조입니까?

Question

인덱스에 액세스 할 때 값을 반환하는 2 차원 배열을 만들려고합니다. 그러나 정의되지 않은 인덱스에 액세스하면 콜백을 호출하고 해당 값으로 인덱스를 채운 다음 값을 반환합니다.

배열에도 음수 인덱스가 있지만 4 배열 (0,0 주위의 각 사분면에 하나씩)을 사용하여이를 극복 할 수 있습니다.

Answer 1

는 다음과 같은 행동, 튜플 및 사전에 의존하는 Matrix 클래스를 생성 할 수 있습니다 :이 질문은 아마 유래 너무 광범위

from collections import namedtuple 
2DMatrixEntry = namedtuple("2DMatrixEntry", "x", "y", "value") 
matrix = new dict() 
defaultValue = 0 

# add entry at 0;1 
matrix[2DMatrixEntry(0,1)] = 10.0 

# get value at 0;1 
key = 2DMatrixEntry(0,1) 
value = {defaultValue,matrix[key]}[key in matrix] 

건배

Answer 2

. - 일반적인 "one size fits all"솔루션이 없기 때문에 결과는 사용 된 언어 (및 표준 라이브러리)에 많이 의존합니다.

이 질문에는 몇 가지 문제점이 있습니다. 우선 우리가 2 차원 배열을 고려하자.이 배열은 이미 언어의 일부분이며 이러한 배열은 액세스시 동적으로 커진다. 이것이 사실이 아닌 경우 질문은 언어에 따라 달라집니다.

이제는 메모리를 할당 할 때 언어가 자동으로 스팟을 초기화합니다 (다시 언어가 어떻게되는지, 가장 좋은 방법은 RAII를 살펴보십시오). 비록 특정 세포의 실제 계산이 (할당과 비교할 때) 값이 비쌀 수도 있음을 예측할 수는 있지만. 이 경우 흥미로운 것은 "2 단계 구성"이라고 할 수 있습니다. 배열은 튜플/객체로 채워야합니다. 객체의 기본 구성은 비트/부울을 거짓으로 설정합니다. 즉 값이 준비되지 않았 음을 나타냅니다. 다음 acces (즉, get() 메서드 또는 operator() - 언어에 따라 다름)이 비트가 거짓이면 구성하고 그렇지 않으면 그냥 읽습니다.

---

또 다른 방법은 사전/키 - 값 맵을 사용하는 것입니다. 여기서 키는 좌표이고 값은 값입니다. 이것은 구조체 접근의 문제가 데이터 구조에 상속된다는 이점을 가지고있다. 그러나지도 사용의 단점은 값의 조회 속도가 O (1)에서 O (logn)로 변경된다는 것입니다. (실제 시간은 언어에 따라 크게 다릅니다.)

---

마지막으로, 더 구체적인 요구 사항, 사용한 언어 및 기타 라이브러리에 따라 다릅니다. 결국에는 각 언어에 하나의 데이터 구조 만 있습니다. 할당되지 않은 값의 긴 시퀀스입니다. 그보다 진보 된 언어는 언어에 따라 다릅니다.