我对Haskell很新,我对使用不纯(可变)数据结构可以提高性能有疑问.我正在尝试拼凑一些我听过的不同的东西,所以如果我的术语不完全正确,或者如果有一些小错误,请耐心等待.

为了具体化,请考虑快速排序算法(取自Haskell wiki).

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

这不是"真正的快速入门"."真正的"快速排序算法就位,但事实并非如此.这是非常低效的内存.

另一方面,可以在Haskell中使用向量来实现就地快速排序.这个stackoverflow答案给出了一个例子.

第二种算法比第一种算法快多少？Big O符号在这里没有用,因为性能的提高将来自更有效地使用内存,而不是更好的算法(对吧？).我厌倦了自己构建一些测试用例,但是我很难让事情运行起来.

理想的答案可以让我们了解在理论上使原位Haskell算法更快的原因,以及某些测试数据集上运行时间的示例比较.

通过阅读和解决Project Euler问题,我是编程和学习Haskell的新手.当然,改善这些问题的性能最重要的是使用更好的算法.但是,我很清楚,还有其他简单易行的方法可以提高性能.粗略搜索提出了这个问题,这个问题给出了以下提示:

• 使用ghc标志-O2和-fllvm.
• 使用Int类型而不是Integer类型,因为它是未装箱的(甚至是Integer而不是Int64).这需要键入函数,而不是让编译器即时决定.
• 使用rem而不是mod进行分区测试.
• 适当时使用Schwartzian变换.
• 在递归函数中使用累加器(尾递归优化,我相信).
• 记忆(？)

(一个答案也提到了工人/包装器转换,但这看起来相当先进.)

问题:在Haskell中可以进行哪些其他简单的优化来提高Project Euler风格问题的性能？是否有任何其他Haskell特定的(或特定于函数编程的？)想法或特性可用于帮助加速Project Euler问题的解决方案？相反,应该注意什么？什么是常见但低效的事情要避免？

在 Haskell 中记住递归函数的最快方法是什么？

背景：最近我一直在用 Haskell 解决 Project Euler 问题。许多需要对递归定义的组合或数论函数进行多次计算，例如斐波那契数。如果这些函数被记忆，即函数的结果被缓存以备后用，性能会显着提高。

我见过很多解决这个问题的方法。最优雅的似乎是这个。一种使用 Data.IntMap（或哈希表）和 State monad。此答案中建议的基于树的解决方案，并且此类解决方案似乎相当普遍。再举一个例子，请参阅这篇博文。我见过使用内置函数的其他解决方案。还有一个在第2节在这里与fix，进一步似乎编译器有时可以按摩到memoizing无需额外的工作。还有几个预构建的解决方案。

我想知道对于 Project Euler 中使用的各种函数，哪种记忆方法在实践中最快。我的直觉是哈希表库，因为哈希表似乎是命令式语言中首选的字典结构。纯函数树解决方案很酷，但我的谷歌搜索告诉我，就渐近性能而言，它们比哈希表更糟糕。

编辑

一些评论说这个问题太宽泛而无法回答，经过反思，我同意。因此，让我举两个具体的函数示例进行记忆：一个函数递归计算第 n 个斐波那契数，一个函数递归计算加泰罗尼亚数。我想为大 n 多次计算这些函数。

我知道这些有明确的公式，但让我们忽略它，因为这里的真正重点是使用它们来对记忆技术进行基准测试。

通常我需要遍历一个数组并对每个条目执行一些操作,其中操作可能取决于索引和条目的值.这是一个简单的例子.

import numpy as np

N=10
M = np.zeros((N,N))

for i in range(N):
    for j in range(N):
        M[i,j] = 1/((i+2*j+1)**2)

是否有更短,更清洁或更pythonic的方式来执行此类任务？

我意识到这是一个微不足道的问题,但我仍然感到困惑.

我有一个带有视网膜显示屏的13英寸MacBook Pro.我的系统声称系统报告中的分辨率为2560×1600.我假设tkinter中的Canvas命令测量高度和宽度(以像素为单位),而tk文档似乎也表明了这一点.然而下面的代码,我使用1200作为宽度,700作为tkinter画布的高度,产生一个主要填充我的屏幕的画布.

画布的高度和宽度是多少单位？

from tkinter import *

master = Tk()

x = 1200
y = 700

w = Canvas(master, width=x, height=y)
w.pack()


mainloop()