how to make a faster algorithm

roberto_santinni

Hey guys, please help? I'm trying to count each character's occurance in a text. This is what I have but if I am working with 20,000 chars it takes forever. How can I make it faster? (Especially the nested for loop) Thanks a lot! private void frequencyItem_Click(object sender, System.EventArgs e) { Form3 form3 = new Form3(); //creating new form that tells the user to please wait... form3.Show(); //displays the form3 cipherTxt.Text = ""; float numTimes = 0; //declaring and initializing numTimes which stores the number of times a char is presented //declaring and initializing my 72 char alphabet String myAlphabet = new String(new char[] {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','0','1','2','3','4','5','6','7','8','9','\u0027','\u002E','\u002C','\u003A','\u003B','\u003F','\u0021','\u0023','\u0028','\u0029'}); //nested for loop comparing every char in the alphabet to every char in the plaintext textbox for(int i=0;i0) //if number of times a char's ocurrence is presented { //print in ciphertext textbox the result of percentages cipherTxt.Text += "Letter " + myAlphabet[i] + " is displayed " + numTimes + " times. It is " + (numTimes/plainTxt.Text.Length)*100 + "% of the whole text." + System.Environment.NewLine; } numTimes = 0; //return the current alphabet's char count to 0 } string frequencyLetters = cipherTxt.Text; //pass results to a string cipherTxt.Text = ""; //clear ciphertext textbox form3.Close(); //closes the waiting form... try //tries following block of code if user selects Cancel on save box { saveFileDialog.ShowDialog(); //show the save dialog String saveFileName = saveFileDialog.FileName; //store output filename as string TextWriter textOut = new StreamWriter(saveFileName); //new streamwriter to filename textOut.WriteLine(frequencyLetters); //writing results to file textOut.Close(); //closing streamwriter } catch(Exception arg) //catches exception { return; //exits void function } } Santinni

ejuanpp

Why don't you try converting your char values to indexes ? ie: int[] frequence = new int[ushort.MaxValue]; for (int i = 0; i < s.Length; i++) { frequence[(ushort)s[i]]++; } regards

toxcct

roberto_santinni wrote:

how to make a faster algorithm

at the beginning of your code, have you tried to write this :

while (!fastEnough()) {
accelerate();
}

ok ok, i leave :rolleyes:

You don't know where to start ? ask a good friend

[VisualCalc 3.0][Flags Beginner's Guide]

Haoman17

you need to: 1. use loop unroling 2. use openmp if you have dual core processor (write openmp in google) 3. use intell tbb - on intel site 4. use lookup tables

peterchen

loop unrolling rarely changes anything on todays compilers/architectures. Multithreading will help, but not as much as picking a better algorithm (as said in the first article).

We are a big screwed up dysfunctional psychotic happy family - some more screwed up, others more happy, but everybody's psychotic joint venture definition of CP
Linkify! || Fold With Us! || sighist

Rob Graham

That algoritm is pretty poor, however, one simple optimization that will roughly double its speed would be

for(int j=0;j

Haoman17

Im sorry, but you are wrong. in many of my programs, i really saw a different. btw, you can use the optimization switch in VS2005, it also does a great job.

Xint0

How about using a hash-table for the counters and forget about the nested loops. Assuming you are doing this with .NET 2.0, here's my take on this:

private string DoCount(string input)
{
    string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ01234567890\u0027\u002E\u002C\u003A\u003B\u003F\u0021\u0023\u0028\u0029";
// create hash-table for counters, set initial capacity to number of counters (characters in alphabet).
    Dictionary counters = new Dictionary(alphabet.Length); 
//initialize just to be safe:
    foreach(char c in alphabet)
        counters[c] = 0;
//count the characters in the input string:
    foreach(char c in input)
        if(counters.ContainsKey(c))
            counters[c]++;
//now output statistics
    string output = string.Empty;
    for (int i = 0; i < alphabet.Length; i++)
    {
        flost percent = 0.0F;
        char c = alphabet[i];
        int count = counters[c];
        if(count > 0)
             percent = (float)count / input.Length;
        output += string.Format("Letter {0} is displayed {1} times.  It is {2:P2} of the whole text.{3}", c, count, percent, Environment.NewLine);
    }
    return output;
}

Hope it works for you. :-D -- modified at 22:56 Thursday 26th October, 2006

- Xint0 :cool: