如何按存储在另一个列表中的索引值排序一个列表

Question

我有一个BigDecimal List如:

[50.0,26.2,29.3]

然后,我有另一种List的Integers:

[2,1,0]

这些整数指的是我想要重新排序第一个列表的索引.所以,我想重新排序第一个列表:

[29.3,26.2,50.0]

我正在使用Java 8.

Answer 1

原始方案

让第一个BigDecimal被调用列表decList和第二个Integer被调用列表intList.

intList.stream().map(decList::get).collect(Collectors.toList());

这将获取第二个列表的每个值,并将其用作访问第一个列表的值的索引.然后将这些收集到一个新的List<BigDecimal>.

(编辑)用LinkedLists 检查效率

这是值得思考的问题,上面的解决方案通常就足够了.

TLDR

唯一的地方LinkedList旨意伤了我原来的解决方案是在"值列表"(即List用BigDecimals在这种情况下)是LinkedList.

推理此测试

因为get在ArrayLists上O(1),但是get在LinkedLists上O(N),可能存在替代的,更快的解决方案.

我想检查一下使用的解决方案Iterator是否会更快LinkedList.我通读各种Javadocs并且无法找到运行linkedList.stream().map(..)是否会.iterator用于LinkedLists而不是调用get.因此我决定进行实际测试.

测试用例

1. 使用ArrayLists ,使用流和映射测试上面的原始解决方案.
2. 使用LinkedLists ,使用流和映射测试上面的原始解决方案.
3. 使用explicit .iterator和LinkedLists 测试解决方案.
4. 使用流和映射测试上面的原始解决方案,使用ArrayList索引和LinkedList值.
5. 使用流和映射测试上面的原始解决方案,使用LinkedList索引和LinkedList值.

检测结果

ArrayList Implementation:
Duration: 70 milliseconds
Duration: 15 milliseconds
Duration: 16 milliseconds
Duration: 15 milliseconds
Duration: 15 milliseconds
Average duration: 26 milliseconds

LinkedList Implementation with Stream and Map:
Duration: 1359 milliseconds
Duration: 1387 milliseconds
Duration: 1309 milliseconds
Duration: 1302 milliseconds
Duration: 1304 milliseconds
Average duration: 1332 milliseconds

LinkedList Implementation with Iterator:
Duration: 2806 milliseconds
Duration: 2173 milliseconds
Duration: 1305 milliseconds
Duration: 1305 milliseconds
Duration: 1305 milliseconds
Average duration: 1778 milliseconds

Mix test case #4:
Duration: 1281 milliseconds
Duration: 1278 milliseconds
Duration: 1278 milliseconds
Duration: 1278 milliseconds
Duration: 1278 milliseconds
Average duration: 1278 milliseconds

Mix test case #5:
Duration: 13 milliseconds
Duration: 7 milliseconds
Duration: 7 milliseconds
Duration: 7 milliseconds
Duration: 7 milliseconds
Average duration: 8 milliseconds

结论

• 由于vs ,我的原始解决方案ArrayList比LinkedLists 快得多.O(N)O(N^2)
• 似乎stream已经使用iterators或类似的增强来解释get效率差异.通过测试用例2和3之间的相似性可以明显看出这一点.
• LinkedList由于使用流进行迭代器优化,因此只会影响此算法中包含值的效率.注意测试用例#5与仅使用ArrayLists 一样快,尽管它如何使用LinkedList索引.

效率测试的来源

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.math.BigDecimal;
import java.util.stream.Collectors;
import java.lang.Math;
import java.util.Iterator;

class Test {
  public static void main(String[] args) {
    testArrayListImplementation();
    testLinkedListImplementation();
    testCaseFourMixed();
    testCaseFiveMixed();
  }

  static void testArrayListImplementation() {
    List<BigDecimal> bigDecList = new ArrayList<BigDecimal>();
    List<Integer> ndxList = new ArrayList<Integer>();

    System.out.println("ArrayList Implementation:");
    timeListImplementation(bigDecList, ndxList, false);
  }

  static void testLinkedListImplementation() {
    List<BigDecimal> bigDecList = new LinkedList<BigDecimal>();
    List<Integer> ndxList = new LinkedList<Integer>();

    System.out.println("LinkedList Implementation with Stream and Map:");
    timeListImplementation(bigDecList, ndxList, false);

    System.out.println("LinkedList Implementation with Iterator:");
    timeListImplementation(bigDecList, ndxList, true);
  }

  static void testCaseFourMixed() {
    //Test case 4
    List<BigDecimal> bigDecList = new LinkedList<BigDecimal>();
    List<Integer> ndxList = new ArrayList<Integer>();

    System.out.println("Mix test case #4:");
    timeListImplementation(bigDecList, ndxList, false);
  }

  static void testCaseFiveMixed() {
    //Test case 5
    List<BigDecimal> bigDecList = new ArrayList<BigDecimal>();
    List<Integer> ndxList = new LinkedList<Integer>();

    System.out.println("Mix test case #5:");
    timeListImplementation(bigDecList, ndxList, false);
  }

  static void timeListImplementation(List<BigDecimal> bigDecList, List<Integer> ndxList, boolean useIterator) {
    for (int i = 0; i < 10000; i++) {
      bigDecList.add(new BigDecimal(123.4));
      ndxList.add((int) (Math.random() * 1000));
    }

    long totalDuration = 0;

    for (int linkedTrial = 0; linkedTrial < 5; linkedTrial++) {
      long startTime = System.nanoTime();

      for (int numComputations = 0; numComputations < 100; numComputations++) {
        if (useIterator) {
          Iterator<Integer> ndxIter = ndxList.iterator();
          List<BigDecimal> specializedList = new LinkedList<BigDecimal>();
          while (ndxIter.hasNext()) {
            specializedList.add(bigDecList.get(ndxIter.next()));
          }
        } else {
          List<BigDecimal> specializedList = ndxList.stream().map(bigDecList::get).collect(Collectors.toList());
        }
      }

      long endTime = System.nanoTime();
      long duration = (endTime - startTime) / 1000000; //milliseconds

      System.out.println("Duration: " + duration + " milliseconds");
      totalDuration += duration;
    }
    System.out.println("Average duration: " + (totalDuration / 5) + " milliseconds");
  }
}