Home > Archive > Java Help > December 2006 > StringBuffer java.lang.OutOfMemoryError
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
StringBuffer java.lang.OutOfMemoryError
|
|
| Jean Pierre Daviau 2006-12-13, 4:25 pm |
| Hi to everyones,
java.lang.OutOfMemoryError
at java.lang.StringBuffer.insert(Compiled Code)
There is about 8200 characters in the buffer including about 257
commas.
strbuf.setLength(strbuf.length()+1000);
for (int j=0;j<strbuf.length() ;j++ )
{
if(strbuf.charAt(j) == ',')
strbuf.insert(j, "\r\n");
}
--
Thanks for your attention.
Jean Pierre Daviau
--
windows Xp
asus p4 s533/333/133
Intel(R) Celeron (R) CPU 2.00 GHz
Processor Radeon7000 0x5159 agp
| |
| Eric Sosman 2006-12-13, 4:25 pm |
| Jean Pierre Daviau wrote:
> Hi to everyones,
>
> java.lang.OutOfMemoryError
> at java.lang.StringBuffer.insert(Compiled Code)
>
> There is about 8200 characters in the buffer including about 257
> commas.
>
> strbuf.setLength(strbuf.length()+1000);
> for (int j=0;j<strbuf.length() ;j++ )
> {
> if(strbuf.charAt(j) == ',')
> strbuf.insert(j, "\r\n");
> }
You don't understand what the insert() method does. The
loop you have written will attempt to insert an infinite number
of "\r\n" pairs before the first comma in the buffer; you are
safe only if the buffer contains no commas at all.
--
Eric Sosman
esosman@acm-dot-org.invalid
| |
| Jean Pierre Daviau 2006-12-13, 4:25 pm |
|
> You don't understand what the insert() method does. The
> loop you have written will attempt to insert an infinite number
> of "\r\n" pairs before the first comma in the buffer; you are
> safe only if the buffer contains no commas at all.
Is there a way to do that?
Whit append()?
| |
| Jean Pierre Daviau 2006-12-13, 4:25 pm |
| I try to be clear. I want a java mailer to send a email with broken strings.
String astring = "This, is a, string.";
will become
astring = "This
is a
string."
PrintStream msg = smtp.startMessage();
msg.print(astring );
| |
| Eric Sosman 2006-12-13, 4:25 pm |
| Jean Pierre Daviau wrote:
> I try to be clear. I want a java mailer to send a email with broken strings.
>
> String astring = "This, is a, string.";
> will become
> astring = "This
> is a
> string."
astring = astring.replaceAll(",", "\r\n");
Notes:
The first argument is a regular expression, not a "plain"
string. "," will make no trouble, but some other characters
have special meanings and would need special treatment. This
could be an advantage, though: for example, to turn commas into
line breaks and delete the surrounding white space you might
write replaceAll("\\s*,\\s*", "\r\n").
The code shown is fine for a few strings, but it compiles
the regular expression every time you execute it. If you want
to make the replacement on many strings, you may be better off
to compile the expression just once with the Pattern class and
then re-use the already-compiled regex for each string. See
the Javadoc for String's replaceAll, and follow the links for
Pattern and Matcher.
--
Eric Sosman
esosman@acm-dot-org.invalid
| |
| Hendrik Maryns 2006-12-13, 4:25 pm |
| -----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Jean Pierre Daviau schreef:
> Is there a way to do that?
> Whit append()?
Please quote some context when replying to a message.
You have to increment the loop counter with the number of characters you
added, since you insert the linebreak (have a look at
System.getProperty(line.separator)) /before/ the comma, so it finds it
again. But probably you just want replace(int,char).
strbuf.setLength(strbuf.length()+1000);
What is this good for?
for (int j=0;j<strbuf.length() ;j++ )
{
if(strbuf.charAt(j) == ','){
strbuf.insert(j++, System.getProperty(line.separator));
}
}
or
for (int j=0;j<strbuf.length() ;j++ )
{
if(strbuf.charAt(j) == ','){
strbuf.replace(j, System.getProperty(line.separator));
}
}
Untested, you might need to change some minor stuff.
And oh, use brackets for if statements, even if they only contain one
expression.
HTH, H.
- --
Hendrik Maryns
http://tcl.sfs.uni-tuebingen.de/~hendrik/
==================
http://aouw.org
Ask smart questions, get good answers:
http://www.catb.org/~esr/faqs/smart-questions.html
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
iD8DBQFFgDC3e+7xMGD3itQRAux1AJ9od0x63YVg
VIEADoF/x3btR+9+GQCfaaes
1R2Ldzd+3KcNIc+oiTc2GWc=
=6mBf
-----END PGP SIGNATURE-----
| |
| Jean Pierre Daviau 2006-12-13, 4:25 pm |
|
> strbuf.setLength(strbuf.length()+1000);
>
> What is this good for?
I thought I was adding more characters...
| |
| Oliver Wong 2006-12-13, 4:25 pm |
| "Hendrik Maryns" <hendrik_maryns@despammed.com> wrote in message
news:elpbbn$let$1@newsserv.zdv.uni-tuebingen.de...
>
> for (int j=0;j<strbuf.length() ;j++ )
> {
> if(strbuf.charAt(j) == ','){
> strbuf.insert(j++, System.getProperty(line.separator));
> }
> }
This code seems to assume that the size of a line separator is always 1
char, but this is not true for Windows, for example. Maybe something like
this: (also untested):
final String separator = System.getProperty(line.separator);
final int separatorLength = separator.length();
for (int j=0;j<strbuf.length() ;j++ )
{
if(strbuf.charAt(j) == ','){
strbuf.insert(j, separator);
j += separatorLength;
}
}
(But Eric's suggestion to use a regexp is probably better.)
- Oliver
| |
| Thomas Hawtin 2006-12-13, 7:09 pm |
| Oliver Wong wrote:
>
> for (int j=0;j<strbuf.length() ;j++ )
> {
> if(strbuf.charAt(j) == ','){
> strbuf.insert(j, separator);
> j += separatorLength;
> }
> }
Erk, it's an O(n^2) algorithm. You'd never get passed a Google interview. ;)
> (But Eric's suggestion to use a regexp is probably better.)
As ever, anything that separates what you are writing from what you are
reading is generally a good idea.
Tom Hawtin
| |
| Oliver Wong 2006-12-14, 7:10 pm |
|
"Thomas Hawtin" <usenet@tackline.plus.com> wrote in message
news:45808a4a$0$8757$ed2619ec@ptn-nntp-reader02.plus.net...
> Oliver Wong wrote:
>
> Erk, it's an O(n^2) algorithm. You'd never get passed a Google interview.
> ;)
Where n is the square root of the length of the input? It seems to be
that it will always do as many "reads" (strbuf.charAt()) as there are
characters in the input, and in the worst case, it will do as many writes
(strbuf.insert()) as there are characters (if the input consists entirely of
commas).
- Oliver
| |
| Thomas Hawtin 2006-12-14, 7:10 pm |
| Oliver Wong wrote:
> "Thomas Hawtin" <usenet@tackline.plus.com> wrote in message
> news:45808a4a$0$8757$ed2619ec@ptn-nntp-reader02.plus.net...
>
> Where n is the square root of the length of the input? It seems to be
> that it will always do as many "reads" (strbuf.charAt()) as there are
> characters in the input, and in the worst case, it will do as many writes
> (strbuf.insert()) as there are characters (if the input consists entirely of
> commas).
StringBuffer.insert is an O(n) operation. Assuming there are O(n) commas
in each of the strings, then we have O(n) * O(n) => O(n^2) algorithm.
Tom Hawtin
| |
| Jean Pierre Daviau 2006-12-14, 7:10 pm |
| The newbe is asking his self
> StringBuffer.insert is an O(n) operation.
???
| |
| Thomas Hawtin 2006-12-14, 7:10 pm |
| Jean Pierre Daviau wrote:
> The newbe is asking his self
> ???
!!!
It has to copy the n following characters the appropriate distance up
the array (backwards). It will therefore take a length of time roughly
proportional to the length of the buffer.
If you do that operation a number of times roughly proportional to the
buffer length, then you will end up with an O(n^2) algorithm.
Tom Hawtin
| |
| Tor Iver Wilhelmsen 2006-12-14, 7:10 pm |
| Thomas Hawtin <usenet@tackline.plus.com> writes:
> It has to copy the n following characters the appropriate distance up
> the array (backwards). It will therefore take a length of time roughly
> proportional to the length of the buffer.
But that uses System.arrayCopy(), which can be assumed to be highly
optimized compared to the "manual" code equivalent would be.
| |
| Jean Pierre Daviau 2006-12-14, 7:10 pm |
|
"Thomas Hawtin" <usenet@tackline.plus.com> a écrit dans le message de news:
45817d5b$0$8753$ed2619ec@ptn-nntp-reader02.plus.net...
> Jean Pierre Daviau wrote:
>
> !!!
>
> It has to copy the n following characters the appropriate distance up the
> array (backwards).
It re reads everytime from the end? It would be the same if it would be
reading from the beginning?
do you have another example?
| |
| Thomas Hawtin 2006-12-14, 7:10 pm |
| Jean Pierre Daviau wrote:
> "Thomas Hawtin" <usenet@tackline.plus.com> a écrit dans le message de news:
> 45817d5b$0$8753$ed2619ec@ptn-nntp-reader02.plus.net...
>
> It re reads everytime from the end? It would be the same if it would be
> reading from the beginning?
> do you have another example?
Are you asking why I said backward? It would probably be slightly faster
to do it forwards, but done naively it wouldn't work.
Say I had a string buffer containing 'a', 'b', 'c'. Now I insert 'x'
between 'a' and 'b'. Copying forward chars[2] = chars[1] gives 'a', 'b',
'b'; chars[3] = chars[2] gives 'a', 'b', 'b', 'b'. So we end up with the
string "axbb" instead of "axbc".
Tom Hawtin
| |
| Thomas Hawtin 2006-12-14, 7:10 pm |
| Tor Iver Wilhelmsen wrote:
> Thomas Hawtin <usenet@tackline.plus.com> writes:
>
>
> But that uses System.arrayCopy(), which can be assumed to be highly
> optimized compared to the "manual" code equivalent would be.
The absolute amount of time is not at issue. O(n) is about how it
scales, for large n.
Below is a little microbenchmark. It takes a string with a repeating
pattern of nine spaces and a comma. It inserts an extra space before
each comma, using the algorithm further up this thread. The test is done
ten time over with strings of length 10, 100, 1000, 10 000 and 100 000.
The whole thing is the repeated five times, to show up warming up
artifacts. My results are (using the Sun 1.6.0 AMD64 HotSpot, on an
Opteron 148):
402069:634 1926404:1387 19228853:4385 69899554:8360 6989864460:83605
93747:306 119041:345 601348:775 33463101:5784 7012110064:83738
95844:309 121114:348 602081:775 33337512:5773 6982603943:83561
95995:309 111818:334 613319:783 33503032:5788 6967612662:83472
94645:307 119614:345 600026:774 33411182:5780 6982415413:83560
The results are in nanoseconds, with the square root of the time after
the colon. As expected for small n, other factors hold sway over the
O(n^2). For the third, fourth and fifth values, it is pretty accurate -
each square root is about ten times the previous. Perhaps blowing the
cache has some influence in the actual results.
Now, let's rewrite it without mixing source and destination.
char[] buff = new char[str.length()*11/10];
int write = 0;
for (int j=0; j<str.length(); ++j) {
char c = str.charAt(j);
if (c == ',') {
buff[write++] = ' ';
}
buff[write++] = c;
}
new String(buff, 0, write);
I claim this is an O(n) algorithm (I haven't tampered with it to try and
make it look faster - no reusing the buffer, no trying different
permutations of code, no splitting into submethods). The results:
201295:448 928502:963 8793120:2965 64837622:8052 14568830:3816
87391:295 97777:312 190372:436 1141673:1068 13025497:3609
87909:296 87599:295 203727:451 1130767:1063 13002021:3605
84779:291 99787:315 191618:437 1199595:1095 13011692:3607
88198:296 98584:313 186264:431 1218971:1104 13033585:3610
Indeed the times (not the square roots) for the third, fourth and fifth
are around ten times the previous. For 1000 character strings we are
only three or four times faster. For 100,000 character strings we are a
handy fifty times faster than the original algorithm.
(Disclaimer: I've not actually checked the code does what it claims to.)
Tom Hawtin
class Ouch {
public static void main(String[] args) throws Exception {
for (int runCt=0; runCt<5; ++runCt) {
String str = " ,";
for (int lenCt=0; lenCt<5; ++lenCt) {
System.gc();
Thread.sleep(100);
long start = System.nanoTime();
doRun(str);
long end = System.nanoTime();
long period = end - start;
System.out.print(period+":"+(int)Math.sqrt(period)+" ");
StringBuilder buff = new StringBuilder(10*str.length());
for (int ct=0; ct<10; ++ct) {
buff.append(str);
}
str = buff.toString();
}
System.out.println();
}
}
private static void doRun(String str) {
for (int loopCt=0; loopCt<10; ++loopCt) {
StringBuilder buff = new StringBuilder(str.length()*11/10);
buff.append(str);
for (int j=0; j<buff.length(); j++) {
if(buff.charAt(j) == ','){
buff.insert(j, ' ');
++j;
}
}
}
}
}
| |
| Oliver Wong 2006-12-15, 7:10 pm |
|
"Thomas Hawtin" <usenet@tackline.plus.com> wrote in message
news:45817409$0$8757$ed2619ec@ptn-nntp-reader02.plus.net...
> Oliver Wong wrote:
>
> StringBuffer.insert is an O(n) operation.
Oops. Yeah, I guess I'd fail the Google entrance exam...
- Oliver
|
|
|
|
|