itertools — Functions creating iterators for efficient looping¶
이 모듈은 APL, Haskell 및 SML의 구성물들에서 영감을 얻은 여러 이터레이터 빌딩 블록을 구현합니다. 각각을 파이썬에 적합한 형태로 개선했습니다.
이 모듈은 자체적으로 혹은 조합하여 유용한 빠르고 메모리 효율적인 도구의 핵심 집합을 표준화합니다. 함께 모여, 순수 파이썬에서 간결하고 효율적으로 특수화된 도구를 구성할 수 있도록 하는 “이터레이터 대수(iterator algebra)”를 형성합니다.
예를 들어, SML은 테이블 화 도구를 제공합니다: 시퀀스 f(0), f(1), ...를 생성하는 tabulate(f). map()과 count()를 결합하여 map(f, count())를 형성해서 파이썬에서도 같은 효과를 얻을 수 있습니다.
General iterators:
이터레이터 |
인자 |
결과 |
예 |
|---|---|---|---|
p [,func] |
p0, p0+p1, p0+p1+p2, … |
|
|
p, n |
(p0, p1, …, p_n-1), … |
|
|
p, q, … |
p0, p1, … plast, q0, q1, … |
|
|
iterable |
p0, p1, … plast, q0, q1, … |
|
|
data, selectors |
(d[0] if s[0]), (d[1] if s[1]), … |
|
|
[start[, step]] |
start, start+step, start+2*step, … |
|
|
p |
p0, p1, … plast, p0, p1, … |
|
|
predicate, seq |
seq[n], seq[n+1], starting when predicate fails |
|
|
predicate, seq |
elements of seq where predicate(elem) fails |
|
|
iterable[, key] |
key(v)의 값으로 그룹화된 서브 이터레이터들 |
|
|
seq, [start,] stop [, step] |
seq[start:stop:step]의 요소들 |
|
|
iterable |
(p[0], p[1]), (p[1], p[2]) |
|
|
elem [,n] |
elem, elem, elem, … 끝없이 또는 최대 n 번 |
|
|
func, seq |
func(*seq[0]), func(*seq[1]), … |
|
|
predicate, seq |
seq[0], seq[1], until predicate fails |
|
|
it, n |
it1, it2, … itn 하나의 이터레이터를 n개의 이터레이터로 나눕니다 |
|
|
p, q, … |
(p[0], q[0]), (p[1], q[1]), … |
|
조합형 이터레이터:
이터레이터 |
인자 |
결과 |
|---|---|---|
p, q, … [repeat=1] |
데카르트 곱(cartesian product), 중첩된 for 루프와 동등합니다 |
|
p[, r] |
r-길이 튜플들, 모든 가능한 순서, 반복되는 요소 없음 |
|
p, r |
r-길이 튜플들, 정렬된 순서, 반복되는 요소 없음 |
|
p, r |
r-길이 튜플들, 정렬된 순서, 반복되는 요소 있음 |
예 |
결과 |
|---|---|
|
|
|
|
|
|
|
|
Itertool Functions¶
The following functions all construct and return iterators. Some provide streams of infinite length, so they should only be accessed by functions or loops that truncate the stream.
- itertools.accumulate(iterable[, function, *, initial=None])¶
Make an iterator that returns accumulated sums or accumulated results from other binary functions.
The function defaults to addition. The function should accept two arguments, an accumulated total and a value from the iterable.
If an initial value is provided, the accumulation will start with that value and the output will have one more element than the input iterable.
대략 다음과 동등합니다:
def accumulate(iterable, function=operator.add, *, initial=None): 'Return running totals' # accumulate([1,2,3,4,5]) → 1 3 6 10 15 # accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 115 # accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 120 iterator = iter(iterable) total = initial if initial is None: try: total = next(iterator) except StopIteration: return yield total for element in iterator: total = function(total, element) yield total
To compute a running minimum, set function to
min(). For a running maximum, set function tomax(). Or for a running product, set function tooperator.mul(). To build an amortization table, accumulate the interest and apply payments:>>> data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8] >>> list(accumulate(data, max)) # running maximum [3, 4, 6, 6, 6, 9, 9, 9, 9, 9] >>> list(accumulate(data, operator.mul)) # running product [3, 12, 72, 144, 144, 1296, 0, 0, 0, 0] # Amortize a 5% loan of 1000 with 10 annual payments of 90 >>> update = lambda balance, payment: round(balance * 1.05) - payment >>> list(accumulate(repeat(90, 10), update, initial=1_000)) [1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]
최종 누적값만 반환하는 유사한 함수에 대해서는
functools.reduce()를 참조하십시오.Added in version 3.2.
버전 3.3에서 변경: Added the optional function parameter.
버전 3.8에서 변경: 선택적 initial 매개 변수를 추가했습니다.
- itertools.batched(iterable, n, *, strict=False)¶
Batch data from the iterable into tuples of length n. The last batch may be shorter than n.
If strict is true, will raise a
ValueErrorif the final batch is shorter than n.Loops over the input iterable and accumulates data into tuples up to size n. The input is consumed lazily, just enough to fill a batch. The result is yielded as soon as the batch is full or when the input iterable is exhausted:
>>> flattened_data = ['roses', 'red', 'violets', 'blue', 'sugar', 'sweet'] >>> unflattened = list(batched(flattened_data, 2)) >>> unflattened [('roses', 'red'), ('violets', 'blue'), ('sugar', 'sweet')]
대략 다음과 동등합니다:
def batched(iterable, n, *, strict=False): # batched('ABCDEFG', 3) → ABC DEF G if n < 1: raise ValueError('n must be at least one') iterator = iter(iterable) while batch := tuple(islice(iterator, n)): if strict and len(batch) != n: raise ValueError('batched(): incomplete batch') yield batch
Added in version 3.12.
버전 3.13에서 변경: Added the strict option.
- itertools.chain(*iterables)¶
Make an iterator that returns elements from the first iterable until it is exhausted, then proceeds to the next iterable, until all of the iterables are exhausted. This combines multiple data sources into a single iterator. Roughly equivalent to:
def chain(*iterables): # chain('ABC', 'DEF') → A B C D E F for iterable in iterables: yield from iterable
- classmethod chain.from_iterable(iterable)¶
chain()의 대체 생성자. 게으르게 평가되는 단일 이터러블 인자에서 연쇄 입력을 가져옵니다. 대략 다음과 동등합니다:def from_iterable(iterables): # chain.from_iterable(['ABC', 'DEF']) → A B C D E F for iterable in iterables: yield from iterable
- itertools.combinations(iterable, r)¶
입력 iterable에서 요소의 길이 r 서브 시퀀스들을 반환합니다.
The output is a subsequence of
product()keeping only entries that are subsequences of the iterable. The length of the output is given bymath.comb()which computesn! / r! / (n - r)!when0 ≤ r ≤ nor zero whenr > n.The combination tuples are emitted in lexicographic order according to the order of the input iterable. If the input iterable is sorted, the output tuples will be produced in sorted order.
Elements are treated as unique based on their position, not on their value. If the input elements are unique, there will be no repeated values within each combination.
대략 다음과 동등합니다:
def combinations(iterable, r): # combinations('ABCD', 2) → AB AC AD BC BD CD # combinations(range(4), 3) → 012 013 023 123 pool = tuple(iterable) n = len(pool) if r > n: return indices = list(range(r)) yield tuple(pool[i] for i in indices) while True: for i in reversed(range(r)): if indices[i] != i + n - r: break else: return indices[i] += 1 for j in range(i+1, r): indices[j] = indices[j-1] + 1 yield tuple(pool[i] for i in indices)
- itertools.combinations_with_replacement(iterable, r)¶
입력 iterable에서 요소의 길이 r 서브 시퀀스들을 반환하는데, 개별 요소를 두 번 이상 반복할 수 있습니다.
The output is a subsequence of
product()that keeps only entries that are subsequences (with possible repeated elements) of the iterable. The number of subsequence returned is(n + r - 1)! / r! / (n - 1)!whenn > 0.The combination tuples are emitted in lexicographic order according to the order of the input iterable. if the input iterable is sorted, the output tuples will be produced in sorted order.
Elements are treated as unique based on their position, not on their value. If the input elements are unique, the generated combinations will also be unique.
대략 다음과 동등합니다:
def combinations_with_replacement(iterable, r): # combinations_with_replacement('ABC', 2) → AA AB AC BB BC CC pool = tuple(iterable) n = len(pool) if not n and r: return indices = [0] * r yield tuple(pool[i] for i in indices) while True: for i in reversed(range(r)): if indices[i] != n - 1: break else: return indices[i:] = [indices[i] + 1] * (r - i) yield tuple(pool[i] for i in indices)
Added in version 3.1.
- itertools.compress(data, selectors)¶
Make an iterator that returns elements from data where the corresponding element in selectors is true. Stops when either the data or selectors iterables have been exhausted. Roughly equivalent to:
def compress(data, selectors): # compress('ABCDEF', [1,0,1,0,1,1]) → A C E F return (datum for datum, selector in zip(data, selectors) if selector)
Added in version 3.1.
- itertools.count(start=0, step=1)¶
Make an iterator that returns evenly spaced values beginning with start. Can be used with
map()to generate consecutive data points or withzip()to add sequence numbers. Roughly equivalent to:def count(start=0, step=1): # count(10) → 10 11 12 13 14 ... # count(2.5, 0.5) → 2.5 3.0 3.5 ... n = start while True: yield n n += step
When counting with floating-point numbers, better accuracy can sometimes be achieved by substituting multiplicative code such as:
(start + step * i for i in count()).버전 3.1에서 변경: step 인자를 추가하고 정수가 아닌 인자를 허용했습니다.
- itertools.cycle(iterable)¶
Make an iterator returning elements from the iterable and saving a copy of each. When the iterable is exhausted, return elements from the saved copy. Repeats indefinitely. Roughly equivalent to:
def cycle(iterable): # cycle('ABCD') → A B C D A B C D A B C D ... saved = [] for element in iterable: yield element saved.append(element) while saved: for element in saved: yield element
This itertool may require significant auxiliary storage (depending on the length of the iterable).
- itertools.dropwhile(predicate, iterable)¶
Make an iterator that drops elements from the iterable while the predicate is true and afterwards returns every element. Roughly equivalent to:
def dropwhile(predicate, iterable): # dropwhile(lambda x: x<5, [1,4,6,3,8]) → 6 3 8 iterator = iter(iterable) for x in iterator: if not predicate(x): yield x break for x in iterator: yield x
Note this does not produce any output until the predicate first becomes false, so this itertool may have a lengthy start-up time.
- itertools.filterfalse(predicate, iterable)¶
Make an iterator that filters elements from the iterable returning only those for which the predicate returns a false value. If predicate is
None, returns the items that are false. Roughly equivalent to:def filterfalse(predicate, iterable): # filterfalse(lambda x: x<5, [1,4,6,3,8]) → 6 8 if predicate is None: predicate = bool for x in iterable: if not predicate(x): yield x
- itertools.groupby(iterable, key=None)¶
iterable에서 연속적인 키와 그룹을 반환하는 이터레이터를 만듭니다. key는 각 요소의 키값을 계산하는 함수입니다. 지정되지 않거나
None이면, key의 기본값은 항등함수(identity function)이고 요소를 변경하지 않고 반환합니다. 일반적으로, iterable은 같은 키 함수로 이미 정렬되어 있어야 합니다.groupby()의 작동은 유닉스의uniq필터와 유사합니다. 키 함수의 값이 변경될 때마다 중단(break)이나 새 그룹을 생성합니다 (이것이 일반적으로 같은 키 함수를 사용하여 데이터를 정렬해야 하는 이유입니다). 이 동작은 입력 순서와 관계없이 공통 요소를 집계하는 SQL의 GROUP BY와 다릅니다.반환되는 그룹 자체는
groupby()와 하부 이터러블(iterable)을 공유하는 이터레이터입니다. 소스가 공유되므로,groupby()객체가 진행하면, 이전 그룹은 이 더는 보이지 않게 됩니다. 따라서, 나중에 데이터가 필요하면, 리스트로 저장해야 합니다:groups = [] uniquekeys = [] data = sorted(data, key=keyfunc) for k, g in groupby(data, keyfunc): groups.append(list(g)) # Store group iterator as a list uniquekeys.append(k)
groupby()는 대략 다음과 동등합니다:def groupby(iterable, key=None): # [k for k, g in groupby('AAAABBBCCDAABBB')] → A B C D A B # [list(g) for k, g in groupby('AAAABBBCCD')] → AAAA BBB CC D keyfunc = (lambda x: x) if key is None else key iterator = iter(iterable) exhausted = False def _grouper(target_key): nonlocal curr_value, curr_key, exhausted yield curr_value for curr_value in iterator: curr_key = keyfunc(curr_value) if curr_key != target_key: return yield curr_value exhausted = True try: curr_value = next(iterator) except StopIteration: return curr_key = keyfunc(curr_value) while not exhausted: target_key = curr_key curr_group = _grouper(target_key) yield curr_key, curr_group if curr_key == target_key: for _ in curr_group: pass
- itertools.islice(iterable, stop)¶
- itertools.islice(iterable, start, stop[, step])
Make an iterator that returns selected elements from the iterable. Works like sequence slicing but does not support negative values for start, stop, or step.
If start is zero or
None, iteration starts at zero. Otherwise, elements from the iterable are skipped until start is reached.If stop is
None, iteration continues until the input is exhausted, if at all. Otherwise, it stops at the specified position.If step is
None, the step defaults to one. Elements are returned consecutively unless step is set higher than one which results in items being skipped.대략 다음과 동등합니다:
def islice(iterable, *args): # islice('ABCDEFG', 2) → A B # islice('ABCDEFG', 2, 4) → C D # islice('ABCDEFG', 2, None) → C D E F G # islice('ABCDEFG', 0, None, 2) → A C E G s = slice(*args) start = 0 if s.start is None else s.start stop = s.stop step = 1 if s.step is None else s.step if start < 0 or (stop is not None and stop < 0) or step <= 0: raise ValueError indices = count() if stop is None else range(max(start, stop)) next_i = start for i, element in zip(indices, iterable): if i == next_i: yield element next_i += step
If the input is an iterator, then fully consuming the islice advances the input iterator by
max(start, stop)steps regardless of the step value.
- itertools.pairwise(iterable)¶
Return successive overlapping pairs taken from the input iterable.
The number of 2-tuples in the output iterator will be one fewer than the number of inputs. It will be empty if the input iterable has fewer than two values.
대략 다음과 동등합니다:
def pairwise(iterable): # pairwise('ABCDEFG') → AB BC CD DE EF FG iterator = iter(iterable) a = next(iterator, None) for b in iterator: yield a, b a = b
Added in version 3.10.
- itertools.permutations(iterable, r=None)¶
Return successive r length permutations of elements from the iterable.
r이 지정되지 않았거나
None이면, r의 기본값은 iterable의 길이이며 가능한 모든 최대 길이 순열이 생성됩니다.The output is a subsequence of
product()where entries with repeated elements have been filtered out. The length of the output is given bymath.perm()which computesn! / (n - r)!when0 ≤ r ≤ nor zero whenr > n.The permutation tuples are emitted in lexicographic order according to the order of the input iterable. If the input iterable is sorted, the output tuples will be produced in sorted order.
Elements are treated as unique based on their position, not on their value. If the input elements are unique, there will be no repeated values within a permutation.
대략 다음과 동등합니다:
def permutations(iterable, r=None): # permutations('ABCD', 2) → AB AC AD BA BC BD CA CB CD DA DB DC # permutations(range(3)) → 012 021 102 120 201 210 pool = tuple(iterable) n = len(pool) r = n if r is None else r if r > n: return indices = list(range(n)) cycles = list(range(n, n-r, -1)) yield tuple(pool[i] for i in indices[:r]) while n: for i in reversed(range(r)): cycles[i] -= 1 if cycles[i] == 0: indices[i:] = indices[i+1:] + indices[i:i+1] cycles[i] = n - i else: j = cycles[i] indices[i], indices[-j] = indices[-j], indices[i] yield tuple(pool[i] for i in indices[:r]) break else: return
- itertools.product(*iterables, repeat=1)¶
Cartesian product of the input iterables.
대략 제너레이터 표현식에서의 중첩된 for-루프와 동등합니다. 예를 들어,
product(A, B)는((x,y) for x in A for y in B)와 같은 것을 반환합니다.중첩된 루프는 매 이터레이션마다 가장 오른쪽 요소가 진행되는 주행 거리계처럼 순환합니다. 이 패턴은 사전식 순서를 만들어서 입력의 이터러블들이 정렬되어 있다면, 곱(product) 튜플이 정렬된 순서로 방출됩니다.
이터러블의 자신과의 곱을 계산하려면, 선택적 repeat 키워드 인자를 사용하여 반복 횟수를 지정하십시오. 예를 들어,
product(A, repeat=4)는product(A, A, A, A)와 같은 것을 뜻합니다.이 함수는 실제 구현이 메모리에 중간 결과를 쌓지 않는다는 점을 제외하고 다음 코드와 대략 동등합니다:
def product(*iterables, repeat=1): # product('ABCD', 'xy') → Ax Ay Bx By Cx Cy Dx Dy # product(range(2), repeat=3) → 000 001 010 011 100 101 110 111 if repeat < 0: raise ValueError('repeat argument cannot be negative') pools = [tuple(pool) for pool in iterables] * repeat result = [[]] for pool in pools: result = [x+[y] for x in result for y in pool] for prod in result: yield tuple(prod)
product()가 실행되기 전에, 입력 이터러블을 완전히 소비하여, 곱을 생성하기 위해 값의 풀(pool)을 메모리에 유지합니다. 따라서, 유한 입력에만 유용합니다.
- itertools.repeat(object[, times])¶
Make an iterator that returns object over and over again. Runs indefinitely unless the times argument is specified.
대략 다음과 동등합니다:
def repeat(object, times=None): # repeat(10, 3) → 10 10 10 if times is None: while True: yield object else: for i in range(times): yield object
A common use for repeat is to supply a stream of constant values to map or zip:
>>> list(map(pow, range(10), repeat(2))) [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
- itertools.starmap(function, iterable)¶
Make an iterator that computes the function using arguments obtained from the iterable. Used instead of
map()when argument parameters have already been “pre-zipped” into tuples.The difference between
map()andstarmap()parallels the distinction betweenfunction(a,b)andfunction(*c). Roughly equivalent to:def starmap(function, iterable): # starmap(pow, [(2,5), (3,2), (10,3)]) → 32 9 1000 for args in iterable: yield function(*args)
- itertools.takewhile(predicate, iterable)¶
Make an iterator that returns elements from the iterable as long as the predicate is true. Roughly equivalent to:
def takewhile(predicate, iterable): # takewhile(lambda x: x<5, [1,4,6,3,8]) → 1 4 for x in iterable: if not predicate(x): break yield x
Note, the element that first fails the predicate condition is consumed from the input iterator and there is no way to access it. This could be an issue if an application wants to further consume the input iterator after takewhile has been run to exhaustion. To work around this problem, consider using more-itertools before_and_after() instead.
- itertools.tee(iterable, n=2)¶
단일 iterable에서 n 개의 독립 이터레이터를 반환합니다.
대략 다음과 동등합니다:
def tee(iterable, n=2): if n < 0: raise ValueError if n == 0: return () iterator = _tee(iterable) result = [iterator] for _ in range(n - 1): result.append(_tee(iterator)) return tuple(result) class _tee: def __init__(self, iterable): it = iter(iterable) if isinstance(it, _tee): self.iterator = it.iterator self.link = it.link else: self.iterator = it self.link = [None, None] def __iter__(self): return self def __next__(self): link = self.link if link[1] is None: link[0] = next(self.iterator) link[1] = [None, None] value, self.link = link return value
When the input iterable is already a tee iterator object, all members of the return tuple are constructed as if they had been produced by the upstream
tee()call. This “flattening step” allows nestedtee()calls to share the same underlying data chain and to have a single update step rather than a chain of calls.The flattening property makes tee iterators efficiently peekable:
def lookahead(tee_iterator): "Return the next value without moving the input forward" [forked_iterator] = tee(tee_iterator, 1) return next(forked_iterator)
>>> iterator = iter('abcdef') >>> [iterator] = tee(iterator, 1) # Make the input peekable >>> next(iterator) # Move the iterator forward 'a' >>> lookahead(iterator) # Check next value 'b' >>> next(iterator) # Continue moving forward 'b'
teeiterators are not threadsafe. ARuntimeErrormay be raised when simultaneously using iterators returned by the sametee()call, even if the original iterable is threadsafe.이 이터레이터 도구에는 상당한 보조 기억 장치가 필요할 수 있습니다 (일시적으로 저장해야 하는 데이터양에 따라 다릅니다). 일반적으로, 다른 이터레이터가 시작하기 전에 하나의 이터레이터가 대부분이나 모든 데이터를 사용하면,
tee()대신list()를 사용하는 것이 더 빠릅니다.
- itertools.zip_longest(*iterables, fillvalue=None)¶
Make an iterator that aggregates elements from each of the iterables.
If the iterables are of uneven length, missing values are filled-in with fillvalue. If not specified, fillvalue defaults to
None.Iteration continues until the longest iterable is exhausted.
대략 다음과 동등합니다:
def zip_longest(*iterables, fillvalue=None): # zip_longest('ABCD', 'xy', fillvalue='-') → Ax By C- D- iterators = list(map(iter, iterables)) num_active = len(iterators) if not num_active: return while True: values = [] for i, iterator in enumerate(iterators): try: value = next(iterator) except StopIteration: num_active -= 1 if not num_active: return iterators[i] = repeat(fillvalue) value = fillvalue values.append(value) yield tuple(values)
If one of the iterables is potentially infinite, then the
zip_longest()function should be wrapped with something that limits the number of calls (for exampleislice()ortakewhile()).
Itertools 조리법¶
이 섹션에서는 기존 itertools를 빌딩 블록으로 사용하여 확장 도구 집합을 만드는 방법을 보여줍니다.
The primary purpose of the itertools recipes is educational. The recipes show
various ways of thinking about individual tools — for example, that
chain.from_iterable is related to the concept of flattening. The recipes
also give ideas about ways that the tools can be combined — for example, how
starmap() and repeat() can work together. The recipes also show patterns
for using itertools with the operator and collections modules as
well as with the built-in itertools such as map(), filter(),
reversed(), and enumerate().
A secondary purpose of the recipes is to serve as an incubator. The
accumulate(), compress(), and pairwise() itertools started out as
recipes. Currently, the sliding_window(), derangements(), and sieve()
recipes are being tested to see whether they prove their worth.
Substantially all of these recipes and many, many others can be installed from the more-itertools project found on the Python Package Index:
python -m pip install more-itertools
Many of the recipes offer the same high performance as the underlying toolset. Superior memory performance is kept by processing elements one at a time rather than bringing the whole iterable into memory all at once. Code volume is kept small by linking the tools together in a functional style. High speed is retained by preferring “vectorized” building blocks over the use of for-loops and generators which incur interpreter overhead.
from itertools import (accumulate, batched, chain, combinations, compress,
count, cycle, filterfalse, groupby, islice, permutations, product,
repeat, starmap, tee, zip_longest)
from collections import Counter, deque
from contextlib import suppress
from functools import reduce
from heapq import heappush, heappushpop, heappush_max, heappushpop_max
from math import comb, isqrt, prod, sumprod
from operator import getitem, is_not, itemgetter, mul, neg, truediv
# ==== 기본 한 줄 함수들 ====
def take(n, iterable):
"반복 가능 객체의 처음 n개 항목을 리스트로 반환합니다."
return list(islice(iterable, n))
def prepend(value, iterable):
"반복 가능 객체의 앞에 단일 값을 추가합니다."
# prepend(1, [2, 3, 4]) → 1 2 3 4
return chain([value], iterable)
def repeatfunc(function, times=None, *args):
"지정된 인자로 함수 호출을 반복합니다."
if times is None:
return starmap(function, repeat(args))
return starmap(function, repeat(args, times))
def flatten(list_of_lists):
"중첩을 한 수준 평탄화합니다."
return chain.from_iterable(list_of_lists)
def ncycles(iterable, n):
"시퀀스 요소를 n번 반복하여 반환합니다."
return chain.from_iterable(repeat(tuple(iterable), n))
def loops(n):
"n번 루프를 돕니다. range(n)과 비슷하지만 정수를 생성하지 않습니다."
# for _ in loops(100): ...
return repeat(None, n)
def tail(n, iterable):
"마지막 n개 항목에 대한 이터레이터를 반환합니다."
# tail(3, 'ABCDEFG') → E F G
return iter(deque(iterable, maxlen=n))
def consume(iterator, n=None):
"이터레이터를 n단계 앞으로 전진시킵니다. n이 None이면 완전히 소모합니다."
# C 속도로 이터레이터를 소모하는 함수를 사용합니다.
if n is None:
deque(iterator, maxlen=0)
else:
next(islice(iterator, n, n), None)
def nth(iterable, n, default=None):
"n번째 항목 또는 기본값을 반환합니다."
return next(islice(iterable, n, None), default)
def quantify(iterable, predicate=bool):
"True 또는 False를 반환하는 서술자가 주어지면, True 결과의 개수를 셉니다."
return sum(map(predicate, iterable))
def first_true(iterable, default=False, predicate=None):
"첫 번째 참(true) 값을 반환하거나 참 값이 없으면 *기본값*을 반환합니다."
# first_true([a, b, c], x) → a or b or c or x
# first_true([a, b], x, f) → a if f(a) else b if f(b) else x
return next(filter(predicate, iterable), default)
def all_equal(iterable, key=None):
"모든 요소가 서로 같으면 True를 반환합니다."
# all_equal('4٤௪౪໔', key=int) → True
return len(take(2, groupby(iterable, key))) <= 1
# ==== 데이터 파이프라인 ====
def unique_justseen(iterable, key=None):
"순서를 유지하면서 고유한 요소를 생성합니다. 방금 본 요소만 기억합니다."
# unique_justseen('AAAABBBCCDAABBB') → A B C D A B
# unique_justseen('ABBcCAD', str.casefold) → A B c A D
if key is None:
return map(itemgetter(0), groupby(iterable))
return map(next, map(itemgetter(1), groupby(iterable, key)))
def unique_everseen(iterable, key=None):
"순서를 유지하면서 고유한 요소를 생성합니다. 지금까지 본 모든 요소를 기억합니다."
# unique_everseen('AAAABBBCCDAABBB') → A B C D
# unique_everseen('ABBcCAD', str.casefold) → A B c D
seen = set()
if key is None:
for element in filterfalse(seen.__contains__, iterable):
seen.add(element)
yield element
else:
for element in iterable:
k = key(element)
if k not in seen:
seen.add(k)
yield element
def unique(iterable, key=None, reverse=False):
"정렬된 순서로 고유한 요소를 생성합니다. 해시 불가능한 입력도 지원합니다."
# unique([[1, 2], [3, 4], [1, 2]]) → [1, 2] [3, 4]
sequenced = sorted(iterable, key=key, reverse=reverse)
return unique_justseen(sequenced, key=key)
def sliding_window(iterable, n):
"데이터를 겹치는 고정 길이 청크 또는 블록으로 수집합니다."
# sliding_window('ABCDEFG', 3) → ABC BCD CDE DEF EFG
iterator = iter(iterable)
window = deque(islice(iterator, n - 1), maxlen=n)
for x in iterator:
window.append(x)
yield tuple(window)
def grouper(iterable, n, *, incomplete='fill', fillvalue=None):
"데이터를 겹치지 않는 고정 길이 청크 또는 블록으로 수집합니다."
# grouper('ABCDEFG', 3, fillvalue='x') → ABC DEF Gxx
# grouper('ABCDEFG', 3, incomplete='strict') → ABC DEF ValueError
# grouper('ABCDEFG', 3, incomplete='ignore') → ABC DEF
iterators = [iter(iterable)] * n
match incomplete:
case 'fill':
return zip_longest(*iterators, fillvalue=fillvalue)
case 'strict':
return zip(*iterators, strict=True)
case 'ignore':
return zip(*iterators)
case _:
raise ValueError('Expected fill, strict, or ignore')
def roundrobin(*iterables):
"각 입력 반복 가능 객체가 소진될 때까지 순환하며 방문합니다."
# roundrobin('ABC', 'D', 'EF') → A D E B F C
# George Sakkis가 제안한 알고리즘
iterators = map(iter, iterables)
for num_active in range(len(iterables), 0, -1):
iterators = cycle(islice(iterators, num_active))
yield from map(next, iterators)
def subslices(seq):
"시퀀스의 비어 있지 않은 모든 연속된 부분 슬라이스를 반환합니다."
# subslices('ABCD') → A AB ABC ABCD B BC BCD C CD D
slices = starmap(slice, combinations(range(len(seq) + 1), 2))
return map(getitem, repeat(seq), slices)
def derangements(iterable, r=None):
"고정점이 없는 r 길이의 순열을 생성합니다."
# derangements('ABCD') → BADC BCDA BDAC CADB CDAB CDBA DABC DCAB DCBA
# Stefan Pochmann이 제안한 알고리즘
seq = tuple(iterable)
pos = tuple(range(len(seq)))
have_moved = map(map, repeat(is_not), repeat(pos), permutations(pos, r=r))
valid_derangements = map(all, have_moved)
return compress(permutations(seq, r=r), valid_derangements)
def iter_index(iterable, value, start=0, stop=None):
"시퀀스 또는 반복 가능 객체에서 값이 나타나는 인덱스를 반환합니다."
# iter_index('AABCADEAF', 'A') → 0 1 4 7
seq_index = getattr(iterable, 'index', None)
if seq_index is None:
iterator = islice(iterable, start, stop)
for i, element in enumerate(iterator, start):
if element is value or element == value:
yield i
else:
stop = len(iterable) if stop is None else stop
i = start
with suppress(ValueError):
while True:
yield (i := seq_index(value, i, stop))
i += 1
def iter_except(function, exception, first=None):
"예외가 발생할 때까지 호출하는 인터페이스를 이터레이터 인터페이스로 변환합니다."
# iter_except(d.popitem, KeyError) → non-blocking dictionary iterator
with suppress(exception):
if first is not None:
yield first()
while True:
yield function()
# ==== 수학 연산 ====
def multinomial(*counts):
"멀티셋의 서로 다른 배열의 수."
# Counter('abracadabra').values() → 5 2 2 1 1
# multinomial(5, 2, 2, 1, 1) → 83160
return prod(map(comb, accumulate(counts), counts))
def powerset(iterable):
"반복 가능 객체의 부분 시퀀스를 짧은 것부터 긴 것 순으로 반환합니다."
# powerset([1,2,3]) → () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def sum_of_squares(iterable):
"입력 값들의 제곱의 합을 구합니다."
# sum_of_squares([10, 20, 30]) → 1400
return sumprod(*tee(iterable))
# ==== 행렬 연산 ====
def reshape(matrix, columns):
"2차원 행렬을 지정된 열 개수를 갖도록 재구성합니다."
# reshape([(0, 1), (2, 3), (4, 5)], 3) → (0, 1, 2) (3, 4, 5)
return batched(chain.from_iterable(matrix), columns, strict=True)
def transpose(matrix):
"2차원 행렬의 행과 열을 바꿉니다 (전치)."
# transpose([(1, 2, 3), (11, 22, 33)]) → (1, 11) (2, 22) (3, 33)
return zip(*matrix, strict=True)
def matmul(m1, m2):
"두 행렬을 곱합니다."
# matmul([(7, 5), (3, 5)], [(2, 5), (7, 9)]) → (49, 80) (41, 60)
n = len(m2[0])
return batched(starmap(sumprod, product(m1, transpose(m2))), n)
# ==== 다항식 산술 ====
def convolve(signal, kernel):
"""두 반복 가능 객체의 이산 선형 컨볼루션(convolution).
다항식 곱셈과 동일합니다.
컨볼루션은 수학적으로 교환 법칙이 성립하지만, 입력은 서로 다르게
평가됩니다. signal은 지연 평가(lazily) 방식으로 소모되며 무한할 수 있습니다.
kernel은 계산이 시작되기 전에 완전히 소모됩니다.
참고 문서: https://betterexplained.com/articles/intuitive-convolution/
동영상: https://www.youtube.com/watch?v=KuXjwB4LzSA
"""
# convolve([1, -1, -20], [1, -3]) → 1 -4 -17 60
# convolve(data, [0.25, 0.25, 0.25, 0.25]) → Moving average (blur)
# convolve(data, [1/2, 0, -1/2]) → 1st derivative estimate
# convolve(data, [1, -2, 1]) → 2nd derivative estimate
kernel = tuple(kernel)[::-1]
n = len(kernel)
padded_signal = chain(repeat(0, n-1), signal, repeat(0, n-1))
windowed_signal = sliding_window(padded_signal, n)
return map(sumprod, repeat(kernel), windowed_signal)
def polynomial_from_roots(roots):
"""뿌리(roots)로부터 다항식의 계수를 계산합니다.
(x - 5) (x + 4) (x - 3) 는 다음과 같이 전개됩니다: x³ -4x² -17x + 60
"""
# polynomial_from_roots([5, -4, 3]) → [1, -4, -17, 60]
factors = zip(repeat(1), map(neg, roots))
return list(reduce(convolve, factors, [1]))
def polynomial_eval(coefficients, x):
"""특정 값에서 다항식을 평가합니다.
Horner의 방법보다 더 나은 수치적 안정성으로 계산합니다.
"""
# x³ -4x² -17x + 60 를 x = 5 에서 평가
# polynomial_eval([1, -4, -17, 60], x=5) → 0
n = len(coefficients)
if not n:
return type(x)(0)
powers = map(pow, repeat(x), reversed(range(n)))
return sumprod(coefficients, powers)
def polynomial_derivative(coefficients):
"""다항식의 1차 도함수를 계산합니다.
f(x) = x³ -4x² -17x + 60
f'(x) = 3x² -8x -17
"""
# polynomial_derivative([1, -4, -17, 60]) → [3, -8, -17]
n = len(coefficients)
powers = reversed(range(1, n))
return list(map(mul, coefficients, powers))
# ==== 정수론 ====
def sieve(n):
"n보다 작은 소수들."
# sieve(30) → 2 3 5 7 11 13 17 19 23 29
if n > 2:
yield 2
data = bytearray((0, 1)) * (n // 2)
for p in iter_index(data, 1, start=3, stop=isqrt(n) + 1):
data[p*p : n : p+p] = bytes(len(range(p*p, n, p+p)))
yield from iter_index(data, 1, start=3)
def factor(n):
"n의 소인수."
# factor(99) → 3 3 11
# factor(1_000_000_000_000_007) → 47 59 360620266859
# factor(1_000_000_000_000_403) → 1000000000000403
for prime in sieve(isqrt(n) + 1):
while not n % prime:
yield prime
n //= prime
if n == 1:
return
if n > 1:
yield n
def is_prime(n):
"n이 소수이면 True를 반환합니다."
# is_prime(1_000_000_000_000_403) → True
return n > 1 and next(factor(n)) == n
def totient(n):
"n까지의 자연수 중 n과 서로소인 수의 개수."
# https://mathworld.wolfram.com/TotientFunction.html
# totient(12) → 4 because len([1, 5, 7, 11]) == 4
for prime in set(factor(n)):
n -= n // prime
return n
# ==== 누적 통계 ====
def running_mean(iterable):
"지금까지 본 값들의 평균."
# running_mean([37, 33, 38, 28]) → 37 35 36 34
return map(truediv, accumulate(iterable), count(1))
def running_min(iterable):
"지금까지 본 값들 중 최솟값."
# running_min([37, 33, 38, 28]) → 37 33 33 28
return accumulate(iterable, func=min)
def running_max(iterable):
"지금까지 본 값들 중 최댓값."
# running_max([37, 33, 38, 28]) → 37 37 38 38
return accumulate(iterable, func=max)
def running_median(iterable):
"지금까지 본 값들의 중앙값."
# running_median([37, 33, 38, 28]) → 37 35 37 35
read = iter(iterable).__next__
lo = [] # max-heap
hi = [] # min-heap lo와 같거나 하나 작음
with suppress(StopIteration):
while True:
heappush_max(lo, heappushpop(hi, read()))
yield lo[0]
heappush(hi, heappushpop_max(lo, read()))
yield (lo[0] + hi[0]) / 2
def running_statistics(iterable):
"지금까지 본 값들에 대한 종합 통계."
# 튜플 생성: (크기, 최솟값, 중앙값, 최댓값, 평균)
t0, t1, t2, t3 = tee(iterable, 4)
return zip(
count(1),
running_min(t0),
running_median(t1),
running_max(t2),
running_mean(t3),
)