선형 레이아웃을 허용하는 빠른 알고리즘/데이터 구조?

키 - 값 구조 쌍을 사용할 시스템을 구현하려고합니다. 그들은 일종의 선형 방식 (즉, 인덱스 될 수 있음)으로 유지되어야하며, 일단 주어진 위치는 움직일 수 없으므로 삽입은 추가 만 할 수 있습니다 (그리고 많은 정렬이 가능하지는 않습니다). 그냥 예를 들어이 마음에 가지고있는 것이다 :선형 레이아웃을 허용하는 빠른 알고리즘/데이터 구조?

키가 검색 될 때, 그것의 인덱스가 캐시 된 후 일정 시간에 액세스 할 수 있도록이 같은 시스템을 설계 한

Data list: 
    0: { "somekey", somevalue } 
    1: { "someotherkey", someothervalue } 
    ... 
    n: { "justanotherkey", justanothervalue }

. 이제는 데이터의 순서 나 양을 예측할 방법이 없기 때문에 정렬 할 수 없습니다. 선형 탐색보다 나은 알고리즘이나 데이터 구조에 대한 아이디어가 필요하지만 여전히 제약 조건을 유지해야합니다. 좋아해.

누구나 아이디어가 있습니까? 나는 속도를 많이 낼 수 있을지는 모르겠지만 조금이라도 도움이된다면 내 시스템의 핵심이 될 것입니다. 미리 감사드립니다!

== 편집 ==

(해시 테이블 및 동적 배열과 같은) 두 개의 분리 된 구조를 사용하는 아이디어는 실제로 처음 의도였다. 불행히도 키와 값을 분리 할 수 없기 때문에이 방법은 저에게는 효과가 없습니다. 키는 오류 및 메시지에 사용되므로 색인이 캐시 된 후에도 원래 키에 액세스해야합니다. 기본적으로 배열 구조체 일뿐입니다.

struct Entry { 
    /* Key is actually a complex struct itself with string, and params */ 
    Key key; 
    Data* data; 
}

출처

2012-02-03 Miguel

왜 색인을 캐시해야합니까? 해시 테이블의 핵심은 O (1) 키를 통해 액세스 권한을 부여하는 것입니다. –

@MikeDunlavey 키는 상당히 복잡합니다 (임의의 길이 문자열 및 설정 배열입니다. 여러 키는 동일한 문자열을 가질 수 있지만 설정에 따라 다릅니다).이 유형의 경우에는 좋은 충돌이 발생하지 않습니다. 사용할 수있는 해시 테이블 알고리즘? – Miguel

글쎄, 내가 할 수있는 것은 단지 큰 긴 키를 가져다가 32 비트 또는 64 비트 체크섬 (또는 아마도 메시지 다이제스트)을 취하는 것과 같이 짧은 것으로 결합하거나 또는 비트의 긴 문자열로 변환하는 것입니다. 또는 긴 문자열. 해시 함수가 원하는 것은 무엇이든간에. 해시를 실행하는 데 필요한주기와 비교할 때 주기적으로 너무 비싸지 않아야하며, 초당 몇 번이나 수행해야하는지에 따라 다릅니다. –

하나의 옵션은 해시 테이블과 동적 배열의 조합을 사용하는 것입니다. 아이디어는 다음과 같습니다 - 데이터 구조에 요소를 삽입 할 때마다 요소를 동적 배열에 추가 한 다음 키와 값 쌍이 상주하는 동적 배열에 색인과 관련된 해시 테이블에 키를 삽입합니다. 그런 식으로 인덱스를 검색하려면 동적 배열을 살펴보고 이름을 검색하기 위해 해시 테이블에서 인덱스를 조회 한 다음 해당 인덱스에서 쿼리합니다. 이것은 삽입, 삭제 및 액세스에 대해 예상되는 O (1) 시간을 소요하며 선형 검색보다 훨씬 빠릅니다.

희망이 도움이됩니다.

출처

2012-02-03 00:14:03 templatetypedef

데이터에서 키를 분리 할 수 없기 때문에이 방법이 저에게 효과적이라고 생각하지 않습니다. 질문에 대한 편집을 참조하십시오. :) – Miguel

@ athlon32- 왜 이것이 작동하지 않는지 잘 모르겠습니다. 배열에 키와 값이 들어 있고 해시 테이블에 키가 저장되어있는 경우이 데이터 구조가 작동하지 않는 이유는 무엇입니까? – templatetypedef

글쎄, 그게 효과가 있지만, 만약 내가 항목의 수천을 말하고 과도한 비트 수 있습니다, 그리고 난 그 열쇠에 대한 포인터를 계속 수 있지만, 그게 내가 원하는 것보다 조금 더있을거야. :/그런데, 나는이 질문에서 훨씬 더 많은 것을 기대하지 않는다. 그래서 아마이 방법을 사용해야 할 것이다. – Miguel

배열의 해시 테이블 키 -> 인덱스는 어떻습니까?

출처

2012-02-03 00:12:14 Marcin

선형 레이아웃을 허용하는 빠른 알고리즘/데이터 구조?

답변

관련 문제