代码之家  ›  专栏  ›  技术社区  ›  Konrad Garus

在Clojure的连锁电话?

  •  4
  • Konrad Garus  · 技术社区  · 14 年前

    我正试图在克洛尤实施埃拉托斯滕的筛子。我想测试的一种方法是:

    1. 获取范围(2 3 4 5 6…n)
    2. 2和lt= i n=n
      • 通过我的范围 filter 它消除了
      • 为了 i+1 第次迭代,使用前一次筛选的结果

    我知道我可以用 loop/recur ,但这会导致堆栈溢出错误(出于某种原因,未应用尾调用优化)。

    我该如何迭代呢?我的意思是调用n个调用到同一个例程,传递 TH迭代 I+ 1 钍。

    2 回复  |  直到 14 年前
        1
  •  5
  •   Michiel Borkent    14 年前
    (defn sieve [beg end]
      (letfn [(siever [to-sieve sieved]
                      (if (empty? to-sieve) sieved
                      (let [[f & r] to-sieve]
                        (if (> f (Math/sqrt end)) (into sieved to-sieve)
                            (recur (remove #(zero? (mod % f)) r) 
                               (conj sieved f))))))]
        (siever (range beg (inc end)) [])))
    

    这个似乎工作得很好。用(1000000号筛子)对其进行了测试,并在几秒钟内返回,无需吹气。

        2
  •  2
  •   Michał Marczyk    14 年前

    哦,在看到这个问题之前,我已经对你的另一个问题发表了评论…无论如何,埃拉托斯滕的筛子不进行余数/模计算,只进行加法(以递增的方式在列表中移动 p 在哪里 是迄今为止发现的最后一个质点)和“穿越”。当然,“余物+过滤”筛产生的结果与SOE产生的结果相同,但是 两种筛选方案的算法复杂度完全不同 .

    现在,一个严格忠实的SOE需要是“有限的”,因为它只能在一个固定长度的数字数组上操作;但是,如果保留了一个额外的数据结构来记录到达的数字的信息,那么基本的算法可以修改为支持“增量”筛选(使用任意数量的素数的延迟生成)Ed到目前为止发现的每一个素数的“划掉”通行证。对于这样的数据结构,最佳选择是优先级队列,但是映射也是非常有用的。

    有关基于此思想的函数语言增量筛选的扩展讨论(包括对所有涉及算法的复杂性的仔细分析),请参阅Melissa E.O'Neill的文章 The Genuine Sieve of Eratosthenes . 它使用haskell,但这不应该是一个问题(没有使用深奥的特性,haskell代码特别清晰,所以它读起来很像常规的数学符号)。

    例如,在Clojure中的实现,请参见Christophe Grand的 Everybody loves the Sieve of Eratosthenes 博客条目——强烈推荐,最终版本绝对漂亮,速度也非常快——如果我可以随意在这里插入它们,也许还有几个要点: the first one , the second one . (请注意,它们一点也不漂亮,但它们对我来说是一个有用的实验……第二个队列使用优先级队列,而其他队列则基于地图,因此希望它现在可以作为一个粗略的示例使用。)

    我想我并没有回答你的主要clojure实施问题,但我认为Michiel的答案和你另一个问题的主要答案之间,那个问题已经解决了。