>

이것은 문자열 입력을받는 미니언 게임 의 구현입니다. 미리 정해진 두 명의 플레이어 사이에서 승자를 선언합니다.

논리는 플레이어 1이 모음으로 시작하지 않는 모든 시퀀스 단어를 가져오고 플레이어 2는 입력 문자열에서 모음으로 시작하는 모든 시퀀스 단어를 가져옵니다.

목표 : 성능 최적화. 코드가 모든 테스트 사례를 통과했지만 성능을 조정할 위치가 확실하지 않습니다.

1000 자 단어의 경우 시간 통계는 다음과 같습니다.

  • 실제 0m10.142 초
  • 사용자 0m6.386s
  • sys 0m0.743s
<시간>
import string
import sys
import itertools
def minion(str):
    person_a_name = 'Stuart'
    person_b_name = 'Kevin'
    letter_list = [a for a in str]
    l = len(letter_list)
    vowel = ['A','E','I','O','U']
    consonants = ['Q','W','R','T','Y','P','S','D','F','G','H','J','K','L','Z','X','C','V','B','N','M']
    all_word = []
    person_a_words = []
    person_b_words = []
    all_word = [letter_list[start:end+1] for start in xrange(l) for end in xrange(start, l)]
    for array in all_word:
        if array[0] in vowel:
            person_b_words.append(array)
    for array in all_word:
        if array[0] in consonants:
            person_a_words.append(array)
    if len(person_a_words) == len(person_b_words):
        print 'Draw'
    if len(person_a_words) > len(person_b_words):
        print person_a_name, len(person_a_words)
    if len(person_b_words) > len(person_a_words):
        print person_b_name, len(person_b_words)
def main():
    str = raw_input()
    minion(str.upper())
if __name__ == '__main__':
    main()

샘플 입력/출력 :


