우선 순위 목록을 나타내는 효율적인 데이터 구조를 찾고 있습니다. 특히 항목 집합에 우선 순위를 지정하고 최상위 점수 항목 만 반환해야합니다. 힙을 처리하는 우선 순위 대기열을 살펴 보았지만 실제로는 필요에 맞지 않는 것 같습니다. 대기열에서 최고 평점 항목을 폴링하자 마자 힙 구조가 재구성됩니다.효율적인 우선 순위 목록
가장 간단한 해결 방법은 물론 연결 목록이며, 최악의 경우 삽입 작업에 꽤 오래 걸립니다.
누구에게 더 좋은 해결책이 있습니까?
힙은 매우 적합하며 잘못된 방향으로 가고있는 것처럼 보입니다.
(이 X BTW, n으로 비교하는 방법?) 당신이 최고 X 요소를 원하는 말당신이 최대 힙에 모든 퍼팅 상단 X를 점점하고 있습니다.
대신에 정확히 x 개의 요소로 구성된 최소 힙을 사용하는 것이 좋습니다.
처음 x 개의 요소를 힙에 삽입합니다.
다음 들어오는 요소는 힙에서 매우 빠르게 수행 할 수있는 시간 (O (1) 시간)과 비교됩니다. 더 작 으면 들어오는 요소를 무시하십시오.
들어오는 요소가 min보다 큰 경우 들어오는 요소로 min을 늘리고 힙에서 아래로 이동합니다. 최악의 경우 logx 시간이어야합니다.
완료되면 (nlogx 시간) O (xlogx) 시간에 정렬 된 순서로 힙에서 요소를 검색 할 수 있습니다.
데이터의 크기 (및 x가 작은 크기)에 따라이 힙 힙 솔루션을 사용하면 속도가 매우 빠릅니다.
삽입물이 초고속이기를 원하고 검색에별로 신경 쓰지 않으려면 다음을 수행 할 수도 있습니다.
요소를 벡터 순서대로 나열합니다 (상각 된 O (1) 삽입 시간이있는 배열).
x 번째로 큰 요소 (O (n) 시간이지만 상수는 클 수 있음)를 찾으려면 선택 알고리즘을 사용하십시오. 그 수가
이제 S와 각 요소를 비교 어레이를 걸어
X가 (같은 N/2 일)이 N 합리적 크기와 비교할 경우 S.
만큼 큰 것들을 선택 S. 받았다고 괜찮을 수도 있지만 x가 n에 비해 작 으면 min-heap을 사용하는 것이 좋습니다.나는 이런 식으로 생각하지 않았다. 이것은 매우 유망 해 보입니다. – ladi
흠. Skip lists? 그들은 (힙 기반 큐로) O (log n) 삽입을 가져야하지만 최상위 요소를 얻는 것은 O (1) [제거하는 것을 포함하여] 여야합니다. 잠금없는 알고리즘을 사용하여 구현할 수도 있습니다.
올바르게 사용하면 힙이 목록을 건너 뛰는 것보다 낫습니다. 상단 x가 필요할 때 x 요소의 최소 힙을 사용하십시오. 당신은 모든 n의 트리/힙을 만들 필요가 없습니다. 그냥 엑스. –
죄송합니다 - 제 잘못 (텍스트를 잘못 읽었습니다. 느린 추가 비용으로도 빠른 설문 조사를 원한다는 것을 이해했습니다). –
JDK에는 힙 알고리즘을 기반으로하는 내장 pqueue 클래스 (java.util.PriorityQueue)가 있습니다.
죄송합니다. 귀하의 요구를 충족시키지 못하는 힙에 대해서만 보았습니다. 이유를 설명해 주시겠습니까? 사용자 지정 비교기를 작성하거나 비교할 수있는 항목을 만들면 PriorityQueue에서 항목을 적절하게 정렬합니다.
나는 그를 이해하기 때문에 그는 O (log n)에서 getNext를 받아 들일 수 없다. –
문제는 ladi가 x 항목을 제거하지 않고 x 항목을 가져올 수 있기를 원합니다. 일반적으로 우선 순위 목록에 의해 지원되는 작업이 아닙니다. –
몇 가지 항목을 평가하고 최상위 점수 항목 만 얻으 려합니다. 그래서 최상위 점수 항목 만 보유하고 있지만 목록 인터페이스를 제공하는 데이터 구조가 있다면 방황하고있었습니다. 즉, 내가 최고 득점 항목 목록을 순차적으로 통과 할 수 있음을 의미합니다. 물론 O (log n) 삽입 및 O (n) 재 확보가있는 힙 알고리즘을 기반으로하는 우선 순위 대기열을 사용할 수 있습니다. 최고 득점 요소를 가져 와서 목록에 추가하십시오. 그보다 더 좋은 것이 있다면 나는 단지 호기심이 많았습니다. – ladi
당신은 단지 K 상위 항목이 필요하면 당신은 a를 다른 사람을 볼 필요가, 당신은 간단한 연결리스트 나 배열은 현재 최고 K 항목을 저장, 플러스 번호를합니다 (사용할 수 없습니다 결코 목록에서 요소의 최악의 점수).
Add() 작업에서 항목을 목록의 최악의 값과 비교하면 좋을 경우 현재 최악의 항목을 추가 된 항목으로 바꿉니다. 현재 최악의 점수를 가진 요소를 찾으려면 O (k) 시간이 최악의 경우 삽입에 걸립니다. 그러나 목록에 더 나은 요소를 추가 할 때 스왑을 수행해야 할 확률은 0이됩니다 (즉, 실제로 항목을 추가하지는 않음) 평균적 경우는 O (1)입니다. .
따라서 무작위로 요소를 생성하면 성능이 매우 좋아질 수 있습니다. 주문한 상품 (최악의 경우)을 생성한다고해도 k 값에 충분히 빠를 수 있습니다.
좋은 생각 ...... –
목록 대신 min-heap (내 대답 참조)을 사용하면 최악의 경우 O (logK)가됩니다. 나머지는 비슷합니다. 실제로 min-heaps를 사용하는 것은이 문제에 대한 꽤 표준적인 방법입니다! (x가 n에 비해 작을 때). –
몇 개입니까? 그들은 어디에서나 지속되고 있습니까? 그렇다면 어떻게됩니까? – Lazarus
* 삽입 *, * 검색 * (우선 순위 항목) 및 * 제거 *가 얼마나 효율적인지 더 자세히 말하십시오. – Artelius
나는 먼저 항목을 평가하고 첫 번째 x 최고 득점 항목을 올바른 순서로 검색하려고합니다. 많은 삽입이 있기 때문에 삽입은 오히려 효율적이어야합니다. 재 입국은 덜 효율적일 수 있습니다. – ladi