Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Четверговый корутин с Гилбертом / 25 сообщений из 29, страница 1 из 2
18.10.2018, 22:00
    #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
18.10.2018, 22:20
    #39719604
Siemargl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
mayton,

А как рекурсия соотносится с распараллеливанием ?
...
Рейтинг: 0 / 0
18.10.2018, 22:39
    #39719608
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
Это не про параллелизм.
...
Рейтинг: 0 / 0
19.10.2018, 05:28
    #39719636
полудух
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
python будете сравнивать с C++ ? смысл?
...
Рейтинг: 0 / 0
19.10.2018, 08:26
    #39719668
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
полудух, для большинства четверговых и тяпничных топиков (которые являются по большей части
потоком сознания) не ставится вопрос "зачем". Я просто предлагаю тему. Сообщество реагирует.
...
Рейтинг: 0 / 0
19.10.2018, 09:49
    #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
19.10.2018, 12:58
    #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
19.10.2018, 14:20
    #39719974
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
Dima T, круть

Thnx.
...
Рейтинг: 0 / 0
19.10.2018, 21:46
    #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
19.10.2018, 21:49
    #39720175
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
fixxer, спасибо.
...
Рейтинг: 0 / 0
20.10.2018, 00:31
    #39720208
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
Dima Tтак проще выворачивать в итератор
Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)
...
Рейтинг: 0 / 0
20.10.2018, 16:29
    #39720294
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
Друзья. Я поднял песочницу здесь .

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

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

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

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

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

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

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

Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)
Да, тема для меня новая, может я отстал и недопонимаю, но интересно как тут 17384728 printf() в самой глубине превратится в итератор без переписывания кода. Ответ желательно кодом.
4 функции были заменены функцией с таблицей. Вроде нормально. Не было попытки
иммитации рекурсии.
...
Рейтинг: 0 / 0
20.10.2018, 22:24
    #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
21.10.2018, 00:11
    #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
21.10.2018, 01:42
    #39720380
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Четверговый корутин с Гилбертом
Хм... непонятно в го-шке есть 2 формы объявления каналов.
Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
func gilbert2(out chan Pos) {
  .....
}


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

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

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


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