0

It's my first working on a quite big project, and I've been asked to obtain the best performances.

So I've thouhgt to replace my for loops with a ListIterator, because I've got around 180 loops which call list.get(i) on lists with about 5000 elements.

So I've got two questions.

1) Are those 2 snippets equal? I mean, do them produce the same output? If no, how can I correct the ListIterator thing?

ListIterator<Corsa> ridesIterator = rides.listIterator();
    while (ridesIterator.hasNext()) {
        ridesIterator.next();
        Corsa previous = ridesIterator.previous(); //rides.get(i-1)
        Corsa current = ridesIterator.next(); //rides.get(i)
        if (current.getOP() < d.getFFP() && previous.getOA() > d.getIP() && current.wait(previous) > DP) {
            doSomething();
            break;
        }
    }

__

for (int i = 1; i < rides.size(); i++) {
    if (rides.get(i).getOP() < d.getFP() && rides.get(i - 1).getOA() > d.getIP() && rides.get(i).getOP() - rides.get(i - 1).getOA() > DP) {
        doSomething();
            break;
        }
    }

2) How will it be the first snippet if I've got something like this? (changed i and its exit condition)

for (int i = 0; i < rides.size() - 1; i++) {
    if (rides.get(i).getOP() < d.getFP() && rides.get(i + 1).getOA() > d.getIP() && rides.get(i).getOP() - rides.get(i + 1).getOA() > DP) {
        doSomething();
            break;
        }
    }

I'm asking because it's the first time that I'm using a ListIterator and I can't try it now!

EDIT: I'm not using an ArrayList, it's a custom List based on a LinkedList

EDIT 2 : I'm adding some more infos. I can't use a caching system because my data is changing on evry iteration and managing the cache would be hard as I'd have to deal with inconsistent data. I can't even merge some of this loops into one big loop, as I've got them on different methods because they need to do a lot of different things.

So, sticking on this particular case, what do you think is the best pratice? Is ListIterator the best way to deal with my case? And how can I use the ListIterator if my for loop works between 0 and size-1 ?

4

3 回答 3

1

如果您知道最大大小，如果您从集合中退出（例如ArrayList用简单数组替换它们），您将获得最佳性能。

因此，请改为ArrayList<Corsa>使用 5000 个元素创建Corsa[] rides = new Corsa[5000]. 例如，不要硬编码，而是5000使用它来避免代码中的幻数。然后用 normal for 迭代，参考.final static int MAX_RIDES = 5000rides[i]

一般来说，如果你追求性能，你应该用 Java 编写代码，就像它是 C/C++ 一样（当然你可以）。代码不是那么面向对象和漂亮，但它很快。记得最后总是做优化，当你确定的时候，你发现了一个瓶颈。否则，你的努力是徒劳的，只会降低代码的可读性和可维护性。还要使用分析器，以确保您的更改实际上是升级，而不是降级。

使用的另一个缺点ListIterator是它在内部分配内存。因此 GC（垃圾收集器）会更频繁地唤醒，这也会对整体性能产生影响。

于 2012-12-01T20:39:54.470 回答
1

  1. 不，他们不这样做。

    while (ridesIterator.hasNext()) {
  ridesIterator.next();
  Corsa previous = ridesIterator.previous(); //rides.get(i-1)
  Corsa current = ridesIterator.next(); //rides.get(i)

    变量previous 和current 将包含相同的“Corsa”值，有关详细信息，请参阅ListIterator 文档（迭代器位于“中间”位置）。

    正确的代码如下所示：

    while (ridesIterator.hasNext()) {
  Corsa previous = ridesIterator.next(); //rides.get(i-1)
  if(!ridesIterator.hasNext())
    break; // We are already at the last element
  Corsa current = ridesIterator.next(); //rides.get(i)
  ridesIterator.previous(); // going back 1, to start correctly next time

  2. 代码实际上看起来完全一样，只是解释（如注释中所示）会有所不同：

    while (ridesIterator.hasNext()) {
  Corsa previous = ridesIterator.next(); //rides.get(i)
  if(!ridesIterator.hasNext())
    break; // We are already at the last element
  Corsa current = ridesIterator.next(); //rides.get(i+1)
  ridesIterator.previous(); // going back 1, to start correctly next time

从（过早的？）优化的角度来看，ListIterator 实现更好。

  • LinkedList 是一个双向链表，这意味着每个元素都链接到它的前任（前一个）和它的后继（下一个）。所以它每个循环做 3 次推荐。=> 3*N
  • 每个 get(i) 需要遍历所有先前的元素才能到达第 i 个索引位置。所以平均每个循环有 N/4 个推荐。（你会认为 N/2，但 LinkedList 从列表的开头或结尾开始。） => 2 * N * N/4 == N^2 /2
于 2013-09-19T16:15:29.257 回答
0

这里有一些建议，希望一两个适用于你的情况。

  1. 尝试每个循环只执行一次 rides.get(x)。
  2. 缓存方法会产生适合您代码的局部变量。

在某些情况下，编译器可以优化对同一事物的多次调用，而不是只做一次，但并非总是出于许多微妙的原因。作为程序员，如果您知道这些应该提供相同的值，那么将它们缓存在局部变量中。

例如，

int sz = rides.size ();
float dFP = d.getFP ();  // wasn't sure of the type, so just called if float..
float dIP = d.getIP ();
Corsa lastRide = rides.get ( 0 );
for ( int i = 1; i < sz; i++ ) {
    Corsa = rides.get ( i );
    float rOP = r.getOP ();
    if ( rOP < dFP ) {
        float lastRideOA = lastRide.getOA (); // only get OA if rOP < dFP
        if ( lastRideOA > dIP && rOP - lastRideOA > DP ) {
            doSomething ();
            // maybe break;
        }
    }
    lastRide = r;
}

这些优化可能并非在所有情况下都有效。例如，如果您doSomething扩展了列表，那么您需要重新计算 sz，或者可能在每次迭代时返回执行rides.size()。这些优化还假设列表是稳定的，因为元素在get..()'s. 如果doSomething对列表进行更改，那么您需要缓存的更少。希望你明白这一点。您也可以将其中一些技术应用于循环的迭代器形式。

于 2012-12-01T20:26:09.287 回答