optmise此代码最小运行时间

-4

def main(): 
    inp=raw_input() 
    x=list(inp.split()[0]) 
    y=list(inp.split()[1]) 
    if (len(x)==len(y)): 
     if (set(x)==set(y)): 
      return "YES" 
     else: 
      return "YES" 
    else: 

     if(set(x)==set(y)): 

      return "NO" 
     else: 
      return "YES" 

main()

我需要的最短运行时间，任何帮助吗？我不知道如何在渐近记法表示此...optmise此代码最小运行时间

来源

2013-02-27 Ajay

它有一个O（1）的运行时间。关于代码没有什么复杂的，虽然有一些分支是多余的（不管这两个集合是否等价，都会返回“YES”）。 – Makoto 2013-02-27 19:18:42

它使用3.9M \t我可以以某种方式进一步减少 – Ajay 2013-02-27 19:20:18

也许你应该告诉我们你在做什么。 – 2013-02-27 19:21:05

删除所有重复和不必要的工作会刮胡子关闭一点点。请不要在inp上拨打split()两次，也不要在结果相同的情况下创建并比较set，等等。另外，如果您唯一要做的事情不需要将str转换为list与他们做的是检查他们的len并将他们变成set s。所以：

def main(): 
    x, y = raw_input().split()   
    if len(x)==len(y): 
     return "YES" 
    else: 
     if set(x)==set(y): 
      return "NO" 
     else: 
      return "YES"  
main()

真的没有办法让Python在Python中显着更快。

渐近运行时间显然是O(N)，其中N是输入字符串的长度。你正在做一堆线性长度的东西（split，复制前半部分，复制后半部分，在每半部分中制作set等等），而且没有超线性的东西。

从理论上讲，通过使用大小为256的位集而不是集合，您可以更快速地完成任务，而且内存更少。下面是一些伪代码：

matches = [0 for i in range(256)] 
for char in x: 
    matches[char] = 1 
for char in y: 
    if matches[char] < 1: matches[char] = -1 
    else: return "YES" 
for match in matches: 
    if match == 1: return "YES" 
return "NO"

这当然仍然是线性的，同时也减少了直线步数，并允许您短路早些时候在许多情况下，再加上你删除“贵”与“贱”散列（它在C中实际上不存在，因此是免费的）。所以，它与更小的乘数成线性关系。

我预计，在实践中，这将是在Python一大堆慢，因为在翻译的C代码中100种元素的隐式循环（例如，set构造函数）是速度远远超过了一个Python显式循环即使你中途短路。但是，如果您将其编码为C扩展名，则可能会比使用set更快。

如果您试图避免记忆，请注意上述解决方案并不要求您一次读取整件事情。例如，代替for char in x:和for char in y:，执行for char in unsplit_string:，然后再输入if char.isspace(): break，然后再输入for char in unsplit_string:。

但是，这并不能真正帮助任何事情，因为raw_input已经必须将整个事件一次读入内存。因此，如果您阅读的字符串足够大，则可能需要更改为sys.stdin.read。（关闭输入缓冲并一次读取1个字节显然会给你提供最好的内存使用，但可能会让事情变得非常慢，所以你需要权衡。通常，让Python/stdio使用默认缓冲区就足够了。）

来源

2013-02-27 19:23:06 abarnert

optmise此代码最小运行时间

回答

相关问题