Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Привет друзья.

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

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

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

Выглядит так.
+
Картинка с другого сайта.

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

Пример
class GilbertRouteIterator implements Iterator<Point>{
   bool hasNext();
   Point next();
}


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

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

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

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

P.S.
+
Сишное решение на сях реализовано в традициях unit-утилит и вобщем-то исполняет
свои функции. Я перехитрил сам себя ограничившись выводом результата в stdout и ответная
утилита должна была читать соотв. stdin. Это не корутин а просто взаимодействие двух unix-процессов.
Тоже рабочее решение. Но сегодня я побуду перфекционистом и поищу решение в виде одного
процесса. На разных ЯП.
18 окт 18, 22:00    [21708273]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Siemargl
Member

Откуда: 010100
Сообщений: 6065
mayton,

А как рекурсия соотносится с распараллеливанием ?
18 окт 18, 22:20    [21708285]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Это не про параллелизм.
18 окт 18, 22:39    [21708292]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 490
python будете сравнивать с C++ ? смысл?
19 окт 18, 05:28    [21708374]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
полудух, для большинства четверговых и тяпничных топиков (которые являются по большей части
потоком сознания) не ставится вопрос "зачем". Я просто предлагаю тему. Сообщество реагирует.
19 окт 18, 08:26    [21708435]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Dima T
Member

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

+ Портировал в лоб на C#
Выглядит не очень, но работает
    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();
        }
    }
19 окт 18, 09:49    [21708500]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Немного отрефакторил С вариант от mayton 17384728
+ так проще выворачивать в итератор
#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;
}
19 окт 18, 12:58    [21708987]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Dima T, круть

Thnx.
19 окт 18, 14:20    [21709163]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
fixxer
Member

Откуда:
Сообщений: 700
Вот, откопал давнишнее на скалевских ленивых коллекциях, даже с отрисовкой.

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)
}
19 окт 18, 21:46    [21709561]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
fixxer, спасибо.
19 окт 18, 21:49    [21709564]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6340
Dima T
так проще выворачивать в итератор

Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)
20 окт 18, 00:31    [21709626]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Друзья. Я поднял песочницу здесь.

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

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

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

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

Надеюсь чуть позже я ее улучшу с более быстрой очередью. И это не корутин а просто двух-потоковый итератор.
20 окт 18, 16:29    [21709807]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 490
mayton
Там аж на 3 часа видео. И кроме того я смотрю такие материалы с бумажкой
и карандашом. Спасибо полудуху конечно но это осилить непросто.

я в файлы скидываю все заметки, так гораздо удобнее
уже 500mb текстов + книжки + картинки = 1.5гб

что касается корутин, то они есть не везде, а кое-где они даже и не нужны (Haskell)
надо сравнивать саму асинхронную многопоточность
20 окт 18, 18:19    [21709863]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Данный топик - про co-routines.

Но если вы сможете поставить вопрос в теме "самой асинхронной многопоточности" - welcome!
Попробуйте с нового топика. Это не так просто на самом деле. Найти тему.
20 окт 18, 18:29    [21709868]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Scala вариант зарефакторил в sbt сборщик.
20 окт 18, 19:01    [21709883]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Dima T
Member

Откуда:
Сообщений: 13348
Anatoly Moskovsky
Dima T
так проще выворачивать в итератор

Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)

Да, тема для меня новая, может я отстал и недопонимаю, но интересно как тут 17384728 printf() в самой глубине превратится в итератор без переписывания кода. Ответ желательно кодом.
20 окт 18, 19:05    [21709887]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Dima T
Anatoly Moskovsky
пропущено...

Так суть корутин как раз в том что не надо ничего выворачивать, код берется как есть :)

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

4 функции были заменены функцией с таблицей. Вроде нормально. Не было попытки
иммитации рекурсии.
20 окт 18, 19:22    [21709893]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Почитал про 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.
20 окт 18, 22:24    [21709989]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6340
Dima T
Да, тема для меня новая, может я отстал и недопонимаю, но интересно как тут 17384728 printf() в самой глубине превратится в итератор без переписывания кода. Ответ желательно кодом.


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

#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;
}
21 окт 18, 00:11    [21710019]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Хм... непонятно в го-шке есть 2 формы объявления каналов.
func gilbert2(out chan Pos) {
  .....
}


func gilbert() <-chan Pos {
  ...
}
21 окт 18, 01:42    [21710038]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Лысый дядька
Member

Откуда:
Сообщений: 330
mayton
Хм... непонятно в го-шке есть 2 формы объявления каналов.


out - это не ключевое слово, это название переменной. В первом случае у тебя переменная - это аргумент функции типа chan Pos, а во втором функция возвращает chan Pos, а стрелка означает только для чтения. Никакие это не две формы, это вообще о разном
21 окт 18, 11:47    [21710139]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
полудух
Member

Откуда: планета орков, г.Зверополис
Сообщений: 490
Go он такой... в стиле Microsoft... "а давайте мы вот тут ВСЕ стандарты поменяем!"
21 окт 18, 12:07    [21710152]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Лысый дядька
mayton
Хм... непонятно в го-шке есть 2 формы объявления каналов.


out - это не ключевое слово, это название переменной. В первом случае у тебя переменная - это аргумент функции типа chan Pos, а во втором функция возвращает chan Pos, а стрелка означает только для чтения. Никакие это не две формы, это вообще о разном

Ок. Thnx.
21 окт 18, 12:44    [21710164]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
Partisan M
Member

Откуда:
Сообщений: 1318
Название темы показалось мне неприличным и я заглянул в неё, чтобы узнать, не делается ли в ней какое-нибудь непристрйное предложение . Но оказалось, что "корутин" это всего лишь сопрограмма. Всё равно в корутине участвовать не буду: он если и не непристойный, то бессмысленный.
25 окт 18, 09:38    [21714505]     Ответить | Цитировать Сообщить модератору
 Re: Четверговый корутин с Гилбертом  [new]
mayton
Member

Откуда: loopback
Сообщений: 39228
Как будет угодно. Но если зайдёте - буду рад.
Тема логически связана с fibers.
25 окт 18, 09:42    [21714509]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить