powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый корутин с Гилбертом
25 сообщений из 29, страница 1 из 2
Четверговый корутин с Гилбертом
    #39719597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Привет друзья.

Илья. Дима. Сова. Зимаргл. И все остальные кодеры и сочуствующие.

Чтоб не флудить спецификой. В продолжение топика 21703023 . А также в продолжение пятничной IP-географии 17380387

Есть графическая кривая заполняющая пространство. Называется кривая Гильберта.
Она - рекурсивна. Ну... по крайней мере известные мне реализации.

Выглядит так.


Необходимо реализовать генератор координат этой кривой в виде Iterator<Point> в различных
языках программирования
- C++,
- C#
- Python
- Go
- D
- Kotlin
- Rust
- и другие...яп
в различных библиотеках и посмотреть на фактическую эффективность. Бенчмарки.

Пример
Код: plaintext
1.
2.
3.
4.
class GilbertRouteIterator implements Iterator<Point>{
   bool hasNext();
   Point next();
}



Разваливание рекурсии в автомат со стеком нас не будет интересовать в данном топике.
Мы ищем "коробочное" решение в виде co-routine.

Забегая вперед я скажу что в некоторых языках coroutine не реализована как элемент языка.
А существует в виде библиотек. Пост-процессинга кода или различных особенностей рантаймов.

Оригинальный (не итеративный) алгоритм на сях опубликован мной здесь 17384728 .
Его можно взять за основу.

Спасибо всем за участие.

P.S.
Сишное решение на сях реализовано в традициях unit-утилит и вобщем-то исполняет
свои функции. Я перехитрил сам себя ограничившись выводом результата в stdout и ответная
утилита должна была читать соотв. stdin. Это не корутин а просто взаимодействие двух unix-процессов.
Тоже рабочее решение. Но сегодня я побуду перфекционистом и поищу решение в виде одного
процесса. На разных ЯП.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39719604
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

А как рекурсия соотносится с распараллеливанием ?
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39719608
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это не про параллелизм.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39719636
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
python будете сравнивать с C++ ? смысл?
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39719668
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудух, для большинства четверговых и тяпничных топиков (которые являются по большей части
потоком сознания) не ставится вопрос "зачем". Я просто предлагаю тему. Сообщество реагирует.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39719715
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonОригинальный (не итеративный) алгоритм на сях опубликован мной здесь 17384728 .
Его можно взять за основу.
Портировал в лоб на C#Выглядит не очень, но работает
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
    struct Point
    {
        Int32 x_;
        Int32 y_;

        public Point(Int32 x, Int32 y)
        {
            x_ = x;
            y_ = y;
        }

        public void print() {
            Console.WriteLine($"{x_}, {y_}");
        }
    }

    class Gilbert2
    {
        const int u = 1;  // pixel step

        int glx;
        int gly;

        // BGI emulation
        Point linerel(int x, int y)
        {
            glx += x;
            gly += y;
            return new Point(glx, gly);
        }

        Point moveto(int x, int y)
        {
            glx = x;
            gly = y;
            return new Point(glx, gly);
        }


        // Elements of curve
        IEnumerable<Point> a(int i)
        {
            if (i > 0)
            {
                foreach(var p in d(i - 1)) yield return p;
                yield return linerel(+u, 0);
                foreach (var p in a(i - 1)) yield return p;
                yield return linerel(0, u);
                foreach (var p in a(i - 1)) yield return p;
                yield return linerel(-u, 0);
                foreach (var p in c(i - 1)) yield return p;
            }
        }

        IEnumerable<Point> b(int i)
        {
            if (i > 0)
            {
                foreach (var p in c(i - 1)) yield return p;
                yield return linerel(-u, 0);
                foreach (var p in b(i - 1)) yield return p;
                yield return linerel(0, -u);
                foreach (var p in b(i - 1)) yield return p;
                yield return linerel(u, 0);
                foreach (var p in d(i - 1)) yield return p;
            }
        }

        IEnumerable<Point> c(int i)
        {
            if (i > 0)
            {
                foreach (var p in b(i - 1)) yield return p;
                yield return linerel(0, -u);
                foreach (var p in c(i - 1)) yield return p;
                yield return linerel(-u, 0);
                foreach (var p in c(i - 1)) yield return p;
                yield return linerel(0, u);
                foreach (var p in a(i - 1)) yield return p;
            }
        }

        IEnumerable<Point> d(int i)
        {
            if (i > 0)
            {
                foreach (var p in a(i - 1)) yield return p;
                yield return linerel(0, u);
                foreach (var p in d(i - 1)) yield return p;
                yield return linerel(u, 0);
                foreach (var p in d(i - 1)) yield return p;
                yield return linerel(0, -u);
                foreach (var p in b(i - 1)) yield return p;
            }
        }

        public IEnumerable<Point> GetPoints(int level)
        {
            yield return moveto(0, 0);
            foreach (var p in a(level)) yield return p;
        }

    }

    class Program
    {
        static void Main(string[] args) {
            var g = new Gilbert2();
            foreach (var p in g.GetPoints(2)) p.print();
        }
    }

