使用列表的HashMap的Java算法优化问题

djmepvbi  于 2023-01-11  发布在  Java
关注(0)|答案(2)|浏览(121)

如果我有以下内容

postcodeToCompaniesList = new HashMap<String, List<Company>>();

经过一些处理后,散列表中有数千个邮政编码,每个邮政编码Map到一个包含1个或多个Company对象的列表中。
现在我想得到前10个最受欢迎的邮政编码,并打印出在邮政编码即"Postcode SW1A 0AA has 50 companies"的公司数量。
我所采用的方法(我认为这是幼稚的)是创建一个Record对象来保存邮政编码和该邮政编码对应的公司数量,然后创建一个RecordList对象来管理count值最高的10个Record对象(见下文)。
RecordList.addRecord(Record record)方法添加records直到添加了10个元素,然后只有当count的值大于列表中当前的最小值时才有条件地添加更多的元素,然后对列表进行排序并删除最小值,从而保持10个元素的计数。

final class Record implements Comparable<Record> {
    public String postcode;
    public int count;

    public Record(String postcode, int count){
        this.postcode = postcode;
        this.count = count;
    }

    @Override 
    public int compareTo(Record r){
        return Integer.valueOf(this.count).compareTo(Integer.valueOf(r.count));
    }
}

final class RecordList{
    List<Record> top10 = new ArrayList<Record>();
    
    public void addRecord(Record record){
        if (this.top10.size() < 10){
            this.top10.add(record);
            Collections.sort(this.top10);
        } else if (record.count > this.top10.get(0).count){
            this.top10.add(record);
            Collections.sort(this.top10);
            this.top10.remove(0);
        }
    }
}

接下来,我使用一个简单的循环遍历所有键(邮政编码),并将它们与companyCount沿着一次添加一个到RecordList

RecordList recordList = new RecordList();
Set<String> postcodes = this.postcodeToCompaniesList.keySet();

for(String postcode : postcodes){
  int companyCount = this.postcodeToCompaniesList.get(postcode).size();
  recordList.addRecord(new Record(postcode, companyCount));
}

System.out.println(gson.toJson(recordList));

这很有效。但是,我觉得这是一种效率很低的方法?也许流会更好?
社区的想法是什么?有没有更好、更优雅的方法来做到这一点?

wbrvyc0a

wbrvyc0a1#

我假设List of Company是一个字符串列表,这样做会更简单:

HashMap<String, Integer> counter = new HashMap<>(); // postcodes counter
postcodeToCompaniesList.forEach((postcode, company) -> counter.put(postcode, company.size()));

counter.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .limit(10)
    .forEach(System.out::println);
zxlwwiss

zxlwwiss2#

你可以把你的条目按列表大小倒序排序,限制在n个条目(在你的例子中是10个),然后把它们收集到一个LinkedHashMap中:

private static Map<String, List<Company>> topN(Map<String, List<Company>> map, int n) {
    return map.entrySet()
              .stream()
              .sorted(Comparator.comparingInt((Map.Entry<String, List<Company>> e) -> e.getValue().size()).reversed())
              .limit(n)
              .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (x, y) -> y, LinkedHashMap::new));
}

并像下面这样使用它,例如,获得前7个邮政编码:

topN(postcodeToCompaniesList, 7)
        .forEach((k,v) -> System.out.printf("Postcode %s has %d companies.%n", k, v.size()));

相关问题