|
First one is faster and because of internal smaller array.
run following code in VB:
Dim i, j As Integer
Dim strArr1(10000) As String
Dim strArr2(20) As String
For i = 0 To 10000
strArr1(i) = i & ""
Next
For i = 0 To 20
strArr2(i) = i * i * i & ""
Next
Response.Write(DateTime.Now.Millisecond.ToString())
For i = 0 To 10000
For j = 0 To 20
If (strArr1(i) = strArr2(j)) Then
Response.Write("
Hello" & strArr1(i) & strArr2(j))
End If
Next
Next
Response.Write(DateTime.Now.Millisecond.ToString())
For i = 0 To 20
For j = 0 To 10000
If (strArr2(i) = strArr1(j)) Then
Response.Write("
Hello " & strArr2(i) & strArr1(j))
End If
Next
Next
Response.Write(DateTime.Now.Millisecond.ToString())
Any systematic work reflects its significance for a long time. So let's discuss the best...
|
|
|
|
|
Yes: finally the best way to find out who is the faster is use ... the clock
Russell
|
|
|
|
|
Sure, measuring is good, smart measuring is even better.
if you have two alternatives that are likely to be almost equal, whichever you try first
will take longer, due to different starting conditions (maybe code needs to be JITted,
probably data needs to be loaded in memory and/or will be loaded in cache, etc).
Remedy: put everything in a for loop, and run a few passes; ignore the first pass,
take the average (or the best time!) of the remaining passes.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Thanks for reply.
rihdus wrote: First one is faster and because of internal smaller array.
can you please explain a bit more.
Best Regards,
Mushq
Mushtaque Ahmed Nizamani
Software Engineer
Ultimus Pakistan
|
|
|
|
|
clock_t start,end;
start=clock();
//your code snippet here
end=clock();
//observe start=end here.
hope you got the point.
|
|
|
|
|
If time is important you could almost certainly do better than either way. For example, instead doing a simple search 10000 times on a set of 20 things, spend a bit of time and either order them or hash them, so that the search that you have to do many times is much faster.
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."
|
|
|
|
|
Mushq wrote: for(i = 0; i < sizeoffirstset(10000); i++)
{
for (j=0; i < sizeofsecondset(20); j++)
{
if(set1[i] == set2[j])
//do some thing
}
}
another optimization:
for(i = 0; i < sizeoffirstset(10000); i++)
{
const double set1_i_ = set1[i];
for (j=0; j < sizeofsecondset(20); j++)
{
if(set1_i_ == set2[j])
}
}
In this way the program not needs to reload that value every time loooking into the array.
Hoping that the compiler is enough smart to better solution itself.
You can only check the time spend in every solutions and see who is the faster...
Important: do this time check in Release mode!!!
also look to the project features...I remember that there is some flags like smallest exe file dimension vs fastest run exe (that somethimes can be bigger)....but I don't remember the name of this flags.
Hope helps
Russell
|
|
|
|
|
_Russell_ wrote: Important: do this time check in Release mode!!!
Could you please explain a bit what the difference is?
Thanks.
|
|
|
|
|
The difference is that in DEBUG mode the code is compiled exactly as you write it and it isn't optimizated. For example, inline functions are not inline and macros like ASSERT are inserted in the application.
In RELEASE mode the code is optimized: inline functions will become inlined and ASSERTs are cutted from the code.
In this case the code is really faster and it does exactly what you want, without do any internal test.
Of course you have, first, to prepare the routines in DEBUG mode, to be sure that there isn't errors, but when you take the clock in your hand to see what algorithm is faster... then use the RELEASE mode.
You can find details on the differences between DEBUG mode and RELEASE mode into the documentation.
Russell
|
|
|
|
|
Both are same because the no. of iterations is same.
Best Regards,
Chetan Patel
|
|
|
|
|
1. A partition of a positive integer n is a sequence of positive integers that sum to n. Write an algorithm in psedocode and then implement the algorithm (in C) to print all non-increasing partitions of n.
eg. If n=4
4
3 1
2 2
2 1 1
1 1 1 1
|
|
|
|
|
convince me it's not homework!
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."
|
|
|
|
|
thank you , however at the moment i'm expecting suport
|
|
|
|
|
The best support and advice I can offer you is to try to tackle the question yourself. By struggling with problems, you develop problem solving skills, the solutions you discover or don't discover yourself are far more important than those you read here. Had you thought about this problem and had that flash of inspiration to use recursion, apart from the self-satisfaction it brings - you would probably have remembered it for a long time. Conversely, the elegance of the recursive approach would be blinding if you had spent a long time trying to solve it some other way.
Tip: If you are going to post your homework questions, at least remove the question number - it makes it too easy to spot.
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."
|
|
|
|
|
|
cp9876 wrote: at least remove the question number - it makes it too easy to spot
 And that was only the first problem, too. 
"Any sort of work in VB6 is bound to provide several WTF moments." - Christian Graus
|
|
|
|
|
prasadbuddhika wrote: however at the moment i'm expecting suport
Expect away, however the relevant variation of the old saying is sh*t in one hand and expect in the other and see which one fills up first.
Save an endangered species. The American Engineer.
|
|
|
|
|
You have only to write a simple recoursive function.
The input is the list of numbers.
it takes the first number on the right that is different from 1 (like N) and split it to (N-1 1), then you can end the function passing the new string to the function again (recursively).
Stop if the string contains only 1s.
prasadbuddhika wrote: 3 1
2 2
here happens something strange, ... so probally the rules are more complicated.
good luck
Russell
|
|
|
|
|
Anyone know how I can implement this in code?
Trying to synchronize data samples from two different hardware devices. One device is sampling around 10pt/s and the other device is sampling at 50pt/s. These samples are displayed on a graph in realtime.
|
|
|
|
|
I think you can simply 'decimate' (factor = 5) the second signal to have the same rate ... and then syncronize they. To do so you can use correlation on all the signal or in a small part of the signal(not in the case of big shifts) to correct little offsets.
If it is in real-time you can develop a dynamic-delay that shift one of the two signal to get the syncronization before to start to record. And of course it can work also during the recording to adjust the shift value.
It is a big chapter on signal processing.
Russell
|
|
|
|
|
I need an algorithm that returns the longest exact matching substring from two strings. For example, passing in the strings "abacadaba" and "dbaadabb" would return "adab". The best way that I can think of would be to construct a boolean table of size m by n, and check each character for a match and put a true value if they match and false if they don't. Then I could look along each diagonal for the largest consecutive set of true values. However, this algorithm takes O(n*m) memory, O(n*m) time to build the table, then O(n*m) time to look for the longest diagonal. There is definitely an algorithm that runs faster, but I cannot figure out what it is. I was wondering if anyone has a better idea as to how I can accomplish this task. Thanks
-- modified at 12:19 Wednesday 29th August, 2007
|
|
|
|
|
s1 vs s2
(s1 is the shorter)
It seems that the longest matcing string can be found comparing
* s1 inside s2
* then s1(0:end-1) vs s2
* then s1(0:end-2) vs s2
* ...
* Stop the research at the first match: it is the longer one
This could be quite slow if you compare two very long string (like 2 books ), but it don't need memory: only m+n (or 0 if you use pointers to the original strings)
Skippums wrote: Levenshtein table
It is also very slow
Russell
|
|
|
|
|
Doesn't that algorithm assume that s2 contains the start of the string s1? This is not actually the case. The longest substring could occur anywhere in either string. So for that algorithm to work, I would have to try s1, then s1 without the first character, then s1 without the second character, then s1 without the third character, etc. I think it would actually be faster (not really sure) to do it the way I proposed with the boolean table.
|
|
|
|
|
Hi,
I can offer a few ideas that may reduce the size of the problem:
1. remove in string1 all chars that don't occur in string2 and vice versa;
this process typically shortens the strings, and reduces the problem to a
larger number of much smaller problems.
In your example it replaces ("abacadaba", "dbaadabb")
by ("aba", "dbaadabb") and ("adaba", "dbaadabb") based on 'c'
and the first of these can be reduced further based on 'd'.
2. search for small patterns that occur in one and not in the other string.
Again in your example that would be "aa", allowing a further reduction (here
you can split in between the two a's).
3. Once you have sufficiently reduced you could consider your quadratic cost
approach.
4. but as an alternative you could do a kind of binary search on the match length:
- start with an arbitrary length, in the shorter string, select some substring
with that length, and try to find it in the other string. If you find one,
the match can only be that size or larger. If you don't find one, you could
try all other substrings or fall back to a smaller length.
It all depends on the kind of data you want to handle well. Your example is not
a real indication I guess.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
OK. I have thought about it some more, and have come up with the following solution:
Let lstr be the longer string and sstr be the shorter string...
First, I will build a dictionary with characters as keys and a singly linked list of integer indexes as the value, which will represent lstr. This table will take O(lstr.len) memory and O(lstr.len) time to build, but will be keyed in O(1) time.
Then I will make the following recursive function, which is sent the lookup table, the two strings, and an integer representing the longest string found thus far:
1. If the longest string found is longer than sstr sent in, return empty string.
2. Initialize result to be the empty string.
3. Choose character c from sstr to be the center character.
4. For each index in the dictionary for c, find the matching substring (match).
5. If match.len from (3) > result.len declared in (1), result = match. If more indexes occur for c in the dictionary, go back to (3)
6. If result.len > sstr.len / 2, return result.
Else
resultLow = recursively call this using sstr.substr(0, sstr.len / 2) and
resultHigh= recursively call this using sstr.substr(sstr.len / 2)
return the longest of (result, resultLow, resultHigh)
This will limit my searches so I don't have to waste my time comparing things that are already found. I think this algorithm will turn out to be O(lstr.len * log(lstr.len)). Any thoughts?
-- modified at 14:28 Wednesday 29th August, 2007
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
