mensanator@[EMAIL PROTECTED]
wrote:
> ...access individual members of a tuple?
>
> This works, but is it right?
> let remainder a b =
> let rem (x,y) = y
There is already a built-in function call "snd" that extracts the second
element of a pair.
> rem (BigInt.divmod a b)
So this could be:
snd (BigInt.divmod a b)
> ...access individual members of a list?
>
> This also works, but appears horribly inefficient...
> > a;;
> val it : int list = [1; 2; 3; 4]
> > List.nth a 1;;
> val it : int = 2
As long as you're using a list, you can do no better.
> ...when used to iterate through the list
> let hailstone_function_parameters sv =
> let mutable list_sum = 0I
> let mutable list_cnt = 0I
> let mutable Z = 0I
> let mutable e = 0I
> let svl = (List.length sv) - 1
> for i = (svl) downto 0 do
> // slow (due to List.nth)
> list_sum <- list_sum + (List.nth sv i)
> // fast
> list_cnt <- list_cnt + 1I
> // REAL slow
> Z <- Z+((BigInt.pow 3I (BigInt.of_int i))*(BigInt.pow 2I e))
Actually that bit is fast.
> // slow
> e <- e + (List.nth sv (svl - i))
But this bit is really slow.
> done
> let X = BigInt.pow 2I list_sum
> let Y = BigInt.pow 3I list_cnt
> (X,Y,Z)
If that is too slow then use an array. Try something like:
let hailstone_function_parameters sv =
let sv = Array.of_list sv
let n = Array.length sv
let mutable z = 0I
let mutable e = 0I
for i = 0 to n - 1 do
z <- z + BigInt.pow 3I (BigInt.of_int i) * BigInt.pow 2I e
e <- e + sv.[n - 1 - i]
BigInt.pow 2I (Array.fold1_left ( + ) sv),
BigInt.pow 3I (Array.length sv |> BigInt.of_int),
z
Also, are you sure you need big ints here?
> I note List methods like .iter and .map but haven't quite
> figured out how to use them or if they are faster than
> List.nth.
Learn them: iter and map are O(n) wheras nth in a loop is O(n^2).
> And I'm not changing every item on the list or
> creating a new list, I'm creating a running sum based on
> list contents.
Then you want a fold, e.g. to compute ((1+2)+3)+4 = 10:
List.fold1_left ( + ) [1;2;3;4]
val it : int = 10
> Is a list even the right thing to use?
Not for your last function, no. You might consider using arrays
throughout.
Lists are great when you want to keep prepending elements.
> To creat the list, I was doing
> while (ccc>1I) do
> let fs = fell_swoop ccc
> ccc <- t_0 fs
> sv <- List.append sv [t_1 fs] // slow
That can be written:
sv @[EMAIL PROTECTED]
[t_1 fs]
Note that this iterates over the whole of sv.
> done
Without fell_swoop, t_0 and t_1, I can't tell what this is trying to
achieve.
You probably want a simple recursive function instead:
let rec create rsv ccc =
if ccc <= 1I then List.rev rsv else
let fs = fell_swoop ccc
create (t_1 fs :: rsv) (t_0 fs)
> But that's real slow also. OTOH,
> while (loop_point_found=0) do
> let fs = test_fell_swoop ccc
> ccc <- t_0 fs
> L <- L + 1
> test_sv <- (t_1 fs)::test_sv // fast
> if ccc=19I then
> (loop_point_found <- 1)
> printf "\n %d odd numbers found\n\n" L
> if L>124000 then (loop_point_found <- 1)
> done
>
> works fast (we're talking a couple seconds vs almost 9 minutes)
> although the list is constructed backwards. Luckily, List.rev
> seems quite fast.
Yes, List.rev is O(n). You've rediscovered that constructing lists in
reverse is very common in the ML family of languages, including F#. The
trade-off is that lists are very lightweight in these languages compared
to
the heavy doubly-linked mutable lists that you find in C++ and (probably)
C#.
> But is this the right way to build a list dynamically?
Lists in F# are fast for prepend only. So always prepend.
> Should I be using something else, like an array?
Possibly. See the article about data structures in the F#.NET Journal.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?u
|
