如何为TreeMap编写equalsTo/compareTo/hasCode以获取前N个值。

huangapple
go评论90阅读模式
英文:

How to write customer equalsTo/compareTo/hasCode for TreeMap to get Top N values

问题

问题是：客户想要查看到目前为止销售最多的物品。我们希望有效地向客户提供这些数据。

样本输入：
已售物品清单：
F|400
B|1000
A|500
A|600
C|1000
D|700
E|300

样本输出：
A|1100
C|1000
B|1000
D|700

我的想法是在第一个 API processInput() 中，使用一个映射将物品和价值关联起来，以跟踪到目前为止已经销售的所有物品，并将更新后的物品添加到最大优先级队列中。在第二个 API processQuery() 中，只需从队列中选择前 K 个物品。一个问题是在 processQuery 中，时间复杂度是 O(NlogN)。

是否可能通过单个 TreeMap 来解决这个问题，通过覆盖 equalsTo、compareTo 和 hasCode，使 TreeMap 按值排序。这样我们只需迭代 TreeMap 并返回前 N 个物品？

英文:

The question is:<br/>Clients want to see which items are most sold so far. We want to provide this data to our clients efficiently.<br/>Sample input:<br/>List of sold items:<br/>F|400 <br/> B|1000<br/>A|500<br/>A|600<br/>C|1000<br/>D|700<br/>E|300<br/>Sample output<br/>A|1100<br/> C|1000<br/>B|1000<br/>D|700

My thought is in first API processInput(), use a map of item and value to track all items sold so far and then add the updated item into a max priority queue. And in second API processQuery(), just select top K from queue. One issue is in processQuery, time complexity is O(NlogN).<br/><br/> Is it possible we solve this problem with a single TreeMap by overriding equalsTo, 'compareTo, and hasCode so that that treemap is sorted by value. So we just iterate over the TreeMap and return topN items?

答案1

得分: 0

假设输入是以提到的格式为例的字符串列表，第一步 processInput 是将输入列表转换为一些对象{name, num}的列表：

  1. public static List<Obj> processInput(List<String> data) {
  2.     return Arrays.stream(data)
  3.                  .map(s -> s.split("\\|"))
  4.                  .map(arr -> new Obj(arr[0], Integer.parseInt(arr[1])))
  5.                  .collect(Collectors.toList());
  6. }

然后第二个方法按名称分组，累加总值，并返回类似的列表作为结果：

  1. public static List<Obj> getTopTotals(List<Obj> data, int topCount) {
  2.     return data.stream()
  3.                .collect(
  4.                        Collectors.groupingBy(Obj::getName, TreeMap::new,
  5.                        Collectors.summingInt(Obj::getNum)
  6.                 )) // 获得总值的 TreeMap<String, Integer>
  7.                 .entrySet().stream()
  8.                 .sorted((a, b) -> b.getValue().compareTo(a.getValue())) // 按值降序排序
  9.                 .limit(topCount)
  10.                 .map(e -> new Obj(e.getKey(), e.getValue()))
  11.                 .collect(Collectors.toList());
  12. }
英文:

Assuming that the input is a list of strings in the mentioned format, the first step processInput is to convert the input list into list of some objects {name, num}:

  1. public static List&lt;Obj&gt; processInput(List&lt;String&gt; data) {
  2.     return Arrays.stream(data)
  3.                  .map(s -&gt; s.split(&quot;\\|&quot;))
  4.                  .map(arr -&gt; new Obj(arr[0], Integer.parseInt(arr[1])))
  5.                  .collect(Collectors.toList());
  6. }

Then the second method groups by the name, sums up the total value, and returns similar list as a result:

  1. public static List&lt;Obj&gt; getTopTotals(List&lt;Obj&gt; data, int topCount) {
  2.     return data.stream()
  3.                .collect(
  4.                        Collectors.groupingBy(Obj::getName, TreeMap::new,
  5.                        Collectors.summingInt(Obj::getNum)
  6.                 )) // get TreeMap&lt;String, Integer&gt; of totals
  7.                 .entrySet().stream()
  8.                 .sorted((a, b) -&gt; b.getValue().compareTo(a.getValue())) // sort by value desc
  9.                 .limit(topCount)
  10.                 .map(e -&gt; new Obj(e.getKey(), e.getValue()))
  11.                 .collect(Collectors.toList());
  12. }

答案2

得分: 0

