Python采访街的中值解题

Question

有什么建议可以提高以下代码的性能吗？这一规定超过了最后四种情况的时限。这是https://www.interviewstreet.com/challenges/dashboard/#problem/4fcf919f11817问题的解决方案

def main():
    N = int(raw_input())
    if(0<=N<=100000):
        x = []
        ans=[]
        l=[]
        m=[]
        for i in xrange(0, N):
            tmp = raw_input()
            a, b = [xx for xx in tmp.split(' ')]
            l.append(a)
            m.append(int(b))  

        for i in xrange(0, N):
            if l[i]=='r':
                if len(x)<1 or m[i] not in x:
                        ans.append('Wrong!')
                elif m[i] in x:
                    x.remove(m[i])
                    q=len(x)
                    if q%2==1:
                        ans.append(x[(q/2)])
                    elif q%2==0:
                        if q==0:
                            ans.append('Wrong!')
                        else:
                            k=x[q/2]+x[(q/2)-1]
                            if k%2==0:
                                ans.append(int(k)/2)
                            else:
                                ans.append(k/2.0)
            elif l[i]=='a':
                x.append(m[i])
                x=sorted(x)
                p=len(x)
                if p%2==1:
                    ans.append(x[(p/2)])
                else:
                    k=x[p/2]+x[(p/2)-1]
                    if k%2==0:
                        ans.append(int(k)/2)
                    else:
                        ans.append(k/2.0)

        for i in ans:
            print i

if __name__ == "__main__":
    main()

from sys import stdin,stdout
from bisect import bisect,insort
def main():
    N = int(raw_input())
    x = []
    ans = []
    append = x.append
    ans_append = ans.append
    remove = x.remove
    read = stdin.readline
    for i in xrange(0, N):
        tmp = read()
        a, b = tmp.split(' ')
        b = int(b)
        if a == 'r':
            search_result = search(x,b)
            if len(x) < 1 or not(search_result):
                ans_append('Wrong!') 
            else:
                remove(b)
                ans_append(median(x))                   
        else:
            insort(x, b)
            ans_append(median(x))
    for i in ans:
        print i

def median(arr):
    q = len(arr)
    if q==0:
        return 'Wrong!'
    if q%2 == 1:
        return arr[(q/2)]
    else:
        k = arr[q/2] + arr[(q/2)-1]
        if k%2 == 0:
            return int(k)/2
        else:
            return k/2.0

def search(arr,element):
    position = bisect(arr, element)
    if len(arr) >= position and len(arr)!=0:
        if arr[position-1] == element:
            return True
        else:
            return False
    else:
        return False

if __name__ == "__main__":
    main()

Answer 1

def main():
    N = int(raw_input())
    if(0<=N<=100000):

检查这个真的没有什么意义。无论值如何，代码都能工作，您不需要担心竞赛是否会为您提供更大的值。

        x = []
        ans=[]
        l=[]
        m=[]

我建议使用更长的名字，即使在比赛场景中也是如此。

        for i in xrange(0, N):
            tmp = raw_input()
            a, b = [xx for xx in tmp.split(' ')]

实际上，这一行和a, b = tmp.split(' ')一样，列表压缩只是浪费了处理能力。由于没有任何不寻常的whitespcae，所以您也可以跳过参数来拆分

            l.append(a)
            m.append(int(b))  

还不清楚你为什么要把它存储在一个列表中。只要你一读到手术就行。不需要将东西存储到列表中，只需在另一个循环中读取它们。

        for i in xrange(0, N):

在这里，您应该使用类似于for action, number in zip(l,m):的东西

            if l[i]=='r':
                if len(x)<1 or m[i] not in x:

检查len < 1没有任何意义，因为第二个条件无论如何都会失败

                        ans.append('Wrong!')

把输出打印出来，不要储存起来

                elif m[i] in x:

你应该能把它变成另一个

                    x.remove(m[i])

这会很慢的。对m[i] in x的检查和要删除的调用必须扫描整个列表以找到元素。但是列表是排序的，这意味着您应该能够更快地找到元素。请查看bisect模块，该模块允许提供二进制搜索，以便在排序列表中更快地查找元素。

                    q=len(x)
                    if q%2==1:
                        ans.append(x[(q/2)])
                    elif q%2==0:
                        if q==0:
                            ans.append('Wrong!')

这种情况在这里有点奇怪，在检查奇数和偶数之前，在水平上检查这一点会更有意义。

                        else:
                            k=x[q/2]+x[(q/2)-1]
                            if k%2==0:
                                ans.append(int(k)/2)
                            else:
                                ans.append(k/2.0)
            elif l[i]=='a':
                x.append(m[i])
                x=sorted(x)

这最好写成x.sort()，以便进行适当的排序。然而，它将是缓慢的，不断诉诸清单。在添加元素之前，列表几乎是按顺序排列的，因此您可以将其用于您的优势。bisect模块可以通过操作来简化操作。

                p=len(x)
                if p%2==1:
                    ans.append(x[(p/2)])
                else:
                    k=x[p/2]+x[(p/2)-1]
                    if k%2==0:
                        ans.append(int(k)/2)
                    else:
                        ans.append(k/2.0)

好吧，你又要这么做了。你应该把这个放进一个函数什么的

        for i in ans:
            print i

if __name__ == "__main__":
    main()

维护排序列表太昂贵了。每次插入或删除元素时，计算机都必须在内存中移动整个数组。知道这一点，竞赛网站将设计问题，以给你最坏的情况。你得做点别的事。

探索的一种可能性是使用二叉树。二叉树具有更快的插入/删除时间，并且是一种计算中间值的相当快的方法。它们的缺点是实现它所需的复杂性。二叉树本身并不复杂，但问题在于平衡策略。

第二种可能是尝试使用在heapq模块中实现的堆。我们的想法是，在任何时候，你都要保持两个堆。一个元素小于中位数，另一个元素大于中值。处理删除的方法有些棘手，但我认为这是可以做到的。