iterable, iterator 그리고 generator

 

yield 키워드

 

지난 yield 와 generator에 대한 글에서 제너레이터를 2가지 관점으로 바라봤었는데 

1) 반복적으로 실행 flow를 pause, resume할 수 있는 경량(유저레벨) 스레드 같은 것.

=> cpu 스케줄 타임을 점유하는 문제와 관련되어 있다.

=> 코루틴 (일반적인 언어들) / Fiber (루비) 으로 연결된다.

 

2) 호출할 때마다 값을 하나씩 produce 함 (next로 호출, yield문을 만나면 caller에게 값을 돌려주고 멈춘다.)

=> memory를 효율적으로 사용하는 문제와 관련되어 있다.

=> 연산전에 모든 element를 메모리에 올릴 것인가? (전통적인 배열 같이) 아님 lazy하게 필요할 때 하나씩 갈 것인가?

=> stream processing 개념으로 연결됨

=> sequence (코틀린) / streams (java 8) / lazy_enumerator (루비) / (더 나아가면 ReactiveX 도 같은 연장선상 아닐까..?)

 

 

 

이번에는 (2) 번에 초점을 맞춰서 각 언어에서 객체 iteration을 어떻게 구현해뒀는지 살펴보려고 한다.

 

(기본)

iterable 인터페이스를 구현하면, next 메소드로 하나씩 다음 값을 탐색할 수 있게되고 for .. each / for.. in / for.. of 와 같은 syntax 를 사용할 수 있다.

동일한 객체에 대해 복수의 iterator를 만들어 동시에 각자 iterate할 수 있음..

 

 

(lazy)

위의 기본 방식에서 generator로 iterate하도록 두가지 개념을 합치면 (iterator를 제너레이터로 만들면) 대상 객체를 lazy하게 돌 수 있다.

(예를 들면 파일 전체를 메모리에 올리지 않고, 한줄씩 가져와서 처리한다든가..)  

 

순회 대상이 되는 객체가 위의 배열처럼 미리 메모리에 모두 올라가 있을 필요가 없고, 파일 : (아직 디스크에 있고, 한 줄씩만 메모리에 올라온다), 이벤트 : (아직 발생하지 않은 미래의 사건은 메모리에 있을 수 없음..)등 다양한 형상의 객체를 같은 인터페이스 ( filter, map, take(3) 등등...)로 다룰 수 있게된다는 점에서 획기적이지 않은가 싶다.

 

 

 

 

 

python

 

받은 인상으로는 파이썬이 제일 표준스러운 느낌이라 가장 먼저 소개 하면 좋을 것 같았다.

이 블로그 글이 짧으면서도 핵심만 잘 담고 있어서 같이 읽어보면 좋을 것 같다.

 

iterable

__iter__ 나 __getitem__ 메소드를 구현하고 있는 객체 ( __getitem__ 은 python 하위 버전 호환문제 때문에 유지중 )

iterable 객체에 iter() 메소드를 호출하면 iterator를 리턴해야 한다.

 

iterator

다음 available한 item을 리턴하거나 더이상 없다면 StopIteration exception을 발생시키는 __next__ 메소드를 구현하고 있는 객체.

python의 iterator는 스스로가 iterable해야 한다는 조건도 있어서, self를 리턴하는 __iter__ 메소드도 구현하고 있어야 한다.

 

 

generator를 합치면

(참고로 python에서 제너레이터는 (1) 제너레이터 함수나 (2) 제너레이터 표현식 : list comprehension 처럼 생겼는데 [] 대신 () 로 감싸져 있음 으로 정의할 수 있다고 함)

 

파일에서 정규표현식과 일치하는 단어를 순회할 수 있는 Sentence 이터러블 객체를 만드는 두가지 방식을 비교해보자.

(출처 : fluent python chapter 14)

 

 

메모리에 미리 다 올리는 버전

class Sentence:
    def __init__(self, text):
        self.text = text
        self.words = RE_WORD.findall(text)

    def __repr__(self):
        return 'Sentence(%s)' % reprlib.repr(self.text)
    
    def __iter__(self):
        return SentenceIterator(self.words)


class SentenceIterator:
    def __init__(self, words):
        self.words = words
        self.index = 0

    def __next__(self):
        try:
            word = self.words[self.index]
        except IndexError:
            raise StopIteration()
        self.index += 1
        return word

    def __iter__(self):
        return self

