java - Javaで二項関係を表す

Question

ある有名なプログラマーは、「なぜ誰もがDBを必要としているのか、ハッシュテーブルを教えてください！」と言っています。文法記号とその頻度のリストがあります。マップの1つの方法：symbol＃->frequency。逆に言えば、その[二項]関係です。問題：頻度で上位5つのシンボルを取得します。

より一般的な質問。私は[二項]関係代数がゆっくりとCS理論に浸透していることを知っています。関係をサポートするJavaライブラリはありますか？

Answer 1

 List<Entry<String, Integer>> myList = new ArrayList<...>();
 for (Entry<String, Integer> e : myMap.entrySet())
       myList.add(e);

 Collections.sort(myList, new Comparator<Entry<String, Integer>>(){

    int compare(Entry a, Entry b){
       // compare b to a to get reverse order
       return new Integer(b.getValue()).compareTo(new Integer(a.getValue());
    }
 });

 List<Entry<String, Integer>> top5 = myList.sublist(0, 5);

もっと効率的：

 TreeSet<Entry<String, Integer>> myTree = new TreeSet<...>(
    new  Comparator<Entry<String, Integer>>(){

      int compare(Entry a, Entry b){
         // compare b to a to get reverse order
         return new Integer(b.getValue()).compareTo(new Integer(a.getValue());
      }
    });
 for (Entry<String, Integer> e : myMap.entrySet())
       myList.add(e);

 List<Entry<String, Integer>> top5 = new ArrayList<>();
 int i=0;
 for (Entry<String, Integer> e : myTree) {
     top5.add(e);
     if (i++ == 4) break;
 }

Answer 2

完成したシンボルHashTableがすでにあると仮定した場合の一般的なアルゴリズムは次のとおりです。

1. 2つの配列を作成します。
   • freq [5] //これを使用して、これまでに最も頻繁に見られた5つの頻度カウントを保存します
   • word [5] //これを使用して、これまでに見た上記の配列に対応する単語を保存します
2. イテレータを使用して、HashTableまたはMapをトラバースします。
   • 現在のシンボルの頻度をfreq[5]の頻度と順番に比較します。
   • 現在のシンボルの頻度が上記の配列ペアのどのエントリよりも高い場合は、そのエントリとその下のすべてのエントリを1つの位置にシフトします（つまり、5番目の位置がキックアウトされます）
   • 現在のシンボル/周波数ペアを新しく空いた位置に追加します
   • それ以外の場合は無視してください。

分析：

• HashTableに表示される各シンボルの配列に対して、最大5回の比較（定数時間）を行うため、これはO（n）です。
• 配列のエントリを下にシフトする必要があるたびに、それは一定時間でもあります。毎回シフトを行うと仮定すると、これはまだO（n）です

スペース：配列を格納するためのO（1）

ランタイム：すべてのシンボルを反復処理するO（n）

Answer 3

それでTreeSet簡単なはずです：

int i = 0;
for(Symbol s: symbolTree.descendingSet()) {
    i++;
    if(i > 5) break; // or probably return
    whatever(s);
}