小编ree*_*eem的帖子

我已经在网上搜索了这个关键字的实际解释.我看过的每个Haskell教程都是随机开始使用它,而不是解释它的作用(我看过很多).

这是Real World Haskell使用的基本代码Just.我理解代码的作用,但我不明白它的目的或功能Just是什么.

lend amount balance = let reserve    = 100
                      newBalance = balance - amount
                  in if balance < reserve
                     then Nothing
                     else Just newBalance

从我所观察到的,它与Maybe打字有关,但这几乎是我所学到的.

Just非常感谢对什么方法的一个很好的解释.

从我对Haskell的有限知识来看,似乎Maps(来自Data.Map)应该像其他语言中的字典或散列表一样使用,但它们被实现为自平衡二进制搜索树.

为什么是这样？使用二叉树将查找时间减少到O(log(n))而不是O(1),并且要求元素在Ord中.当然有一个很好的理由,那么使用二叉树有什么好处呢？

也:

在什么应用程序中,二叉树比哈希表更差？反过来呢？在许多情况下,一个人会比另一个人更受欢迎吗？Haskell中是否有传统的哈希表？

因为我可以看到它的出现:这是一个不同的问题,而GHC可以实现哪些优化可靠？因为我不是要求最可靠的优化,只是最聪明/最强大的优化.

我特别希望GHC能够对性能产生严重影响的非直观优化,并展示与惰性评估或纯度相关的编译器优化的强大功能.并直接解释如何实现它们.

最好的答案将是:

• 优化的解释以及为什么它如此聪明或强大
• 为何优化可以提高性能
• GHC如何识别何时可以使用此优化
• 优化实际上将代码转换为什么
• 为什么这种优化需要惰性评估或纯度

这会产生一个Segmentation Fault: 11,我不知道为什么.

在我进入之前,这是代码:

import numpy.random as nprnd
import heapq
import sys

sys.setrecursionlimit(10**6)


def rlist(size, limit_low, limit_high):
    for _ in xrange(size): 
        yield nprnd.randint(limit_low, limit_high)

def iterator_mergesort(iterator, size):
    return heapq.merge(
         iterator_mergesort(
           (iterator.__next__ for _ in xrange(size/2)), size/2),
         iterator_mergesort(
            iterator, size - (size/2))
       )

def test():
    size = 10**3
    randomiterator = rlist(size, 0, size)
    sortediterator = iterator_mergesort(randomiterator, size)
    assert sortediterator == sorted(randomiterator)

if __name__ == '__main__':
    test()

基本上,它只是一个mergesort,它适用于迭代器和生成器表达式,而不是在列表上工作,以便在任何时候最小化内存占用.它没什么特别的,并使用heapq.merge()内置方法来合并迭代器,所以当一切都中断时我很惊讶.

快速运行代码Segmentation Fault: 11并给出一个错误窗口告诉我python崩溃了.我不知道在哪里看或如何调试这个,所以任何帮助将不胜感激.

我对Web上的许多python radix实现的排序感到非常沮丧.

它们一直使用10的基数,并通过除以10的幂或得到数字的log10来得到它们迭代的数字的数字.这是非常低效的,因为与位移相比,log10不是特别快的操作,这几乎快了100倍!

更高效的实现使用256的基数并逐字节地对数字进行排序.这允许使用可笑的快速位运算符完成所有"字节获取".不幸的是,似乎绝对没有人在python中实现了使用位运算符而不是对数的基数排序.

因此,我亲自动手并想出了这只野兽,它的运行速度大约是小型阵列的一半,并且在大型阵列上的运行速度几乎一样快(例如len大约10,000,000):

import itertools

def radix_sort(unsorted):
    "Fast implementation of radix sort for any size num."
    maximum, minimum = max(unsorted), min(unsorted)

    max_bits = maximum.bit_length()
    highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1

    min_bits = minimum.bit_length()
    lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1

    sorted_list = unsorted
    for offset in xrange(lowest_byte, highest_byte):
        sorted_list = radix_sort_offset(sorted_list, offset)

    return sorted_list

