python - 在 Python 2 中对 10**6 位数字进行高效排序

标签 python performance python-2.7 long-integer

我使用long类型来存储数字并使用普通排序方法进行排序,但效率不够。

我认为 long(raw_input()) 花费了太多时间。

有人能想出一种有效的方法来解决这个问题吗?

n = int(raw_input().strip())
unsorted = []
for i in xrange(n):
    term = long(raw_input())
    unsorted.append(term)

for i in sorted(unsorted):
    print i

最佳答案

既然你说这是一个竞争性的编程问题,那么这个解决方案就可以工作,否则它永远不会工作,因为它需要太多的内存,并且在糟糕的情况下会崩溃。但在竞争性编程中,限制并不那么大,它应该有效。

我们只是添加比较器,即 gtlt 方法来决定两个对象之间的比较。

class VeryBigNumber(object):
    def __init__(self,number_string):
        self.number = number_string


def __gt__(self,other):
    if len(self.number)>len(other.number):
        return True
    elif len(self.number)<len(other.number):
        return False

    for i in xrange(min(len(self.number),len(other.number))):
        if int(self.number[i])>int(other.number[i]):
            return True
        elif int(self.number[i])<int(other.number[i]):
            return False
    return False

def __eq__(self,other):
    return self.number == other.number

def __lt__(self,other):
    return not (self.__eq__(other) or self.__gt__(other))

arr = []
for i in xrange(n):
    arr.append(VeryBigNumber(raw_input().strip())

arr = sorted(arr)
for a in arr:
    print a.number,

大解释:

  1. 在评论中您曾说过这是为了编程比赛。这确保了内存足够小,可以在一秒钟内读入。

  2. 我们不会将这么大的字符串转换为数字,因为这是不必要的。相反,我们保持字符串原样。

  3. 那我们如何排序呢?我们创建自己的类并使用字符串比较。

  4. 这些工作原理是比较字符串之间的字符数字,因此一次只有一个字符转换为 int,这是非常高效的。

  5. 我已经测试了上面的代码,它可以正常工作

关于python - 在 Python 2 中对 10**6 位数字进行高效排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42397729/

相关文章:

c# - 高性能内存缓存的线程安全

python - 检查 Google App Engine 模型中的属性类型

sql-server - 如何解决sql server性能问题

python - 为什么 PyMongo 会抛出 AutoReconnect?

performance - 让 Oracle 9i 使用索引

python - 如何在 python 中执行 os.environ 连接?

python - 将嵌套字典转换为多级数据帧

python - 重复 os.path.isdir 调用中的巨大内存泄漏?

python - 我将如何打包和销售 Django 应用程序?

python - subprocess.Popen 和执行 ssh 命令出现问题