Job Market

I'm sure it's not the 'fastest way' cpu cycle wise, but it works! I've been teaching myself javascript the last few weeks and my way of thinking right now is just combining/condensing logic so that's what I came up with, so whateva!
 
Wiseguy2001 said:
And they say early optimisation is the route of all evil.. The mod operator isn't that expensive (just tried it in a loop of a trillion integers and it took 3.564 seconds, that was single threaded).

So you removed a bottleneck that never existed, meanwhile you introduced a huge amount of code repetition with code that is almost impossible to test.
Click to expand...

Yeah, loop unrolling is certainly a possible place for error introduction, but the question Mike had asked was if there is a place to optimize. There certainly is, as the standard FizzBuzz has 100 branch checks, while the modified one has (int) 100/15+(100-100/15) = 6 + 10 = 16 branch checks. As he has made clear throughout this thread, the "trivial" or "first approximation" algorithm is sometimes good enough to make sure you know the problem space, but scaling a problem requires a lot more investigation. Relatively, the amount of space or memory that my unrolled version takes is tiny for a 6.25x speedup. If we were dealing with a trillion numbers to be Fizz'd or Buzz'd, I may even write code to generate the unrolled loop, because I'm guessing (though have not empirically verified) that there is a sweet spot on length of unrolling depending on your problem size.
 
finally got my day with the boss to wrap up 2011, with a fat 10% increase, feels good after all the hard work, kept me from having to take the other job offer to make ends meet
 
nobody_here said:
finally got my day with the boss to wrap up 2011, with a fat 10% increase, feels good after all the hard work, kept me from having to take the other job offer to make ends meet
Click to expand...

Got with my boss right before December and ended up with a fat 23% increase :D It's called "Having in-demand skills in a tight field." So whoever says that software development jobs are all going to India, I'm here to tell you, there are still companies that recognize the value of keeping jobs here.
 
I already know that my company won't counter offer if I put in my notice. They've let 8 developers walk in the last 8 months. I think they have more contractors than direct hires at this point.
 
william_fontaine said:
my company is getting dozens of $150K full-year contractors and making the $75K in-house developers manage them
Click to expand...

this. if you have good skills and are not afraid to shop yourself around, i would definitely have to consider contract work, companies tend to pay them much more, saying "oh we will only use him for the initial work" and then 6 months in they realize they can't find someone to replace the contractor (or the contractor builds in job security...) and they keep the contractor on payroll........ i know of situations where they are STILL a slave to the designer years later and after a while the company just kind of accepts it
 
My solution to fizz buzz: two rounds of sieve of eratosthenes. Don't all hire me at once now :D
 
Last edited:
mikeblas said:
Don't worry, we won't. Your proposed solution is somewhere between "incomplete" and "won't work".
Click to expand...
Going by this description of the problem,
1) Start with an array with elements 1 to n.
2) Strike out multiples of 3 via SoE (i.e. say replace with -1)
3) Strike out multiples of 5 via SoE (i.e. say replace with -2); if already struck with -1, replace with say -3.
4) Scan array once and print elements, unless -1 (fizz), -2 (buzz), or -3 (fizzbuzz).

Better algorithm efficiency than any modulo solution as n grows large.

Edit: Just programmed my solution as well as a standard solution using modulo (similar to the ones in this thread), and for an input size of 100 million, here are the results:
Using modulo: 0.914821795
Using sieve: 0.344026249
 
Last edited:
now i know why i have no interest in coding at ALL after following your link......I'll stick with hardware, you can have that software crap
 
drleospaceman said:
Going by this description of the problem,
1) Start with an array with elements 1 to n.
2) Strike out multiples of 3 via SoE (i.e. say replace with -1)
3) Strike out multiples of 5 via SoE (i.e. say replace with -2); if already struck with -1, replace with say -3.
4) Scan array once and print elements, unless -1 (fizz), -2 (buzz), or -3 (fizzbuzz).

Better algorithm efficiency than any modulo solution as n grows large.

Edit: Just programmed my solution as well as a standard solution using modulo (similar to the ones in this thread), and for an input size of 100 million, here are the results:
Using modulo: 0.945289544 seconds
Using sieve: 0.088034459 seconds
Click to expand...

Now can you do it without using an array to hold all the numbers? That is, can you make it take less memory, yet still use, conceptually, the sieve algorithm? Note: I don't mean do it to multiple smaller arrays.
 
Tawnos said:
Now can you do it without using an array to hold all the numbers? That is, can you make it take less memory, yet still use, conceptually, the sieve algorithm? Note: I don't mean do it to multiple smaller arrays.
Click to expand...
Nope, got me there, the sieve needs a structure to hold the numbers afaik ;)

edit: On second thought, using lazy sequences in clojure would use less memory.
 
Last edited:
Answer to my own problem in spoiler tags below:
1. Take two ints, one initialized to 3, one initialized to 5
2. Iterate on i from 1 to n
3. At each step, check if i is equal to either of the ints from step 1
a. if it is not equal to the 3 or 5 int, print the number, else
ab. if it is equal to the 3 int, print Fizz then add 3 to the 3 int
ac. if it is equal to the 5 int, print Buzz then add 5 to the 5 int.