banana
Stuart 12
guavaisanotherfruit     
Kevin 98


  • 답변 # 1

    성능에 큰 타격은 아마도이 코드 블록에서 나올 것입니다.이 배열에서는 많은 배열 조작과 루핑을합니다 :

    all_word = [letter_list[start:end+1] for start in xrange(l)
                                         for end in xrange(start, l)]
    for array in all_word:
        if array[0] in vowel:
            person_b_words.append(array)
    for array in all_word:
        if array[0] in consonants:
            person_a_words.append(array)
    if len(person_a_words) == len(person_b_words):
        print 'Draw'
    if len(person_a_words) > len(person_b_words):
        print person_a_name, len(person_a_words)
    if len(person_b_words) > len(person_a_words):
        print person_b_name, len(person_b_words)
    
    

    배열에 추가하는 것은 목록을 반복하는 것처럼 (상대적으로) 비싼 작업입니다. 여기에 여러 가지 최적화가 있습니다.[수정 :나는 그것들을 생각한 순서대로 썼습니다;마지막 항목에서 성능이 크게 향상됩니다. 나머지 항목은 여기에 직접 적용 할 수없는 경우에도 여전히 유익하기 때문에 남겨두고 있습니다.]

    all_word를 한 번만 반복합니다.동일한 루프 반복에서 자음과 모음으로 시작하는지 확인할 수 있습니다.

    for array in all_word:
        if array[0] in vowel:
            person_b_words.append(array)
        elif array[0] in consonants:
            person_a_words.append(array)
    
    

    all_word에 대한 반복을 잘라 냈습니다. all_word가 크면 크게 절약됩니다.

    단어에 단어를 저장하지 않고 카운트 만하십시오.관심이있는 것은 각 목록의 상대 단어 수입니다. 단어 자체는 중요하지 않습니다. 목록을 변경하는 것보다 정수를 증가시키는 것이 훨씬 쉬우므로 다음을 고려하십시오.

    person_a_words = 0
    person_b_words = 0
    for array in all_word:
        if array[0] in vowel:
            person_b_words += 1
        elif array[0] in consonants:
            person_a_words += 1
    
    

    그리고 마지막에 두 정수를 비교할 수 있습니다. 성능을 향상시켜야합니다.

    all_word를 목록으로 구성하지 마십시오. 생성기를 사용합니다.대괄호를 괄호로 바꾸는 경우 :

    all_word = (letter_list[start:end+1] for start in xrange(l)
                                         for end in xrange(start, l))
    
    

    그러면 이것이 목록 이해 대신 생성자 이해가됩니다. 즉, for 루프에 필요한 요소 만 작성합니다. 계속하기 전에 메모리에 모두 생성하지는 않습니다.

    목록 대신 생성기를 사용하면 점유를 줄이고 프로그램 속도를 높일 수있는 좋은 방법입니다.

    all_word를 사용해야합니까?start의 각 값에 대해 결과 단어의 첫 글자가 동일하며 이는 (l - start) 를 제공합니다  다른 단어. 실제로 단어를 만들 필요는 없습니다. 첫 글자와 몇 개의 별개의 단어를 만드는지 신경 써야합니다.

    각 개인의 점수에 별개의 단어를 직접 추가 할 수 있습니다 :

    person_a_words = 0
    person_b_words = 0
    for idx, letter in enumerate(letter_list):
        if letter in vowel:
            person_b_words += len(letter_list) - idx
        else:
            person_a_words += len(letter_list) - idx
    
    

    이것은 상당히 빠릅니다 : 1.5m 문자열로 이것을 실행했고 ~ 1.5 초 안에 끝났습니다.

    기타 비 성능 관련 의견 :

    str 를 사용하지 마십시오  변수 이름으로;내장을 재정의하는 것은 나쁜 습관입니다.

    문자열, sys 및 itertools 모듈을 가져 왔지만 사용하지 않았습니다. 왜?

    PEP 8은 목록에서 쉼표 뒤에 공백이 필요합니다. 이것을 vowel 에 추가해야합니다  그리고 consonants .

    list() 를 호출하여 문자열의 개별 문자를 얻을 수 있습니다  그 위에. 이 통화는 동일합니다 :

    letter_list = [a for a in my_string]
    letter_list = list(my_string)
    
    

    이 경우에도 먼저 목록을 강제 할 필요는 없습니다. 문자열의 문자를 직접 반복 할 수 있습니다.

    letter_list 의 길이를 지정할 필요가 없습니다  변수, 특히 l 와 같이 설명이없는 이름이 아닌 변수 . 코드를 읽기 어렵게 만듭니다.

    함수 이름은 특별히 도움이되지 않습니다. 이상적으로 함수의 기능에 대한 아이디어를 제공해야합니다. 결과를 설명 할 수있는 docstring도 있어야합니다.

    person_a* 의 이름을 바꾸겠습니다.  그리고 person_b*   consonant* 가 될 변수  그리고 vowel* 코드를보다 쉽게 ​​읽을 수 있도록합니다. A와 B는 실제로 아무 의미가 없습니다 (그리고 증거로서, 나는 그 문장을 처음 썼을 때 잘못된 길을 찾았습니다).

    함수에서 몇 가지 작업 (모음 모음 단어 또는 자음 부분 단어가 더 있는지 확인)을 수행하고 화면에 인쇄합니다 (결과). 하나는 작업을 수행하고 다른 하나는 결과를 수행하는 두 가지 기능으로 구분하는 것이 좋습니다.

    그러면 모음과 자음의 작업을 더 쉽게 재사용 할 수 있습니다.

    가독성을 돕기 위해 마지막에 비교할 때 동일한 순서로 변수를 유지합니다. 즉,

    if vowel_count > consonant_count:
        print("Vowels victorious!")
    elif vowel_count < consonant_count:
        print("Consonants champion!")
    else:
        print("Draw!")
    
    

  • 답변 # 2

    코드에서 성능 불이익으로 강조하고 싶은 두 가지 사항이 있습니다.

    가능한 모든 단어 조합을 생성 할 때 메모리 사용, 단어 길이를 늘릴 때 지수

    점수 계산에 불필요한 복잡성

    이 점에 뛰어 들기 전에 alexwlchan과 SuperBiasedMan이 다른 코드 냄새와 관련하여 좋은 포인터를 제공했다고 말하고 싶습니다.

    지수 메모리 사용량

    정말 눈에 띄는 줄만 있고 텍스트 길이가 길어지면 메모리가 많이 필요합니다 :

    all_word = [letter_list[start:end+1] 
                   for start in xrange(length) 
                      for end in xrange(start, length)]
    
    

    length = 4 의 텍스트에서 일부 숫자를 수행하도록합시다 abcd 에서처럼 다음과 같은 단어 조합이 제공됩니다.

    첫 글자로 시작하는 4 단어 :abcd,abc,ab,a

    두 번째 문자로 시작하는 3 단어 :bcd,bc,b

    세 번째 문자로 시작하는 두 단어 :cd,c

    네번째 문자로 시작하는 단어 :d

    즉, 게임에서 \ $N \ $길이의 텍스트에 사용할 수있는 총점은 \ $N + N-1 + N-2 + ... + 2 + 1 \ $의 합입니다. . 운좋게도 이 수를 계산하는 쉬운 공식: \ $(N + 1) * N/2 \ $. 아래 표에 나와 있습니다.

    그러나 그것은 메모리 포인트를 볼 때 적어도 각 단어의 길이를 살펴볼 필요가 있습니다. \ $N = 4 \ $를 사용한 예제를 계속 진행하면 길이가 1 인 단어 4 개, 길이가 2 인 단어 3 개 등이 있습니다. 일반적으로 \ $N \ cdot 1 + (N-1) \ cdot 2 + ... + 2 \ cdot (N-2) + 1 \ cdot N \ $. 나는 이것을위한 일반적인 공식1을 찾지 못했지만 그것을 계산하는 간단한 파이썬 함수를 만들었다 :

    # Shift the range index by +1 so that we get the proper 1 to N sequence
    sum( (n+1-k)*k for k in xrange(1, n+1) )
    
    

    아래의 표에는 텍스트의 길이에 해당하는 포인트/단어 수와 이러한 단어를 저장하는 데 필요한 문자 수가 나와 있습니다. 보다시피,이 숫자는 매우 빠르게 증가합니다. 마지막 줄은 원래 코드에서 memory_profiler 를 사용할 때 메가 바이트 단위의 메모리 사용량입니다.

    text length :   4   10     50     100       500       1000         5000 
    points/words:  10   55   1275    5050    125250     500500      1250250
    characters:    20  220  22100  171700  20958500  167167000  20845835000
    usage in MiB:       ~0   0.24    1.52    185.68    1251.93     too much
    
    
    불필요한 복잡성

    원래 문제 진술을 검토 할 때 모음이나 자음으로 시작하는 단어의 포인트를 계산해야합니다. 당신은 실제로 지금 단어를 할 필요가 없습니다.

    이를 이전 섹션의 지식과 결합하여 \ $Nk \ $단어를 생성 할 수있는 텍스트에서 \ $k \ $라는 특정 위치에서 다음과 같은 방법으로 전체 복잡성이 상당히 줄어 듭니다.

    def count_minion_words(text):
        text_length = len(text)
        word_count_vowels = 0
        word_count_consonants = 0
        for (index, character) in enumerate(text):
            if character in ['A', 'E', 'I', 'O', 'U']:
                word_count_vowels += text_length - index
            else:
                word_count_consonants += text_length - index
        return (word_count_vowels, word_count_consonants)
    
    

    원본 텍스트 외에 메모리가 필요하지 않으며 전체 텍스트를 한 번에 반복하며 모음 또는 자음으로 시작하는 단어 수에 대한 포인트를 계산합니다. 텍스트 길이가 1000 이상인 경우 자유롭게 테스트하십시오. 1.5m 길이의 텍스트로 테스트했으며 0.35 초 내에 완료되었습니다.

    <시간>

    1추가 :Mathematica SE에 대한 질문 I 이제 공식은 다음과 같습니다.

    $$ \ frac {n (n + 1) (n + 2)} {6} $$

  • 답변 # 3

    여러 가지 실적 아이디어가 있지만 다른 아이디어보다 작지만 일관된 우수한 실적 선택은 좋은 마음가짐입니다.

    사소한 메모, 당신은 list() 를 사용하여 문자열에서 문자 목록을 얻을 수 있습니다 . 따라서 목록 이해 대신 letter_list = list(str) 를 사용하십시오. . str 와 다른 이름을 사용해야한다는 것에 동의합니다. 하지만 지금은 성능에 중점을두고 있습니다.

    또한 len(letter_list) 를 호출 할 때  문자열의 길이를 얻는 것보다 느리므로 len(str) 를 호출하십시오.  대신에. 일반적으로 문자열은 목록보다 빠릅니다. 더 복잡한 목록 기능이 필요하지 않으면 문자열을 사용하십시오. 따라서 모음과 자음 목록을 만드는 대신 문자열로 만듭니다.

    그러나 목록보다 훨씬 더 효율적인 정수입니다. 그리고 마치 각 개인의 단어 목록을 중요한 것처럼 만듭니다. 그러나 필요한 것은 이러한 값의 개수입니다. 모든 append 교체   += 1 와 함께  훨씬 빠를 것입니다. 이것이 내가 느리게하는 주요 원인입니다.

    for array in all_word:
        if array[0] in vowel:
            person_b_words += 1
        else:
            person_a_words += 1
    
    

    else 를 사용하는 경우에도 한 번만 반복하면됩니다. . sum 를 사용하는 것이 더 빠를 수 있습니다  여기서 더 복잡해져 실제로는 도움이되지 않을 수 있습니다. 더 알고 싶은 분은 나중에 설명해주세요.

    물론 이제 더 이상 여러 개의 len 가 필요하지 않습니다.  호출하면 변수가 모두 정수이므로 변수를 직접 비교할 수 있습니다. 또한 elif 를 사용해야합니다  그리고 else  조건 중 하나만 알고 있기 때문에 진술이 가능합니다.

    if person_a_words == person_b_words:
        print 'Draw'
    elif person_a_words > person_b_words:
        print person_a_name, person_a_words
    else:
        print person_b_name, person_b_words
    
    

    당신이 할 수있는 또 다른 것은 모든 시퀀서를 반복하는 더 지능적인 방법을 찾는 것입니다. 거대한 문자열 목록을 만들지 만 각각의 첫 글자 만 필요합니다. 인덱스 범위를 기반으로 한 거대한 목록이 아닌 각 첫 글자를 적절한 횟수만큼 반복하는 루프를 사용하는 것이 더 쉽습니다.

  • 답변 # 4

    Python2를 사용하면 효과가있었습니다.

    def minion_game(s):
        Stuart, Kevin = 0,0
        length = len(s)
        for idx,sub in enumerate(s):
            if sub in 'AEIOU': Kevin += length - idx
            else: Stuart += length - idx
        print(['Draw','Kevin {}'.format(Kevin),'Stuart {}'.format(Stuart)][0 if Kevin == Stuart else 1 if Kevin>Stuart else 2])
    
    if __name__ == '__main__':
        s = raw_input()
        minion_game(s)
    
    

  • 이전 javascript - 간단한 Nodejs 사용자 관리 시스템
  • 다음 javascript - 대부분의 물을 담은 용기