누구나 Python에서 훌륭한 스파 스 1 차원 배열 라이브러리를 아십니까?

Question

저는 int64s의 배열을 많이 사용하는 파이썬의 알고리즘을 연구하고 있습니다. 배열은 일반적으로 스파 스 (sparse)하고 지속적으로 읽고 쓰여집니다. 현재 상대적으로 큰 기본 배열을 사용하고 있으며 성능은 좋지만 메모리 사용량은 예상대로 높습니다.

배열 구현을 사용하고 싶지 않은 값을위한 공간을 낭비하지 않고 0 이외의 인덱스 오프셋을 허용하고 싶습니다. 예를 들어, 내 숫자가 1,000,000에서 시작하면 1,000,000부터 배열을 인덱싱 할 수 있기를 원하며 미사용 값이 백만 개가 아닌 메모리를 낭비하지 않아도됩니다.

어레이 읽기 및 쓰기가 빠를 필요가 있습니다. 새로운 영토로 확장하는 것은 약간 지연 될 수 있지만 가능하다면 읽기와 쓰기는 O (1)이어야합니다.

누구나 할 수있는 라이브러리에 대해 알고 있습니까?

감사합니다.

데이터 유형으로 언급 된 int64로 업데이트되었습니다.

Answer 1

blist 유형 (documentation, download)과 같이 들릴 수도 있습니다 (면책 조항 : 저자입니다). Python의 list과 똑같은 인터페이스를 가지고 있으므로 학습 곡선이 없지만 성능 특성이 다릅니다. 특히, 많은 경우에 스파 스리스트를 효율적으로 처리 할 수 ​​있습니다. 다음은 2 ** 29 요소가있는 목록을 만드는 예제입니다. 그것은 거의 즉시입니다. 이런 방식으로 생성 된 스파 스 목록은 O (log n) 공간을 사용합니다. 전체 목록을 반복

>>> from blist import * 
>>> x = blist([0])    # x is a blist with one element 
>>> x *= 2**29     # x is a blist with > 500 million elements 
>>> x.append(5)    # append to x 
>>> y = x[4:-234234]   # Take a 500 million element slice from x 
>>> del x[3:1024]    # Delete a few thousand elements from x 

작업은 여전히 ​​O (n)의 시간 (remove, reverse, count 등)을 가지고. 이 문서는 각 작업의 시간 복잡성에 대해 설명하므로 요구 사항을 충족시킬 수 있는지 평가할 수 있어야합니다.

당신이 당신의 데이터 공간에 색인 공간에서 함수를 정의하여 스파 스 배열을 시뮬레이션 할 수있는 몇 가지 언어에 : 나는 파이썬을 모르는

Answer 2

희박한 배열로 numpy sparse matrix을 다시 매핑하거나 해시 테이블 (python dict)을 사용할 수 있습니다. 오프셋에 관해서는, 사용하고있는 저장 클래스를 랩핑하고, insert/lookup/remove 메소드를 소유하게하십시오.

Answer 3

은 그래서 이것은 아마 않은 대답이다. 예를 들어 (의사 코드) : 일부 언어 (가장 좋은 것들) 배열 참조의 형태로

f[1000000] = 32; 
f[2000000] = 51; 

(예 f[3])는 단지 함수 호출의 형태 (예를 들어 f[3])처럼 보인다. 물론 이것은 배열이 인덱스 공간에서 데이터 공간으로 함수를 정의하기 때문입니다. 이런 식으로 고차원의 희소 배열을 구현하는 것은 매우 쉽습니다.

Answer 4

왜 그냥 딕테이션을 사용하지 않는가?

sparse = dict() 
sparse[100000] = 1234 
sparse[123456] = 2345 

Answer 5

또 다른 옵션은 - 적어도 하나를 직접 구현하고자하는 경우 - Page table이다. 이것은 가상 메모리 시스템에서 가상 주소를 실제 주소에 매핑하는 데 일반적으로 사용되며 주소 공간이 드문 드문 있고 사용 된 주소가 클러스터 된 경우 가장 잘 작동합니다. 사용 된 주소가 무작위로 배포되는 경우 효과가 떨어집니다.

페이지 테이블의 기본 접근 방식은 Trie - 재귀 적 하위 구분과 동일합니다. 페이지 테이블은 고정 된 수의 레벨을 가지며 각 노드는 고정 된 크기의 배열입니다. 지정된 서브 노드의 엔트리가 null의 경우, 그 노드가 가리키는 모든 잎은 null가됩니다. 페이지 테이블의 가장 큰 장점은 조회가 빠르며 약간의 비트 시프트 및 참조 해제 만 필요하다는 것입니다. 난 아직이 질문에 대한 "완벽한"해답을 발견하지 않았습니다

class Pagetable(object): 
    def __init__(self, num_bits=8): 
    """Creates a new Pagetable with num_bits bits per level. 

    Args: 
     num_bits: The number of bits per pagetable level. 
     A 2 level pagetable will be able to store indexes between 0 and 2^(num_bits*2). 
    """ 
    self.num_bits = num_bits 
    self.mask = (1 << num_bits) - 1 
    self.root = [None] * (2 ** num_bits) 

    def __getitem__(self, idx): 
    page = self.root[idx >> self.num_bits] 
    return page and page[idx & self.mask] 

    def __setitem__(self, idx, val): 
    page = self.root[idx >> self.num_bits] 
    if not page: 
     page = self.root[idx >> self.num_bits] = [None] * (2 ** self.num_bits) 
    page[idx & self.mask] = val