Haskell的网站介绍了一个非常有吸引力的5行快速排序功能,如下所示.
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
它们还包括"C中的真正快速排序".
// To sort array a[] of size n: qsort(a,0,n-1)
void qsort(int a[], int lo, int hi)
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l …只是为了澄清,这不是一个功课问题:)
我想找到我正在建造的数学应用程序的素数并且遇到了Eratosthenes的Sieve方法.
我用Python编写了它的实现.但它非常慢.比方说,如果我想找到不到200万的所有素数.大约需要20分钟.(此时我停了下来).我怎样才能加快速度呢？
def primes_sieve(limit):
limitn = limit+1
primes = range(2, limitn)
for i in primes:
factors = range(i, limitn, i)
for f in factors[1:]:
if f in primes:
primes.remove(f)
return primes
print primes_sieve(2000)
更新: 我最终对这段代码进行了分析,发现花了很多时间从列表中删除一个元素.考虑到它必须遍历整个列表(最坏情况)才能找到元素然后将其删除然后重新调整列表(可能还有一些副本继续？),这是相当容易理解的.无论如何,我把字典列表删掉了.我的新实施 -
def primes_sieve1(limit):
limitn = limit+1
primes = dict()
for i in range(2, limitn): primes[i] = True
for i in primes:
factors = range(i,limitn, i)
for f in factors[1:]:
primes[f] = False
return [i for i in primes if primes[i]==True]
print primes_sieve1(2000000)
这不是作业,我只是好奇.
INFINITE是这里的关键词.
我希望在primes()中使用它作为p.我相信这是Haskell中的内置函数.
所以,答案不能像"Just do a Sieve"那样天真.
首先,您不知道将消耗多少连续素数.好吧,假设你可以一次编制100个.您是否会使用相同的Sieve方法以及素数公式的频率？
我更喜欢非并发方法.
感谢您阅读(和写作;))!
我一直在努力解决Clojure中的Project Euler问题,以便变得更好,而且我已经遇到了几次素数.我的问题是它只是花了太长时间.我希望有人可以帮我找到一种以Clojure-y方式做到这一点的有效方法.
当我拳头做到这一点时,我粗暴地强迫它.这很容易做到.但是计算10001个素数在Xeon 2.33GHz上用了2分钟,对规则来说太长了,一般来说太长了.这是算法:
(defn next-prime-slow
"Find the next prime number, checking against our already existing list"
([sofar guess]
(if (not-any? #(zero? (mod guess %)) sofar)
guess ; Then we have a prime
(recur sofar (+ guess 2))))) ; Try again
(defn find-primes-slow
"Finds prime numbers, slowly"
([]
(find-primes-slow 10001 [2 3])) ; How many we need, initial prime seeds
([needed sofar]
(if (<= needed (count sofar))
sofar ; Found enough, we're done
(recur needed (concat sofar [(next-prime-slow …请问有人请告诉我这段代码我做错了什么？无论如何,它只是打印'计数'.我只想要一个非常简单的素数发生器(没什么特别的).
import math
def main():
count = 3
one = 1
while one == 1:
for x in range(2, int(math.sqrt(count) + 1)):
if count % x == 0:
continue
if count % x != 0:
print count
count += 1
如何在Haskell中实现素数列表,以便可以懒惰地检索它们？
我是Haskell的新手,想了解懒惰评估功能的实际用途.
此代码取自"Haskell之路逻辑,数学和编程"一书.它实现了eratosthenes算法的筛选并解决了Project Euler Problem 10.
sieve :: [Integer] -> [Integer]
sieve (0 : xs) = sieve xs
sieve (n : xs) = n : sieve (mark xs 1 n)
where
mark :: [Integer] -> Integer -> Integer -> [Integer]
mark (y:ys) k m | k == m = 0 : (mark ys 1 m)
| otherwise = y : (mark ys (k+1) m)
primes :: [Integer]
primes = sieve [2..]
-- Project Euler #10
main = print $ sum $ takeWhile …我对Haskell很新,我只想找到前200万个素数的总和.我正试图用筛子生成素数(我想是Eratosthenes的筛子？),但它真的很慢,我不知道为什么.这是我的代码.
sieve (x:xs) = x:(sieve $ filter (\a -> a `mod` x /= 0) xs)
ans = sum $ takeWhile (<2000000) (sieve [2..])
提前致谢.
给定N > 0和M > 0,我想枚举所有(x,y)对,使得1 <= x <= N且1 <= y <= M,按(x*y)的降序排列.例如:给定N = 3且M = 2,枚举序列应为:
1. (3, 2) -- 3 * 2 = 6
2. (2, 2) -- 2 * 2 = 4
3. (3, 1) -- 3 * 1 = 3
4. (2, 1) -- 2 * 1 = 2
5. (1, 2) -- 1 * 2 = 2
6. (1, 1) -- 1 * 1 = 1
顺序(2, 1)和(1, …