...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39719911
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Немного отрефакторил С вариант от mayton 17384728
так проще выворачивать в итератор
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <signal.h>
#include <io.h>

#ifdef _WIN32
#include "windows.h"
#endif

const int u = 1;  // pixel step

int glx;
int gly;

// BGI emulation
void linerel(int x, int y)
{
	glx += x;
	gly += y;
	printf("%d,%d\n", glx, gly);
}

void moveto(int x, int y)
{
	glx = x;
	gly = y;
	printf("%d,%d\n", glx, gly);
}

int offset_1[] = { u, -u, 0, 0 };
int offset_2[] = { 0, 0, -u, u };

void gilbert(int type, int level) {
	if (level > 0) {
		gilbert(3 - type, level - 1);
		linerel(offset_1[type], offset_2[type]);
		gilbert(type, level - 1);
		linerel(offset_2[type], offset_1[type]);
		gilbert(type, level - 1);
		linerel(-offset_1[type], -offset_2[type]);
		gilbert((3 - type) ^ 1, level - 1);
	}
}

int main(int argc, char **arg, char **env) {
	int level = 2;

	moveto(0, 0);
	gilbert(0, level);

	return 0;
}

...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39719974
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, круть

Thnx.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720172
Фотография fixxer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот, откопал давнишнее на скалевских ленивых коллекциях, даже с отрисовкой.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
import java.awt.geom.{GeneralPath, Path2D}
import java.awt.{Dimension, Graphics, Graphics2D}
import javax.swing.JFrame;

object Guilbert extends App {
  val p = 5
  val u = 10

  def a(i: Int): Stream[(Int, Int)] =
    if (i > 0)
      d(i - 1) #::: (u, 0) #:: a(i - 1) #::: (0, u) #:: a(i - 1) #::: (-u, 0) #:: c(i - 1)
    else Stream.empty

  def b(i: Int): Stream[(Int, Int)] =
    if (i > 0)
      c(i - 1) #::: (-u, 0) #:: b(i - 1) #::: (0, -u) #:: b(i - 1) #::: (u, 0) #:: d(i - 1)
    else Stream.empty

  def c(i: Int): Stream[(Int, Int)] =
    if (i > 0)
      b(i - 1) #::: (0, -u) #:: c(i - 1) #::: (-u, 0) #:: c(i - 1) #::: (0, u) #:: a(i - 1)
    else Stream.empty

  def d(i: Int): Stream[(Int, Int)] =
    if (i > 0)
      a(i - 1) #::: (0, u) #:: d(i - 1) #::: (u, 0) #:: d(i - 1) #::: (0, -u) #:: b(i - 1)
    else Stream.empty

  val f = new JFrame() {
    override def paint(g: Graphics): Unit = {
      val g2 = g.asInstanceOf[Graphics2D];
      val polyline = new GeneralPath(Path2D.WIND_EVEN_ODD, 5000);
      polyline.moveTo(100, 100)
      a(p).scanLeft((100, 100))((a, b) => (a._1 + b._1, a._2 + b._2)).take(5000).foreach(
        point => polyline.lineTo(point._1, point._2)
      )
      g2.draw(polyline)
    }
  }

