How to Order one list by the index values stored in another list

Question

I have a BigDecimal List such as:

[50.0,26.2,29.3]

Then, I have another List of Integers:

[2,1,0]

These integers refer to the index by which I want to reorder the first list. So, I would like to reorder the first list to be:

[29.3,26.2,50.0]

I'm using Java 8.

Answer 1

Original Solution

Let the first list of BigDecimal be called decList and the second list of Integer be called intList.

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

This takes each value of the second list and uses it as the index for accessing the value of the first list. These are then collected into a new List<BigDecimal>.

(Edit) Examining Efficiency with LinkedLists

This is food for thought and the solution above will normally suffice.

TLDR

The only place LinkedLists will hurt my original solution is when the "values list" (the List with BigDecimals in this case) is a LinkedList.

Reasoning for this Testing

Since get on ArrayLists is O(1), but get on LinkedLists is O(N), there may be alternate, faster solutions.

I wanted to examine if using a solution with Iterator would be faster for LinkedLists. I read through all kinds of Javadocs and couldn't find if running linkedList.stream().map(..) would use .iterator for LinkedLists instead of calling get. Therefore I decided to time an actual test.

Test Cases

1. Test the original solution above with streaming and mapping, using ArrayLists.
2. Test the original solution above with streaming and mapping, using LinkedLists.
3. Test a solution using an explicit .iterator and LinkedLists.
4. Test the original solution above with streaming and mapping, using an ArrayList for the indexes and a LinkedList for the values.
5. Test the original solution above with streaming and mapping, using an LinkedList for the indexes and a LinkedList for the values.

Test Results

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

Conclusions

• My original solution is much faster for ArrayLists than LinkedLists, due to O(N) vs O(N^2).
• It would seem streams already use iterators, or similar enhancements to account for the get efficiency difference. This is apparent through the similarity between test cases 2 and 3.
• LinkedLists only affect the efficiency when they contain the value in this algorithm, due to the iterator optimization with streams. Notice how test case #5 is just as fast as only using ArrayLists, despite how it uses a LinkedList for the indexes.

Source for Efficiency Testing

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");
  }
}