相关疑难解决方法(0)

我有许多大型(> 35,000,000)整数列表,它们将包含重复项.我需要计算列表中每个整数的计数.以下代码有效,但似乎很慢.任何人都可以使用Python更好的基准测试,最好是Numpy吗？

def group():
    import numpy as np
    from itertools import groupby
    values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4')
    values.sort()
    groups = ((k,len(list(g))) for k,g in groupby(values))
    index = np.fromiter(groups,dtype='u4,u2')

if __name__=='__main__':
    from timeit import Timer
    t = Timer("group()","from __main__ import group")
    print t.timeit(number=1)

返回:

$ python bench.py 
111.377498865

干杯!

根据回复进行编辑:

def group_original():
    import numpy as np
    from itertools import groupby
    values = np.array(np.random.randint(0,1<<32,size=35000000),dtype='u4')
    values.sort()
    groups = ((k,len(list(g))) for k,g in groupby(values))
    index = np.fromiter(groups,dtype='u4,u2')

def group_gnibbler():
    import numpy as np
    from …

我对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 …

NumPy的没有尚未有一个基数排序,所以我想知道是否有可能使用一个预先存在numpy的功能来写.到目前为止,我有以下,它确实有效,但比numpy的快速排序慢约10倍.

测试和基准测试:

a = np.random.randint(0, 1e8, 1e6)
assert(np.all(radix_sort(a) == np.sort(a))) 
%timeit np.sort(a)
%timeit radix_sort(a)

该mask_b循环可以至少部分地被矢量化,从掩码中广播&并cumsum与axisarg一起使用,但是这最终是一种悲观,可能是由于增加的存储器占用.

如果有人能够看到一种方法来改进我所拥有的东西,我会有兴趣听到,即使它仍然比np.sort... 慢......这更像是一种对知识的好奇心和对numpy技巧的兴趣.

请注意,您可以轻松地实现快速计数排序,但这仅与小整数数据相关.

编辑1:以np.arange(n)圈外的帮助一点,但不是很exiciting.

编辑2:在cumsum实际上是多余的(哎呀!),但这个简单的版本仅具有性能稍微帮助..

def radix_sort(a):
    bit_len = np.max(a).bit_length()
    n = len(a)
    cached_arange = arange(n)
    idx = np.empty(n, dtype=int) # fully overwritten each iteration
    for mask_b in xrange(bit_len):
        is_one = (a & 2**mask_b).astype(bool)
        n_ones = np.sum(is_one)      
        n_zeros = n-n_ones
        idx[~is_one] = cached_arange[:n_zeros] …

我试图在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数组.