相关疑难解决方法(0)

我知道Haskell一点点,我想知道是否有可能在Haskell中编写类似于矩阵矩阵产品的东西,它具有以下所有特性:

1. 纯函数:在其类型签名中没有IO或Statemonad(我不关心函数体中发生了什么.也就是说,我不关心函数体是否使用monad,只要整个函数是纯的).我可能想在纯函数中使用这个矩阵矩阵乘积.
2. 内存安全:没有malloc或指针.我知道在Haskell中"写C"是可能的,但是你会失去内存安全性.实际上用C编写这个代码并将其与Haskell连接也会损失内存安全性.
3. 和Java一样高效.具体来说,我们假设我所说的是一个简单的三重循环,单精度,连续的列主要布局(float[]非float[][])和大小为1000x1000的矩阵,以及一个单核CPU.(如果你每个周期得到0.5-2个浮点运算,你可能会在球场.)

(我不希望这听起来像是一个挑战,但请注意Java可以轻松满足以上所有要求.)

我已经知道了

1. 三重循环实现不是最有效的.这是相当缓存 - 忘记了.在这种特殊情况下,最好使用编写良好的BLAS实现.但是,人们不能总是指望C库可用于尝试做什么.我想知道是否可以在普通的Haskell中编写合理有效的代码.
2. 有些人写了完整的研究论文,证明了#3.但是,我不是计算机科学研究员.我想知道在Haskell中是否可以保持简单的事情.
3. Haskell的Gentle简介有一个矩阵产品实现.但它不能满足上述要求.

致意见:

我有三个原因:首先,"没有malloc或指针"的要求尚未定义(我要求你编写任何不使用指针的Haskell代码);

我看到很多Haskell程序没有使用Ptr.也许它指的是在机器指令级别使用指针的事实？那不是我要表达的意思.我指的是Haskell源代码的抽象级别.

第二,对CS研究的攻击是不合适的(而且我无法想象比使用别人已经为你编写的代码更简单的事情); 第三,Hackage上有很多矩阵包(要求这个问题的准备工作应该包括审查和拒绝每个).

你的#2和#3似乎是相同的("使用现有的库").我对矩阵产品感兴趣,只是测试Haskell可以自己做什么,以及它是否允许你"简单易懂".我可以很容易地想出一个没有任何现成库的数值问题,但是我必须解释这个问题,而每个人都已经知道矩阵产品是什么.

Java如何可能满足1.？任何Java方法本质上都是 :: IORef Arg -> ... -> IORef This -> IO Ret

这是我问题的根源,实际上是(+1).虽然Java并没有声称追踪纯度,但Haskell确实如此.在Java中,注释中指出了函数是否纯粹.我可以声称矩阵产品是纯的,即使我在函数体中做了突变.问题在于Haskell的方法(在类型系统中编码的纯度)是否与效率,内存安全性和简单性兼容.

我一直在努力学习生成素数的算法,我在维基百科上遇到了阿特金的Sieve.我理解算法的几乎所有部分,除了少数几个.以下是问题:

1. 下面的三个二次方程如何形成？4x ^ 2 + y ^ 2,3x ^ 2 + y ^ 2和3x ^ 2-y2
2. 维基百科中的算法讨论模数为60但我不明白在下面的psudocode中使用的方式/位置.
3. 如何找到这些提醒1,5,7和11？

以下是维基百科的伪代码供参考:

// arbitrary search limit                                                   
limit ? 1000000                                                             

// initialize the sieve                                                     
for i in [5, limit]: is_prime(i) ? false                                    

// put in candidate primes:                                                 
// integers which have an odd number of                                     
// representations by certain quadratic forms                               
for (x, y) in [1, ?limit] × [1, ?limit]:                                    
    n ? 4x²+y²                                                              
    if (n ? limit) and (n mod 12 = 1 or …

今天我读了一篇论文:

O'Neill,Melissa E.," Eratosthenes的真正筛选",功能编程期刊,由剑桥大学出版社出版2008年10月9日doi:10.1017/S0956796808007004.

它描述了一种使用优先级队列生成素数的算法:

sieve [] = []
sieve (x:xs) = x : sieve' xs (insertprime x xs PQ.empty)
    where
        insertprime p xs table = PQ.insert (p*p) (map (* p) xs) table
        sieve' [] table = []
        sieve' (x:xs) table
            | nextComposite <= x = sieve' xs (adjust table)
            | otherwise = x : sieve' xs (insertprime x xs table)
            where
                nextComposite = PQ.minKey table
                adjust table
                    | n <= x = adjust (PQ.deleteMinAndInsert n' ns table)
                    | …

我需要计算小于或等于某个 N 的素数个数，这就是素数计数函数或 PI 函数。我有这个，但运行速度太慢：

function PI(x) {
    var primes = 4;
    for (var i = 3; i <= x; i += 2) {
        if (i % 3 === 0 || i % 5 === 0 || i % 7 === 0) continue;
        var r = ~~Math.sqrt(i), p = true;
        for (var j = 2; j <= r; j++) {
            if (i % j === 0) {
                p = false;
                break;
            }
        }
        if (p)
            primes++;
    }
    return primes;
} …