Java Function Challenge

Fastest, smallest function wins!

  • (7 Pages)
  • +
  • « First
  • 5
  • 6
  • 7

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

#91 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



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

Re: Java Function Challenge

Posted 24 December 2010 - 02:06 PM

Thanks you guys for participating! It has been very interesting to see not only the different algorithms, but it was also interesting to see how the times may not be consistent. That tells you a little something about the nature of Java though and how the JVM is doing things that we may not always know about or plan for. When it comes down to it, if you want to purely test an algorithm, use assembly.
Was This Post Helpful? 0
  • +
  • -

#92 flavian  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 17-December 13

Re: Java Function Challenge

Posted 17 December 2013 - 06:22 PM

My second attempt tryin to use charAt as little as possible.. haha

	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;   
	}


Chars outputted: 460
Time (in nanoseconds): 4932.919
Was This Post Helpful? 0
  • +
  • -

#93 CasiOo  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1414
  • View blog
  • Posts: 3,136
  • Joined: 05-April 11

Re: Java Function Challenge

Posted 24 December 2013 - 06:27 AM

There is one improvement that I havent seen any of you guys try yet
Remove the loop condition, keep on looping until an IndexOutOfBounds exception is thrown
Add a try-catch and count on the exception being thrown. It will save you many checks :)
Sadly I cant test the code from this device, but hopefully somebody will try it for me

Update:
Seems like building up the Exception (stack trace etc.) really hurts the performance

This post has been edited by CasiOo: 25 December 2013 - 01:31 PM

Was This Post Helpful? 0
  • +
  • -

#94 jamiemcl001  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 05-January 14

Re: Java Function Challenge

Posted 05 January 2014 - 08:19 AM

Hi all, I know I'm probably too late to submit now, but I just wanted to share the attempts I made at this challenge. Looking back through other entries I'm pretty sure I've got similar code to others (apologies for that). Anyways here's a number of my attempts:

Attempt No. 1:
public static int countNonWhitespaceCharacters(String stringToParse) {
	int count = 0;

	for(int i=0; i < stringToParse.length(); ++i) {
		if(stringToParse.charAt(i) != ' ') {
			++count;
		}
	}

	return count;
}

This was pretty slow as it was computing the stringToParse.length() on every iteration, also the charAt doesn't seem to be very optimal.

Attempt No. 2:
public static int countNonWhitespaceCharacters(String stringToParse) {
	char[] charArray = stringToParse.toCharArray();
	int count = 0;

	for (char character : charArray) {
	    if (character != ' '){
		    ++count;
	    }
	}

	return count;
}

This did seem to be an improvement, using a for-each loop.

Attempt No. 3:
public static int countNonWhitespaceCharacters(String stringToParse) {
	char[] charArray = stringToParse.toCharArray();
	int count = charArray.length;
	
	for(char character : charArray) {
		if(Character.isWhitespace(character)) {
			--count;
		}
	}

	return count;
}

By assuming the subtraction would need to be executed less times than the addition I changed it to check whether or not the character was a white-space character. The logic was better, but using the Character.isWhitespace boolean call on every character the execution time was horrendous.

Attempt No. 4:
public static int countNonWhitespaceCharacters(String stringToParse) {
	char[] charArray = stringToParse.toCharArray();
	int count = charArray.length;
	
	for(char character : charArray) {
		if(character == ' ') {
			--count;
		}
	}

	return count;
}

Essentially the same as #3, but using my own check to check whether or not it was a space character. Much improved execution time over the previous attempt.
Chars outputted: 460
Time (in nanoseconds): 23000


Finally Attempt No. 5.
public static int countNonWhitespaceCharacters(String stringToParse) {
	char[] charArray = stringToParse.toCharArray();
	int initialCount = charArray.length, i = 0, count;
	
	count = initialCount;
	
	do {
		if(charArray[i] == ' ') {
			--count;
		}
		
		++i;
	} while(i < initialCount);

	return count;
}

I thought this one would take a longer time to execute, but according to my JVM it took less:
Chars outputted: 460
Time (in nanoseconds): 15000

I'm pretty sure this was just accidental, as sometimes it can take longer than #4, sometimes it is quicker though.

Anyways, as this was my first post I just wanted to thank Dogstopper for running this challenge. It's been a while since I've done any Java. Apologies again if any of my attempts is similar to others, I swear I did not cheat. :dozingoff:/>
Was This Post Helpful? 0
  • +
  • -

#95 4n35h  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 12-January 14

Re: Java Function Challenge

Posted 12 January 2014 - 10:41 AM

Here is my code..
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) {
		int count = s.length(),size = s.length();
		for(int i=0;i<size;i++) {
		    if((s.charAt(i)==' ')) count--;
		}
		return count;
	}
		
}

Was This Post Helpful? 0
  • +
  • -

#96 farrell2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 856
  • View blog
  • Posts: 2,620
  • Joined: 29-July 11

Re: Java Function Challenge

