Java Function Challenge

Fastest, smallest function wins!

  • (7 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »

100 Replies - 46949 Views - Last Post: 21 August 2014 - 05:26 AM

#1 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Java Function Challenge

Post icon  Posted 22 December 2010 - 06:55 AM

*
POPULAR

Hey </Dream.In.Code>ers!

It's time to wake up and really face a challenge. This is short, but it should take some work. This challenge is to find a small, super fast algorithm that counts the number of non-space characters in any given String. To play, just do something like this:

public class Main {
	
	public static void main(String[] args) {
		String s = "This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string" +
				"This is a really long string";
		
			// Output the result.
			System.out.println("Chars outputted: " + countNumChars(s));
			
			// Now get average of 1000 trials.
			long before = System.nanoTime();
			for (int i = 0; i < 1000; i++) {
				countNumChars(s);
			}
			long after = System.nanoTime();
			System.out.println("Time (in nanoseconds): " + ((after-before))/1000.0);
	}

	private static int countNumChars(String s) {
		
	}
		
}


Just fill in the body for the countNumChars method or change it a little bit and see if you can beat everybody else. The fastest algorithm wins!

Please post your code and the results in your post.

*For the benefit of those functional coders who use a JVM functional language, just create something that mimics this output so that we can properly test it.

Get coding! The deadline is January 5th, which gives you all a week to find the fastest algorithm.

This post has been edited by Dogstopper: 22 December 2010 - 10:18 AM


Is This A Good Question/Topic? 11
  • +

Replies To: Java Function Challenge

#2 moopet  Icon User is offline

  • binary decision maker
  • member icon

Reputation: 339
  • View blog
  • Posts: 1,185
  • Joined: 02-April 09

Re: Java Function Challenge

Posted 22 December 2010 - 07:11 AM

To be compared on your reference system, I'm assuming?
Was This Post Helpful? 0
  • +
  • -

#3 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 07:17 AM

Yes. But if you can up a better reference system, by all means, let me know!

Edit: At the end, they will all be retested on a single machine. That way, machine inconsistencies do not hinder the results.

This post has been edited by Dogstopper: 22 December 2010 - 07:29 AM

Was This Post Helpful? 0
  • +
  • -

#4 Sergio Tapia  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1253
  • View blog
  • Posts: 4,168
  • Joined: 27-January 10

Re: Java Function Challenge

Posted 22 December 2010 - 07:30 AM

First shot, using built in helpers. Can't wait to see the crazy crap you guys come up with. :lol:

Spoiler


Second attempt!

Spoiler


Third attempt, and I'm spent! *lights cigarette* Was it good for you DIC?

Spoiler


Last try, no more dice to throw:

Spoiler

This post has been edited by Sergio Tapia: 22 December 2010 - 07:57 AM

Was This Post Helpful? 1
  • +
  • -

#5 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 07:32 AM

Sergio, can you include the method code so that we can test it later? That way, we can get consistent time at the end and so you get credit for a particular solution.
Was This Post Helpful? 0
  • +
  • -

#6 Sergio Tapia  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1253
  • View blog
  • Posts: 4,168
  • Joined: 27-January 10

Re: Java Function Challenge

Posted 22 December 2010 - 07:36 AM

Ah sure, I thought I read somewhere in the rules not to post code yet. :P
Was This Post Helpful? 0
  • +
  • -

#7 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 07:41 AM

I'm going to post mine after a few of the newer members come up with solutions. I don't want to just give it to them... :P

Thanks for participating!

Just as a not, your first algorithm is counting spaces, not non-space characters....
Here is the output I got for you:

Quote

Chars outputted: 100
Time (in nanoseconds): 4366.293


so, it's really close to mine...
Was This Post Helpful? 0
  • +
  • -

#8 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3120
  • View blog
  • Posts: 19,163
  • Joined: 14-September 07

Re: Java Function Challenge

Posted 22 December 2010 - 07:46 AM

Are we allowed to make any assumptions of the input string?


Simple first go around:

Spoiler



Quote

Chars outputted: 460
Time (in nanoseconds): 2599.772

Was This Post Helpful? 0
  • +
  • -

#9 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 07:51 AM

Assumptions that can be made is it's a standard English String over 100 characters long with no newlines.

Since others have played, I'll go ahead and reveal mine:
Spoiler


It makes an assumption that there are overall less spaces than characters, and thus it's faster to subtract than add like yours did KYA. It'd be interesting to see which is fastest on the the same computer...
Was This Post Helpful? 1
  • +
  • -

#10 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3120
  • View blog
  • Posts: 19,163
  • Joined: 14-September 07

Re: Java Function Challenge

Posted 22 December 2010 - 07:53 AM

What was your time output for that?



Computational efficiency wise, ours are both O(n). Since we have to touch each char, we can't do better. :(
Was This Post Helpful? 0
  • +
  • -

#11 Sergio Tapia  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1253
  • View blog
  • Posts: 4,168
  • Joined: 27-January 10

Re: Java Function Challenge

Posted 22 December 2010 - 07:55 AM

View PostDogstopper, on 22 December 2010 - 09:41 AM, said:

I'm going to post mine after a few of the newer members come up with solutions. I don't want to just give it to them... :P

Thanks for participating!

Just as a not, your first algorithm is counting spaces, not non-space characters....
Here is the output I got for you:

Quote

Chars outputted: 100
Time (in nanoseconds): 4366.293


so, it's really close to mine...


Yeah I changed the != symbol. Now it's what I have.
Was This Post Helpful? 0
  • +
  • -

#12 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 07:55 AM

My output:

Quote

Chars outputted: 460
Time (in nanoseconds): 3714.284


Your output:

Quote

Chars outputted: 460
Time (in nanoseconds): 3927.45


So the difference is nearly nothing.
Was This Post Helpful? 0
  • +
  • -

#13 KYA  Icon User is offline

  • g++ jameson.cpp -o beverage
  • member icon

Reputation: 3120
  • View blog
  • Posts: 19,163
  • Joined: 14-September 07

Re: Java Function Challenge

Posted 22 December 2010 - 08:04 AM

Shaved 100 nanoseconds off:

Spoiler


Quote

Chars outputted: 460
Time (in nanoseconds): 2457.296


Taking a look at the source, length() only returns a pre-calculated count variable, but there's no reason to call it each loop iteration.



Modifying Dogstopper'slightly:

Spoiler


Quote

Chars outputted: 460
Time (in nanoseconds): 2522.388

Was This Post Helpful? 1
  • +
  • -

#14 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 08:09 AM

I shaved 100ns off as well by using a char array and a saved length variable:
Spoiler


And time:

Quote

Chars outputted: 460
Time (in nanoseconds): 2510.354


KYA, I got your fastest time as

Quote

Chars outputted: 460
Time (in nanoseconds): 3802.823


On my system. Which one of our newest 2 is fastest on yours?

This post has been edited by Dogstopper: 22 December 2010 - 08:11 AM

Was This Post Helpful? 0
  • +
  • -

#15 SixOfEleven  Icon User is offline

  • using Caffeine;
  • member icon

Reputation: 945
  • View blog
  • Posts: 6,342
  • Joined: 18-October 08

Re: Java Function Challenge

Posted 22 December 2010 - 08:10 AM

Interesting question Dogstopper. Think I'm going to do something similar for the .NETers.
Was This Post Helpful? 0
  • +
  • -

  • (7 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »