java: best way to do deep copy of list of lists

Question

I am trying to write a procedure do the deep copy of List<List<Integer>>, and I am doing like this:

public static List<List<Integer>> clone(final List<List<Integer>> src) { List<List<Integer>> dest = new ArrayList<List<Integer>>(); for( List<Integer> sublist : src) { List<Integer> temp = new ArrayList<Integer>(); for(Integer val: sublist) { temp.add(val); } dest.add(temp); } return dest ; }

Is this a good way to do? Is it possible to get rid of the inner loop? The fact is that each of the inner sub-lists can grow to large lengths.

If you want to do a deep copy, then there's nothing you can do about the size of the sub-lists - something will need to iterate over them at some point (unless you can build a copy-on-write mechanism). — Oliver Charlesworth
– Oliver Charlesworth, Commented Jun 19, 2017 at 22:02
Integer is immutable; anything you do to an Integer is lost unless you re-add it back into the list in its exact place. Why do you think you want a deep copy? — Makoto
– Makoto, Commented Jun 19, 2017 at 22:04
@Makoto - I believe the OP is referring to memcpy only because in C it's generally faster than manually iterating and copying, not because memcpy has any semantic value. He/she is essentially asking "am I doing a deep copy as efficiently as possible?". — Oliver Charlesworth
– Oliver Charlesworth, Commented Jun 19, 2017 at 22:15
Using the copy constructor should indeed give you performance closer to memcpy. See my updated answer. — shmosel
– shmosel, Commented Jun 19, 2017 at 22:56

shmosel · Accepted Answer · 2017-06-19 23:01:35Z

Is this a good way to do?

It's fine.

Is it possible to get rid of the inner loop?

Yes, you can use the ArrayList copy constructor:

for( List<Integer> sublist : src) { dest.add(new ArrayList<>(sublist)); }

The fact is that each of the inner sub-lists can grow to large lengths.

The above will shorten the code, and it delegates to System.arraycopy, which will likely improve performance somewhat. It also avoids the repeated resize/copy when you fill an empty ArrayList. But there's fundamentally no way to avoid the O(n) time complexity of copying a list/array, if you truly need a deep copy. Since you don't explain why you need a deep copy, I'll have to take you at your word.

DerDingens · Accepted Answer · 2017-06-19 22:36:08Z

You might be able to speed things up with some parallel approach, like using a Thread pool to split the work at first and merge the results together after everything is done.

I can't provide an example since I'm on my phone, but may try to look that way.

Collectives™ on Stack Overflow

java: best way to do deep copy of list of lists

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related