首页 / PYTHON / 一个循环？Python

一个循环？Python

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了一个循环？Python，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7396字，纯文字阅读大概需要11分钟。

内容图文

所以我写了这个函数给出了可能的数字,它必须找到构成给定数字的可能数字内的两个数字.但是,我仍在学习Python(一种非常好的语言),所以我只能使用一组有限的函数.

我创建了这个函数：

def sumPair(theList, n):

    theList = charCount(theList) #charCount is a function i made to convert the list into a dictionary
    for i in theList:
        for a,b in theList.iteritems():
            print a,b
            if a + i == n:
                if theList[b] > 1:
                    return [i, b]
                if a != i:
                    return [i, b]
        return "[]"
print sumPair([6,3,6,8,3,2,8,3,2], 11)

就像我说的,它找到了两个加起来给定数字的数字. charCount是我编写的一个函数,它将数组添加到字典中.

在这个程序中,我确保值大于1,以防添加的数字相同.有时如果它检查10的总和并给你5的数字,它只会将5添加到自身并返回10.这就是if theList [b]> 1：
在那儿.

为什么我在这里？我的导师对两个循环不满意.我花了5个小时进行故障排除,无处可去.我需要将此程序转换为单循环程序.

我整天都花在这上面,我不是想让你做我的作业,我真的被困住了,我需要你的帮助.我听说我应该检查是否存在一个密钥才能完成.

解决方法:

用铅笔和纸或者甚至只看纸上的数字行,如何用手来做这个问题总是有助于思考问题.然而,更好的解决方案起初可能看起来过于复杂,而且它们的优势可能不是那么清楚 – 见gnibbler’s solution(他的答案是我个人的赢家,见下文).

首先,您需要将一个数字与所有其他数字进行比较.然后使用其余的第二个数字等.当使用朴素方法时,使用单个处理器时无法避免两个嵌套循环.那么时间复杂度总是为O(n ^ 2),其中n是序列的长度.事实是,一些循环可能隐藏在像list或index.index()这样的操作中,这在原则上不能使解决方案更好.

想象一下数字的笛卡尔积 – 它由数字的夫妻组成.这些夫妇中有n ^ 2个,但是相对于加法操作的可交换性质,大约一半是相同的,并且其中n个是与itsef的对.这意味着您只需要检查n ^ 2/2 – n对.如果它们适合测试,最好避免循环遍历不必要的对,而不是稍后进行测试：

for each first element in theList:
    for each second element in the rest of theList from the checked one on:
        if the first and the second elements give the solution:
            report the result
            possibly early break if only the first should be reported

对于已选中的列表的其余部分使用切片,使用第一个(也可能是第二个)循环中的enumerate()来了解索引.

最小化循环中的操作总是好主意.想想内循环体是最多次完成的.这样,您可以在进入内循环之前计算搜索到的数字：searching = sum – first.然后,如果在列表的其余部分中搜索,则第二个循环加上if可以替换为：

[此处出现更多完整解决方案后编辑]

这是找到第一次出现或无的O(n ^ 2)解决方案(纯Python,简单,没有图书馆,内置函数和仅切片,几行)：

def sumPair(theList, n):
    for index, e in enumerate(theList):     # to know the index for the slicing below
        complement = n - e                  # we are searching for the complement
        if complement in theList[index+1:]: # only the rest is searched
            return e, complement            

print sumPair([6,3,6,8,3,2,8,3,2], 11)

[在gnibbler评论切片和复制后添加]

gnibbler是关于切片的.切片是副本. (问题是切片是否未使用“写入时复制”技术进行优化 – 我不知道.如果是,那么切片将是一个廉价的操作.)为了避免复制,可以使用列表进行测试.index()方法,允许传递起始索引.唯一奇怪的是,当找不到该项时,它会引发ValueError异常.这样,if补码……必须由try替换…除外：

def sumPair2(theList, n):
    for ind, e in enumerate(theList):
        try:
            theList.index(n - e, ind + 1)
            return e, n - e
        except ValueError:
            pass

Gnibbler的评论让我更多地思考这个问题.事实是集合可以接近O(1)来测试它是否包含元素和O(n)来构造集合.对于非数字元素(其中集合类型不能实现为位数组)并不清楚.当哈希数组进入游戏并且可能使用其他技术解决可能的冲突时,质量取决于实现.

如有疑问,请测量.这里gnibbler的解决方案稍作修改,与其他解决方案一样：

import timeit

def sumPair(theList, n):
    for index, e in enumerate(theList):
        if n - e in theList[index+1:]:
            return e, n - e

def sumPair2(theList, n):
    for ind, e in enumerate(theList):
        try:
            theList.index(n - e, ind + 1)
            return e, n - e
        except ValueError:
            pass

