• Post Reply Bookmark Topic Watch Topic
  • New Topic

Counting 0s and 1s  RSS feed

 
Tahmid Choyon
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I am new to Java Programming Language. In one of my programs I am trying to count 0s and 1s from a String which contains only 0 and 1 and mark their position with their frequency.
For example,

If x is the String I am working with then my output should be

Number inside [] represents number of 1s and {} represents number of 0s.

Another example to make my words clear.

For this y String the output should be

What I have tried so far is here:

bracketTheory.java


main.java


I tried giving 111000 as an Input and it should return [3]{3}. But instead it returns [3]{0}{0}{0}. I have tried debugging and trying to figure out the real problem here. Anybody here to help me out with this? Where exactly am I making mistake?
 
Tahmid Choyon
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Funny thing is while copying and pasting the codes from my project source file, I forgot to edit the lines which may end up with compilation error. So here is the corrected version of the codes

bracketTheory.java


main.java
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't see the need for maintaining substrings. Having a previous char should be sufficient. When the charAt() no longer matches the previous char the output the count. If it matches then increment a counter.
 
Tahmid Choyon
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:I don't see the need for maintaining substrings. Having a previous char should be sufficient. When the charAt() no longer matches the previous char the output the count. If it matches then increment a counter.

Thanks a lot for this suggestion. I have come up with this...


Then again, for 111000 it returns [3]{3}{2}{1}. That is the problem I am trying to figure out!  >
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There really is no need for a StringBuilder either. Just use String.toCharArray() and iterate over that array.
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A short way is

and then it is easy to get the required output.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tahmid Choyon wrote:That is the problem I am trying to figure out! 


You use the concept of "changing tracks" -- in your inner loop. When the new track is different than the previous track, you clean up (and fix up) your indexes, so that the outer loop correctly moves to the next group of letter... you also do a "not completely set the indexes correctly, so that when the outer loop does its increments, it is correct".

... but ... hint ... what happens when there is no change of tracks? What happens, at the end of the input, where the inner loop just finishes? Does the clean up code, fixes the indexes, so that, the outer loop finishes correctly?

Henry
 
Tahmid Choyon
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:A short way is

and then it is easy to get the required output.


This is one brilliant solution to my problem! 
Thank you so much!
 
Tahmid Choyon
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Henry Wong wrote:
Tahmid Choyon wrote:That is the problem I am trying to figure out! 


You use the concept of "changing tracks" -- in your inner loop. When the new track is different than the previous track, you clean up (and fix up) your indexes, so that the outer loop correctly moves to the next group of letter... you also do a "not completely set the indexes correctly, so that when the outer loop does its increments, it is correct".

... but ... hint ... what happens when there is no change of tracks? What happens, at the end of the input, where the inner loop just finishes? Does the clean up code, fixes the indexes, so that, the outer loop finishes correctly?

Henry


Thank you
I understood my mistake now!
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It's interesting to see a different approach to solving this problem. You are basically breaking the string down into substrings of the same character then looking at the length of each substring. Piet's little String.replace incantation works nicely for that.

There are a number of extraneous steps you can eliminate to tighten up your code though.  For one, you use a StringBuilder but only at the end of the method. Inside the method, and more significantly, inside a loop, you use string concatenation. One normally uses a StringBuilder inside a loop to avoid string concatenation, which is less efficient inside a loop.  The fact that you return a StringBuilder is also a bit unusual. Normally, a StringBuilder is used as a local temporary buffer and you'd return it's toString() from the method instead.

This is what I did in my solution (the local StringBuilder as a buffer, that is). I also just converted the String to a char[] as I mentioned in previous reply and just used one for loop to iterator over that.

With your approach, and taking into account the two calls to String.replace() and then to String.split(), you are essentially going over the String four times: once to replace "10" with "1-0", once to replace "01" with "0-1", once to split the string, then one more time to count the lengths of each substring.

I have to go out for a while but it would be interesting to see the difference in the times that these two approaches take in converting long inputs and at what point one will start showing a significant performance advantage over the other, if any.
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here's my code with timing for a string of length 256 and 1/2 million iterations:
1 millis: 1944
2 millis: 8832
The replaceAll approach was about 4.5 times slower.

 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The code I used was:

with

 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok Piet, this is what I plugged in for your method. I highly suspect there's a better Java8 way to do this but I'm a bit weak in that area. The timing is (yours is #3):
1 millis: 2090
2 millis: 9214
3 millis: 10853


 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Carey Brown wrote:
The replaceAll approach was about 4.5 times slower.


The problem with the replaceAll() regex approach is that it takes 4 passes to complete (three of which are regex). Two loops in the two replaceAll() calls, one loop in the split() call, and one loop to put it all together.

What if it was done with one regex pass?


Henry
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Found this collector

Now timing is
1 millis: 1936
2 millis: 9198
3 millis: 9795
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wow! This was what I had in mind, but I'm not a regex expert and I was unable to come up with 

Compliments!

Edit: this is about Henry's solution.

@Carey
I had missed the last part, that we should end up with just one joined string; That's why I stopped at my list.
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
With Henry's one-regex approach
1 millis: 1911
2 millis: 9161
3 millis: 9731 Piet's Java8
4 millis: 5287 Henry's one-regex
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For what it's worth: I ran my version on a string of 5M zero's and ones, and the run time was about 5 seconds, with the parallel version slightly under 5 seconds.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I cleaned up the tester program a bit. These are the results I got:

Seems like dealing with char is a little faster than dealing with Strings in a StringBuilder.
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is no reason to call String#toCharArray() as this will create a not required copy of the array, String#charAt(int) is sufficient.

Small benchmarks, n is the string length:
*Is literally the same as compress, just using String#charAt instead of directly accessing the array
**Replaced m.group() with m.start() and m.end() to avoid String#substring, moved pattern out of the method

 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Tobias, what is "jlS_value" ? And "u" ?
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
(Btw. sorry for posting this in the beginning forum) Sorry, forgot to add this, 'u' is an Unsafe instance and 'jlS_value' is the field offset of the String#value field (access with Lookup#findGetter(String.class, "value", char[].class) would work too), used to avoid the cost of String#charAt calls.
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm trying to implement a custom Collector and I'm getting a compile error I don't understand on line 55. (Sorry, unable to post error message.)
 
Tobias Bachert
Ranch Hand
Posts: 86
18
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The streams for primitive types do not have a collect(Collector) method, only collect(Supplier, Accumulator, Combiner).
Something like
should work (edit: Accum#combine has to do a bit more than I thought initally, but as long as the stream is sequential, providing null should be sufficient)).
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Tobias.

So here are my new timings with the custom Collector added in:

Utilizing the Collector:
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!