words 변수에 이미 매치하는 값들을 배열로 모두 가지고 있고, iterator는 index만 하나씩 높여가면서 값 리턴하는 방식.

 

 

lazy 버전 with generator

class Sentence:
    def __init__(self, text):
        self.text = text

    def __repr__(self):
        return 'Sentence(%s)' % reprlib.repr(self.text)
    
    def __iter__(self):
        for match in RE_WORD.finditer(self.text):
            yield match.group()

iterator로 제너레이터를 리턴함. words 배열을 미리 계산해서 가지고 있을 필요가 없다.

 

 

참고로 아래에서 헷갈릴 것 같아서 미리 용어 정리를 하자면 python의 시퀀스가 코틀린, 자바의 collection과 비슷한 거라고 생각하면 좋을 것 같다.

python3 자료형 (출처 : 파이썬 알고리즘 인터뷰)

 

 

 

 

 

javascript

iterable

Symbol.iterator 가 구현되어 있는 객체 (python의 __iter__와 같은 역할)

obj[Symbol.iterator] 와 같이 호출했을 때, iterator가 리턴되어야 함.

 

- 배열, 문자열과 같은 것들에도 내부적으로 Symbol.iterator가 구현되어 있다. (고로 js의 배열, 문자열도 이터러블이다)

- for..of 구문을 사용하면 자동으로 Symbol.iterator를 호출해서 iterator로 element 순회를 진행한다.

 

iterator

{done: false, value: 10} 과 같은 형태의 값을 반환하는 next() 메소드가 구현된 객체.

 

 

generator

 

(출처 : 모던 javascript 튜토리얼 페이지)

기본 버전

let range = {
  from: 1,
  to: 5,

  // for..of 최초 호출 시, Symbol.iterator가 호출됩니다.
  [Symbol.iterator]() {
    // Symbol.iterator는 이터레이터 객체를 반환합니다.
    // for..of는 반환된 이터레이터 객체만을 대상으로 동작하는데, 이때 다음 값도 정해집니다.
    return {
      current: this.from,
      last: this.to,

      // for..of 반복문에 의해 각 이터레이션마다 next()가 호출됩니다.
      next() {
        // next()는 객체 형태의 값, {done:.., value :...}을 반환해야 합니다.
        if (this.current <= this.last) {
          return { done: false, value: this.current++ };
        } else {
          return { done: true };
        }
      }
    };
  }
};

// 객체 range를 대상으로 하는 이터레이션은 range.from과 range.to 사이의 숫자를 출력합니다.
alert([...range]); // 1,2,3,4,5

 

제너레이터 사용한 버전

let range = {
  from: 1,
  to: 5,

  *[Symbol.iterator]() { // [Symbol.iterator]: function*()를 짧게 줄임
    for(let value = this.from; value <= this.to; value++) {
      yield value;
    }
  }
};

alert( [...range] ); // 1, 2, 3, 4, 5

 

자바스크립트에는 특이하게 next() 호출시 "{done: false, value : 3}"  대신 프라미스를 리턴하는 async 이터레이터라는 것도 있어서 

비동기 처리에 사용할 수 있다고 한다.

 

 

 

 

 

ruby

루비는 다른 언어들과는 좀 다르게 용어를 enumerable, enumerator라고 명명하는 것 같다.

 

Enumerable 모듈 사용하는 방법

( include?, count, map, select, uniq 과 같은 메소드들을 사용할 수 있게 된다)

1) 순회 기능을 원하는 클래스에 include Enumerable 하기

2) each 메소드 정의하기 => each를 block 없이 호출하면 enumerator를 리턴.

(내부적으로 map, filter 같은 Enumerable의 메소드들은 each에 의존하고 있기때문에 여기서 each에 대해 정의하지 않으면 NoMethodError가 발생할 것이다)

 

 

예) Enumerable LinkedList 클래스 만들기 (출처 : AppSignal 기술블로그 )

class LinkedList
  include Enumerable
 
  def initialize(head, tail = nil)
    @head, @tail = head, tail
  end
 
  def <<(item)
    LinkedList.new(item, self)
  end
 
  def inspect
    [@head, @tail].inspect
  end
 
  def each(&block)
    if block_given?
      block.call(@head)
      @tail.each(&block) if @tail
    else
      to_enum(:each)
    end
  end
end

 

Enumerable

(1) Enumerator.new , (2) (enumerable 객체).to_enum, (3) (enumerable 객체).each (그 외 다른 메소드 block 없이 호출)

