Programing

요소를 제거하지 않고 세트에서 요소를 검색하는 방법은 무엇입니까?

lottogame 2020. 2. 28. 18:37
반응형

요소를 제거하지 않고 세트에서 요소를 검색하는 방법은 무엇입니까?

다음을 가정하십시오.

>>> s = set([1, 2, 3])

내가 s하지 않고 어떻게 가치 (값)를 얻 s.pop()습니까? 제거 할 수있을 때까지 항목을 세트에 그대로두고 싶습니다. 다른 호스트에 대한 비동기 호출 후에 만 ​​확인할 수있는 것입니다.

빠르고 더러운 :

>>> elem = s.pop()
>>> s.add(elem)

그러나 더 나은 방법을 알고 있습니까? 일정한 시간에 이상적입니다.

전체 세트를 복사 할 필요가없는 두 가지 옵션 :

for e in s:
    break
# e is now an element from s

또는...

e = next(iter(s))

그러나 일반적으로 세트는 인덱싱 또는 슬라이싱을 지원하지 않습니다.

가장 작은 코드는 다음과 같습니다.

>>> s = set([1, 2, 3])
>>> list(s)[0]
1

분명히 이것은 세트의 각 멤버를 포함하는 새 목록을 생성하므로 세트가 매우 큰 경우 좋지 않습니다.

서로 다른 접근 방식에 대한 타이밍 수치를 제공하려면 다음 코드를 고려하십시오. get ()은 Python의 setobject.c에 대한 사용자 정의 추가이며 요소를 제거하지 않고 pop () 일뿐입니다.

from timeit import *

stats = ["for i in xrange(1000): iter(s).next()   ",
         "for i in xrange(1000): \n\tfor x in s: \n\t\tbreak",
         "for i in xrange(1000): s.add(s.pop())   ",
         "for i in xrange(1000): s.get()          "]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100))")
    try:
        print "Time for %s:\t %f"%(stat, t.timeit(number=1000))
    except:
        t.print_exc()

출력은 다음과 같습니다.

$ ./test_get.py
Time for for i in xrange(1000): iter(s).next()   :       0.433080
Time for for i in xrange(1000):
        for x in s:
                break:   0.148695
Time for for i in xrange(1000): s.add(s.pop())   :       0.317418
Time for for i in xrange(1000): s.get()          :       0.146673

이는 for / break 솔루션이 가장 빠르다는 것을 의미합니다 (때로는 사용자 정의 get () 솔루션보다 빠름).

tl; dr

for first_item in muh_set: breakPython 3.x에서 최적의 접근 방식으로 남아 있습니다. 저주, 귀도

너 이거 해

wr 에서 추정 한 또 다른 Python 3.x 타이밍 세트에 오신 것을 환영합니다 . 탁월한 Python 2.x 전용 응답 . AChampion 의 똑같이 도움이되는 Python 3.x 특정 응답 과는 달리 아래의 타이밍 은 위에서 제안한 이상치 해결책 도 포함합니다.

큰 기쁨을위한 코드 스 니펫

켜고 조정하고 시간을 정하십시오.

from timeit import Timer

stats = [
    "for i in range(1000): \n\tfor x in s: \n\t\tbreak",
    "for i in range(1000): next(iter(s))",
    "for i in range(1000): s.add(s.pop())",
    "for i in range(1000): list(s)[0]",
    "for i in range(1000): random.sample(s, 1)",
]

