java - 在java中表示二元关系

Question

一位著名的程序员说“为什么有人需要数据库，只要给我哈希表！”。我有语法符号列表及其频率。一种方式是地图：符号#->频率。另一种方式是[二元]关系。问题：按频率获得前 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

有了TreeSet它应该很容易：

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

Answer 3

这是一个通用算法，假设您已经有一个完整的符号 HashTable

1. 制作2个数组：
   • freq[5] // 使用它来保存迄今为止最常见的 5 个频率计数
   • word[5] // 用这个保存上面数组对应的单词，目前看到的
2. 使用迭代器遍历您的 HashTable 或 Map：
   • 按顺序将当前符号的频率与 freq[5] 中的频率进行比较。
   • 如果当前符号的频率高于上述数组配对中的任何条目，则将该条目及其下方的所有条目移动一个位置（即第 5 个位置被踢出）
   • 将当前符号/频率对添加到新空出的位置
   • 否则，忽略。

分析：

• 您最多对 HashTable 中看到的每个符号的数组进行 5 次比较（恒定时间），所以这是 O(n)
• 每次您必须将数组中的条目向下移动时，它也是恒定的时间。假设你每次都换班，这仍然是 O(n)

空间：O(1) 来存储数组

运行时：O(n) 遍历所有符号