개수를 유지하기위한 인덱스가있는 PriorityQueue

Question

Java에서 종종 발생하는 문제 (일반적으로 전산 언어 코드 작성 중)는 데이터 세트의 일부 항목 발생 횟수를 계산 한 다음 해당 횟수로 항목을 정렬해야합니다. 가장 간단한 예는 단어 계산입니다. 텍스트 파일에서 각 단어의 발생 횟수를 계산 한 다음, 가장 자주 사용되는 단어를 찾기 위해 단어 수를 정렬해야합니다.

불행히도 Java는이 작업에 적합한 데이터 구조를 갖고 있지 않습니다. 내가 계산할 때 컬렉션의 인덱스로 단어를 사용해야하므로 단어를 읽을 때마다 올바른 카운터를 효율적으로 찾아 볼 수 있지만 정렬하려는 값은 카운트가 아니라 숫자입니다. 말.

Map<String, Integer>은 단어와 관련된 수를 찾는 데 필요한 인터페이스를 제공하지만지도는 키 (예 : TreeMap)로만 정렬 할 수 있습니다. PriorityQueue은 당신이 제공하는 비교기를 정렬 할 수있는 좋은 힙 구현이지만 어떤 종류의 인덱스로 요소에 액세스 할 수있는 방법이 없으며 요소를 업데이트하고 다시 heapify 할 수 없습니다 (제거 및 추가를 제외하고) . 단일 유형 매개 변수를 사용하면 단어와 카운트를 함께 사용하여 하나의 객체로 묶어야합니다.

Map<String, Integer> wordCounts = countStuff(); 
PriorityQueue<NamedCount> sortedCounts = new PriorityQueue<>(wordCounts.size(), 
              Collections.reverseOrder()); 
for(Entry<String, Integer> count : wordCounts.entrySet()) { 
    sortedCounts.add(new NamedCount(count.getKey(), count.getValue())); 
} 

(NamedCount는 단순한 pair<string, int> 구현하는 것을 주 :

내 현재 "솔루션"은 다음을 정렬 할 PriorityQueue로 모두 복사를 계산하는 동안지도의 수를 저장하는 것입니다 Comparable)를 사용하여 정수를 비교하십시오. 그러나 이것은 비효율적입니다. 특히 데이터 세트가 매우 커질 수 있고 메모리에 두 세트의 카운트 세트를 유지하는 것이 낭비입니다.

PriorityQueue 안에있는 객체에 무작위로 액세스 할 수있는 방법이 있습니까? 그렇다면 PriorityQueue에 하나의 복사본을 저장하고 업데이트 할 때 다시 복사 할 수 있습니까? PriorityQueue<NamedCount>에있는 객체에 "포인터"를 유지하는 Map<String, NamedCount>을 사용하는 것이 합리적입니까?

Answer 1

우선 Set<String>이 Map<String, Boolean>보다 바람직합니다. 그것은 더 깨끗한 API이고 증가를 캡슐화합니다.

자, 이것이 나인 경우 사용자 정의 Multiset을 구현하여 몇 가지 추가 로직을 추가하여 카운트를 인덱싱하고 리턴합니다. 다음과 같이 입력하십시오.

class IndexedMultiset<T extends Comparable<T>> extends ForwardingMultiset<T> { 

    private final Multiset<T> delegate = HashMultiset.create(); 
    private final TreeMultimap<Integer, T> countIndex = TreeMultimap.create(); 

    @Override 
    protected Multiset<T> delegate() { 
     return delegate; 
    } 


    @Override 
    public int add(T element, int occurrences) { 
     int prev = super.add(element, occurrences); 
     countIndex.remove(prev, element); 
     countIndex.put(count(element), element); 
     return prev; 
    } 

    @Override 
    public boolean add(T element) { 
     return super.standardAdd(element); 
    } 

    //similar for remove, setCount, etc 


} 

그런 다음 계산에 필요한 쿼리 기능을 추가하십시오. 예를 들어, 단어의 반복 가능한 검색/같은 것을 볼 수 있었다 내림차순으로 쌍을 수 :

public Iterable<CountEntry<T>> descendingCounts() { 
    return countIndex.keySet().descendingSet().stream() 
      .flatMap((count) -> countIndex.get(count).stream()) 
      .map((element) -> new CountEntry<>(element, count(element))) 
      .collect(Collectors.toList()); 
} 

public static class CountEntry<T> { 
    private final T element; 
    private final int count; 

    public CountEntry(T element, int count) { 
     this.element = element; 
     this.count = count; 
    } 

    public T element() { 
     return element; 
    } 

    public int count() { 
     return count; 
    } 

    @Override 
    public String toString() { 
     return element + ": " + count; 
    } 
} 

을 그리고 그것은 모두 같이 사용됩니다 : 당신은 자바 8 사용하는 경우

public static void main(String... args) { 
    IndexedMultiset<String> wordCounts = new IndexedMultiset<>(); 

    wordCounts.add("foo"); 
    wordCounts.add("bar"); 
    wordCounts.add("baz"); 
    wordCounts.add("baz"); 

    System.out.println(wordCounts.descendingCounts()); //[baz: 2, bar: 1, foo: 1] 


    wordCounts.add("foo"); 
    wordCounts.add("foo"); 
    wordCounts.add("foo"); 

    System.out.println(wordCounts.descendingCounts()); //[foo: 4, baz: 2, bar: 1] 
} 

Answer 2

당신은 구아바 같은 타사 라이브러리를 사용할 수있는 경우는, Multiset이 문제에 대한 해결책으로 꽤 특별히 설계 :

구아바의 Multiset<String>가에 Map<String, Integer>하는 것이 바람직하다 일반적으로 기본 데이터 구조에 대한,

Multiset<String> multiset = HashMultiset.create(); 
for (String word : words) { 
    multiset.add(word); 
} 
System.out.println(Multisets.copyHighestCountFirst(multiset));