Coroutine

2007-10-11

Coroutine бол жирийн функц процедурын өргөтгөсөн хэлбэр юм. Функцүүд нэг эхлэлтэй байдаг, өөрөөр хэлбэл функцыг дуудахад эхний мөрөөсөө эхлэн ажилладаг. Харин Coroutine нь олон эхлэлтэй байж болно. Юу гэсэн үг вэ гэвэл, Coroutine-ийг дуудах болгонд өөр өөр мөрөөс эхлэн ажиллаж болдог гэсэн үг. Иймд бидний өдөр тутам хэрэглэдэг функц процедурууд нь Coroutine-ийн нэгэн эгэл тохиолдол.

Нэгэн жишээ авч үзье. Фибоначийн тоонууд гэдэг нь дарааллын гишүүн нь өмнөх хоёрынхоо нийлбэрээр тодорхойлогддог тоонууд юм. Мэдээж эхний 2 тоо нь өгөгдөх ёстой.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,…

Дуудах болгонд нэг фибоначийн тоо өгдөг функцийг ruby дээр бичвэл:

fib = Fiber.new do
  x, y = 0, 1
  loop do
    Fiber.yield y
    x,y = y,x+y
  end
end

20.times { puts fib.resume }

Энэ функцыг дуудах болгонд дараагийн фибоначийн тоог буцаах болно. Учир нь resume -ээр дуудах болгонд функц yield гэсэн хэсгээс үргэлжлэн ажилладаг. Дараах хуурмаг C кодыг харья.

int coroutine Generate_1_2_3() {
  yield 1;  /* Execution begins here upon first call to Generate123 */
  yield 2;  /* execution continues here upon "resume Generate123" */
  yield 3;  /* execution continues here upon second "resume Generate123" */
}

main() {
  printf("%d\\n", Generate_1_2_3());  /* prints "1" */
  printf("%d\\n", resume Generate_1_2_3()); /* prints "2" */
  printf("%d\\n", resume Generate_1_2_3()); /* prints "3" */
}

Дээрхи кодноос Coroutine нь олон хаалгатай байшин шиг өөр өөр газраар орж, өөр өөр газраар гарч болох нь харагдаж байгаа байх.

Coroutine-ийг ихэвчлэн Thread-тэй харьцуулж үздэг. Thread-ээс давуу тал нь гэвэл deadlock, synchronization гэх мэт асуудлууд байхгүй. Гэхдээ мэдээж Thread бол зэрэг ажилладаг учраас түүгээрээ давуу.

Coroutine нь State machine програмчлах, ямар нэгэн дараалсан зүйлсийг үүсгэх, өмнөх фибоначийн жишээ шиг төгсгөлгүй цуваа зэрэгт хэрэглэгддэг. Заримдаа нилээн хүнд бодлогуудыг coroutine ашиглаад хялбархан шийдэх тохиолдол байдаг. Жишээ нь “Ижил хөвөөний бодлого”: Хоёр ширхэг хоёртын модны бүх навчнууд зүүнээсээ баруун хүртлээ харгалзан ижил байвал тэр хоёр модыг ижил хөвөөтэй гэнэ. Өгөгдсөн хоёр модыг ижил хөвөөтэй эсэхийг шалга.

Энэ бодлогыг Lua хэл дээр шийдсэн нь:

function tree_leaves(tree)
if tree.leaf then
   coroutine.yield(tree.leaf)
else
   tree_leaves(tree.left)
   tree_leaves(tree.right)
end
end

function same_fringe(tree1, tree2)
local iter1 = coroutine.wrap(tree_leaves)
local iter2 = coroutine.wrap(tree_leaves)
for node in iter1, tree1 do
   if node ~= iter2(tree2) then
       return false
   end
end
return iter2() == nil
end

Coroutine ашиглан шийдсэнээр хийгдэх үйлдэл нь O(n) юм. Та энэ бодлогыг өөрийн мэддэг хэл дээр coroutine ашиглалгүй шийдээд хийгдэх үйлдлийг(O) тооцоод үзээрэй.

Зарим coroutine -г дэмжсэн програмчлалын хэлүүд:

Хэрэгцээтэй хуудсууд: