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, Jun 19 '17 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, Jun 19 '17 at 22:04
@Makoto He's not copying the `Integer` objects, just the lists containing them. — shmosel, Jun 19 '17 at 22:05
for example in c, if the structure is an array, we could use `memcpy` which can be faster than running a loop. I was wondering if there is any compatible method in java. — ramgorur, Jun 19 '17 at 22:05
@shmosel: Yes, I'm acutely aware of this. However, I'm not sure what purpose that's going to serve since a deep copy usually means one is mutating something, and understanding *why* that mutation needs to happen would be beneficial too. By virtue of the OP copying the lists, the contents are also copied, but I don't want to lull them into a false sense of security saying that this will *always* work for *any* object. So, I need to know what they're doing with this. — Makoto, Jun 19 '17 at 22:06
So if I understand it correctly, you're looking for a similar function to `memcpy` in Java? Why, exactly? — Makoto, Jun 19 '17 at 22:07
@Makoto Any mutation to the inner lists (e.g. sorting, filtering) would make the approach valid. — shmosel, Jun 19 '17 at 22:08
@shmosel: A little bit of investigating didn't hurt. Looks like they want to replicate `memcpy`, and it's unclear what purpose that would even serve in Java. — Makoto, Jun 19 '17 at 22:09
@Makoto In my case, I need to have a multiple numbers of `List>`s with exactly same values but every structure will have different hashcode. So that I can differentiate among them. I will call the `clone()` procedure above many times in different places. — ramgorur, Jun 19 '17 at 22:10
@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, Jun 19 '17 at 22:15
Using the copy constructor should indeed give you performance closer to `memcpy`. See my updated answer. — shmosel, Jun 19 '17 at 22:56

shmosel · Accepted Answer · 2017-06-19T23:01:35.530

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.

score -2 · Answer 2 · answered Jun 19 '17 at 22:36

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.

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

2 Answers2

Linked