• Post Reply Bookmark Topic Watch Topic
  • New Topic

Can someone give me a direction where to start from , about space/memory complexity  RSS feed

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi.
i learn about complexity.
time complexity i undersdtood well and found a lot of material about it .
but about space/memory complexity i didnt find some material . and i searched a lot. i know its a big subject on its own. so maybe someone in here can give me a good link , or direction ?
thanks.
i'm talking about bigO only ..
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dan D'amico wrote:but about space/memory complexity i didnt find some material . and i searched a lot. i know its a big subject on its own. so maybe someone in here can give me a good link , or direction ?
i'm talking about bigO only ..

Well, I've only ever seen "big O" notation used for time, but I suppose it could be used for space too...

The fact is that space complexity is generally less important in Java than in some other languages because you don't have much control over it (beyond the obvious practise of not creating unnecessary objects). If you're using a published algorithm (eg, a particular type of sort), it will usually tell you what the space "complexity" will be and, TBH, quadratic space algorithms are relatively rare in normal apps programming.

One specific thing you can do that may help though: Favour immutability.

The reason? Immutable objects can share internals.

The classic example is Strings. If I create a substring() of an existing String, it will probably not take up as much space as you think, because the substring will use the same characters as the original.

And, if you end up creating lots of them, the space savings can be huge. The only problem is that they can be quite difficult to quantify since, for obvious reasons, designers tend to hide these "implementation details" from you.

HIH

Winston
 
Campbell Ritchie
Marshal
Posts: 56553
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote: . . .
The classic example is Strings. If I create a substring() of an existing String, it will probably not take up as much space as you think, because the substring will use the same characters as the original.
. . .
Rob (S) says that used to be the case, but it can be counter‑productive, so they have changed the implementation of substring() so as not to use the same internal array any more.

Winston is right that few people worry about space complexity. When I started programming you could spend about the same on a megabyte of memory as on a large house and the two probably occupied about the same space (some figures here). Now a megabyte costs about the same as a little sweetie the children buy on the way home from school, and occupies so little space you need a magnifying glass to see it. So space use is a minor problem. That applies even more so to Java® and similar languages with automatically managed heaps.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Rob (S) says that used to be the case, but it can be counter‑productive, so they have changed the implementation of substring() so as not to use the same internal array any more.

Really? News to me. Be interested to know why.

I can sort of see that it would remove the need for an "offset" and "length"; but if you know of a link that explains the reasons in more detail, I'd be most grateful.

Winston
 
Paweł Baczyński
Bartender
Posts: 2083
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Memory leaks. Consider a large String of 1000000 characters. You want a short substring from index 23442 to 23472.
Before, you would need to keep this huge array of chars and it would never be garbage-collected.

Now, consider 1000 of those huge Strings...

No need to use new String(String) anymore .

link
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paweł Baczyński wrote:Memory leaks...

Yah. Kind of worked it out; and also found this link - apparently by the author of the substring change. It seems that there was also a need for an "alternative hash", and the removal of "offset" and "count" balanced out the increase in size.

Not sure I agree with it, but I kind of understand it now; and it just goes to prove how powerful immutability is.

Winston
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!