  f.setSize(new Dimension(500, 500))
  f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE)
  f.setVisible(true)
}
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720175
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
fixxer, спасибо.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720208
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima Tтак проще выворачивать в итератор
Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720294
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Друзья. Я поднял песочницу здесь .

Так что если у вас есть мысли прошу делать пул-реквесты. Я каюсь. Не успеваю пока даже
просмотреть и осмыслить видео-материалы которые приаттачены в родительском топике.
Там аж на 3 часа видео. И кроме того я смотрю такие материалы с бумажкой
и карандашом. Спасибо полудуху конечно но это осилить непросто.

Но могу отвечать быстро в рамках этого топика.

Здесь-же надо придумать как оценить стоимость реализации разных корутин в разных ЯП.
Грубо говоря ответить на вопрос как дорого стоит корутина.

По Java к примеру коробочной реализации я не видел. И хотя в потоке есть метод yield() -
его назначение немного другое. Саму реализацию Гильбертова итератора я уже делал на Java.
На BlockingQueue. И она скорее годится в качестве контр-примера. Или примера того
как не надо делать.

Надеюсь чуть позже я ее улучшу с более быстрой очередью. И это не корутин а просто двух-потоковый итератор.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720324
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonТам аж на 3 часа видео. И кроме того я смотрю такие материалы с бумажкой
и карандашом. Спасибо полудуху конечно но это осилить непросто.
я в файлы скидываю все заметки, так гораздо удобнее
уже 500mb текстов + книжки + картинки = 1.5гб

что касается корутин, то они есть не везде, а кое-где они даже и не нужны (Haskell)
надо сравнивать саму асинхронную многопоточность
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720327
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Данный топик - про co-routines.

Но если вы сможете поставить вопрос в теме "самой асинхронной многопоточности" - welcome!
Попробуйте с нового топика. Это не так просто на самом деле. Найти тему.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720332
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Scala вариант зарефакторил в sbt сборщик.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720333
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly MoskovskyDima Tтак проще выворачивать в итератор
Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)
Да, тема для меня новая, может я отстал и недопонимаю, но интересно как тут 17384728 printf() в самой глубине превратится в итератор без переписывания кода. Ответ желательно кодом.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720336
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TAnatoly Moskovskyпропущено...

Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)
Да, тема для меня новая, может я отстал и недопонимаю, но интересно как тут 17384728 printf() в самой глубине превратится в итератор без переписывания кода. Ответ желательно кодом.
4 функции были заменены функцией с таблицей. Вроде нормально. Не было попытки
иммитации рекурсии.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720365
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почитал про Go-Lang. Забавно. У него вообще нет уступчивого return среди ключевых слов языка.
Но есть концепция канала channel который связывает го-рутины.

https://golang.org/ref/spec#Keywords

https://gobyexample.com/channels Channels are the pipes that connect concurrent goroutines.
You can send values into channels from one goroutine and
receive those values into another goroutine.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720370
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TДа, тема для меня новая, может я отстал и недопонимаю, но интересно как тут 17384728 printf() в самой глубине превратится в итератор без переписывания кода. Ответ желательно кодом.

См. начиная с private тот самый код один в один. Только в каждую функцию добавлен параметр push_type& result, через который в глубине вызовов и передаются значения в вызывающую корутину.
В принципе т.к. это класс, то можно было не добавлять параметр, а хранить его в классе, но я привел код для общего случая который годится и для свободных функций.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
#include <boost/coroutine2/all.hpp>
#include <iostream>

const int u = 1;  // pixel step

int offset_1[] = { u, -u, 0, 0 };
int offset_2[] = { 0, 0, -u, u };

struct Gilbert {
    using value_type = std::pair<int, int>;
    using push_type = boost::coroutines2::coroutine<value_type>::push_type;
    using pull_type = boost::coroutines2::coroutine<value_type>::pull_type;

    Gilbert(int max_level)
        : coro{[max_level, this](push_type& result){
            start(result, max_level);
        }}
    {

    }

