나는 1 백만 ID의 큰 배열/목록을 가지고 있으며 사용할 수있는 첫 번째 무료 ID를 찾아야합니다. 이 데이터 구조를 참조하고 (나중에 사용 된 것으로 표시되어야하는) id를 취한 후 나중에 다시 반환하는 모듈이 있다고 가정 할 수 있습니다 (자유롭게 표시해야합니다). 어떤 데이터 구조를 사용할 수 있는지 알고 싶습니다. 그리고이 알고리즘을 효율적으로 시간과 공간을 처리하는 데 사용할 수있는 알고리즘은 무엇입니까? 이미 존재하는 경우 여기에, 나는 게시하기 전에 검색 않았다면 용서해주십시오.첫 번째 무료 색인 검색
단순하지만 효율적인 방법은 모든 ID를 스택에 저장하는 것입니다. ID 가져 오기는 일정 시간 작동입니다. 목록의 첫 번째 항목을 팝합니다. 작업이 끝나면 스택의 ID를 누릅니다.
최소 자유 ID가 반환되어야하고 무료 ID가 아닌 경우 최소 O (로그 N)에 삽입 및 팝이있는 최소 힙을 사용할 수 있습니다.
올바른 장소를 찾기 위해 스택을 스캔해야하기 때문에 ID O (n)을 다시 삽입하는 비용이 들지 않습니까? – templatetypedef
@templatetypedef 아니요, 목록의 모든 ID가 사용 가능해야하기 때문에 일정 시간이어야합니다. 상단에 삽입하는 것이 좋습니다. – log0
오 - 우리가 질문을 다르게 해석하고 있다고 생각합니다. 나는 "우선적으로"OP는 "최저"를 의미하는 반면, "자유로운 것"으로 해석한다고 생각했습니다. 이 경우 큰 도움이됩니다. – templatetypedef
글쎄, 배열이 아마도 최상의 구조는 아닙니다. 해시가 더 좋을 것입니다. 각 "노드"의 구조에 관해서는, 내가 필요한 모든 것을 볼 수있는 것은 ID 뿐이며 사용되는지 아닌지입니다.
다음 무료 ID 번호를 어떻게 추적 하시겠습니까? – templatetypedef
초기 아이디어로는 사용되지 않은 모든 ID의 우선 순위 큐를 저장하고 높은 ID보다 낮은 ID가 대기열에서 제외되도록 정렬 할 수 있습니다. 표준 바이너리 힙을 사용하면 O (log n) 시간에 사용되지 않은 ID 풀에 ID를 반환하고 O (log n) 시간에 다음 사용 가능 ID를 찾을 수 있습니다. 이것은 모든 ID를 명시 적으로 저장해야한다는 단점이 있습니다. 엄청난 수의 ID가있는 경우 공간 비효율적 일 수 있습니다.
하나의 잠재적 인 공간 절약 최적화는 연속 ID 값을 ID 범위로 결합하려고 시도하는 것입니다. 예를 들어 무료 ID가 1, 3, 4, 5, 6, 8, 9, 10 및 12 인 경우 1, 3-6, 8-10 및 12 범위 만 저장할 수 있습니다. 기본 데이터 구조를 약간 변경하십시오. 바이너리 힙을 사용하는 대신 범위를 저장하는 균형 이진 검색 트리를 사용할 수 있습니다. 이 범위는 겹치지 않으므로 다른 범위보다 작거나 같거나 큰 범위를 비교할 수 있습니다. BST는 정렬 된 순서로 저장되기 때문에 트리의 최소 요소 (O (log n) 시간)를 취하고 해당 범위의 최하위를 보면 첫 번째 자유 ID를 찾을 수 있습니다. 첫 번째 요소를 제외하도록 범위를 업데이트하면 트리에서 빈 범위를 제거해야 할 수 있습니다. 사용되지 않은 ID 풀에 ID를 반환 할 때 선행 및 후속 검색을 수행하여 ID 직후에 오는 범위를 결정할 수 있습니다. 둘 중 하나가 해당 ID를 포함하도록 확장 될 수 있으면 범위를 확장 할 수 있습니다. 두 범위를 병합해야 할 수도 있습니다. 이것은 또한 O (log n) 시간 만 걸립니다.
희망이 도움이됩니다.
이것은 데이터베이스의 시퀀스 객체와 같은 개념입니다. 잘 작동한다. –
자세한 설명 주셔서 감사합니다. Fenwwick 트리가 어느 것이 최소의 복잡성/공간/시간으로 완료 될 수 있는지 알아보기 위해 다른 접근 방법으로 언급 한 접근법을 구현해야합니다. –
연결된 목록 (ID의 연결된 목록)을 사용해보십시오. Linkup 모든 목록과 머리는 무료 목록을 가리켜 야합니다 (init에서 모두 무료라고 말하십시오). 사용 된 것으로 표시 될 때마다이를 제거하고 목록의 끝에 놓고 헤드가 다음 사용 가능 목록을 가리 키도록하십시오. 이 방법으로 귀하의 목록은 "무료에서 중고"방식으로 구성됩니다. O (1)에서 무료 목록을 얻을 수도 있습니다. 또한 id가 free로 표시되면 링크 된 목록의 첫 번째 구성원으로 사용 가능하게됩니다 (즉, 사용 가능한 상태가 됨). 즉,이 목록에 헤드 포인트를 지정합니다. 희망이 도움이 될 것입니다!
프리앰블 : 바이너리 힙이 실제로 가장 좋은 대답 인 것 같습니다. 나는 여기에 대안을 제시 할 것이고, 그것은 몇몇 시나리오에서 이점을 가질 수도있다.
가능한 한 가지 방법은 Fenwick Tree입니다. 위치가 이미 사용되었는지 여부를 나타내는 0 또는 1의 각 위치를 저장할 수 있습니다. 그리고 이진 탐색 (첫 번째 범위 [1..n]을 찾기 위해 합계 n-1을 가짐)을 사용하여 첫 번째 빈 위치를 찾을 수 있습니다.이 작업의 복잡도는 O 바이너리 힙보다 더 나쁜 것입니다 (^ 2 로그 n),하지만이 방법은 또 다른 장점이 있습니다
를 (로그 n) O의 범위의 밀도 (사용/총 식별자의 수)를 계산할 수 있습니다 id를 해제하면 목록의 뒤쪽에 추가 할 수 있습니다. 그리고 잠시 동안 목록을 정렬하여 다시 확인하십시오. 할당 한 ID는 낮은 쪽에서 나옵니다.
이 문맥에서 무엇을 의미합니까? 무료 ID 또는 최소 ID (합당한 주문이 있다고 가정) 또는 ID 목록의 첫 번째 ID가 필요합니까? 그것들 각각은 다른 해결책을 줄 것입니다. – Joel
1 백만 개의 특정 ID와 관련된 ID가 있습니까? 아니면 고유 ID 만 있으면됩니까? 유일한 ID가 필요하면 간단히 합리적인 조건을 가정하고 충돌 가능성이 0 인 고유 한 GUID를 생성 할 수있는 라이브러리입니다. – log0