고유 한 순서 지정 데이터 구조

저장할 데이터가 고정 된 수의 고유 한 값으로 구성된다는 것을 알고 최적의 데이터 구조는 무엇입니까? 특히, 각 카드가 1에서 52까지의 숫자로 표시되는 52 개의 카드 갑판의 상태를 최적으로 저장하려고합니다.고유 한 순서 지정 데이터 구조

출처

2012-04-14 taktoa

1에서 색인보다 간단 것 대부분의 프로그래밍 언어로, 0에서 51까지의 인덱스에 있는지 확인을 순열에 대한 가장 작은 생각 가능한 표현 인 factorial number system을 선택할 수 있습니다.

BTW : 이것은 매우 실제적인 해결책이 아닙니다. 52! 대략 8E67입니다 ;-)

출처

2012-04-14 15:38:14 wildplasser

52 factoradic digits 만 필요하지 않습니까? – taktoa

또한 52! 값은 225 비트로 표현 될 수 있는데, 52 비트 6 비트 값의 배열을 만드는 데 필요한 312 비트보다 작습니다. – taktoa

각 기수 위치를 최소 비트 수로 설정하면 257 비트 (21 * 6 + 16 * 5 + 8 * 4 + 4 * 3 + 2 * 2 + 1)로 계산됩니다. 이것은 약간의 코드 공간을 낭비하지만 비교적 쉽게 digit_at_position_x를 추출합니다. (bignum 사업부는 필요하지 않음) – wildplasser

A 배열/벡터가이 작업을 잘 처리합니다.

가능한 정수 값 사이에 공백없이 정수로 식별 할 수있는 고정 된 수의 개체 (카드)가 있습니다. 이렇게하면 인접한 메모리 블록을 차지하고 값 (인덱싱)을 기반으로 직접 액세스 할 수있는 데이터 구조를 사용할 수 있으며 액세스는 정수 값의 자연 순서를 사용합니다. 이것은 배열/벡터에 완벽하게 맞습니다.

출처

2012-04-14 15:30:23 Attila

배열입니다 확실히 _easiest_ 솔루션 나는 순서를 저장할 때문에, 내가 가장 최적의 솔루션으로 그냥 궁금 해요 값 자체를 저장하지 않고 값의 – taktoa

가장 단순하고 최적 - 최소한의 메모리를 차지하며 요소에 대한 O (1) 액세스 허용, 요소 삭제/삽입을 원하지 않음 - 이것은 배열/벡터가 제공하는 것과 정확히 같습니다 – Attila

당신이 세트의 고유성을 보장하려면 당신은 자바
에 LinkedHashSet을 사용할 수 나는 도서관이/다른 언어를 기대 유사한 순서 문제 및 요소의 고정 된 수 거기는 단순히 배열을 사용하는 점을 감안

출처

2012-04-14 15:32:40

다음과 같은 카드 :

Card[] cards = new Card[52];

은 그냥 당신의 유일한 관심사는 순열합니다 (자연 순서를 WRT)을 표현하는 경우 (52)

출처

2012-04-14 15:35:49

"Attila" 그것이 해결책이 아닌 이유에 대한 대답. – taktoa

@taktoa 값의 순서 만 저장하려면,'Card []'에 카드의 인덱스를 저장하기 위해 52 위치의'int []'를 사용하고, 인덱스에주의하십시오. 카드를 0에서 51까지 색인화하는 것이 더 쉬울 것입니다.) 어느 쪽이든, 여기서 최적의 데이터 구조는 배열입니다. –

데크를 가능한 순서로 매핑하기 위해 하나의 226 비트 정수와 번호 체계가 필요합니다.

Storing a message in a deck of cards

Detailed explanation of the above link

key-deck (간단한 파이썬 코드)

출처

2014-01-14 17:26:22

고유 한 순서 지정 데이터 구조

답변

관련 문제