how to make a faster algorithm
-
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 -
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 } }SantinniHow 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:
-
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:
thanks: https://movied.org
-
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.
thanks: https://movied.org
-
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! || sighistthanks: https://movied.org
-
That algoritm is pretty poor, however, one simple optimization that will roughly double its speed would be
for(int j=0;j
thanks: https://movied.org
-
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
thanks: https://movied.org
-
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 } }Santinnithanks: https://movied.org
-
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
thanks: https://movied.org
-
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
thanks: https://movied.org