for stat in stats:
    t = Timer(stat, setup="import random\ns=set(range(100))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

빠르게 쓸모없는 영원한 타이밍

보다! 가장 빠르거나 느린 코드 조각으로 주문 :

$ ./test_get.py
Time for for i in range(1000): 
    for x in s: 
        break:   0.249871
Time for for i in range(1000): next(iter(s)):    0.526266
Time for for i in range(1000): s.add(s.pop()):   0.658832
Time for for i in range(1000): list(s)[0]:   4.117106
Time for for i in range(1000): random.sample(s, 1):  21.851104

온 가족을위한 페이스 플랜트

당연히 수동 반복은 다음으로 빠른 솔루션 보다 2 배 이상 빠릅니다 . 수동 반복이 4 배 이상 빠르 던 Bad Old Python 2.x 일과의 격차가 줄어들었지만 가장 장황한 솔루션이 최고 라는 PEP 20 열성에 실망합니다 . 집합의 첫 번째 요소를 추출하기 위해 집합을 목록으로 변환하는 것은 예상만큼 끔찍합니다. 귀도에게 감사합니다. 그의 빛이 우리를 계속 인도 할 수 있기를 바랍니다.

놀랍게도 RNG 기반 솔루션은 끔찍합니다. 목록 변환은 좋지 않지만 random 실제로 는 끔찍한 소스 케이크가 필요합니다. 난수 신을 위해 너무 많은 .

나는 단지 비정질을 원합니다. 그들은 set.get_first()이미 우리를 위해 방법을 PEP 할 것 입니다. 이 글을 읽고 있다면, "제발. 뭔가 해봐."

임의의 요소를 원하므로 다음과 같이 작동합니다.

>>> import random
>>> s = set([1,2,3])
>>> random.sample(s, 1)
[2]

설명서에는의 성능에 대해서는 언급되어 있지 않습니다 random.sample. 방대한 목록과 방대한 집합을 사용하여 실제로 빠른 실험적 테스트에서, 그것은 목록을위한 일정한 시간 인 것처럼 보이지만 집합을위한 것은 아닙니다. 또한 집합에 대한 반복은 무작위가 아닙니다. 순서는 정의되지 않았지만 예측 가능합니다.

>>> list(set(range(10))) == range(10)
True

임의성이 중요하고 일정한 시간 (큰 세트)에 많은 요소가 필요한 경우 random.sample먼저 목록을 사용 하고 변환합니다.

>>> lst = list(s) # once, O(len(s))?
...
>>> e = random.sample(lst, 1)[0] # constant time

함수가 다른 세트에서 어떻게 수행되는지 궁금해하여 벤치 마크를 수행했습니다.

from random import sample

def ForLoop(s):
    for e in s:
        break
    return e

def IterNext(s):
    return next(iter(s))

def ListIndex(s):
    return list(s)[0]

def PopAdd(s):
    e = s.pop()
    s.add(e)
    return e

def RandomSample(s):
    return sample(s, 1)

def SetUnpacking(s):
    e, *_ = s
    return e

from simple_benchmark import benchmark

b = benchmark([ForLoop, IterNext, ListIndex, PopAdd, RandomSample, SetUnpacking],
              {2**i: set(range(2**i)) for i in range(1, 20)},
              argument_name='set size',
              function_aliases={first: 'First'})

b.plot()

여기에 이미지 설명을 입력하십시오

이 그림은 일부 접근 방식 ( RandomSample, SetUnpacking및 ListIndex)이 세트의 크기에 따라 다르며 일반적인 경우 (적어도 성능 이 중요 할 수 있는 경우) 피해야 한다는 것을 명확하게 보여줍니다 . 이미 다른 답변에서 볼 수 있듯이 가장 빠른 방법은 ForLoop입니다.

그러나 일정한 시간 접근법 중 하나를 사용하는 한 성능 차이는 무시할 수 있습니다.

iteration_utilities(면책 조항 : 저자입니다)이 사용 사례에 대한 편의 기능이 포함되어 있습니다. first:

>>> from iteration_utilities import first
>>> first({1,2,3,4})
1

또한 위의 벤치 마크에도 포함 시켰습니다. 다른 두 가지 "빠른"솔루션과 경쟁 할 수 있지만 그 차이는 그리 크지 않습니다.

내가 작성한 유틸리티 기능을 사용합니다. 이름이 임의의 항목이거나 그와 비슷한 것을 암시하기 때문에 다소 오해의 소지가 있습니다.

def anyitem(iterable):
    try:
        return iter(iterable).next()
    except StopIteration:
        return None

설정 요소를 얻는 데 매우 느린 방법 이지만 가장 컴팩트 한 (6 개의 기호) 겉보기 ( PEP 3132 로 가능 ) :

e,*_=s

Python 3.5 이상에서는이 7- 심볼 표현식을 사용할 수 있습니다 ( PEP 448 덕분에 ).

[*s][0]

두 옵션 모두 for-loop 방법보다 약 1000 배 느립니다.

팔로우 @wr. 게시물, 비슷한 결과를 얻습니다 (Python3.5의 경우)

from timeit import *

stats = ["for i in range(1000): next(iter(s))",
         "for i in range(1000): \n\tfor x in s: \n\t\tbreak",
         "for i in range(1000): s.add(s.pop())"]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100000))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

산출:

Time for for i in range(1000): next(iter(s)):    0.205888
Time for for i in range(1000): 
    for x in s: 
        break:                                   0.083397
Time for for i in range(1000): s.add(s.pop()):   0.226570

그러나 기본 집합 (예 : call to remove())을 변경하면 반복 가능한 예제 ( for, iter)에 문제가 발생합니다.

from timeit import *

stats = ["while s:\n\ta = next(iter(s))\n\ts.remove(a)",
         "while s:\n\tfor x in s: break\n\ts.remove(x)",
         "while s:\n\tx=s.pop()\n\ts.add(x)\n\ts.remove(x)"]

for stat in stats:
    t = Timer(stat, setup="s=set(range(100000))")
    try:
        print("Time for %s:\t %f"%(stat, t.timeit(number=1000)))
    except:
        t.print_exc()

결과 :

Time for while s:
    a = next(iter(s))
    s.remove(a):             2.938494
Time for while s:
    for x in s: break
    s.remove(x):             2.728367
Time for while s:
    x=s.pop()
    s.add(x)
    s.remove(x):             0.030272

어때요 s.copy().pop()? 시간을 정하지는 않았지만 작동해야하며 간단합니다. 그러나 전체 세트를 복사하므로 작은 세트에 가장 적합합니다.

다른 옵션은 상관없는 값을 가진 사전을 사용하는 것입니다. 예 :


poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
...

키가 배열이라는 것을 제외하고 키를 세트로 취급 할 수 있습니다.


keys = poor_man_set.keys()
print "Some key = %s" % keys[0]

이 선택의 부작용은 코드가 이전의 이전 set버전의 Python 과 호환되는 것 입니다. 아마도 가장 좋은 대답은 아니지만 다른 옵션입니다.

편집 : 배열이나 세트 대신 dict를 사용했다는 사실을 숨기려면 다음과 같이 할 수도 있습니다.


poor_man_set = {}
poor_man_set[1] = None
poor_man_set[2] = None
poor_man_set[3] = None
poor_man_set = poor_man_set.keys()

참고 URL : https://stackoverflow.com/questions/59825/how-to-retrieve-an-element-from-a-set-without-removing-it



반응형

'Programing' 카테고리의 다른 글

KeyValuePair의 기본값  (0) 2020.02.28
Xcode 프로젝트와 Xcode 작업 영역-차이점  (0) 2020.02.28
Google은 어떤 데이터베이스를 사용합니까?  (0) 2020.02.28
Java의 메소드 매개 변수에 키워드 "final"을 사용해야하는 이유는 무엇입니까?  (0) 2020.02.28
참조 및 값별 자바 스크립트  (0) 2020.02.28

'Programing'의 다른글

  • 현재글요소를 제거하지 않고 세트에서 요소를 검색하는 방법은 무엇입니까?

관련글

댓글

티스토리툴바