0

say I have a list like this {1,2,3,4,5,6,7,8}. Is there a fast way to create two lists(one with the first half and the other with the second half)? The location of the split is always half the size of the list(lists are always even numbers)

Currently my approach is to divide the size by 2 and then iterate the list adding anything below the value in list1 and anything above in list2. I was just wondering if there was a quicker way(I need to do over a billion of these, so even a slight improvement in performance can save me alot of time).

Lostsoul
  • 25,013
  • 48
  • 144
  • 239
  • There's no faster way (to copy an array, you must copy each element), but you can do it automatically at least: http://stackoverflow.com/questions/1100371/grabbing-a-segment-of-an-array-in-java – Ry- Apr 29 '12 at 22:39

2 Answers2

4

As far as built-in functionality, you could use List#subList(int, int):

int size = original.size();
List<Integer> first = original.subList(0, size / 2);
List<Integer> second = original.subList(size / 2, size);

Whether or not you want to use subList() depends on what you're doing with the contents. subList() returns views into the original list (instead of actually copying). Make sure you read the javadoc. Here's a snippet:

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. (If fromIndex and toIndex are equal, the returned list is empty.) The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa. The returned list supports all of the optional list operations supported by this list.

Also, I can't really speak to the performance of subList() and how it may or may not meet your requirements. I'd imagine since it's just creating views and not copying that it'd be relatively fast. But again, pretty situational, and you'd need to profile it either way to know.

Rob Hruska
  • 118,520
  • 32
  • 167
  • 192
  • Not 100% but shouldn't the second be `sublist(size / 2, size -1)`. – Ash Burlaczenko Apr 29 '12 at 22:42
  • 1
    The second argument is exclusive, so I think `size` is correct. Haven't tested this though. – Rob Hruska Apr 29 '12 at 22:43
  • You may want to mention that this method does not create copies of the list, so any structural changes to the underlying list invalidate the result of `sublist`. – Sergey Kalinichenko Apr 29 '12 at 22:44
  • I tested this and it works perfected. Now time to profile! Thanks so much(I didn't know sublist existed, I searched for split/partition,etc). – Lostsoul Apr 29 '12 at 22:46
  • 2
    @Lostsoul Don't worry about profiling it - that's as fast as it gets, assuming that you do not mind changes in the original collection being visible in the sublist, and structural changes invalidating the results. – Sergey Kalinichenko Apr 29 '12 at 22:48
  • @dasblinkenlight There will be no changes in the original list. I have a massive list(thousands of items) and made a list of data and items, then merged them into one list(to make the transfer over a network faster). Once it reaches the other end, I'm doing the above process to reconstruct the list. So the above two lists are going to be used to make a new list then discarded. – Lostsoul Apr 29 '12 at 22:51
  • Yeah, subList is going to be as fast as it gets if it is suitable. – esej Apr 29 '12 at 22:55
0

Ok, you have to do over a billion of theese - fun.

You should profile different methods.

My bet would be to use arrays and System.arraycopy

If your code isn't the code producing the lists, it depends on which implementation of List you are being provided.

You'd be given a better answer if you we're providing more details about the requirements. Is a copy necessary or is a view (as provided by subList() enought). Which implementation of List are you using/being provided etc. The speed is also going to be affected by jvm (version and platform).

esej
  • 3,059
  • 1
  • 18
  • 22