def sumPair_gnibbler(theList, n):
    # If n is even, check whether n/2 occurs twice or more in theList
    if n%2 == 0 and theList.count(n/2) > 1:
        return n/2, n/2

    theSet = set(theList)
    for e in theSet:
        if n - e in theSet:
            return e, n - e

该问题的原始数字用于第一次测试.当无法找到解决方案时,n = 1会导致最坏的情况：

theList = [6,3,6,8,3,2,8,3,2]

n = 11
print '---------------------', n
print sumPair(theList, n), 
print timeit.timeit('sumPair(theList, n)', 'from __main__ import sumPair, theList, n', number = 1000)

print sumPair2(theList, n), 
print timeit.timeit('sumPair2(theList, n)', 'from __main__ import sumPair2, theList, n', number = 1000)

print sumPair_gnibbler(theList, n),
print timeit.timeit('sumPair_gnibbler(theList, n)', 'from __main__ import sumPair_gnibbler, theList, n', number = 1000)

n = 1
print '---------------------', n
print sumPair(theList, n), 
print timeit.timeit('sumPair(theList, n)', 'from __main__ import sumPair, theList, n', number = 1000)

print sumPair2(theList, n), 
print timeit.timeit('sumPair2(theList, n)', 'from __main__ import sumPair2, theList, n', number = 1000)

print sumPair_gnibbler(theList, n),
print timeit.timeit('sumPair_gnibbler(theList, n)', 'from __main__ import sumPair_gnibbler, theList, n', number = 1000)

它在我的控制台上产生以下输出：

--------------------- 11
(3, 8) 0.00180958639191
(3, 8) 0.00594907526295
(8, 3) 0.00124991060067
--------------------- 1
None 0.00502748219333
None 0.026334041968
None 0.00150958864789

从短的数字序列和一个特殊情况来看,从时间复杂性的角度来说,质量是不可能的.无论如何,gnibbler的解决方案赢了.

当序列包含唯一值时,gnibbler的解决方案使用最多的内存.让我们尝试更长的包含0,1,2,…,9999的序列.n等于11和3000表示具有解决方案的任务.对于n等于30000的情况,无法找到这对数字.必须检查所有元素 – 最坏的情况：

theList = range(10000)

n = 11
print '---------------------', n
print sumPair(theList, n), 
print timeit.timeit('sumPair(theList, n)', 'from __main__ import sumPair, theList, n', number = 100)

print sumPair2(theList, n), 
print timeit.timeit('sumPair2(theList, n)', 'from __main__ import sumPair2, theList, n', number = 100)

print sumPair_gnibbler(theList, n),
print timeit.timeit('sumPair_gnibbler(theList, n)', 'from __main__ import sumPair_gnibbler, theList, n', number = 100)

n = 3000
print '---------------------', n
print sumPair(theList, n), 
print timeit.timeit('sumPair(theList, n)', 'from __main__ import sumPair, theList, n', number = 100)

print sumPair2(theList, n), 
print timeit.timeit('sumPair2(theList, n)', 'from __main__ import sumPair2, theList, n', number = 100)

print sumPair_gnibbler(theList, n),
print timeit.timeit('sumPair_gnibbler(theList, n)', 'from __main__ import sumPair_gnibbler, theList, n', number = 100)

n = 30000
print '---------------------', n
print sumPair(theList, n), 
print timeit.timeit('sumPair(theList, n)', 'from __main__ import sumPair, theList, n', number = 100)

print sumPair2(theList, n), 
print timeit.timeit('sumPair2(theList, n)', 'from __main__ import sumPair2, theList, n', number = 100)

print sumPair_gnibbler(theList, n),
print timeit.timeit('sumPair_gnibbler(theList, n)', 'from __main__ import sumPair_gnibbler, theList, n', number = 100)

请注意,序列要长得多.该测试仅重复100次,以便在合理的时间内得到结果. (除非您将其除以数字,否则时间无法与之前的测试进行比较.)它在我的控制台上显示以下内容：

--------------------- 11
(0, 11) 0.00840137682165
(0, 11) 0.00015695881967
(0, 11) 0.089894683992
--------------------- 3000
(0, 3000) 0.0166750746034
(0, 3000) 0.00966040735374
(0, 3000) 0.12532849753
--------------------- 30000
None 180.328006493
None 163.651082944
None 0.204691100723

对于非最坏情况,gnibbler的解决方案似乎很慢.原因是它需要经历所有序列的准备阶段.天真的解决方案在第一次通过的大约三分之一中找到了数字.什么告诉anythig是最糟糕的情况. gnibbler的解决方案快了大约1000倍,并且对于更长的序列,差异会增加. Gnibbler的解决方案是明显的赢家.

内容总结

以上是互联网集市为您收集整理的一个循环？Python全部内容，希望文章能够帮你解决一个循环？Python所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/765452.html

来源：【匿名】