6 Replies - 514 Views - Last Post: 08 May 2013 - 01:10 PM Rate Topic: -----

#1 ghqwerty  Icon User is offline

  • if($spareTime > 0){ $this->writeCode(); }
  • member icon

Reputation: 43
  • View blog
  • Posts: 903
  • Joined: 08-August 08

Optimising algorithm issue

Posted 02 December 2011 - 11:35 AM

I'm trying to optimise a simple algorithm i have for one of the project euler questions.

the question can be found here
Problem 14


using the following code, a brute force attempt, it executes in approx 3.4 seconds
Function problem14() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
        Dim startTime As DateTime = DateTime.Now()
        Dim longestChain As Integer = 0
        Dim longestStart As Integer = 0
        Dim maxValue As Integer = 1000000
        Dim currNum As Int64
        Dim currChain As Integer
        For x = 500001 To maxValue
            currNum = x
            currChain = 0
            While currNum <> 1
                If currNum Mod 2 = 0 Then
                    currNum /= 2
                Else
                    currNum = (3 * currNum) + 1
                End If
                currChain += 1
            End While
            currChain += 1
            If currChain > longestChain Then
                longestChain = currChain
                longestStart = x
            End If
        Next


        Dim Timespan As TimeSpan = DateTime.Now() - startTime
        Return longestStart & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms."
    End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)


In an attempt to optimise it i wanted to create a table of any values i come across. That way if you follow the pattern and get to a number you have already come across you already know the chain length for that number and can simply add it on the the currChain length and stop looping that number. in theory it should be quicker.
However the following runs in approx 8.5 seconds.

Perhaps i am looking at it the wrong way or simply performing the checks on the hashtable takes longer than iterating the required number of times but could someone please explain the problem?


'optimised' code
Function problem14() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
        Dim startTime As DateTime = DateTime.Now()
        Dim longestChain As Integer = 0
        Dim longestStart As Integer = 0
        Dim maxValue As Integer = 1000000
        Dim cache As New Hashtable

        Dim currNum As int64
        Dim currChain As Integer
        For x = 500001 To maxValue
            currNum = x
            currChain = 0
            While currNum <> 1
                If currNum Mod 2 = 0 Then
                    currNum /= 2
                    If cache.ContainsKey(currNum) Then
                        currChain += cache.Item(currNum) - 1
                        currNum = 1
                    End If
                Else
                    currNum = (3 * currNum) + 1
                    If cache.ContainsKey(currNum) Then
                        currChain += cache.Item(currNum) - 1
                        currNum = 1
                    End If
                End If
                currChain += 1
            End While
            currChain += 1
            cache.Add(x, currChain)
            If currChain > longestChain Then
                longestChain = currChain
                longestStart = x
            End If
        Next


        Dim Timespan As TimeSpan = DateTime.Now() - startTime
        Return longestStart & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms."
    End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)


Thankyou

This post has been edited by ghqwerty: 02 December 2011 - 11:38 AM


Is This A Good Question/Topic? 1
  • +

Replies To: Optimising algorithm issue

#2 trevster344  Icon User is offline

  • The Peasant
  • member icon

Reputation: 224
  • View blog
  • Posts: 1,511
  • Joined: 16-March 11

Re: Optimising algorithm issue

Posted 02 December 2011 - 06:51 PM

You want to store every value that comes up into a table? Why a hash table? I'm sorry if I missed what you meant. Just declare a new variable, and store the value of your expression, and every time your code runs through those expressions add a new value.
Was This Post Helpful? 0
  • +
  • -

#3 ghqwerty  Icon User is offline

  • if($spareTime > 0){ $this->writeCode(); }
  • member icon

Reputation: 43
  • View blog
  • Posts: 903
  • Joined: 08-August 08

Re: Optimising algorithm issue

Posted 03 December 2011 - 03:52 AM

Thanks for replying,

I am sill very new to VB.NET and before that I only knew php, so there are a lot of concepts I don't fully understand. In the forum for this question on ProjectEuler, i noticed people talking about a 'hashtable' to store the values and when googling hashtables for VB.NET I discovered the 'hashtable' datatype/array/function/object (not even 100% sure what it is)and simply assumed they were the same thing, I guess I was wrong for that assumption.


I think i am misunderstanding you, or visa versa, but considering this is looping 500 thousand times surely I don't want to be adding a new variable each time ?

How do you mean?
Was This Post Helpful? 0
  • +
  • -

#4 trevster344  Icon User is offline

  • The Peasant
  • member icon

Reputation: 224
  • View blog
  • Posts: 1,511
  • Joined: 16-March 11

Re: Optimising algorithm issue

Posted 03 December 2011 - 09:48 AM

Well you can put these values in anything, doesn't have to be a hashtable. I was just curious why you were doing that. ;) In your code where you check if the value is odd, or even add the number that is returned for the equation(didn't mean expression sorry to confuse you) and input it into your table, or whatever you want to put the value into. You'll only be putting the value into a single variable.
Was This Post Helpful? 0
  • +
  • -

#5 ghqwerty  Icon User is offline

  • if($spareTime > 0){ $this->writeCode(); }
  • member icon