Posted 02 February 2014 - 03:08 PM

 static int countChars(String... s) {
        int count = 0;
        char[] charArray = s[0].toCharArray();
        for (char c : charArray) {
            if (c != ' ') {
                ++count;
            }
        }
        return count;
    }



The enhanced for loop should be the fastest because it does only one length check, I believe.

This post has been edited by farrell2k: 02 February 2014 - 03:31 PM

Was This Post Helpful? 0
  • +
  • -

#97 Flukeshot  Icon User is offline

  • A little too OCD
  • member icon

Reputation: 417
  • View blog
  • Posts: 1,030
  • Joined: 14-November 12

Re: Java Function Challenge

Posted 03 February 2014 - 04:27 AM

I decided to think outside the box a little for this challenge.. This code is very slow compared to a simple loop when it comes to this particular string, but change that from 20 lines to 20 thousand lines and it makes no difference.

Pro: code relies solely on the first 2 lines of the string, making length irrelevant.
Con: code relies entirely on the String being repetitive.

Spoiler

This post has been edited by Flukeshot: 03 February 2014 - 05:13 AM

Was This Post Helpful? 0
  • +
  • -

#98 jbshu4546  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 09-March 14

Re: Java Function Challenge

Posted 09 March 2014 - 01:59 PM


public class SpaceTest {

	public static void main(String[] args)
	{
		String longString = "Someone must have been telling lies about Josef K., he knew he had done nothing wrong but, one morning, he was arrested. Every day at eight in the morning he was brought his breakfast by Mrs. Grubach's cook - Mrs. Grubach was his landlady - but today she didn't come. That had never happened before. K. waited a little while, looked from his pillow at the old woman who lived opposite and who was watching him with an inquisitiveness quite unusual for her, and finally, both hungry and disconcerted, rang the bell. There was immediately a knock at the door and a man entered. He had never seen the man in this house before. He was slim but firmly built, his clothes were black and close-fitting, with many folds and pockets, buckles and buttons and a belt, all of which gave the impression of being very practical but without making it very clear what they were actually for. 'Who are you?' asked K., sitting half upright in his bed. The man, however, ignored the question as if his arrival simply had to be accepted, and merely replied, 'You rang?' 'Anna should have brought me my breakfast,' said K. He tried to work out who the man actually was, first in silence, just through observation and by thinking about it, but the man didn't stay still to be looked at for very long. Instead he went over to the door, opened it slightly, and said to someone who was clearly standing immediately behind it, 'He wants Anna to bring him his breakfast.' There was a little laughter in the neighbouring room, it was not clear from the sound of it whether there were several people laughing. The strange man could not have learned anything from it that he hadn't known already, but now he said to K., as if making his report 'It is not possible.' 'It would be the first time that's happened,' said K., as he jumped out of bed and quickly pulled on his trousers. 'I want to see who that is in the next room, and why it is that Mrs. Grubach has let me be disturbed in this way.' It immediately occurred to him that he needn't have said this out loud, and that he must to some extent have acknowledged their authority by doing so, but that didn't seem important to him at the time. That, at least, is how the stranger took it, as he said, 'Don't you think you'd better stay where you are?' 'I want neither to stay here nor to be spoken to by you until you've introduced yourself.' 'I meant it for your own good,' said the stranger and opened the door, this time without being asked. The next room, which K. entered more slowly than he had intended, looked at first glance exactly the same as it had the previous evening. It was Mrs. Grubach's living room, over-filled with furniture, tablecloths, porcelain and photographs. Perhaps there was a little more space in there than usual today, but if so it was not immediately obvious, especially as the main difference was the presence of a man sitting by the open window with a book from which he now looked up. 'You should have stayed in your room! Didn't Franz tell you?' 'And what is it you want, then?' said K., looking back and forth between this new acquaintance and the one named Franz, who had remained in the doorway. Through the open window he noticed the old woman again, who had come close to the window opposite so that she could continue to see everything. She was showing an inquisitiveness that really made it seem like she was going senile. 'I want to see Mrs. Grubach ,' said K., making a movement as if tearing himself away from the two men - even though they were standing well away from him - and wanted to go. 'No,' said the man at the window, who threw his book down on a coffee table and stood up. 'You can't go away when you're under arrest.' 'That's how it seems,' said K. 'And why am I under arrest?' he then asked. 'That's something we're not allowed to tell you. Go into your room and wait there. Proceedings are underway and you'll learn about everything all in good time. It's not really part of my job to be friendly towards you like this, but I hope no-one, apart from Franz, will hear about it, and he's been more friendly towards you than he should have been, under the rules, himself. If you carry on having as much good luck as you have been with your arresting officers then you can reckon on things going well with you.' K. wanted to sit down, but then he saw that, apart from the chair by the window, there was nowhere anywhere in the room where he could sit. 'You'll get the chance to see for yourself how true all this is,' said Franz and both men then walked up to K. They were significantly bigger than him, especially the second man, who frequently slapped him on the shoulder. The two of them felt K.'s nightshirt, and said he would now have to wear one that was of much lower quality, but that they would keep the nightshirt along with his other underclothes and return them to him if his case turned out well. 'It's better for you if you give us the things than if you leave them in the storeroom,' they said. 'Things have a tendency to go missing in the storeroom, and after a certain amount of time they sell things off, whether the case involved has come to an end or not. And cases like this can last a long time, especially the ones that have been coming up lately. They'd give you the money they got for them, but it wouldn't be very much as it's not what they're offered for them when they sell them that counts, it's how much they get slipped on the side, and things like that lose their value anyway when they get passed on from hand to hand, year after year.' K. paid hardly any attention to what they were saying, he did not place much value on what he may have still possessed or on who decided what happened to them. It was much more important to him to get a clear understanding of his position, but he could not think clearly while these people were here, the second policeman's belly - and they could only be policemen - looked friendly enough, sticking out towards him, but when K. looked up and saw his dry, boney face it did not seem to fit with the body. His strong nose twisted to one side as if ignoring K. and sharing an understanding with the other policeman. What sort of people were these? What were they talking about? What office did they belong to? K. was living in a free country, after all, everywhere was at peace, all laws were decent and were upheld, who was it who dared accost him in his own home? He was always inclined to take life as lightly as he could, to cross bridges when he came to them, pay no heed for the future, even when everything seemed under threat. But here that did not seem the right thing to do. He could have taken it all as a joke, a big joke set up by his colleagues at the bank for some unknown reason, or also perhaps because today was his thirtieth birthday, it was all possible of course, maybe all he had to do was laugh in the policemen's face in some way and they would laugh with him, maybe they were tradesmen from the corner of the street, they looked like they might be - but he was nonetheless determined, ever since he first caught sight of the one called Franz, not to lose any slight advantage he might have had over these people. There was a very slight risk that people would later say he couldn't understand a joke, but - although he wasn't normally in the habit of learning from experience - he might also have had a few unimportant occasions in mind when, unlike his more cautious friends, he had acted with no thought at all for what might follow and had been made to suffer for it. He didn't want that to happen again, not this time at least; if they were play-acting he would act along with them.";
		int count = 0;
				
		for (int i = 0; i < longString.length(); i++)
		{
			if (longString.indexOf(i) != ' ')
			{
				count++;
			}
		}
		
		System.out.println(count);
	}
}


