Java Function Challenge

Fastest, smallest function wins!

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

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

#16 m-e-g-a-z  Icon User is offline

  • Winning
  • member icon


Reputation: 497
  • View blog
  • Posts: 1,457
  • Joined: 19-October 09

Re: Java Function Challenge

Posted 22 December 2010 - 08:19 AM

Brilliant challenge Dogstopper, going to see what I can come up with after I finish work :).
Was This Post Helpful? 0
  • +
  • -

#17 Sergio Tapia  Icon User is offline

  • D.I.C Lover
  • member icon

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

Re: Java Function Challenge

Posted 22 December 2010 - 08:20 AM

Values will be skewed of course, according to the hardware. Hell even on my machine if I run the same method many times, I get different results. ;)

Use the numbers as ballpark figures. :D
Was This Post Helpful? 0
  • +
  • -

#18 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon

Reputation: 2965
  • View blog
  • Posts: 11,222
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 08:22 AM

Of course. That's why when we judge it, all the submissions will be run on the same machine 5 times and the fastest run takes the points. I love excel!
Was This Post Helpful? 0
  • +
  • -

#19 CodeGrappler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 41
  • View blog
  • Posts: 120
  • Joined: 29-November 10

Re: Java Function Challenge

Posted 22 December 2010 - 08:40 AM

Ah people posted all over the place while I left this topic open. Quite a few responses now.

Attempt #1: This solution can be improved by about 1000 nanoseconds if we are guaranteed to have a string length that is evenly divisible by 4.

Spoiler

This post has been edited by CodeGrappler: 22 December 2010 - 08:58 AM

Was This Post Helpful? 2
  • +
  • -

#20 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Java Function Challenge

Posted 22 December 2010 - 09:16 AM

I don't think there's an algorithm faster than O(n). The time it takes will depend on the programming language, compiler, and the machine it is run on. Any optimizations done will speed it up a little bit, but nothing significant.
Was This Post Helpful? 0
  • +
  • -

#21 CodeGrappler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 41
  • View blog
  • Posts: 120
  • Joined: 29-November 10

Re: Java Function Challenge

Posted 22 December 2010 - 09:20 AM

Attempt #2: Now that I know subtracting is faster for some reason. (Took Dogstopper's original solution and modified it.)

Strangely i tried doing the same subtraction trick on "i" and it was slower...No idea why.

Spoiler

Was This Post Helpful? 0
  • +
  • -

#22 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 729
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Java Function Challenge

Posted 22 December 2010 - 09:22 AM

anyways here are 2 attempts, both O(n)

Spoiler


Spoiler


of course the second one will be faster because in recursion there's some overhead.

This post has been edited by skyhawk133: 22 December 2010 - 09:25 AM
Reason for edit:: Added [spoiler] tags

Was This Post Helpful? 0
  • +
  • -

#23 KYA  Icon User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3194
  • View blog
  • Posts: 19,220
  • Joined: 14-September 07

Re: Java Function Challenge

Posted 22 December 2010 - 09:27 AM

In case anyone is curious, even bare minimal threading (just two threads, using a divide and conquer approach) adds too much overhead, rendering it irrelevant :(
Was This Post Helpful? 2
  • +
  • -

#24 CodeGrappler  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 41
  • View blog
  • Posts: 120
  • Joined: 29-November 10

Re: Java Function Challenge

Posted 22 December 2010 - 09:30 AM

View PostKYA, on 22 December 2010 - 08:27 AM, said:

In case anyone is curious, even bare minimal threading (just two threads, using a divide and conquer approach) adds too much overhead, rendering it irrelevant :(


I was curious about that but was feeling way too lazy to try it! Thanks =p
Was This Post Helpful? 0
  • +
  • -

#25 SpeedisaVirus  Icon User is offline

  • Baller

Reputation: 115
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Re: Java Function Challenge

Posted 22 December 2010 - 09:40 AM

I wanted to post my solution before looking at the others...dunno how it compares speed yet but this is the first thing I thought of.

Spoiler

Was This Post Helpful? 1
  • +
  • -

#26 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon

Reputation: 2965
  • View blog
  • Posts: 11,222
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 09:42 AM

Lol...we tried that one about a year ago and established that replaceAll() is almost the absolute slowest way to handle it next to actually intentionally slowing it down. Thanks though!
Was This Post Helpful? 0
  • +
  • -

#27 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 614
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: Java Function Challenge

Posted 22 December 2010 - 09:57 AM

So, I cheated and did this in Clojure. Don't hate me, few people know Clojure 'round these parts, so I don't have any Clojure challenges. If I don't do this challenge, what else do I have in life? ;) It compiles to Java bytecode anyway, so it's mostly as fast as Java if you want it to be.

This is the fastest implementation I could come up with:

(def s (apply str (repeat 20 "This is a really long string")))

(defn count-num-chars [s]
  (loop [s s acc 0]
    (if (seq s)
      (recur (rest s) (if (= (first s) \space) acc (inc acc)))
      acc)))

(println "Chars outputted:" (count-num-chars s))

(let [before (System/nanoTime)]
  (dotimes [_ 1000]
    (count-num-chars s))
  (let [after (System/nanoTime)]
    (println "Time (in nanoseconds):" (/ (- after before) 1000.0))))



Output:

Quote

[email protected]:~$ cake run ~/challenge.clj
Chars outputted: 460
Time (in nanoseconds): 136259.514
[email protected]:~$ cake run ~/challenge.clj


Note that you would should never see code like this in practice unless you really, really care about this insignificant performance. I wrote three different implementations. The best and slowest was this:

(defn count-num-chars [s]
  (count (remove #{\space} s)))



And the output was:

Quote

[email protected]:~$ cake run ~/challenge.clj
Chars outputted: 460
Time (in nanoseconds): 308657.914


The second and also reasonable example was this:

(defn count-num-chars [s]
  (reduce #(if (= \space %2) % (inc %)) 0 s))



It was faster, clocking in at:

Quote

[email protected]:~$ cake run ~/challenge.clj
Chars outputted: 460
Time (in nanoseconds): 180272.447


So that was pretty good.

Don't take this as a serious submission to the challenge. I just did it for fun because I was bored. Hope you enjoy it! :>
Was This Post Helpful? 1
  • +
  • -

#28 SpeedisaVirus  Icon User is offline

  • Baller

Reputation: 115
  • View blog
  • Posts: 855
  • Joined: 06-October 08

Re: Java Function Challenge

Posted 22 December 2010 - 10:01 AM

Yeah, after I posted that I realized how horrible that must be implemented. I didn't see the thread one year ago.

Spoiler

Was This Post Helpful? 0
  • +
  • -

#29 KYA  Icon User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3194
  • View blog
  • Posts: 19,220
  • Joined: 14-September 07

Re: Java Function Challenge

Posted 22 December 2010 - 10:02 AM

136k+! I thought Clojure was supposed to be fast. ;)
Was This Post Helpful? 0
  • +
  • -

#30 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon

Reputation: 2965
  • View blog
  • Posts: 11,222
  • Joined: 15-July 08

Re: Java Function Challenge

Posted 22 December 2010 - 10:03 AM

I hope you realize you can't win because I can't check for consistency with the others. However, it is certainly an interesting program AND it does run on the JVM. It certainly was cool to see!

Thanks!
Was This Post Helpful? 0
  • +
  • -

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