什么是此代码而不是double for循环（python）的更快版本？ [英] What is a faster version of this code instead of the double for-loop (python)?

问题描述

当我将代码提交到（来自我的大学）对其进行更正的网站上时，对于其标准而言，这太长了。
这是代码：

When I hand this code in on a site (from my university) that corrects it, it is too long for its standards. Here is the code:

def pangram(String):
    import string
    alfabet = list(string.ascii_lowercase)
    interpunctie = string.punctuation + "’" + "123456789"
    String = String.lower()
    string_1 = ""
    for char in String:                    
        if not char in interpunctie:
            string_1 += char
    string_1 = string_1.replace(" ", "")    
    List = list(string_1)
    List.sort()                            
    list_2 = []
    for index, char in enumerate(List):     
        if not List[index] == 0:
            if not (char == List[index - 1]):
                list_2.append(char)
    return list_2 == alfabet              

def venster(tekst):
    pangram_gevonden = False
    if pangram(tekst) == False: 
        return None
    for lengte in range(26, len(tekst)):
        if pangram_gevonden == True:
            break
        for n in range(0, len(tekst) - lengte):
            if pangram(tekst[n:lengte+n]):
                kortste_pangram = tekst[n:lengte+n]
                pangram_gevonden = True
                break
    return kortste_pangram

第一个函数（pangram）很好，它确定给定的字符串是否是一个pangram：它至少包含一次字母表中的所有字母。

So the first function (pangram) is fine and it determines whether or not a given string is a pangram: it contains all the letters of the alphabet at least once.

第二个函数检查该字符串（通常是较长的tekst）是否是一个pangram，如果是，则返回该tekst中最短的pangram（即使英语不正确）。如果有两个长度相同的字母：返回最左边的字母。

The second function checks whether or not the string(usually a longer tekst) is a pangram or not and if it is, it returns the shortest possible pangram within that tekst (even if that's not correct English). If there are two pangrams with the same length: the most left one is returned.

对于第二个功能，我使用了double for循环：第一个确定了长度。被检查的字符串（26-len（string）），第二个字符串使用此长度在每个可能的点遍历该字符串，以检查它是否是字符集。一旦找到最短（也是最左边）的pangram，它就会脱离两个for循环。

For this second function I used a double for loop: The first one determines the length of the string that's being checked (26 - len(string)) and the second one uses this length to go through the string at each possible point to check if it is a pangram. Once the shortest (and most left) pangram is found, it breaks out of both of the for loops.

（显然）这仍然需要太长时间。因此，我想知道是否有人知道解决该第二功能的更快方法。

However this (apparantly) still takes too long. So i wonder if anyone knew a faster way of tackling this second function. It doesn't necessarily have to be with a for loop.

预先感谢

卢卡斯

推荐答案

创建地图 {letter; int} 和 activecount 计数器。

使两个索引左和 right ，将它们设置为0。

Create a map {letter; int} and activecount counter.
Make two indexes left and right, set them in 0.

向右移动 索引。

如果 l = s [right] 是字母，则地图键 l 。

如果值变为非零-递增 activecount 。

继续直到 activecount 达到26

Move right index.
If l=s[right] is letter, increment value for map key l.
If value becomes non-zero - increment activecount.
Continue until activecount reaches 26

现在移动向左索引。

如果 l = s [left] 是字母，映射键 l 的减量值。

如果值变为零-递减 activecount 并停止。

Now move left index.
If l=s[left] is letter, decrement value for map key l.
If value becomes zero - decrement activecount and stop.

开始向右移动 重新索引，依此类推。

Start moving right index again and so on.

在

时左和右之间的最小差>
activecount == 26 对应最短的连字符。

Minimal difference between left and right while
activecount==26 corresponds to the shortest pangram.

算法是线性的。

仅包含字母 abcd的小写字母的字符串的示例代码。返回包含来自 abcd 的所有字母的最短子字符串的长度。

Example code for string containing only lower letters from alphabet 'abcd'. Returns length of the shortest substring that contains all letters from abcd. Does not check for valid chars, is not thoroughly tested.

import string
def findpangram(s):
    alfabet = list(string.ascii_lowercase)
    map = dict(zip(alfabet, [0]*len(alfabet)))
    left = 0
    right = 0
    ac = 0
    minlen = 100000

    while left < len(s):

        while right < len(s):
            l = s[right]
            c = map[l]
            map[l] = c + 1
            right += 1
            if c==0:
                ac+=1
                if ac == 4:
                    break
        if ac < 4:
            break
        if right - left < minlen:
            minlen = right - left

        while left < right:
            l = s[left]
            c = map[l]
            map[l] = c - 1
            left += 1
            if c==1:
                ac-=1
                break

        if right - left + 2 < minlen:
            minlen = right - left + 1
    return minlen

print(findpangram("acacdbcca"))

这篇关于什么是此代码而不是double for循环（python）的更快版本？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！