Четверговый корутин с Гилбертом

mayton

Дата: 18.10.2018 22:00:41

Привет друзья.

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

Чтоб не флудить спецификой. В продолжение топика 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.

Siemargl

Дата: 18.10.2018 22:20:08

mayton,

А как рекурсия соотносится с распараллеливанием ?

mayton

Дата: 18.10.2018 22:39:09

Это не про параллелизм.

полудух

Дата: 19.10.2018 05:28:14

python будете сравнивать с C++ ? смысл?

mayton

Дата: 19.10.2018 08:26:48

полудух, для большинства четверговых и тяпничных топиков (которые являются по большей части
потоком сознания) не ставится вопрос "зачем". Я просто предлагаю тему. Сообщество реагирует.

Dima T

Дата: 19.10.2018 09:49:40

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();
        }
    }

Dima T

Дата: 19.10.2018 12:58:41

Немного отрефакторил С вариант от mayton 17384728

+ так проще выворачивать в итератор

mayton

Дата: 19.10.2018 14:20:58

Dima T, круть

Thnx.

fixxer

Дата: 19.10.2018 21:46:25

Вот, откопал давнишнее на скалевских ленивых коллекциях, даже с отрисовкой.

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)
}

mayton

Дата: 19.10.2018 21:49:36

fixxer, спасибо.