|
Benchmarking is not to determine algorithmic complexity.
It can be used to confirm that your theoretically determined O() is correct, but a few timing values is not an O().
To the OP: In my studies, algorithmic complexity was the sole subject of a quarter-long course. The textbook was a few hundred pages long. I don't remember if I took it during our junior or senior year; in any case, we were quite experienced programmers then, and had completed courses in related subjects like statistics and queue theory. The foundation was in place.
If you want to learn how to determine the algorithmic complexity in general, you may have a long path to walk. There may be quick and easy answers to specific, simple, algorithms (an experienced guy can pop an O() right out of his head for the examples you present), but you would benefit from learning more general methods for complexity estimation.
And: If you are doing timing benchmarks, make sure to test over a broad range of input - here: in terms of problem size. With small problem sets, initial setup, reporting etc. can make up a large part of the time consumed. Also, be very much aware of compiler optimizations. Some compilers are clever shortcutting loops etc. in a way that may severely affect timings. It may be safer to turn all optimization off. (Actually, for verifying a theoretical O(), you might come better out by adding counters to your code in appropriate places, rather than measuring execution times!)
|
|
|
|
|
Why are you telling me this? You need to reply to the OP.
|
|
|
|
|
because you seem to suggest to the OP that "coding the two algorithms and running some tests" can serve as a replacement for an analytic complexity determination.
Besides: What is posted in a public forum is not directed at you alone, but to all readers of the forum.
|
|
|
|
|
All I said was, "You could answer the question yourself by coding the two algorithms and running some tests.". I left it up to the OP to decide if that was what he wanted. But either way, it is unlikely that OP will read your message, so missing some useful information.
|
|
|
|
|
Member 11512486 wrote: Could you please help with that? It would be beneficial for me and very much appreciable.
Sure! Hope the below would help.
Start by learning about complexity: Understanding Time Complexity with Simple Examples - GeeksforGeeks
Then, have a look at something like: How to analyze time complexity: Count your steps · YourBasic
There are many more material online in case you need more info to understand what it means and helps.
Overall,
1. code a sample doing same problemX using algorithm 1 & 2
2. compare the time taken for both to solve that problem with multiple set of inputs (increasing)
3. you can also compare the space used by both and use as another comparing parameter
Try out!
|
|
|
|
|
Thank you for your response. I have executed both algorithm and get second algorithm taken less time. But need to prove by equation. I hope you are expert but I am not. So if you help me that would be very helpful for me.
|
|
|
|
|
The second one has an "if ... for".
As for the rest, they have a deterministic number of iterations. Count iterations, then assume the second can be faster because of the "if ... for" (depending on the counts).
 
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
How can you state as a general conclusion that "the second algorithm takes less time"?
Execution times depend on, for algorithm 1, four different input variables (m, n, x, y), and the outcome of four different if-tests, so you may consider p(if-1) .. p(if-4) four additional input variables. Total execution time depends heavily on the resources (mainly CPU) required for evaluating the four different conditions, and for the seven different actions. The execution counts for six of the actions depend on two or three input variables.
Algorithm 2 has three input variables (m, n, x) and five tests so p(if-1) .. p(if-5) are input variables. Timing depend on five different evaluation times, seven different actions execution times. Here, too, execution counts for six of seven actions, and two conditions, depend on two or three input variables.
An algorithm, as such, is independent of both implementation and the context where it is applied; each step may have an arbitrary interpretation. (The pseudocode description reflects this.) So, e.g. performing another loop iteration may involve a lot more than just incrementing an integer variable and perform a conditional jump back to the top; it could take a lot work to get hold of the next element. So, the loop management itself might be the dominating cost, measured time might be practically independent on all the 'if()' and 'do something'.
Total execution times depend heavily on the relative cost of evaluating an 'if()' vs. an action ('do something'). Say, an 'if()' searching a candidate photo for similar ones in a photo archive (a very heavy test), the action simply logs the outcome (very lightweight) - then the number of tests greatly dominate the execution time, almost independent of p(if) probabilities. Or rather: If a test is super-cheap, like looking up the photo's serial number in a list, but the action is like compressing the image, then test outcomes (determined by p(if)) strongly affect execution times.
All of this affects benchmark timings, but only them. No matter how dramatic the effects on the timings if you apply the same algorithm in another context - or even port the same program code to another platform with significantly different relative costs: O() is unaffected by relative costs of loop management, tests and actions.
Given these considerations, how can we make any reliable statements about algorithm complexity based on execution times measurement measured with a (usually very small) set of combinations of eight explicit input values and a bunch of hidden ones (the relative costs of test/action execution)? Can you claim that algorithm 2 is faster than algorithm 1 for any combination of input variables? Even when considering that y affects algorithm 1 but not algorithm 2? Even when algorithm 1 depends on four different p(if), algorithm 2 on five?
If you give me the freedom to set arbitrary cost values (in terms of CPU execution times) for all actions and if() tests, to freely set values for m, n, x and y, and p(if) values, I am quite certain that I could make algorithm 2 significantly slower for given values, but faster for others.
Execution times "all depends"! If you set up an O() expression in the input variables, you can, for a given set of input values, estimate (relative) expected execution time for the alternatives.
Usually, you simplify the O()-expression, leaving out e.g. constant parts (like step 4 / step 2, independent of input values). If you know that e.g. if tests will always be super-simple, you may leave them out - but you should make that explicit in your presentation of the complexity. It is sort of customary to give O() only by the highest order subexpression(s) (such as m*m*x in algorithm 2, disregarding all p(if)) - but as a main rule, that restricts you complexity analysis to non-extreme values of those parts you have shaven off. If you know the application area, you will usually know the expected range of variation of each value, so you e.g. chop off the x if it varies from 1 to 3 but not if it varies from zero to a billion.
In any case: Benchmarks generally covers only a tiny little selection of possible explicit inputs (in particular in an 8-dimentional input space!). Usually, they are based on a large number of hidden (usually unidentified) factors affecting the results. For a specific application of the algorithm, in a specific implementation environment, and with a limited value range for all inputs, the benchmarks may give an indication of expected execution time. But they cannot provide anything comparable to an analytic derived expression for the complexity.
|
|
|
|
|
You're over-thinking it: it's a thought experiment.
One assumes all the "if's" and "do somethings" are equivalent. It's the "complexity" (looping and branching) that one is interested in; not a bunch of "yeah buts".
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Hi all, i tried to implement the Sieve of Eratosthenes for finding all primes under a given number n.
I came up with the this solution, and i think its kind of neat. But when i run it, it is many times slower than the standard solution i found on the net afterwards.
Can someone explain to me, why my solution is slower:
public static List<Integer> sieveEratosthenes(List<Integer> numbers){
int baseNum = 0;
while(baseNum < Math.sqrt(numbers.size())){
for(int i = 1; i < numbers.size()-baseNum; i++){
if(numbers.get(baseNum+i) % numbers.get(baseNum) == 0)
{
numbers.remove(baseNum+i);
}
}
baseNum++;
}
System.out.println("Calcs: "+calc);
return numbers;
}
|
|
|
|
|
while(baseNum < Math.sqrt(numbers.size())){
You are calculating the square root each time round the loop. Change it to:
int root = Math.sqrt(numbers.size());
while(baseNum < root){
Also, make sure your list only contains odd numbers. Or even faster use a fixed size array.
|
|
|
|
|
I suspect it's also going to be incorrect, since numbers.size() will potentially change on each iteration. 
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
It's slow because you're using a List instead of an array.
Every time you remove an entry from the List, the remaining values in the list after the item removed have to be moved down one position. Depending on the size of the List, that can take quite a bit of time.
Use an array of flags instead of integers.
|
|
|
|
|
Question:
I always thought .NET Lists were implemented as linked lists. After all, what would differentiate them from arrays?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Nope. Internally, it's an array. You can see it in the reference source: Reference Source - List<t>[^]
What differs it from a normal array is just managing the array size and making it easy to add/remove items to the array. If the array gets too full, it automatically creates a new, larger array and copies the items over to it.
|
|
|
|
|
Member 14932873 wrote: Can someone explain to me, why my solution is slower:
Your code is slow because it seems your code combine all the worst choices.
- you are continuously resizing the list, it is very time expensive.
Use an array allocated once.
- you are checking if a number is multiple with a modulo, it is very expensive too.
When you check for a prime, start from the prime and add repeatedly the prime to scan all multiples.
Speed of operations: fast to slow
Addition, subtraction < multiplication, squaring < division, modulo, square root
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
I'm building a language learning website. In one of the exercises the user has to guess the missing words. For example in the sentence:
What is the weather like? It is sunny today.
My developer has created an algorithm that shows the first and last words of the sentence, while removing the alternate words within it. The result is:
What ____ the ____ like? ____ is ____ today.
However, in a sentence like this:
It is not the entrance, it is the exit.
My developer says that the algorithm does not work because the word "the" is repeated.
I don't understand why the algorithm does not work when words are repeated. They still appear in alternate position, right?
Is there a solution? I could post our current algorithm if necessary.
|
|
|
|
|
It doesn't work because the last sample has an "even" number of words. The "last word" would have to be the last 2 words (due to "alternating"). Nothing to do with "the".
This adds the "last 2 words" if the word count is even.
string sentence = "It is not the entrance, it is the other exit.";
var words = sentence.Split( new char[] { ',', '.', ' ' }, StringSplitOptions.RemoveEmptyEntries );
List<string> selected = new List<string>();
for ( int i = 0; i < words.Length; i++ ) {
if ( ( i + 1 ) % 2 > 0 ) {
selected.Add( words[ i ] );
}
}
if ( words.Length > 1 && words.Length % 2 == 0 ) {
selected.Add( words.Last() );
}
string result = string.Join( " ", selected );
Console.WriteLine( sentence );
Console.WriteLine( result );
Console.ReadKey();
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
modified 6-Sep-20 12:46pm.
|
|
|
|
|
Gerry Schmitz wrote: the last sample has an "even" number of words
Really, 9 is even?
|
|
|
|
|
It's either odd or even that doesn't work. It's early.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
maicart wrote: My developer says that the algorithm does not work because the word "the" is repeated.
I think you should ask him to explain.
|
|
|
|
|
I'll talk to him tomorrow. If he does not solve the issue I will paste the algorithm in this thread in case you could help us.
|
|
|
|
|
I cannot think what could be difficult in a piece of code to remove alternate words from a sentence.
|
|
|
|
|
I suspect it is homework.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I just talked to my developer. Actually, there are 2 rules:
1st rule: In case of an odd number of words, the system will show the first and last word and will remove alternate words in the middle. Example:
A pear and an apple.
After the algorithm, the system will show:
A _____ and _____ apple.
2nd rule: In the case of an even number of words, the system will also show the first and last word and will randomly remove any of the alternate clues. Example:
How are you today?
After the algorithm, the result could be rendered either a) or b)
a) How _____ you today?
b) How are _____ today?
My developer sent me a PHP file with a clarification. Here's the link:
ClueAlgo.php - Google Drive[^]
I would appreciate your help if this is a quick fix. If it takes time this could be a paid job, for example on Fiverr.com
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
