2

In C/C++ we have realloc which will efficiently allocate additional space for an existing collection. I guess it is sub linear (or even constant) in complexity.

Is there a way to achieve the same in Java? Here are the items that I looked at,

  1. Array resize is not possible,
  2. Copying an array to another of bigger size is linear in complexity. Looked at both System.arrayCopy as well as Arrays.copyOf
  3. ArrayList must be same as point 2 above.

Note : My requirement is to expand possibly an extremely large array to even further.

Community
  • 1
  • 1
anoopelias
  • 9,240
  • 7
  • 26
  • 39
  • I think no, but you can get closer to it by using some factors like amortized time and using system methods. In this case System.arrayCopy is much faster. – Aditya Peshave Mar 22 '14 at 04:31
  • 2
    Don't even worry about it in Java, frankly. – Louis Wasserman Mar 22 '14 at 04:37
  • 2
    Must it really be one large array? Unless you are interfacing it with something else (jni) I'd probably use a different structure--a linked list of arrays or something? You can still wrap it in a class that lets it interact with it however you like--that is all assuming you are talking an array more than, say, 1/3 the ram of your PC, if it's not that big I'd just do what Louis said, don't worry about it and let java handle it for you, Java will do very smart things in general. – Bill K Mar 22 '14 at 04:40
  • @BillK, & louis, I get the general picture. Thank you for the inputs. – anoopelias Mar 22 '14 at 04:56

1 Answers1

5

realloc is likely to be O(n) in practice, since it sometimes/often involves memory copying. In that sense, it's equivalent in theoretical complexity to allocating a new array in Java.

Now Java always zeros the newly allocated memory which may take it a bit longer, but OTOH the GC has insanely fast memory allocations so it may even be faster than realloc in some cases. I'd expect a strategy that involves allocating new arrays in Java to be overall roughly comparable in speed to realloc. Possibly Java is better for smaller arrays, C/C++ would have the edge for big arrays, but YMMV. You'd have to benchmark in your particular implementation and workload to be sure.

So overall:

  • Don't worry about it, just reallocate new arrays in Java
  • If you do this a lot, be sure to recreate arrays with more space than you need so that you don't need to reallocate with each single element added (this is what the Java ArrayList does internally.

Final but important point: unless you are writing very low level code, you probably shouldn't be worrying about this anyway. Just use one of the fine collection classes that already exist (Java Collections, Google Collections, Trove etc.) and let them handle all of this stuff for you.

mikera
  • 105,238
  • 25
  • 256
  • 415
  • Based on all your inputs, I get the idea. Will try with `Arrays.copyTo` and see how it goes. Thank you. – anoopelias Mar 22 '14 at 04:58
  • +1 for [trove](http://trove.starlight-systems.com/overview) and [google collection](https://code.google.com/p/guava-libraries/wiki/GuavaExplained) – 0x90 Mar 22 '14 at 09:52