Reputation: 43
  • View blog
  • Posts: 903
  • Joined: 08-August 08

Re: Optimising algorithm issue

Posted 03 December 2011 - 10:31 AM

Sorry, either i'm just having a complete mental block in understanding what you mean (which is likely given the amount of school work i have been doing recently, leaving me brain-dead in the evenings), or you've interpretted what i want done wrong (both being my fault :P).

I can't add it to a single variable there because i need to know 2 values - the number + the chain length after that point.

Both for your benefit and mine i will outline the pseudo process so that you know what i mean, and it is clear what i want to do.


Quote

for example you are given the following chain as an example in the question

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

so to speed things up when i iterate through the values starting from 1 i want to add the chain length each value generated in a table. so by the time we get to 13 in the iteration we will have the chain lengths for each number 1-13

just looking at the example chain we can see

starting value => chain length
1 => 1
2 => 2
3 unknown
4 => 3
5 => 6
6 unknown
7 unknown
8 => 4
9 unknown
10 => 7
11 unknown
12 unknown

now we can use these values to reduce the amount of iterations necesary.
when calculating 13
chain length = 0
is it in the table -> no -> perform operation -> 40 chain length = 1
40 -> is it in the table -> no -> perform operation -> 20 chain length = 2
20 -> is it in the table -> no -> perform operation -> 10 chain length = 3
10 -> is it in the table -> yes -> add the corresponding value to the chain length and stop looping.
add 13 => *the resulted chain length from the previous process* to the table and start 14.



Hopefully this makes more sense ?
Was This Post Helpful? 0
  • +
  • -

#6 trevster344  Icon User is offline

  • The Peasant
  • member icon

Reputation: 224
  • View blog
  • Posts: 1,511
  • Joined: 16-March 11

Re: Optimising algorithm issue

Posted 03 December 2011 - 02:35 PM

I'm sorry today I'm just not able to follow along on what exactly the chain is, maybe someone else can give ya a hand but it's as they say going in one ear, and out the other lol.
Was This Post Helpful? 0
  • +
  • -

#7 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Optimising algorithm issue

Posted 08 May 2013 - 01:10 PM

First, allow me to thank you for the link to Project Euler. Those are some very interesting problems.

I played around with Problem 14, and used an array to store the chain lengths already figured out. It's a pretty big array, but it sure speeds up the processing. Isn't it always the case? Trade speed for size.

Anyway, I cheated a bit on the array. I made it an array of Int16, because I had foreknowledge of the longest chain, so the array would be even bigger if we increased the maximum number to test.

A few comments on the code...

Since we know that the only way for the sequence to end in a 1, is for it to land on a power of 2, I decided to prefill the array with the chain lengths starting at every power of 2, up to the maximum power of two less than 1000000. I included this prefilling in the time taken, though t's minuscule.

There was no need to check the cache twice (once in the even numbered, and once in the odd numbered currNums).

I added "Iterations Saved" to the label output in order track the number of chain amounts found in the cache(), and thus, the number of times we would have gone through the loop otherwise).

I also changed the For loop to go from 1 to 1,000,000, which better showed the speed differences.

Anyway, here's the code. I had a lot of fun doing it, and I thank you for that, too.

    Function problem14Cache2() As String ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)
        Dim startTime As DateTime = DateTime.Now()

        Dim n As Integer = 1
        Dim count As Integer = 1
        Dim cache(1000000) As Int16
        Do Until n > 1000000
            cache(n) = CShort(count)
            count += 1
            n *= 2
        Loop

        Dim longestChain As Integer = 0
        Dim longestStart As Integer = 0
        Dim iterationsSaved As Int64 = 0
        Dim maxValue As Integer = 1000000

        Dim currNum As Int64
        Dim currChain As Integer
        'For x = 500001 To maxValue
        For x = 1 To maxValue
            currNum = x
            currChain = 0
            While currNum <> 1
                If currNum < 1000001 Then
                    If cache(CInt(currNum)) > 0 Then
                        iterationsSaved += CInt(cache(CInt(currNum)))
                        currChain += CInt(cache(CInt(currNum)))
                        currNum = 1
                    End If
                End If
                If currNum > 1 Then
                    If currNum Mod 2 = 0 Then
                        currNum = CLng(currNum / 2)
                    Else
                        currNum = (3 * currNum) + 1
                    End If
                    currChain += 1
                End If
            End While
            cache(x) = CShort(currChain)
            If currChain > longestChain Then
                longestChain = currChain
                longestStart = x
            End If
        Next

        Dim Timespan As TimeSpan = DateTime.Now() - startTime
        Return longestStart & vbCrLf & longestChain & vbCrLf & "Iterations Saved: " & iterationsSaved & vbCrLf & "Execution time: " & Timespan.Seconds() & "s " & Timespan.Milliseconds() & "ms."
    End Function ' Which starting number, under one million, produces the longest chain? (Even, odd => n=n/2, n=3n+1)


Here are my results for the three methods:

Attached image(s)

  • Attached Image

This post has been edited by lar3ry: 08 May 2013 - 01:11 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1