Как уменьшить временную сложность этого кода O (n ^ 3) - PullRequest
Новая
       24

Как уменьшить временную сложность этого кода O (n ^ 3)

0 голосов
/ 10 июля 2019

Вот кусок кода, который беспокоит меня.Это делает задачу, но я хочу оптимизировать ее, если это возможно.

  1. У меня есть список Entities
  2. Config для каждого Entity на основе ID.
  3. С Config имеет Tips для каждого Entity
  4. С Config имеет Rejects для каждого Entity
  5. Rejects имеет IDдля каждого Tip

  6. я получаю ID из Tip равным reject, удалите его из allItems и добавьте его к removeItems

    Map<String, String> removeItems = new HashMap<>();
Map<String, Pair<String, Config>> allItems = new HashMap<>();
for(final Entity entity : entities) {
    final Config config = Configs
            .get(entity.getId());
    if (config == null || entity.getTxId() == null) {
        continue;
    }
    if (config.getTips() != null) {
        for (final Tip tip : config.getTips()) {
            String currentId = entity.getId();
            String currentTipId = tip.getTipId();
            if(allItems.containsKey(currentTipId)) {
                Pair<String, Config> item = allItems.get(currentTipId);
                if(tip.getPriority() > item.getValue().getPriority()) {
                    removeItems.put(currentTipId, item.getKey());
                    allItems.put(currentTipId, new Pair(currentId, tip));
                } else {
                    removeItems.put(currentTipId, currentId);
                }
            } else {
                allItems.put(currentTipId, new Pair(currentId, tip));
            }
            List<String> rejects = tip.getRejects();
            if(CollectionUtils.isEmpty(rejects)) {
                continue;
            }
            for (String reject : rejects) {
                Pair<String, Config> pair = allItems.get(reject);
                if (null != pair) {
                    String rejectId = pair.getKey();
                    if (StringUtils.isNotEmpty(rejectId)) {
                        removeItems.put(reject, rejectId);
                    }
                }
            }
        }
    }
}
...