Forked from netdance/TestSortedListStreams.java
Last active
September 8, 2015 07:36
-
-
Save Divyendra/aee1fd1af7f16c8ca9cd to your computer and use it in GitHub Desktop.
Various Java methods to create one sorted list from two sorted lists
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package testsortedliststreams; | |
import java.util.*; | |
import java.util.stream.*; | |
/* | |
Sample output on late-2013 MacBook Pro: | |
Starting Naive List Sort, via Collections | |
Total number of sorted values: 40000000 | |
Total execution time: 2514 | |
Starting Naive List Sort, via Streams | |
Total number of sorted values: 40000000 | |
Total execution time: 2286 | |
Starting Naive List Sort, via Streams without conversion | |
Total number of sorted values: 40000000 | |
Total execution time: 1965 | |
Starting Sorted List Sort | |
Total number of sorted values: 40000000 | |
Total execution time: 1752 | |
*/ | |
public class TestSortedListStreams { | |
public static void main(String[] args) throws Exception { | |
// Create two sorted lists | |
List<Double> random1 = Collections.unmodifiableList(Stream.generate(Math::random).limit(20000000) | |
.sorted().collect(Collectors.toList())); | |
List<Double> random2 = Collections.unmodifiableList(Stream.generate(Math::random).limit(20000000) | |
.sorted().collect(Collectors.toList())); | |
rest(); | |
naiveListSort(random1, random2); | |
rest(); | |
sortStreams(random1, random2); | |
rest(); | |
sortStreamsNoConvert(random1, random2); | |
rest(); | |
fasterListSort(random1, random2); | |
} | |
private static void naiveListSort(List<Double> first, List<Double> second) { | |
System.out.println("Starting Naive List Sort, via Collections"); | |
long starttime = System.currentTimeMillis(); | |
List<Double> combinedList = new ArrayList(first.size() + second.size()); | |
combinedList.addAll(first); | |
combinedList.addAll(second); | |
Collections.sort(combinedList); | |
System.out.println("Total number of sorted values: " + combinedList.size()); | |
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime)); | |
// uncomment to print | |
//combinedList.stream().forEach(System.out::println); | |
} | |
private static void sortStreams(List<Double> first, List<Double> second) { | |
System.out.println("Starting Naive List Sort, via Streams"); | |
long starttime = System.currentTimeMillis(); | |
Stream<Double> random1 = first.stream(); | |
Stream<Double> random2 = second.stream(); | |
Stream<Double> combined = Stream.concat(random1, random2).sorted(); | |
List<Double> combinedList = combined.collect(Collectors.toList()); | |
System.out.println("Total number of sorted values: " + combinedList.size()); | |
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime)); | |
// uncomment to print | |
//combinedList.stream().forEach(System.out::println); | |
} | |
private static void sortStreamsNoConvert(List<Double> first, List<Double> second) { | |
System.out.println("Starting Naive List Sort, via Streams without conversion"); | |
long starttime = System.currentTimeMillis(); | |
Stream<Double> random1 = first.stream(); | |
Stream<Double> random2 = second.stream(); | |
Stream<Double> combined = Stream.concat(random1, random2).sorted(); | |
System.out.println("Total number of sorted values: " + combined.count()); | |
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime)); | |
// uncomment to print | |
//Stream.concat(first.stream(),second.stream()).sorted().forEach(System.out::println); | |
} | |
// take advantage of the fact that both lists are sorted | |
private static void fasterListSort(List<Double> first, List<Double> second) { | |
System.out.println("Starting Sorted List Sort"); | |
long starttime = System.currentTimeMillis(); | |
List<Double> combinedList = new ArrayList(first.size() + second.size()); | |
int i = 0; // first index | |
int j = 0; // second index | |
int firstsize = first.size(); | |
int secondsize = second.size(); | |
//Validation to avoid ArrayOutofBoundException when secondlist is empty and first ain't | |
if (firstsize==0) return second; | |
if (secondsize==0) return first; | |
while (i < firstsize) { | |
while (first.get(i) >= second.get(j)) { | |
combinedList.add(second.get(j++)); | |
if (j >= secondsize) { | |
break; | |
} | |
} | |
combinedList.add(first.get(i)); | |
if (j >= second.size()) { | |
break; | |
} | |
i++; | |
} | |
if (j < second.size()) { // add remaining | |
combinedList.addAll(second.subList(j, secondsize)); | |
} else if (i < first.size()) { | |
combinedList.addAll(first.subList(i+1, firstsize)); | |
} | |
System.out.println("Total number of sorted values: " + combinedList.size()); | |
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime)); | |
// uncomment to print | |
//combinedList.stream().forEach(System.out::println); | |
} | |
private static void rest() throws Exception { | |
System.gc(); | |
Thread.sleep(5000); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment