Re: [Haskell-cafe] how to make it faster ?
On Mar 24, 2010, at 6:01 PM, 国平张 wrote: Hi, I wrote a type program to compute fibonacci series, It certainly is possible to compute Fibonacci numbers as a type program, but what you wrote is not a type program, just plain old Haskell. if the max value is big, then it becomes very slow. like take 100 fib How can I make it faster :-) Don't do it that way. Each element of your list is computed independently, and each computation takes exponential time (and would in C or Java). There are well known ways to compute Fibonacci numbers in linear and logarithmic time (assuming integer operations are constant time, which of course isn't true for big enough integers). They work well in Haskell too. The simplest thing -in Haskell- is to make the list element computations share the work using lazy evaluation. fibs :: [Integer] fibs = 1 : 1 : [x+y | (x,y) - zip fibs (tail fibs)] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] how to make it faster ?
Hi, I wrote a type program to compute fibonacci series, if the max value is big, then it becomes very slow. like take 100 fib How can I make it faster :-) fibo 0 = 0 fibo 1 = 1 fibo (n+2) = (fibo n) + (fibo (n+1)) fib :: [Int] fib = [fibo i | i - [0..]] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How To Make It Faster?
Hi, I come up with the following solution for this spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How To Make It Faster?
Hi, I come up with the following solution for this easy spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How To Make It Faster?
Diego Souza dso...@bitforest.org writes: I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. The usual approach is to compile with profiling (ghc -prof -auto-all, don't forget to optimize!), and run with time profiling enabled (./my-program -my-options +RTS -p). You can then examine the resulting profiling output (my-program.prof) to identify hotspots, and try to improve them. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How To Make It Faster?
On Wed, Jun 10, 2009 at 10:11 AM, paravinic...@yahoo.com.br wrote: Hi, I come up with the following solution for this spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, My profiling-fu is rather weak, but I think about 40% of the time is spent on reading from stdin, about 17% on splitting that into lines and then words. Only about 10% is spent in arith_expression and 8% in the lambda you pass into forM. I don't have any suggestions for actually speeding it up, but profiling helps in concentrating your efforts. :-) /M -- Magnus Therning(OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
The challenge was the implement the modcount algorithm not to calculate primes per se. (see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html). -Alex- Donald Bruce Stewart wrote: alex: This implementation of calculating 1 primes (compiled with GHC -O2) is 25% slower than the naive python implementation. Shouldn't it be faster? Am I doing something obviously stupid? Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) That's super naive, and seems to be around 5x faster than the code you were trying. (So make sure you're doing the same thing as the python version) -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Thought perhaps the problem is that modcount is just a slower algorithm. ... nevermind. Thanks. -Alex- Alex Jacobson wrote: The challenge was the implement the modcount algorithm not to calculate primes per se. (see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html). -Alex- Donald Bruce Stewart wrote: alex: This implementation of calculating 1 primes (compiled with GHC -O2) is 25% slower than the naive python implementation. Shouldn't it be faster? Am I doing something obviously stupid? Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) That's super naive, and seems to be around 5x faster than the code you were trying. (So make sure you're doing the same thing as the python version) -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Alex: The challenge was the implement the modcount algorithm not to calculate primes per se. (see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html). Can you show us the Python code? Paulo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) I am unable to see how exactly this will run. Given that primes is an infinite list, and that when it reaches numbers say, as large as 1, it will have to keep track of all the numbers (essentially prime numbers, which is the answer), whose mutliples it has to remove! Say for eg: I give take 100 primes 2 : [ 3...] then 2:3:[4 ... ] It will *now* have to remove 4, 2:3:[5...] Then 2:3:5:[6 ...] Now. It has to remove 6, based on the fact that it was a multiple of 2 ... (or 3? Which one comes first?) This happens in a different order than what would be expected generally in a sieve :-) So, the question is, does this improve efficiency? -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
On 8/6/07, Vimal [EMAIL PROTECTED] wrote: I am unable to see how exactly this will run. Given that primes is an infinite list, and that when it reaches numbers say, as large as 1, it will have to keep track of all the numbers (essentially prime numbers, which is the answer), whose mutliples it has to remove! Say for eg: I give take 100 primes 2 : [ 3...] then 2:3:[4 ... ] It will *now* have to remove 4, 2:3:[5...] Then 2:3:5:[6 ...] Isn't it how it runs ? : 2: sieve [3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45, 47,49,... ] then 2:3:sieve [5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,... ] then 2:3:5:sieve [7,11,13,17,19,23,29,31,37,41,43,47,49,... ] then 2:3:5:7:sieve [11,13,17,19,23,29,31,37,41,43,47,... ] then 2:3:5:7:11:sieve [13,17,19,23,29,31,37,41,43,47,... ] etc... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Isn't it how it runs ? : 2: sieve [3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45, 47,49,... ] then 2:3:sieve [5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,... ] then 2:3:5:sieve [7,11,13,17,19,23,29,31,37,41,43,47,49,... ] then 2:3:5:7:sieve [11,13,17,19,23,29,31,37,41,43,47,... ] then 2:3:5:7:11:sieve [13,17,19,23,29,31,37,41,43,47,... ] etc... Well well, see how the values are requested for: print (take 1000 primes) So, after sieve completes its action, the first 1000 elements are taken. Since Haskell is lazy, it doesnt do beyond 1000. I would expect your argument to hold good for something like this: primes n = sieve (take n [2..]) sieve (p:xs) = p : sieve [x | x - xs, x `mod` p 0] print (primes 1000) -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
primes n = sieve (take n [2..]) sieve (p:xs) = p : sieve [x | x - xs, x `mod` p 0] print (primes 1000) -- Vimal But as we can see, this obviously doesn't *take* 1000 primes, :-) -- Vimal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Vimal wrote: Why not just: primes = sieve [2..] sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] main = print (take 1000 primes) I am unable to see how exactly this will run. Given that primes is an infinite list, and that when it reaches numbers say, as large as 1, it will have to keep track of all the numbers (essentially prime numbers, which is the answer), whose mutliples it has to remove! Say for eg: I give take 100 primes 2 : [ 3...] then 2:3:[4 ... ] It will *now* have to remove 4, 2:3:[5...] Then 2:3:5:[6 ...] Now. It has to remove 6, based on the fact that it was a multiple of 2 ... (or 3? Which one comes first?) This happens in a different order than what would be expected generally in a sieve :-) To get a grip on the order in which things are sieved, try the following little experiment (should also work for other sieves): The original sieve (p : xs) = p : sieve [x | x - xs, x `mod` p 0] is equivalent (by desugaring the list comprehension) to sieve (p : xs) = p : sieve (filter (\x - x `mod` p 0) xs) To see the non-primes as well, replace the filter with a map, where the result type is an Either, with Left for primes and Right for non-primes. To keep track of which modules have been tested for each given number, let the element type of the Either-alternatives be a pair consisting of the number and the list of checked modules. This gives: sieve (Left l@(p,_) : xs) = Left l : sieve (map (either (\(x,e) - (if x `mod` p 0 then Left else Right) (x,p:e)) Right) xs) sieve (r : xs) = r : sieve xs Now try: sieve [Left (i,[]) | i -[2..]] [Left (2,[]),Left (3,[2]),Right (4,[2]),Left (5,[3,2]),Right (6,[2]),Left (7,[5,3,2]),Right (8,[2]),Right (9,[3,2]),Right (10,[2]),Left (11,[7,5,3,2]),... The Left-entries are primes, the Right-entries are non-primes, and the second element of each pair shows against which modules the first pair element has been checked (in reverse order). Ciao, Janis. -- Dr. Janis Voigtlaender http://wwwtcs.inf.tu-dresden.de/~voigt/ mailto:[EMAIL PROTECTED] ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] how to make haskell faster than python at finding primes?
Paulo Tanimoto wrote:
The challenge was the implement the modcount algorithm not to calculate
primes per se.
(see e.g. http://jjinux.blogspot.com/2005/11/io-comparison.html).
Can you show us the Python code?
Note this is python for the naive, accumulate and do modulus version.
Not for modcount. See below for ocaml version of modcount.
Having slept a few hours, I still think the modcount version should be
faster than the naive version because you don't have to recalculate a
full modulues operator for each new value. You just increment and check
equality. So would love to get short fast haskell modcount.
-Alex-
---
#!/usr/bin/env python -OO
Find prime numbers. See usage() for more information.
Author: JJ Behrens
Date: Sun Dec 30 03:36:58 PST 2001
Copyright: (c) JJ Behrens
Description:
Find prime numbers. See usage() for more information. The algorithm used
to determine if a given number, n, is prime is to keep a list of prime
numbers, p's, less than n and check if any p is a factor of n.
import sys
Output usage information to the user.
mesg -- If this is not NULL, it will be output first as an error message.
def usage(mesg):
if mesg: sys.stderr.write(Error: %s\n % mesg)
sys.stderr.write(Usage: %s NUMBER_OF_PRIMES\n % sys.argv[0])
sys.stderr.write(Print out the first NUMBER_OF_PRIMES primes.\n)
if mesg: sys.exit(1)
else: sys.exit(0)
Output a prime number in a nice manner.
def printPrime(p): print p
Is numCurr prime?
primeRecList -- This is the list of primes less than num_curr.
def isPrime(numCurr, primeRecList):
for p in primeRecList:
if not numCurr % p: return 0
else: return 1
Print out the first numPrimes primes.
numPrimes must be positive, of course.
FIRST_PRIME = 2
def findPrimes(numPrimes):
numCurr = FIRST_PRIME - 1
primeRecList = []
while numPrimes 0:
numCurr += 1
if isPrime(numCurr, primeRecList):
numPrimes -= 1
printPrime(numCurr)
primeRecList.append(numCurr)
if len(sys.argv) != 2: usage(missing NUMBER_OF_PRIMES)
try:
numPrimes = int(sys.argv[1])
if numPrimes 1: raise ValueError
except ValueError: usage(NUMBER_OF_PRIMES must be a positive integer)
findPrimes(numPrimes)
(* Author: JJ Behrens
Date: Sun Nov 4 02:42:42 PST 2001
Copyright: (c) JJ Behrens
Description:
Find prime numbers. See usage() for more information. The algorithm
used to determine if a given number, n, is prime is to keep a list of
tuples (p, mc) where each p is a prime less than n and each mc is
n % p. If n is prime, then no mc is 0. The effeciency of this
algorithm is wholly determined by how efficiently one can maintain this
list. mc does not need to be recalculated using a full % operation
when moving from n to n + 1 (increment and then reset to 0 if mc = p).
Furthermore, another performance enhancement is to use lazy evaluation
of mc (i.e. collect multiple increments into one addition and one
modulo--this avoids a traversal of the entire list for values of n that
are easy to factor). As far as I know, I'm the inventor of this
algorithm. *)
(* We'll contain a list of [prime_rec]'s that replace the simple list of
primes that are used in simple algorithms.
[prime] This is the prime, as before.
[count] Given [n], [count] = [n] % [prime].
[updated] One way to keep [count] up to date is to update it for each
new [n]. However, this would traversing the entire list of
[prime_rec]'s for each new value of [n]. Hence, we'll only update
[count] each time that [prime] is considered as a possible factor
of [n]. When we do update [count], we'll set [updated] to [n].
E.g., if [count] has not been updated since [n1] and [n] is now [n2],
then [updated] will be [n1]. If [prime] is now considered as a
factor of [n2], then we'll set [updated] to [n2] and [count] to
[count] + [n2] - [n1] % [prime]. If [count] is now 0, [prime] is
indeed a factor of [n2].
*)
type prime_rec =
{ prime : int;
mutable count: int;
mutable updated: int }
(* Output usage information to the user. If [mesg] is provided, it will
be output first as an error message. *)
let usage ?(mesg = ) () =
if not (mesg = ) then Printf.fprintf stderr Error: %s\n mesg;
Printf.fprintf stderr Usage: %s NUMBER_OF_PRIMES\n Sys.argv.(0);
prerr_string Print out the first NUMBER_OF_PRIMES primes.\n;
if mesg = then exit 0 else exit 1
(* Output a prime number in a nice manner. *)
let print_prime p =
Printf.printf %d\n p
(* Find [numerator] % [divisor] quickly by assuming that [numerator] will
usually be less than [opt_tries] * [divisor]. Just leave [opt_tries]
to its default value unless you plan on doing some tuning. *)
let rec fast_mod ?(opt_tries = 2) numerator divisor =
match opt_tries with
0 - numerator mod divisor
| _ - begin
if numerator divisor then numerator
else fast_mod ~opt_tries:(opt_tries - 1)
