针对大输入优化程序

Question

考虑一下：

i=raw_input()
y=int(i.split()[1])
r=raw_input()

for k in range(0,y):
    if raw_input() in r:       #####introduce binary search here
        print "YES"
    else:
        print "NO"

这是一个非常简单的问题程序。程序输入如下：

3 1
34 54 36
54
YES

第一行是no of elements in an array，no of queries

第二行是array

第三个是query，它只是询问元素是否在array中，如果是printYES，则是NO。 这是一个非常琐碎的问题程序。但是问题是，当我用10000和10000查询数组运行这个程序时，程序给出的时间限制超过了其中一个站点。你知道吗

问题是在这方面我可以优化什么？你知道吗

解决方案1，我认为是介绍binary search，但这需要sorting，这将再次采取nlogn，即使使用最快的ie快速排序。你知道吗

有什么想法吗？？？？你知道吗

Answer 1

如注释中所述，您可以通过首先在数字列表中创建一个set表单来显著缩短查找时间。但也要注意，您实际上是在字符串中搜索字符串！例如，在您的示例input 34 54 36中，它还将为input 3或4 5报告YES。您应该将两个输入都转换为int。试试这个：

nums = set(map(int, r.split()))
for k in range(0, y):
    if int(raw_input()) in nums:
        print "YES"
    else:
        print "NO"

还要注意的是，实际上并没有使用“数组中的元素数”输入；不确定这对放坡是否重要。。。你知道吗

Answer 2

我想你想要的是：

elements, queries = map(int, raw_input().split())
array = set(raw_input().split())  # not really an array, but...
if len(array) != elements:
    raise ValueError('unexpected number of elements in array')
for _ in range(queries):
    print 'YES' if raw_input() in array else 'NO'

一个^{}有O(1)成员资格测试，所以元素是可散列的（我选择将字符串直接放入集合中，但您可以将它们转换为整数，整数也是可散列的），并且顺序无关紧要，因此您可以获得显著的加速。你知道吗

注意，elements的数目在Python中并不是很有用，因为您可以简单地接受任意输入并split它。您可以省去针对len(array)的测试，只需解包到_, queries。你知道吗