와 같은 방식으로 Enumerator를 instantiate할 수 있다. (python에서 iter()를 호출하는 것 같은 역할)

- 루비의 Array, Hash, Range 클래스들도 Enumerable 모듈을 include하고 있다.

 

Enumerator

일반적으로는 iteration 로직은 내부적으로 처리하고 client code에서는 각 요소에 적용할 block만 넘겨주는 방식으로 코드를 짜게 되지만

enumerator 객체를 next, peek, rewind 같은 메소드로 명시적으로 internal cursor를 조작할 수도 있다.

a = [1,2,3]
e = a.to_enum
p e.next   #=> 1
p e.next   #=> 2
p e.next   #=> 3
p e.next   #raises StopIteration

 

 

lazy_enumerator

Enumerator::lazy 는 enumerator의 subclass.

lazy메소드는 enumerable 객체의 lazy_enumerator를 리턴한다.

 

lazy_enumerator가 어떤건지 살펴보자.

출처 : ruby doc

def filter_map(sequence)
  Lazy.new(sequence) do |yielder, *values|
    result = yield *values
    yielder << result if result
  end
end

filter_map(1..Float::INFINITY) {|i| i*i if i.even?}.first(5)
#=> [4, 16, 36, 64, 100]

 

first(5), take(3), force와 같이 demand가 있는 상황에서만 code를 execute하도록 한다.

(그냥 일반 enumerator였다면 모든 element를 순서대로 하나씩 block에 넘겼겠지만)

그럴 경우에만 Enumerable객체의 요소를 순회하면서 values 부분에 값을 넘기고, block 문을 yield *values 해서 yielder로 generate 한다.

(yielder => 제너레이터. 정확히는 Enumerator::Yielder인스턴스. << 는 yield와 alias)

 

lazy가 사용되면 좋을 예시 (엄청 큰 파일이라고 상상하자)

p File.open(filename).lazy.detect {|line| line=~ /rails/i }

 

(아 복잡해라)

 

 

 

 

 

kotlin

kotlin collection 인터페이스 diagram

크게 mutable collection과 immutable collection(read-only)로 나눌 수 있다.

 

iterable

iterator() 함수를 구현해야 한다. 이터레이터를 리턴.

 

iterator

hasNext(), next() 함수를 구현해야 한다.

 

sequence

iterable vs sequence

Iterable은 collection전체 요소에 대한 작업을 마친뒤 다음 step으로 넘어가는데

Sequence는 single element에 대해 모든 단계 처리를 다 거치고 다음 element 로 넘어간다.

 

ruby의 lazy_enumerator 같은 것..!

asSequence() 메소드로 이터러블을 시퀀스로 바꿀 수 있다.

 

 

 

 

 

java

iterable

iterator() 메소드 구현 필요

 

iterator

hasNext(), next() 등의 메소드 구현 필요

 

stream (java8+)

 int sum = widgets.stream()
                  .filter(w -> w.getColor() == RED)
                  .mapToInt(w -> w.getWeight())
                  .sum();

1) Collection.stream() -> collection 객체에서 stream 생성

2) 스트림 파이프라인 -> filter, mapToInt 같은 중간 operation

3) terminal operation -> sum, count, forEach 같은 것!

 

Streams are lazy; computation on the source data is only performed when the terminal operation is initiated, and source elements are consumed only as needed.

 

코틀린 시퀀스, ruby lazy_enumerator 같은 것. 

마찬가지로 lazy해서 consumer가 있을 때만 (terminal operation이 호출되었을 때) source data에 대한 계산을 진행한다.

 

 

 

reference

(python)

http://ethen8181.github.io/machine-learning/python/iterator/iterator.html

 

(javascript)

https://ko.javascript.info/iterable

https://ko.javascript.info/async-iterators-generators

 

(ruby)

https://blog.appsignal.com/2018/05/29/ruby-magic-enumerable-and-enumerator.html

https://www.bootrails.com/blog/ruby-enumerator-what-why-how/

https://medium.com/rubycademy/the-enumerable-module-in-ruby-part-i-745d561cfebf

https://medium.com/rubycademy/the-enumerable-module-in-ruby-part-ii-41f69b36360

https://stackoverflow.com/questions/41953286/difference-between-enumerable-and-iterator-methods-in-ruby

 

(kotlin)

collection vs sequence in kotlin