키 값 쌍 평가에 가장 적합한 데이터 구조

Question

다음과 같이 사전 정의 된 일치가 있습니다. 상위 ENTITY에 연관된 키 값 집합이 있습니다. 키 2는이 개 값을 가지고 있으며, KEY3은 하나의 값을 가지며, 키 1 세 값이 의미

{ 
    key1 : [v11,v12,v13], 
    key2 : [v23,v24], 
    key3 : [v31,v39] 
} 

: 부모 ENTIRY에서 각 SET 나는대로 입력을 받게됩니다

ENTITY A: 
    SET A1. {key1=v11 and key2!=v25} 
    SET A2. {key1=v12 and key3=v31, v33} 
    SET A3. {key1=v15 and key2=v25 and key3=v35} 

Entity B: 
    SET B1. {key1=v16 and key2=v26} 
    SEY B2. {key3!=v39} 
    SET B3. {key1!=v11 and key3=v31} 

과 같이 정의 할 수있다.

그런 다음 모든 키 - 값 일치가 전달 된 키 값 쌍에 의해 충족되는 적어도 하나의 SET을 가진 모든 엔터티를 반환해야합니다.

따라서 위에서 언급 한 엔티티 A의 경우 세트 A1과 세트 A2는 입력에 의해 충족되는 키 ​​- 값 쌍을 갖지만 반면에 ENTITY B의 경우 키 - 값 쌍이 충족되지 않습니다. ENTITY A 만 대답입니다.

200-1000 개의 상위 ENTITIES, 부모 당 20 개의 SET ENTITY & SET 당 200 개의 키 - 값 쌍이있을 수 있습니다. 입력에는 최대 50 개의 키 - 값 쌍이 포함될 수 있습니다.

평가를 위해 외부 DB를 쿼리 할 수 ​​없습니다. 그러나 데이터 구조는 memcache 또는 redis에 저장되도록 직렬화 가능해야합니다.

Answer 1

간단히하기 위해 표기법을 수정하고 파이썬으로 작성하겠습니다.

ENTITY는 '키'라는 레이블이 붙은 사전 세트로 개체 목록을 값으로 사용합니다. 단순화를 위해 이제

E1 = { 
    {'k1': [4], 'k2': [20,12]}, 
    {'k4': [2,20,25], 'k3': [2,3]} 
} 

E2 = { 
    {'k2': [2,3,4], 'k4': [2], 'k3': [14]}, 
    {'k3': [1]}, 
    {'k3': [12,23]} 
} 

입력 다시 '키'에 의해 값으로 오브젝트의 목록으로 표시 다만 사전이며, 값이 숫자 (하지만 우리가 진정으로 필요로하는 것은 바로 비교 작업입니다) 있다고 가정하자.

INPUT = {'k2': [2], 'k3': [14,12] } 

정렬 된 값의 배열을 유지해야한다고 생각합니다. 이렇게하면 선형 시간에 주어진 키에 대한 목록을 비교할 수 있습니다. 전체적으로 주어진 입력에 대한 복잡도는 O (EKL) 여야합니다. 여기서 E는 엔티티의 수이고, K는 키의 수이고 L은 목록의 길이입니다. 마찬가지로 O (EKL) 메모리가 필요합니다.

이 경우 경계 비교에 몇 초가 걸릴 것으로 예상됩니다. 이 충분하지 않으면 다음의 더 생각해 봅시다 :

-

편집 : 당신은 단순히 값을 인덱스로 균형 BST와 함께, 튜플 (ENTITY_ID, set_id, 키, 값)의 집합을 사용할 수 있습니다 . 그런 다음 O (log n)을 검색해야합니다. 이런 구조에 대해 생각해 봤어?