在java中表示二進制關係

Question

一位着名程序員說：「爲什麼有人需要DB，只給我散列表！」。我有語法符號列表及其頻率。一種方式是地圖：符號＃ - >頻率。另一種方式是它的[二元]關係。問題：通過頻率獲得前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個數組：
   • 頻率[5]//用這個來保存到目前爲止最常見的5個頻率計數
   • 字[5] //使用這個保存對應於上述陣列的話，迄今爲止看到
2. 使用迭代器遍歷您的哈希表或地圖：
   • 比較當前符號的頻率對按freq [5]順序排列。
   • 如果當前符號的頻率高於上述陣列配對中的任何條目，則將該條目及其下方的所有條目移動一個位置（即第5個位置被踢出）
   • 將當前符號/頻率對添加到新騰空的位置
   • 否則，忽略。

分析：

• 你讓最多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); 
}