你需要在两个方向上都实现高效的访问：当项目到达时，您需要根据它们的名称（A、B、C）获取聚合金额，但是为了对它们进行排序，将使用聚合金额。我认为您可以使用Map来按名称查找项目，并使用SortedSet来进行排序。由于金额本身不是唯一的（例如在示例中，B和C都为1000），所以排序也应该利用名称（因为名称是唯一的），这就是为什么对于排序部分而言，只使用一个集合就足够了：

  1. import java.util.HashMap;
  2. import java.util.Map;
  3. import java.util.SortedSet;
  4. import java.util.TreeSet;
  6. public class Test {
  7.     static class Item implements Comparable<Item> {
  8.         final String name;
  9.         int amount;
  10.         Item(String name, int amount) {
  11.             this.name = name;
  12.             this.amount = amount;
  13.         }
  14.         public int compareTo(Item o) {
  15.             if (o.amount < amount)
  16.                 return -1;
  17.             if (o.amount > amount)
  18.                 return 1;
  19.             return o.name.compareTo(name);
  20.         }
  21.         public String toString() {
  22.             return name + "|" + amount;
  23.         }
  24.     }
  25.     
  26.     Map<String, Item> itemmap = new HashMap<>();
  27.     SortedSet<Item> sorted = new TreeSet<>();
  28.     
  29.     void add(String name, int amount) {
  30.         Item i = itemmap.get(name);
  31.         if (i != null) {
  32.             sorted.remove(i);
  33.             i.amount += amount;
  34.         } else {
  35.             i = new Item(name, amount);
  36.         }
  37.         itemmap.put(name, i);
  38.         sorted.add(i);
  39.     }
  40.     public static void main(String[] args) {
  41.         Test t = new Test();
  42.         t.add("F", 400);
  43.         t.add("B", 1000);
  44.         t.add("xA", 500);
  45.         t.add("xA", 600);
  46.         t.add("C", 1000);
  47.         t.add("D", 700);
  48.         t.add("E", 300);
  49.         System.out.println("itemmap: " + t.itemmap);
  50.         System.out.println("sorted: " + t.sorted);
  51.     }
  52. }

它会产生如下输出（在 Ideone 上测试：https://ideone.com/2d79aC）

  1. itemmap: {B=B|1000, C=C|1000, D=D|700, E=E|300, F=F|400, xA=xA|1100}
  2. sorted: [xA|1100, C|1000, B|1000, D|700, F|400, E|300]

我故意将A重命名为xA，否则itemmap将会是A|1100, B|1000, C|1000，但这只是字母顺序的巧合（对几个连续的单个字母字符串进行哈希处理实际上并不能很好地混合顺序）。C和B以相反的顺序出现是因为这是您要求的。如果您希望它们是B，然后是C，请交换compareTo()方法的返回值，或者只需将当前返回值添加一个负号。

英文:

You need efficient access in both directions: when items come, you need to get the aggregated amount based on their name (A,B,C), but for sorting them, the aggregated amount is going to be used. I think you could use a Map for finding items by name, and a SortedSet for sorting. As amounts themselves are not unique (like B and C have both 1000 in the example), sorting should also make use of the name (as those are unique), and that's why a set is enough for that part:

  1. import java.util.HashMap;
  2. import java.util.Map;
  3. import java.util.SortedSet;
  4. import java.util.TreeSet;
  5. public class Test {
  6. static class Item implements Comparable&lt;Item&gt; {
  7. final String name;
  8. int amount;
  9. Item(String name,int amount){
  10. this.name=name;
  11. this.amount=amount;
  12. }
  13. public int compareTo(Item o) {
  14. if(o.amount&lt;amount)
  15. return -1;
  16. if(o.amount&gt;amount)
  17. return 1;
  18. return o.name.compareTo(name);
  19. }
  20. public String toString() {
  21. return name+&quot;|&quot;+amount;
  22. }
  23. }
  24. Map&lt;String,Item&gt; itemmap=new HashMap&lt;&gt;();
  25. SortedSet&lt;Item&gt; sorted=new TreeSet&lt;&gt;();
  26. void add(String name,int amount) {
  27. Item i=itemmap.get(name);
  28. if(i!=null) {
  29. sorted.remove(i);
  30. i.amount+=amount;
  31. } else {
  32. i=new Item(name,amount);
  33. }
  34. itemmap.put(name,i);
  35. sorted.add(i);
  36. }
  37. public static void main(String[] args) {
  38. Test t=new Test();
  39. t.add(&quot;F&quot;,400);
  40. t.add(&quot;B&quot;,1000);
  41. t.add(&quot;xA&quot;,500);
  42. t.add(&quot;xA&quot;,600);
  43. t.add(&quot;C&quot;,1000);
  44. t.add(&quot;D&quot;,700);
  45. t.add(&quot;E&quot;,300);
  46. System.out.println(&quot;itemmap: &quot;+t.itemmap);
  47. System.out.println(&quot;sorted: &quot;+t.sorted);
  48. }
  49. }

It produces the output (test on Ideone: https://ideone.com/2d79aC)

> itemmap: {B=B|1000, C=C|1000, D=D|700, E=E|300, F=F|400, xA=xA|1100}
> sorted: [xA|1100, C|1000, B|1000, D|700, F|400, E|300]

I deliberately renamed A to xA, otherwise the map would be A|1100, B|1000, C|1000, but that's just a coincidence of alphabetical order (hashing a few consecutive, single-letter strings does not really mix the order). C and B come in this reverse order because that's what you have asked for. If you want them as B, then C, swap the compareTo(), or just return the current one with a negative sign.

huangapple
  • 本文由 发表于 2020年10月3日 05:24:08
  • 转载请务必保留本文链接：https://go.coder-hub.com/64178414.html
  • java
  • sorting
  • treemap
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定