python-2.7 - Python进程被杀死

Question

我正在运行以下代码，并且收到来自python的“killed”消息:

import random,string

def rotations(t):
        ''' Return list of rotations of input string t '''
        tt = t * 2
        return [ tt[i:i+len(t)] for i in xrange(0, len(t)) ]
def bwtViaBwm(t):
        return ''.join(map(lambda x: x[-1], bwm(t)))
def bwm(t):
        return sorted(rotations(t))

def build_FM(fname):
        stream=readfile(fname)
        fc=[x[0] for x in bwtViaBwm(stream)]


def readfile(sd):
    s=""
    with open(sd,'r') as myfile:
        s =myfile.read()
    return s.rstrip('\n')

def writefile(sd,N):
        with open(sd, "wb") as sink:
            sink.write(''.join(random.choice(string.ascii_uppercase + string.digits) for _ in xrange(int(N))))
            sink.write('$')
        return
def main():
    fname= sys.argv[1]
    N =sys.argv[2]
    writefile(fname,N)
    build_FM(fname)
    return

if __name__=='__main__':
        main()

输入文件名和数字作为输入。该代码创建大小为 N的随机流，然后对该流运行BWT转换。当我输入 N=500000作为输入时，我收到一条“killed”消息，对于内存错误而言似乎很小。我的系统运行Ubuntu 14.04、8GB RAM和python 2.7。

这是我运行脚本的方式:

python  fm.py new_file.csv 500000

我几秒钟后得到这个:

killed

Answer 1

问题出在您的rotations函数上:

def rotations(t):
    ''' Return list of rotations of input string t '''
    tt = t * 2
    return [ tt[i:i+len(t)] for i in xrange(0, len(t)) ]

查看它的作用:

>>> rotations('x')
['x']
>>> rotations('xx')
['xx', 'xx']
>>> rotations('xxxxx')
['xxxxx', 'xxxxx', 'xxxxx', 'xxxxx', 'xxxxx']

其结果将成倍扩大。因此，一个 500000字符文件将产生一个长度为 500000^2的结果。

从计算上讲，对于大的输入，不可能有一种方法可以完成您要尝试的操作:即使字符串的每个旋转长度为500k个字符。我们知道输入中每个元素都有一个输出，每个输出的长度都与原始输入的长度相同。因此，最小大小为 n*n或 n^2。除非您知道只需要有限的数量(并且可以尽早剔除它们)，否则您总是会遇到问题。

如何解决问题

首先，我们需要找出问题所在。让我们看看代码在做什么。假设一个简单的开始集:

bacb
rotation()提供该集合的所有可能的旋转:

>>> rotations('bacb')
['bacb', 'acbb', 'cbba', 'bbac']

然后，您对该列表进行排序。

>>> sorted(rotations('bacb'))
['acbb', 'bacb', 'bbac', 'cbba']

然后使用每个元素的最后一个元素，生成 bdac。这就是说，对于输入中的每个元素 n，您正在分配一个排序顺序，这样 n+1 ... n(环绕)将按字母数字顺序进行排序。

为了解决这个问题，算法将是:

创建一个空列表'final_order'，它将是输入列表的“排序”索引的列表。

每个元素

获取从该元素开始的原始字符串的“旋转”加上一个

以一种排序方式放置到“final_order”列表中:

获取“final_order”列表的第一个元素的“旋转”。

比较两个旋转。

如果新的旋转小于旧的旋转，请在该点插入列表。否则转到下一个旋转。

如果没有其他旋转，则将新的旋转放置在那里。

(可能有一种更快的排序方式，但是为了便于说明，我将使用它。)

我们需要的第一件事是 get_rotation(input, idx):

def get_rotation(input, idx):
    return input[idx + 1:] + input[:idx + 1]

现在最困难的部分(请参阅评论):

def strange_sort(input):
    sorted_indices = list()  # Initialize the list

    for idx in range(len(input)):  # For each element in the list
        new_rotation = get_rotation(input, idx)  # Get the rotation starting at that index
        found_location = False  # Need this to handle the sorting
        for sorted_idx in range(len(sorted_indices)):  # Iterate through all 'found' indices
            old_rotation = get_rotation(input, sorted_indices[sorted_idx])  # Get the rotation starting at the found/old rotation
            if new_rotation < old_rotation:  # Which comes first?
                # If this one, insert the new rotation's starting index before the index of the already sorted rotation
                sorted_indices.insert(sorted_idx, idx)
                found_location = True
                break
        if not found_location:  # If greater than everything, insert at end
            sorted_indices.insert(len(sorted_indices), idx)
    return "".join(map(lambda x: input[x], sorted_indices))  # Join and return result

运行此命令，我们会在较短的输入上得到预期的结果:

>>> print("Final result={}".format(strange_sort('bacb')))
Final result=bbca

这是带有测试/计时器的完整程序:

import random, string, datetime

def get_rotation(input, idx):
    return input[idx + 1:] + input[:idx + 1]

def strange_sort(input):
    sorted_indices = list()

    for idx in range(len(input)):
        new_rotation = get_rotation(input, idx)
        found_location = False
        for sorted_idx in range(len(sorted_indices)):
            old_rotation = get_rotation(input, sorted_indices[sorted_idx])
            if new_rotation < old_rotation:
                sorted_indices.insert(sorted_idx, idx)
                found_location = True
                break
        if not found_location:
            sorted_indices.insert(len(sorted_indices), idx)
    return "".join(map(lambda x: input[x], sorted_indices))

n1 = 5
n2 = 50
n3 = 500
n4 = 5000
n5 = 50000
n6 = 500000

n = [n1, n2, n3, n4, n5, n6]

