-
생산자-소비자 큐
- 선입선출 큐
- FIFO 큐
-
수신된 전자우편을 장기 보관하기 위해 처리하는 프로그램, 이 프로그램이 리스트를 생산자-소비자 큐를 사용한다고 가정
try_receive_email, 전자우편을 수신하는 역할을 하는 함수- 소켓, 파일 시스템 또는 다른 유형의 I/O 시스템을 사용해 전자우편 받을 수 있음
Email인수턴스를 반환하거나NoEmailError예외 발생
class Email: def __init__(self, sender, receiver, message): self.sender = sender self.receiver = receiver self.message = message ...
class NoEmailError(Exception): pass def try_receive_email(): # Email 인스턴스를 하나 반환하거나,# NoEmailError를 발생시킨다 ...
- 생산자 함수는 전자우편을 받아 나중에 소비할 수 있게 큐에 삽입
- 리스트의
append메소드를 사용해 새 메시지를 뒤에 추가
- 리스트의
def produce_emails(queue): while True: try: email = try_receive_email() except NoEmailError: return else: queue.append(email) # 생산자
- 소비자 함수는 큐에 대해
pop(0)호출, 리스트의 첫번째 원소를 제거하고 제거된 첫번째 값을 호출자에게 돌려줌- 소비자는 항상 큐 맨 앞에 있는 원소를 처리하여 원소 도착 순서대로 처리
def consume_one_email(queue): if not queue: return email = queue.pop(0) # 소비자 # 장기 보관을 위해 메시지를 인덱싱함 ...
keep_running함수가False를 반환할 때까지 생산과 소비를 반복하는 함수loop추가
def loop(queue, keep_running): while keep_running(): produce_emails(queue) consume_one_email(queue) def my_end_func(): ... loop([], my_end_func)
- 단점
-
생산자-소비자 큐를 사용 여부는 지연 시간과 단위 사간당 throughput 사이의 trade-off
- 생산자-소비자 큐를 사용할 때는 가능하면 빨리 원소를 수집하길 원하므로 새로운 원소를 받아들이는 지연 시간 최소화, 소비자 큐에 쌓인 원소를 일정한 throughput 으로 처리
- 종단점 사이의 지연 시간을 희생함으로써 안정적인 성능 프로파일과 일관성 있는 throughput 달성 가능
-
큐를 리스트로 사용할 때 원소 개수가 일정 개수를 초과하면 성능은 선형보다 더 나빠짐
원소 수: 500 걸린 시간: 0.000023초 원소 수: 1,000 걸린 시간: 0.000045초 데이터 크기 2.0배, 걸린 시간 2.0배 원소 수: 2,000 걸린 시간: 0.000087초 데이터 크기 4.0배, 걸린 시간 3.8배 원소 수: 3,000 걸린 시간: 0.000134초 데이터 크기 6.0배, 걸린 시간 5.8배 원소 수: 4,000 걸린 시간: 0.000181초 데이터 크기 8.0배, 걸린 시간 7.9배 원소 수: 5,000 걸린 시간: 0.000231초 데이터 크기 10.0배, 걸린 시간 10.1배
- 리스트 타입에 있는
append메소드가 거의 상수 시간이 걸림 - 데이터 크기가 커짐에 따라 큐에 데이터를 넣는 데 걸리는 전체 시간이 선형적으로 증가
- 리스트 타입에 있는
-
큐 맨 앞 원소를 제거하는
pop(0)호출 성능원소 수: 500 걸린 시간: 0.000043초 원소 수: 1,000 걸린 시간: 0.000097초 데이터 크기 2.0배, 걸린 시간 2.2배 원소 수: 2,000 걸린 시간: 0.000252초 데이터 크기 4.0배, 걸린 시간 5.8배 원소 수: 3,000 걸린 시간: 0.000464초 데이터 크기 6.0배, 걸린 시간 10.7배 원소 수: 4,000 걸린 시간: 0.000751초 데이터 크기 8.0배, 걸린 시간 17.3배 원소 수: 5,000 걸린 시간: 0.001229초 데이터 크기 10.0배, 걸린 시간 28.3배
- 큐 길이가 늘어남에 따라 큐 길이의 제곱에 비례해 증가
- 리스트의 모든 남은 원소를 제 위치로 이동하는 작업 존재하기 때문
- 대략
len(queue) * len(queue)
- 대략
-
-
deque- 양방향 큐
- 시작과 끝 지점에 원소를 삽입/제거하는데 상수 시간 소요
-
deque를 사용한 예제- 생산자 함수의
append는 그대로 사용 - 소비자 함수에서는
popleft메소드를 사용하도록 변경 loop메소드 호출 시deque인스턴스 전달
- 생산자 함수의
import collections
def consume_one_email(queue):
if not queue:
return
email = queue.popleft() # 소비자
# 전자우편 메시지를 처리한다
...
def my_end_func():
...
loop(collections.deque(), my_end_func)-
벤치마크 수행 결과
# produce 원소 수: 500 걸린 시간: 0.000022초 원소 수: 1,000 걸린 시간: 0.000044초 데이터 크기 2.0배, 걸린 시간 2.0배 원소 수: 2,000 걸린 시간: 0.000091초 데이터 크기 4.0배, 걸린 시간 4.2배 원소 수: 3,000 걸린 시간: 0.000142초 데이터 크기 6.0배, 걸린 시간 6.5배 원소 수: 4,000 걸린 시간: 0.000192초 데이터 크기 8.0배, 걸린 시간 8.8배 원소 수: 5,000 걸린 시간: 0.000244초 데이터 크기 10.0배, 걸린 시간 11.1배 #consume 원소 수: 500 걸린 시간: 0.000019초 원소 수: 1,000 걸린 시간: 0.000041초 데이터 크기 2.0배, 걸린 시간 2.1배 원소 수: 2,000 걸린 시간: 0.000081초 데이터 크기 4.0배, 걸린 시간 4.2배 원소 수: 3,000 걸린 시간: 0.000126초 데이터 크기 6.0배, 걸린 시간 6.6배 원소 수: 4,000 걸린 시간: 0.000169초 데이터 크기 8.0배, 걸린 시간 8.8배 원소 수: 5,000 걸린 시간: 0.000213초 데이터 크기 10.0배, 걸린 시간 11.0배
- 생산자 함수에서의 성능은 리스트 사용에서의 성능과 비슷
- 소비자 함수에서의 성능은 대기열 길이에 선형적으로 비례하여 증가
- 프로그램에서 생산자-소비자 큐가 임계 단계라면 deque 로 변경하는 것이 성능상 좋음
- 임계 단계임을 확신할 수 없는 경우 벤치마크를 사용하여 성능 측정을 통해 임계 단계인지 여부 확인 필요함