def …

如何在Python中检查对象是否可订购/可排序？

我正在尝试为__init__我的二叉树类的方法实现基本类型检查,我希望能够检查节点的值是否可订购,如果不是则抛出错误.它类似于在哈希表的实现中检查哈希性.

我正在尝试完成类似于Haskell的(Ord a) => etc.限定符.在Python中有类似的检查吗？

• 列表推导只是一种语言特征吗？
• 使用纯Haskell伪造列表理解的最简单方法是什么？
• 您是否必须使用do block/>>=来执行此操作,还是可以使用其他方法将列表理解混合在一起？

澄清:通过"假"列表理解我的意思是创建一个函数,它接受相同的输入并产生相同的输入,即返回值的表单,压缩在一起的列表,以及谓词或多个谓词.

我通过快速加倍使用从矩阵求幂算法得到的算法编写了一个非常标准的斐波纳契函数,该算法应该在O(log(n))时间和调用中运行,但是在大约1,000,000的时候停止 - 即使这应该只是大约25个电话.

码:

"""
O(log(n)) time fibonacci algorithm using fast doubling derived from the matrix
squaring algorithm for the same thing.
"""

def fibonacci(num):
    "O(log(n)) implementation of fibonacci using fast doubling."
    if num >= 0:
        return fib_helper(num)[0]

def fib_helper(num):
    "Helper function for fibonacci()."
    if num == 0:
        return (0, 1)
    elif num == 1:
        return (1, 1)
    else:
        f_k, f_k_1 = fib_helper(num // 2)
        f_k_even = f_k * (2 * f_k_1 - f_k)
        f_k_odd = f_k_1 * f_k_1 + …

我试图在python中编写一个计数排序,以在某些情况下击败内置的timsort.现在它击败了内置的排序函数,但仅适用于非常大的数组(长度为100万个整数,更长,我没有尝试超过1000万个),并且仅适用于不大于10,000的范围.此外,胜利是狭隘的,计数排序仅在专门为其量身定制的随机列表中获得了显着的优势.

我已经读过可以通过矢量化python代码获得惊人的性能提升,但我不是特别了解如何做到这一点或如何在这里使用它.我想知道如何对此代码进行矢量化以加快速度,并欢迎任何其他性能建议.

目前python和stdlibs的最快版本:

from itertools import chain, repeat

def untimed_countsort(unsorted_list):
    counts = {}
    for num in unsorted_list:
        try:
            counts[num] += 1
        except KeyError:
            counts[num] = 1

    sorted_list = list(
        chain.from_iterable(
            repeat(num, counts[num])
            for num in xrange(min(counts), max(counts) + 1)))
    return sorted_list

• 重要的是这里的原始速度,因此为速度增益牺牲更多空间是完全公平的游戏.

• 我已经意识到代码已经相当简短和清晰,所以我不知道有多少空间可以提高速度.

• 如果有人对代码进行了更改以使其更短,只要它不会使它变慢,那也是很棒的.

• 执行时间下降了近80%!在我目前的测试中,现在是Timsort的三倍!

通过LONG镜头执行此操作的绝对最快的方法是使用这个带有numpy的单线程:

def np_sort(unsorted_np_array):
    return numpy.repeat(numpy.arange(1+unsorted_np_array.max()), numpy.bincount(unsorted_np_array))

这比纯python版快了大约10-15倍,比Timsort快大约40倍.它需要一个numpy数组并输出一个numpy数组.

我已经对字节序及其在C语言中的作用进行了一些阅读,但没有什么能真正为我澄清这一点.我刚开始使用C,我看到了这个例子:

#include <stdio.h>

int main(void) {
    int x = 017;
    int y = 12;
    int diff = x - y;
    printf("diff is %d\n", diff);
    return 0;
}

它询问会打印什么.我编译和运行的例子,得到了差异为3,那么x是15.我有点看这是为什么,但真的很感激,如果有人真的澄清对我来说.

[1]我已经找到了类似的问题,但没有找到任何彻底解释这个问题的问题.如果有人可以将我与一个也很好的人联系起来.