def test(lst):
    for l in range(len(lst)):
        input = ''.join(random.choice(string.ascii_uppercase+string.digits) for x in range(lst[l]))
        start = datetime.datetime.now()
        result = strange_sort(input)
        end = datetime.datetime.now()
        runtime = end - start
        print("n{} runtime={} head={} tail={}".format(l, runtime.seconds, result[:5], result[-5:]))

test(n)

尝试利用不需要存储所有内容的优势，只需为初始排序的每个索引存储最终排序的索引即可。可悲的是，上面的实现显然太慢了，正如我们从运行它可以看到的那样:

$ python2 strange_sort.py
n0 runtime=0 head=SJP29 tail=SJP29
n1 runtime=0 head=5KXB4 tail=59WAK
n2 runtime=0 head=JWO54 tail=7PH60
n3 runtime=4 head=Y2X2O tail=MFUGK
(Still running)

好的，所以我们知道排序很糟糕。我们可以更快吗？我们从 Python Wiki Entry on Big-O中看到，需要 O(M)来获取字符串 slice 。对我们来说，这意味着 O(N)，因为我们要提取两个加在一起的完整片段。在计算上这是一场灾难，因为我们每次都这样做。

而不是每次都进行完整的旋转，而是进行迭代和比较。一个旋转的一个索引与另一个旋转的一个索引的单个比较应该是 O(2)。在最坏的情况下，我们必须这样做 O(N)次，但每次都不太可能。

我们添加了一个额外的for循环，并对其进行了重新处理以仅查看下一个索引:

for offset in range(len(input)):
    if new_rotation[offset] < input[(sorted_indices[sorted_idx] + offset) % len(input)]:
        sorted_indices.insert(sorted_idx, idx)
        found_location = True
        break
if found_location:
    break

现在，我们使用计时器执行它:

$ python2 strange_sort.py
n0 runtime=0 head=VA6KY tail=VA6KY
n1 runtime=0 head=YZ39U tail=63V0O
n2 runtime=0 head=JFYKP tail=8EB2S
n3 runtime=0 head=IR4J9 tail=VLR4Z
n4 runtime=28 head=EYKVG tail=7Q3NM
n5 runtime=4372 head=JX4KS tail=6GZ6K

正如我们所看到的，这次仅用28秒就使其成为 n4。不过，这对于 n6来说并不是一个好兆头。 las，这似乎在计算上很复杂，这表明我们需要一种比 Insertion Sort更好的排序方法，而 O(n^2)最糟糕(甚至是平均)。输入 500K后，至少需要进行 250B(十亿)计算。 (时间 n，每次计算由计算机完成的实际指令数)。

我们了解到，您实际上并不需要写轮换。为了解决这个问题，您必须编写一种快速排序算法，该算法将输入的不是实际值，而是一个可以在给定精度下计算值的函数。

转过头来，我想过要尝试创建一个对象，该对象可以进行足够多的搜索以了解其如何针对另一个对象进行排序，并使用内置的Python排序。

import random, string, datetime
from functools import total_ordering


@total_ordering
class Rotation(object):
    """Describes a rotation of an input based on getting the original and then offsetting it."""

    def __init__(self, original, idx):
        self.original = original
        self.idx = idx

    def getOffset(self, offset):
        return self.original[(self.idx + offset) % len(self.original)]

    def __eq__(self, other):
        print("checking equality")
        if self.idx == other.idx:
            return True
        for offset in range(len(self.original)):
            if self.getOffset(offset) is not other.getOffset(offset):
                print("this={} is not that={}".format(self.getOffset(offset), other.getOffset(
                        offset)))
                return False
        return True

    def __lt__(self, other):
        for offset in range(len(self.original)):
            if self.getOffset(offset) < other.getOffset(offset):
                return True
            elif self.getOffset(offset) > other.getOffset(offset):
                return False
        return False

    def __str__(self):
        return self.getOffset(-1)

    def __repr__(self):
        return "".join(map(lambda x: str(x), [self.getOffset(idx) for idx in range(len(
                self.original))]))


def improved_strange_sort(input):
    original = list(input)
    rotations = [Rotation(original, idx) for idx in range(len(original))]
    result = sorted(rotations)
    # print("original={} rotations={} result={}".format(original, rotations, result))
    return "".join(map(lambda x: str(x), result))


def test(input):
    start = datetime.datetime.now()
    result = improved_strange_sort(input)
    end = datetime.datetime.now()
    runtime = end - start
    print("input={} runtime={} head={} tail={}".format(input[:5], runtime.seconds, result[:5],
                                                       result[-5:]))


def timed_test(lst):
    for l in range(len(lst)):
        print("Test {} with length={}".format(l, lst[l]))
        test(''.join(random.choice(string.ascii_uppercase + string.digits) for x in range(lst[l])))


n1 = 5
n2 = 50
n3 = 500
n4 = 5000
n5 = 50000
n6 = 500000

n = [n1, n2, n3, n4, n5, n6]

test('bacb')
timed_test(n)

这似乎会产生正确的结果:

$ python2 strange_sort.py 
input=bacb runtime=0 head=bbca tail=bbca
Test 0 with length=5
input=FB2EH runtime=0 head=BF2HE tail=BF2HE
Test 1 with length=50
input=JT3ZP runtime=0 head=W8XQE tail=QRUC3
Test 2 with length=500
input=TL8L7 runtime=0 head=R4ZUG tail=M268H
Test 3 with length=5000
input=PYFED runtime=1 head=L5J0T tail=HBSMV
Test 4 with length=50000
input=C6TR8 runtime=254 head=74IIZ tail=U69JG
Test 5 with length=500000
(still running)