Code: 
public void SieveFizzBuzz(int max)
{
  int threes = 3;
  int fives = 5;
  for (int i = 1; i <= max; i++)
  {
    if (i != threes && i != fives)
    {
      printf("%d",i);
    }
    else
    {
      if (i == threes)
      {
        printf("Fizz");
        threes += 3;
      }
      if (i == fives)
      {
        printf("Buzz");
        fives += 5;
      }
    }
  }
}
 
Last edited:
This was the answer that first came to mind to me (PHP):
Nothing optimized for efficiency, but this seemed like the obvious way to solve the problem:
Code: 
<?php
for($i=1;$i<=100;$i++){
	if($i % 3 == 0 && $i % 5 == 0){
		echo 'FizzBuzz';
	}elseif($i % 3 == 0){
		echo 'Fizz';
	}elseif($i % 5 == 0){
		echo 'Buzz';
	}else{
		echo $i;
	}
}
?>
 
mikeblas said:
Hey, great -- now you've actually answered the question! Your algorithm still has a fatal flaw, though. And why did you decide to optimize for speed instead of memory usage?
Click to expand...
Using lazy sequences, it will use significantly less memory. If you had understood how sieve of erastothenes works, I wouldn't have needed to say anything more. Why did I optimize for speed? For fun. I saw the connection and thought it was interesting.
 
Last edited:
drleospaceman said:
Nope, got me there, the sieve needs a structure to hold the numbers afaik ;)

edit: On second thought, using lazy sequences in clojure would use less memory.
Click to expand...

To be fair, this is something I came across when I was teaching myself some F#, but it was quite eye opening. The sieve can be thought of as a priority queue, where the next number to be checked is to be checked against the next prime number's composite that is less than this number. A priority queue of pairs, ordered on the prime number's current "composite" value (e.g. for 7, it could be 14, 21, 28, etc) and paired with its prime value (e.g. 7) can determine if the next number is prime or composite, and it isn't as memory intensive nor wasteful as the naive sieve. Adding in things like a wheel makes it even better. You can read the paper for more, but it's pretty cool how you can simplify this algorithm.

PS: I think Mike "understood how [the] sieve of [E]rasthenes works" ;)
 
drleospaceman said:
Using lazy sequences, it will use significantly less memory. If you had understood how sieve of erastothenes works, I wouldn't have needed to say anything more. Why did I optimize for speed? For fun. I saw the connection and thought it was interesting.
Click to expand...

I understand how the sieve works; you hadn't made explicit your modification of the algorithm for the proposed application. It's easy to approach a problem by proclaiming that it's just the same as another problem. It's another matter, entirely, to describe a detailed and workable solution of that problem based on the original solution.

You might use less memory than a naive sieve implementation (busting rhymes, yo), but you'll never use less memory than the casual storage consumed by the looping implementation.

If you've actually implemented and timed code, I wonder why you haven't posted it.
 
Code: 
// add -Xmx1000m to runtime options to increase heap size
public class sieve
{
   public static void main(String[] args)
   {
      int[] arr = new int[100000000];

		long endTime;
      long startTime = System.nanoTime();

      for (int i = 1; i < 100000000; i++)
      {
      	if ((i % 3) == 0)
         {
         	if ((i % 5) == 0) { } // System.out.println("fizzbuzz");
            else { } // System.out.println("fizz"); 
         }
         else if ((i % 5) == 0) { } // System.out.println("buzz");
         else { } // System.out.println(i);
      }
      endTime = System.nanoTime();

      long duration = endTime - startTime;
      System.out.println(duration / 1000000000.00);

      startTime = System.nanoTime();

     	for (int i = 0; i < 100000000; i++)
      {
     		arr[i] = i + 1;
      }
      	
      int mult = 1;
      while ((3 * mult) < 100000000)
      {
      	arr[(3 * mult) - 1] = -1;
         mult += 1;
      }

      mult = 1;
      int fiveMult = 5 * mult; 
      while (fiveMult < 100000000)
      {
      	int value = arr[fiveMult - 1];
      	if (value == -1) arr[fiveMult - 1] = -3;
      	else arr[fiveMult - 1] = -2;
      	mult += 1;
      	fiveMult = 5 * mult;
      }
      for (int i = 1; i < 100000000; i++)
      {
         if (arr[i] == -1) { } // System.out.println("fizz");
         else if (arr[i] == -2) {} // System.out.println("buzz");
         else if (arr[i] == -3) { } // System.out.println("fizzbuzz");
         else { } // System.out.println(arr[i]);
      }
		endTime = System.nanoTime();

      duration = endTime - startTime;
      System.out.println(duration /1000000000.00);
   }
}
}
edit: Yes forgot to put the print in the timer, .34 now :( Still faster though.
 
Last edited:
You've also got the printing loop outside the timer. I guess you're not turning on optimizations, as the compiler should be able to inspect the loop you've got, find it does no externally visible actions, and eliminate it from the generated code.
 
You must log in or register to reply here.
Back
Top