[Dogstopper]

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

[moopet]

To be compared on your reference system, I'm assuming?

[Dogstopper]

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

[Sergio Tapia]

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

Spoiler

private static int countNumChars(String s) {
    int count = 0;

    for(char c : s.toCharArray()){
        if (c != ' ')
            count++;
    }

    return count;
}

Chars outputted: 460
Time (in nanoseconds): 21129.119

Second attempt!

Spoiler

private static int countNumChars(String s) {
    int count = 0;

    for(char c : s.toCharArray()){
        if (!Character.isSpaceChar(c))
            count++;
    }

    return count;
}

Chars outputted: 460
Time (in nanoseconds): 11649.995

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

Spoiler

private static int countNumChars(String s) {
    int count = 0;
    char[] chars = s.toCharArray();

    //Cheating, I know! :D/>
    for (int i = 0; i < 560; i++) {
        if (!Character.isSpaceChar(chars[i])){
            count++;
        }
    }

    return count;
}

Chars outputted: 460
Time (in nanoseconds): 9341.908

Last try, no more dice to throw:

Spoiler

private static int countNumChars(String s) {
    int count = 0;
    for (int i = 0; i < 560; i++) {
        if (s.charAt(i) != ' '){
            count++;
        }
    }
    return count;
}

Chars outputted: 460
Time (in nanoseconds): 3763.694

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

[Dogstopper]

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.

[Sergio Tapia]

Ah sure, I thought I read somewhere in the rules not to post code yet.

[Dogstopper]

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...

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...

[KYA]

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


Simple first go around:

Spoiler

private static int countNumChars(String s) {
int count = 0;
for(int i = 0; i < s.length(); i++){
if(!(s.charAt(i) == ' ')) count++;
}
return count;
}

Quote

Chars outputted: 460
Time (in nanoseconds): 2599.772

[Dogstopper]

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

	private static int countNumChars(String s) {
		int num = s.length();
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == ' ') {
				num--;
			}
		}
		return num;
	}

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...

[KYA]

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.

[Sergio Tapia]

Dogstopper, 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...

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.

[Dogstopper]

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.

[KYA]

Shaved 100 nanoseconds off:

Spoiler

private static int countNumChars(String s) {
		int count = 0;
		int size = s.length();
		for(int i = 0; i < size; i++){
			if(!(s.charAt(i) == ' ')) count++;
		}
		return count;
	}

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

private static int countNumChars(String s) {
		int count = s.length();
		int size = count;
		for(int i = 0; i < size; i++){
			if(s.charAt(i) == ' ') count--;
		}
		return count;
	}

Quote

Chars outputted: 460
Time (in nanoseconds): 2522.388

[Dogstopper]

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

Spoiler

	private static int countNumChars(String s) {
		char[] a = s.toCharArray();
		int length = a.length;
		int num = length;
		for (int i = 0; i < length; i++) {
			if (a[i] == ' ') {
				num--;
			}
		}
		return num;
	}

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

[SixOfEleven]

Interesting question Dogstopper. Think I'm going to do something similar for the .NETers.