Was This Post Helpful? 0
  • +
  • -

#99 javaJarrett  Icon User is offline

  • New D.I.C Head

Reputation: 7
  • View blog
  • Posts: 19
  • Joined: 30-April 14

Re: Java Function Challenge

Posted 01 May 2014 - 01:21 PM

so i'm a little late to this challenge but then again I just found this forum the other day. Here is my solution. I routinely got times in the 1300 to 1400's. awaiting all critiques.

Chars outputted: 460
Time (in nanoseconds): 1394.182

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)
	{
		int count = 0;
		
		for(int i = 0; i < s.length(); i++)
		{
			if(s.charAt(i) == ' ')
			{
				count++;
			}
		}

		return s.length() - count;
		
	}



Was This Post Helpful? 0
  • +
  • -

#100 bmnpls  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 8
  • Joined: 31-October 08

Re: Java Function Challenge

Posted 13 June 2014 - 08:18 AM

Hi everyone,
i know its a long time since this was posted but im suprised not one of you came up with a version not including a if-statement. Modern CPUs do some magic with branche prediction but if that fails the whole pipeline has to be cleared. Therfore benchmark code should try to avoid branches. And indeed i came up with a version that is ~twice as fast as the fastest one posted here. Obviously this is hardware specific but having a common i5 im shure this will be true for ~95% of you.

But before i post that code some hints to benchmarks:
- execute the code you want to messure some times before you actualy messure it! Therfore the JIT has all the time it needs to fully optimize. If you dont do that yout results will vary a lot.
- randomize the execution order! (or pre run your code for several minutes.) As some optimizations take realy long you either have to pre run your code for minutes or run it in randomized order and check the results of several independent runs (whole jvm cicle).

The test code ill post below shows all of this (and some idears i had).

The "best" version of my code is hard to determin as all 4 attempts performe different if the amount of spaces in the given text is changed.
Also i'm not shure if declaring a new variable for the length of the string has any effect. My tests on my machine showed that it could be possible but not with stringToTest.length() < 8k

Enough babbling, here is my best bet:
Spoiler


And if someone is interessted here is the code i used for my benchmarks:
Spoiler

Was This Post Helpful? 0
  • +
  • -

#101 yashwanth.c.b  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 234
  • Joined: 07-July 13

Re: Java Function Challenge

Posted 21 August 2014 - 05:26 AM

Spoiler

Was This Post Helpful? 0
  • +
  • -

  • (7 Pages)
  • +
  • « First
  • 5
  • 6
  • 7