New Topic/Question
Reply
Introduction
Optimization is an important part of software development, especially if the software is a game or some kind of scientific software which performs thousand or millions of calculations each second. In such application some method which is called all the time (path finding in a game or some formula in calculations) has to be fast. It might take only 100 ticks when called once so the optimization wouldn't be noticed but if it's called all the time, just reducing the time taken by 20 ticks might make your whole software few percents faster.
The Challenge
In this challenge you have to optimize a very basic method which is called ten thousand times. The method counts how many times one character appears in a string.
The only method you have to edit to give right results is CountCharactersOptimized(string str, char c). You are NOT allowed to change the signature of this method in any way, for example to (string str, string c). But you can edit the inside of the method any way you want. Create a loop, use string class methods, whatever it is that you desire.
Here is the code you can copy-paste into your Console application:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Optimization_Challenge_1
{
class Program
{
private static Random random = new Random();
static void Main(string[] args)
{
string str = GetRandomString(10000);
char c = GetRandomChar();
System.Diagnostics.Stopwatch st = new System.Diagnostics.Stopwatch();
st.Start();
for (int i = 0; i < 10000; i++) {
CountCharactersSlow(str, c);
}
st.Stop();
Console.WriteLine("CountSlow: " + CountCharactersSlow(str, c));
long elapsedSlow = st.ElapsedTicks;
Console.WriteLine("TimeSlow: " + elapsedSlow);
st.Restart();
for (int i = 0; i < 10000; i++) {
CountCharactersOptimized(str, c);
}
st.Stop();
Console.WriteLine("CountOptimized: " + CountCharactersOptimized(str, c));
long elapsedOptimized = st.ElapsedTicks;
Console.WriteLine("TimeOptimized: " + elapsedOptimized);
decimal difference = ((decimal)elapsedOptimized / (decimal)elapsedSlow);
if (difference > 1)
Console.WriteLine("CountCharactersOptimized is slower by " + (difference - 1).ToString("P"));
else
Console.WriteLine("CountCharactersOptimized is faster by " + (1 - difference).ToString("P"));
Console.ReadKey();
}
static string GetRandomString(int length)
{
string str = "";
for (int i = 0; i < length; i++)
str += (char)random.Next((int)'a', (int)'f');
return str;
}
static char GetRandomChar()
{
return (char)random.Next((int)'a', (int)'f');
}
static int CountCharactersSlow(string str, char c)
{
return str.Count(c1 => c1 == c);
}
static int CountCharactersOptimized(string str, char c)
{
//return str.Count(c1 => c1 == c);
}
}
}
Example run:
CountSlow: 2002 TimeSlow: 9091487 CountOptimized: 2002 TimeOptimized: 3893097 CountCharactersOptimized is faster by 57,18 %
As you can see in the Main method, the results will be in percentages. Milliseconds/Ticks wouldn't tell us enough because someone might have faster computer.
For testing you may reduce the number of calls or the length of the string because the Slow method takes about 9 seconds on my computer (which is slow like the method) when ran in debug mode.
Please don't use solution where you cache the answer and then just return the same answer
This might not be the case in real world application that the method is called with the same string every time.Rewards
The one who is able to reduce the time taken the most will be rewarded with the awesome "Optimization guru" title which you can include in your profile signature as text. However, no one will be telling you that you had the fastest time, you have to check it yourself in this thread.
Final words
Good luck and have fun optimizing. Creating 50% faster method might be easy. But don't stop there, try to be 80% or 90% faster!
Remember to use Spoiler and Code tags when posting code. But you can post the results outside of the code tags.
Feel free to post your unsuccessful solutions too.
MultiQuote
| 