0

我有一个有效的问题陈述，但我仍然想知道更有效、更快、更重要的是正确设计来处理下面提到的场景。

我有一个 POJO 类

class A {
  String s;
  Double d;
}

我正在尝试填充一个列表，基本上是一个对象 A 的列表到列表中。现在有问题的实施。在将对象 A 添加到列表中时，我需要检查是否已经存在带有 String 的对象。如果是，我想用旧的 d1 + 新的 d1 更新旧的对象，并且不将新对象添加到列表中，如果没有，则将新对象添加到列表中。我目前的实现如下所示。

double dd = 0.0;
    List<A> aList = new List<A>();
    List<A> aListToRemove = new List<A>();
    A newA = null;
    for(int i=0;i<=100;i++ ){
        newA = method call which returns newA;
        for(A oldA: aList ){
            if(oldA.getS().equals(newA.getS())){
                dd = oldA.getD() + newA.getD();
                newA.setD(dd);
                aListToRemove.add(oldA);
            }
            aList.add(newA);
            aList.removeAll(aListToRemove);
        }
    }

//at the end, i would like to see aList with no duplicates, but with updated d value.

有没有更有效的方法在第二个 for 循环中进行处理？

4

6 回答 6

2

看来您可以为您的用例使用地图：

Map<String, A> map = new HashMap<> ();

并像这样在地图中放置项目：

map.put(someA.s, someA);

那应该将您的 O(n^2) 算法变成 O(n) 算法。

当您收到 时newA，您可以使用以下内容：

A a = map.get(newA.getS());
if (a == null) {
    map.put(newA.getS(), newA); //new string => new item in the map
} else {
    a.setD(a.getD() + newA.getD()); //found string => updating the existing item
}
于 2013-01-03T11:16:28.640 回答
1

你真的应该考虑使用Map.

于 2013-01-03T11:16:04.677 回答
1

它必须是一个List吗？听起来Map可以为您完成这项工作。具体来说，该put()操作添加或替换了一个完全符合您的语义的键值对。

干杯，

于 2013-01-03T11:16:30.800 回答
1

如果你想要效率，我会使用MultiMap或者Map<String, List<String>>这将更有效地执行查找和数据的累积。如果您需要将字符串附加在一起，最好的选择可能是使用Map<String, double[]>

class A {
  String s;
  double d; // don't use Double unless you need null values.
}

Map<String, double[]> map = new LinkedHashMap<>();

for(A newA: getAs()) {
    double[] total = map.get(newA.getS());
    if (total== null)
        map.put(newA.getS(), total = new double[0]);
    total[0] += newA.getD();
}

这将为您提供 O(1) 查找并以最少的对象创建累积值。

于 2013-01-03T11:16:46.240 回答
1

考虑使用Map。您可以使用 get 方法检查项目是否在地图中（似乎 s 将是关键）：

A a = myMap.get(newA.getS());
if (a != null){
 a.setD(a.getD() + newA.getD());
} else {
 myMap.put(newA);
}
于 2013-01-03T11:19:40.653 回答
0

您应该将 ajava.util.Set用于您的操作。

您可以在 O(1) 时间内检查您的对象是否存在并相应地执行您的操作。

它还将负责删除重复项。

   double dd = 0.0;
    Set<A> aList = new HashSet<A>();
    A newA = null;
    for(int i=0;i<=100;i++ ){
        newA = //method call which returns newA;
        A oldA = aList.get(newA);
        if(oldA != null){
           aList.remove(oldA);
        }
        dd = oldA.getD() + newA.getD();
        newA.setD(dd);
        aList.add(newA);
    }

请确保您覆盖类 A 中的equals和hashcode()方法，Set否则将使用默认实现

于 2013-01-03T11:18:24.463 回答