    bool has_next()
    {
        return static_cast<bool>(coro);
    }

    value_type next()
    {
        auto ret = coro.get();
        coro();
        return ret;
    }


private:
    // BGI emulation
    void linerel(push_type& result, int x,int y)
    {
        glx+=x;
        gly+=y;
        //printf("%d,%d\n",glx,gly);
        result({glx,gly});
    }

    void moveto(push_type& result, int x,int y)
    {
        glx=x;
        gly=y;
        //printf("%d,%d\n",glx,gly);
        result({glx,gly});
    }


    // Elements of curve
    void a(push_type& result, int i)
    {
        if (i > 0)
        {
            d(result, i-1);
            linerel(result, +u,0);
            a(result, i-1);
            linerel(result, 0, u);
            a(result, i - 1);
            linerel(result, -u, 0);
            c(result, i - 1);
        }
    }

    void b(push_type& result, int i)
    {
        if (i > 0)
        {
            c(result, i - 1);
             linerel(result, -u, 0);
             b(result, i - 1);
             linerel(result, 0, -u);
             b(result, i - 1);
             linerel(result, u, 0);
            d(result, i - 1);
        }
    }

    void c(push_type& result, int i)
    {
        if (i > 0)
        {
            b(result, i - 1);
            linerel(result, 0, -u);
            c(result, i - 1);
            linerel(result, -u, 0);
            c(result, i - 1);
            linerel(result, 0, u);
            a(result, i - 1);
        }
    }

    void d(push_type& result, int i)
    {
        if (i > 0)
        {
            a(result, i - 1);
            linerel(result, 0, u);
            d(result, i - 1);
            linerel(result, u, 0);
            d(result, i - 1);
            linerel(result, 0, -u);
            b(result, i - 1);
        }
    }


    // Nearest to power of 2
    unsigned int flp2(unsigned int x){
        x = x | (x>>1);
        x = x | (x>>2);
        x = x | (x>>4);
        x = x | (x>>8);
        x = x | (x>>16);
        return x - (x >> 1);
    }

    void start(push_type& result, int max_level)
    {
        moveto(result, 0, 0);
        a(result, max_level);
    }


private:
    pull_type coro;
    int glx;
    int gly;
};

int main()
{

    Gilbert gen(2);

    while (gen.has_next()) {
        auto v = gen.next();
        std::cout << v.first << "," << v.second << std::endl;
    }

    return 0;
}
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720380
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм... непонятно в го-шке есть 2 формы объявления каналов.
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
func gilbert2(out chan Pos) {
  .....
}


func gilbert() <-chan Pos {
  ...
}
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720414
Лысый дядька
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonХм... непонятно в го-шке есть 2 формы объявления каналов.

out - это не ключевое слово, это название переменной. В первом случае у тебя переменная - это аргумент функции типа chan Pos, а во втором функция возвращает chan Pos, а стрелка означает только для чтения. Никакие это не две формы, это вообще о разном
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720422
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Go он такой... в стиле Microsoft... "а давайте мы вот тут ВСЕ стандарты поменяем!"
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39720429
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Лысый дядькаmaytonХм... непонятно в го-шке есть 2 формы объявления каналов.

out - это не ключевое слово, это название переменной. В первом случае у тебя переменная - это аргумент функции типа chan Pos, а во втором функция возвращает chan Pos, а стрелка означает только для чтения. Никакие это не две формы, это вообще о разном
Ок. Thnx.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39722627
Partisan M
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Название темы показалось мне неприличным и я заглянул в неё, чтобы узнать, не делается ли в ней какое-нибудь непристрйное предложение . Но оказалось, что "корутин" это всего лишь сопрограмма. Всё равно в корутине участвовать не буду: он если и не непристойный, то бессмысленный.
...
Рейтинг: 0 / 0
Четверговый корутин с Гилбертом
    #39722629
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Как будет угодно. Но если зайдёте - буду рад.
Тема логически связана с fibers.
...
Рейтинг: 0 / 0
25 сообщений из 29, страница 1 из 2
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый корутин с Гилбертом
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]