跟踪列表老化

我的程序定期收到一个项目列表，让我们让他们成为水果。因此，第一个列表可能是这样的：跟踪列表老化

[apple, pear, banana]

一两个名单：

[pear, banana, plum, mandarin] 
[banana, plum, apple]

我要的是一个数据结构，具有在最近列表中的所有项目和多少个连续的次每个项目都出现了。这里的最终状态应该是：

[banana:3, plum:2, apple:1]

因为香蕉已经存在，在过去三个列表，梅刚过去两个苹果是一个新的条目（尽管我们看到它在不久前的事实，我们忘了因为它上次没有）。

最显而易见的方法（和我们的软件做它的方式）是：

foreach(Fruit f in oldList){ 
    f.old = true; 
} 

foreach(Fruit newF in newList){ 
    foreach(Fruit oldF in oldList){ 
     if(newF == oldF){ 
      oldF.old = false; 
      oldF.count++; 
     } 
    } 
} 

// iterate through oldList to remove all old entries 
oldList.Remove((x) => x.old);

但是，这是一个很大的循环，并正在成为一个瓶颈的程序处理更多的数据。这可以更有效地完成吗？

来源

2015-04-15 Daniel

给定的溶液是O（n 2 ）。如果你排序这两个列表在一起，那么合并和删除水果，它是O（n log n）。

来源

2015-04-15 23:31:58 Beta

最明显的方式在这里得到的性能提升是检查要增加计数之前做去除不再需要的水果 - 这将意味着内部循环的反复次数比较少。

然而，更好的解决方案是按照已知的顺序对水果进行排序（或者如果可能的话 - 最初存储）这样做会完全消除内部循环的需要。

来源

2015-04-15 23:34:42 jProg2015

你可以做到这一点在O（n）的（理论上最佳的渐进复杂，你可以得到这个问题），如果你使用HashMap。如果你不担心创建新对象，最简洁的解决方案就是做到这一点。下面的代码是用Java编写的，但我认为它很容易理解。

public final class ConsistentFruitCountMaintainer { 
     private Map<String, Integer> fruitToCount = new HashMap<>(); 

     public void processList(final List<Fruit> fruits) { 
      final Map<String, Integer> nextMap = new HashMap<>(); 
      for(final Fruit fruit : fruits) { 
       if (fruitToCount.containsKey(fruit)) { 
        nextMap.put(fruit, fruitToCount.get(fruit) + 1); 
       } else { 
        nextMap.put(fruit, 1); 
       } 
      } 
      fruitToCount = nextMap; 
     } 

     public Map<Fruit, Integer> getCurrentCounts() { 
      return new HashMap<>(fruitToCount); 
     } 
    }

来源

2015-04-30 00:34:46

跟踪列表老化

回答

相关问题