|
These days, I'm almost insulted when I haven't been asked to do a coding test. And, I did have a job recently where the interview should have clued me in to the fact they didn't know what the hell was going on... worked there for two months - everybody was real smart and legit with their skills - but I only did one productive thing the whole time. I should have known something was hinky in the interview when they did zero actual assessment of my skills.
modified 18-Apr-13 17:41pm.
|
|
|
|
|
Jasmine2501 wrote: but I only did one productive thing the whole time.
That's when you start updating that resume again 
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
|
|
|
|
|
Oh heck yeah, I had another gig lined up before I quit from there. It's hard to stay unemployed if you have programming skills and you're being honest about it 
|
|
|
|
|
|
Something like:
sb.ToString().Split(' ').ToList().Distinct().Count()
That does (or should be close to) what your subject line wants to do.
But that's different from what you wrote:
kanamala subin wrote: i want to check the count of "hi" in the sb
so my final output would be like this.
Count is 2.
Which is "count the number of instances of a word", for which you could do something like this:
Dictionary<string, int> wordCount = new Dictionary<string,int>();
sb.ToString().Split(' ').ToList().ForEach(w=>
{
if (wordCount.ContainsKey(w) ++wordCountCount[w];
else wordCount[w]=1;
}
Marc
|
|
|
|
|
Hello,
me and a coworker had thought about optimzing the fibonacci calculation.
This is what we have ended up and is pretty fast. (It is fast enough, for our product, but we want to know what is possible)
private static ulong GetFib3(int n)
{
ulong a = 0;
ulong b = 1;
if (n == 0) return a;
if (n == 1) return b;
for (int i = 2; i <= n ; i++)
{
a ^= b;
b ^= a;
a ^= b;
b += a;
}
return b;
}
The method has following restrictions: Only up to n=200; n=201 result is bigger than ulong and no negative fibonaccis.
This method is actually pretty fast (20x faster than our first approach) and (as I think) it is well optimized.
My main question is: Is it possible to improve the execution speed even more? (I dont mean precalculating the values and then just access the values)
Regards,
Max
modified 18-Apr-13 8:58am.
|
|
|
|
|
Yes.
Precalculate the values. Since you are only working with 200 items, run your existing code to output the list of values into a text file, then add those values as an array:
private static ulong[] fibValues = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...};Then your routine is just a limit test and an array access.
The universe is composed of electrons, neutrons, protons and......morons. (ThePhantomUpvoter)
|
|
|
|
|
Ofcourse precalculating the values and then just accessing the array is fastest.
But I want to calculate it the fastest way...
|
|
|
|
|
That wasn't what you asked! 
The universe is composed of electrons, neutrons, protons and......morons. (ThePhantomUpvoter)
|
|
|
|
|
Thought it will be understood correctly. I edited the inital post.
But thanks for your efforts answering my question 
|
|
|
|
|
There is a formula:
Private Function Fibonacci(ByVal n As Integer) As Double
Return (1 / Math.Sqrt(5)) * ((1 + Math.Sqrt(5)) / 2) ^ n - (1 / Math.Sqrt(5)) * ((1 - Math.Sqrt(5)) / 2) ^ n
End Function
And it seems to do the trick, mening no tables
http://en.wikipedia.org/wiki/Fibonacci_number[^]
|
|
|
|
|
Yes, this implementation works great, BUT it is actually slower on my machine than my code I initially posted.
|
|
|
|
|
Whats the slowdown? if it is Sqrt that could be fixed, and if its the power function you could make that better too.
|
|
|
|
|
This is faster on my computer:
Private Function Fibonacci2(ByVal n As Integer) As Double
Dim gold As Double = 1.6180339887498949
Dim gold2 As Double = 0.6180339887498949
Dim sqrt1over5 As Double = 0.44721359549995793
Return sqrt1over5 * ((gold) ^ n - (gold2) ^ n)
End Function
|
|
|
|
|
My Results so far:
Link to screenshot
Last one is your Goldratio implementation (second fast), second from bottom is my last implementation (and fastest I found)...
I ran it one time (n=50), speed is always a bit different, but differences are accurate.
|
|
|
|
|
The one you posted in your question is that v1 or v2 in your picture? The version you posted in the question I cant run with when n = 60 or above.
|
|
|
|
|
It is the v2.
I can run it fine till 200, 201 would be too big for the ulong.
I see you code in vb.net, maybe there is a problem with datatypes?
|
|
|
|
|
The code looks like this:
Private Function GetFib3(ByVal n As Integer) As ULong
Dim a As Int64 = 0
Dim b As Int64 = 1
If (n = 0) Then Return a
If (n = 1) Then Return b
For i As UInt64 = 2 To n
a = a Xor b
b = b Xor a
a = a Xor b
b += a
Next
Return b
End Function
And it always gives me trouble with aretmetic overflow on the add part.
|
|
|
|
|
Kenneth Haugland wrote: Dim a As Int64 = 0
Dim b As Int64 = 1
Shouldn't those be ULong?
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
They should, but I get the same error anyways...
|
|
|
|
|
I've just tried this in LinqPad, and it works up to n = 93:
Private Function GetFib3(ByVal n As Integer) As ULong
Dim a As ULong = 0
Dim b As ULong = 1
If (n = 0) Then Return a
If (n = 1) Then Return b
For i As ULong = 2 To Convert.ToUInt64(n)
a = a Xor b
b = b Xor a
a = a Xor b
b += a
Next
Return b
End Function
The C# version is only working on higher numbers because it's using an unchecked context by default; the results for n = 94 or higher are wrong.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
None of my implementations work above n=70 regardless of what I do so I went for Numerics.BigInteger:
Private Function GetFib2(ByVal n As Integer) As Numerics.BigInteger
Dim a As New Numerics.BigInteger
a = 0
Dim b As New Numerics.BigInteger
b = 1
If (n = 0) Then Return a
If (n = 1) Then Return b
For i As UInt64 = 2 To n
a = a Xor b
b = b Xor a
a = a Xor b
b += a
Next
Return b
End Function
This is always correct, however it might be a little slower...
|
|
|
|
|
define a and b as uint64 too
|
|
|
|
|
Only for small N... the formula is faster for larger numbers. You won't see any advantage until you get to the larger numbers, and the point where it crosses over (formula becomes faster) will vary on different machines.
|
|
|
|
|
Here is the matrix-power version, it's asymptotically faster but probably not real-life faster because `n` is always low. Worth a try though
static ulong Fibonacci(uint n)
{
ulong m00 = 1, m01 = 1, m10 = 1, m11 = 0;
ulong x00 = 1, x01 = 1, x10 = 1, x11 = 0;
while (n != 0)
{
if ((n & 1) != 0)
{
ulong t00 = m00 * x00 + m01 * x10;
ulong t01 = m00 * x01 + m01 * x11;
ulong t10 = m10 * x00 + m11 * x10;
ulong t11 = m10 * x01 + m11 * x11;
x00 = t00;
x01 = t01;
x10 = t10;
x11 = t11;
}
ulong y00 = m00 * m00 + m01 * m10;
ulong y01 = m00 * m01 + m01 * m11;
ulong y10 = m10 * m00 + m11 * m10;
ulong y11 = m10 * m01 + m11 * m11;
m00 = y00;
m01 = y01;
m10 = y10;
m11 = y11;
n >>= 1;
}
return x01;
}
By the way, is that XOR-swap really faster than a normal swap?
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
