|
I’m posting this question after a conversation with one of my friends.
There are two algorithms that accomplish the same goal – search through XML file. These algorithms are developed by two different academic research groups. A friend of mine works in one of them, and she wants to compare the performance of the algorithms. The problem is that they are implemented in different languages: C++ and Java. Source codes for both are available. The question is – is there an experimental method for comparing the performance of these algorithms without having both of them implemented in the same language? What assumptions are safe to make?
Thanks,
- Nick
|
|
|
|
|
None. Unless the runtimes of the two algorithms are different (say, one is T(n) and the other is T(n*n)), you cannot say which is faster in any language or on any processor with certainty. You will need to either (1) find that the two algorithms have different asymptotic run times, or (2) run benchmarks comparing the two algorithms using different languages, processors, and input data. For the second option, at the end of the day all you can claim is that, "On ___ processor with ___ configuration, and ___ input data, using the ___ compiler (or the ___ runtime engine), the relative runtimes of the two algorithms was ___ and ___". Using this information, you can make certain generalizations with a high level of confidence, but unfortunately asymptotically equivalent algorithms cannot be compared with any level of certainty for all systems, or all compiler optimizations. Good luck,
Sounds like somebody's got a case of the Mondays
-Jeff
|
|
|
|
|
Does anyone know of a good algorithm for calculating minimum whole number ratios.
For instance:
800x600 would be 4x3
300x110 would be 30x11
250x150 would be 5x3
thanks in advance
|
|
|
|
|
Simply divide by the greatest common divisor (gcd)
800x600 gcd(800,600)=200 so you get 4x3 etc
You calculate gcd using Euclid's algorithm, Wikipedia article[^]
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hello everyone..
I am planning to design a timetable system for my 3rd year project. I would like to know what is the best algorithm to use for this. will be doing my system in C#, will also have a website using ASP.NET! I want a algorithm that is simple and easy to understand - nothing complex. i'm no einstein. 
|
|
|
|
|
That is a pretty broad post there. What ideas have you come up with?
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
|
|
|
|
|
Its going to be a timetable system that schedules timetables for maybe a university or highschool but right now am looking to base it for the university.. should be able to schedule in the venues - check if venue is big enough for the amount of students in that certain course\module. allocate resources to rooms(resources needed to carry out a lecture) assign lecturers to courses, check for clashes. from whatever information you put into the system - student, lecturer, rooms can have personalised timetable.. dont know if this helps!
someone suggested that i will need to use a scheduling\timetabling algorithm to be able to do this. am not sure.. 
|
|
|
|
|
Angel69 wrote: I am planning to design a timetable system for my 3rd year project. I would like to know what is the best algorithm to use for this.
Algorithm to do what? Work out how to put the timetable together? As I recall some research fellows at my University were attempting to work out the best algorithm when I was there 14 years ago. There results were a disaster. The department used their software and nobody liked the time tables it produced.
|
|
|
|
|
Afaik it might be NP-hard so bad luck there with the simple part.
As in you'll never get optimal result in a polinomial time so very fast your program will have to be running for months to get a full result.
|
|
|
|
|
that would be my concern as well. I have no way to prove it but making that sort of schedule seems reminiscent of the knapsack problem which is NP-Complete.
Otherwise [Microsoft is] toast in the long term no matter how much money they've got. They would be already if the Linux community didn't have it's head so firmly up it's own command line buffer that it looks like taking 15 years to find the desktop.
-- Matthew Faithfull
|
|
|
|
|
wrote: making that sort of schedule seems reminiscent of the knapsack problem which is NP-Complete.
I remember my Algorithms Analysis professor talk about this very thing.
"I guess it's what separates the professionals from the drag and drop, girly wirly, namby pamby, wishy washy, can't code for crap types." - Pete O'Hanlon
|
|
|
|
|
|
Hmmmm, interesting....
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
|
|
|
|
|
About Floyd's Cycle Detection,
It can only "detect" a loop in a Linked List right?
it can't tell where the loop exists...
The Only Solution i got to "fix Loops" in Linked list is O(n^2)
(involves creating a newlist, nodes are added if searching them in the new list fails...if node is found then adding prcedure stops..)
is there anything more effiecient?
Also Can Someone explain Brent's Algorithm (wiki confused me) 
modified 20-Oct-19 21:02pm.
|
|
|
|
|
Seriously?? No one can help me??
modified 20-Oct-19 21:02pm.
|
|
|
|
|
OK, I'll give it a shot. The basic algorithm moves two pointers through a linked list. One pointer takes single steps and the other takes double steps. If there's a cycle, the two pointers will eventually point to the same node. The algorithm doesn't tell where the loop is.
Here's my extension to Floyd's Algorithm. You mentioned O(n^2) so I assume time is more important to you than space.
1. Count the number of times the single-step pointer is advanced. When the loop is detected you know its length is definitely less than or equal to this counter.
2. When the loop is detected, you know the node both pointers reference is definitely in the loop. Save this pointer.
3. At this point create a hash table big enough to hold pointers to all nodes in the loop. (You can do this because the counter gives you an upper bound on the loop size.)
4. Continue chaining through the loop in single steps. Add each node pointer to the hash table. Compare each node pointer to the saved pointer. When you find a match, you know the whole loop is in the hash table.
5. Go back to the start of the list, and chain through it again, checking if each node pointer is in the hash table. When this happens, you've identified where the cycle begins.
Alternative: If you have a tiny loop at the end of a very very long linked list and you want to optimize space, after Step 2 go through the loop again and count the number of nodes in the loop. The hash table only has to hold this number of pointers, which is much smaller than the count from Step 1. (It will be a bit slower because you have to traverse the loop an extra time to count its length.)
The running time is O(n). We can call this the Floyd-Balkany Algorithm.
|
|
|
|
|
Hi,
if you have the memory for a big hash table, you probably can also add a single bool to each
node (call it "visited"); initialize at false, test for false and set true on each visit,
until a true is revisited. No need for two pointers, and certainly not O(n^2).
However, not reentrant.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
But then you have to carry the overhead for the extra bool throughout the whole use of the linked list, instead of a one-time test.
|
|
|
|
|
bools aren't that expensive nowadays; of course they don't generate revenue when compared
to a sophisticated algorithm that carries your name...
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
What if, we want to reinitialize the boolean (to false),we'll need to traverse the list (hence getting caught in the loop)....it's like a Catch-22 situation...
Also, as mentioned,we have a large overhead...
here's a page i found... http://ostermiller.org/find_loop_singly_linked_list.html discussing some Incorrect "Solutions" (including the Boolean Method)...
But, still no Brent's Algorithm?? eh?  
modified 20-Oct-19 21:02pm.
|
|
|
|
|
st0le wrote: if we want to reinitialize the boolean (to false),we'll need to traverse the list
if you need it more than once, use one of the following:
1. a collection that allows you to iterate all the nodes without following the normal links;
2. a generation number that increments every time you start a cycle test; it gets initialized
only once (at node creation time), and it gets compared and stored during a cycle test.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Making 'b' the subject
square root( ( b+1 ) / b )= a
We know the answer is
1/(a<sup>2</sup> - 1)
Our workings
Get rid of square
(b+1) / b = a<sup>2</sup>
Then - get rid of single b
b+1 = b.a<sup>2</sup>
Then the 1
b = (b.a<sup>2</sup>) - 1
then..... stuck. No idea.
we tried
(b / a<sup>2</sup> -1 ) = b which is as near as I got.
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
modified on Sunday, February 24, 2008 8:40 AM
|
|
|
|
|
|
Hi Malcolm,
Malcolm Smart wrote: My boys (not mine - honest!!)
Seems to me the difference is only a matter of time.
Malcolm Smart wrote: b+1 = b.a2
almost there. It is hard to believe you get stuck at this point.
Move all the terms containing b to one side, all other to the other and you get
b.a2 - b = 1
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Hi Luc! Had a sneeky feeling you might turn up.
Luc Pattyn wrote: Seems to me the difference is only a matter of time.
 Can't believe how much I've forgotten (or never knew!)
Luc Pattyn wrote: almost there. It is hard to believe you get stuck at this point.
Move all the terms containing b to one side, all other to the other and you get
b.a2 - b = 1
We've been here - we can't the get a2 - 1. You managed to tease an answer out me before regarding lemmings so I know you're not gonna give me the answer, but there is some obvious algebraic rule I am missing.
I need to get down to a single b on one side of the equation. If I take the a2 over to get 1/a2, I am left on the left hand side with b-b, which equals zero, so that seems wrong. We took the a2-b over, giving us b= 1/a2-b, which is very nearly there, except it should ne a2-1, not a2-b. (maths isn't my main thing - you can tell!)
My son is convinced the book is wrong - can you at least confirm
b = 1 / (a<sup>2</sup> - 1)
is correct?
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
