「技術」カテゴリーアーカイブ

【C#】【アルゴリズム】カエルの移動(動的計画法の例)

カエルの移動というのはこんな感じの問題です。

アルゴリズムのテキストから抜粋しました。

これを計算するのに動的計画法を使用します。

動的計画法とは、数列の漸化式のように問題を小さな問題(一つ前の)計算結果を使用して解くアルゴリズムで、

では漸化式とは?というと、例えばフィボナッチ数列のように、1+1=2、1+2=3、2+3=5、3+5=8のような数列です。

一般化すると、H[i-1]を使用して計算した値と、H[i-2]を使用して計算した値を比較して、適用する値を決定、それを繰り返していく、というやりかたですな。(現時点での理解)

        public int FrogMove(int[] H)
        {
            int[] dp = new int[H.Length];

            for(int i = 0; i < H.Length; i++)
            {
                if(i == 0)
                {
                    dp[i] = 0;
                }
                if(i == 1)
                {
                    dp[i] = Math.Abs(H[i - 1] - H[1]);
                }
                if(i >= 2)
                {
                    int v1 = dp[i - 1] + Math.Abs(H[i - 1] - H[i]);
                    int v2 = dp[i - 2] + Math.Abs(H[i - 2] - H[i]);
                    dp[i] = Math.Min(v1, v2);
                }
            }
            return dp[H.Length - 1];
        }

【数学】【PYTHON】平方根の定理で円を描く

平方根の定理はa^2+b^2=c^2なので、

円の半径rを組み込むと、

y=√r^2-x^2

で求めることができます。

import matplotlib.pyplot as plt
import numpy as np

r = 300
x = np.arange(-r, r + 1)
y = np.sqrt(r**2 - x**2)

#描画
plt.plot(x, y)
plt.axis('equal')
plt.grid(color='0.8')
plt.show()

RUST勉強中、11/3の積み上げ

今回はGUIアプリケーションとして、デジタル時計を作っていきます。

フォントデータはテキストにはURL書かれていなかったのですが、

以下のサイトからダウンロードできます。

use iced::{
    button, executor, Align, Application, Button, Column, Command, Element, Font,
    HorizontalAlignment, Length, Row, Settings, Subscription, Text,
};

const FONT: Font = Font::External {
    name: "PixelMplus12-Regular",
    bytes: include_bytes!("../rsc/PixelMplus12-Regular.ttf"),
};

struct GUI {
    start_stop_button_state: button::State,
    reset_button_state: button::State,
}

impl Application for GUI {
    type Executor = executor::Null;
    type Message = ();
    type Flags = ();

    fn new(_flags: ()) -> (GUI, Command<Self::Message>) {
        (
            GUI {
                start_stop_button_state: button::State::new(),
                reset_button_state: button::State::new(),
            },
            Command::none(),
        )
    }

    fn title(&self) -> String {
        String::from("DEMO")
    }

    fn update(&mut self, _message: Self::Message) -> Command<Self::Message> {
        Command::none()
    }

    fn view(&mut self) -> Element<Self::Message> {
        let tick_text = Text::new("00:00:00.00").font(FONT).size(60);
        let start_stop_button = Button::new(
            &mut self.start_stop_button_state,
            Text::new("Start")
                .horizontal_alignment(HorizontalAlignment::Center)
                .font(FONT),
        )
        .min_width(80);
        let reset_button = Button::new(
            &mut self.reset_button_state,
            Text::new("Reset")
                .horizontal_alignment(HorizontalAlignment::Center)
                .font(FONT),
        )
        .min_width(80);

        Column::new()
            .push(tick_text)
            .push(
                Row::new()
                    .push(start_stop_button)
                    .push(reset_button)
                    .spacing(10),
            )
            .spacing(10)
            .padding(10)
            .width(Length::Fill)
            .height(Length::Fill)
            .align_items(Align::Center)
            .into()
    }
}

fn main() {
    let mut settings = Settings::default();
    settings.window.size = (400u32, 120u32);
    GUI::run(settings);
}

【C#】【アルゴリズム】マージソート

テキストに書いてあったマージソートのアルゴリズムです。

        public void MargeSort(List<int> A)
        {
            List<int> C = new List<int>();
            for(int i = 0; i < A.Count; i++)
            {
                C.Add(0);
            }
            MargeSortSub(A, C, 0, A.Count);
        }

        public void MargeSortSub(List<int> A, List<int> C, int l, int r)
        {
            if(r - l == 1)
            {
                return;
            }

            int m = (l + r) / 2;
            MargeSortSub(A, C, l, m);
            MargeSortSub(A, C, m, r);

            int c1 = l;
            int c2 = m;
            int cnt = 0;

            while(c1 != m || c2 != r)
            {
                if (c1 == m)
                {
                    C[cnt] = A[c2];
                    c2++;
                }else if (c2 == r)
                {
                    C[cnt] = A[c1];
                    c1++;
                }else
                {
                    if(A[c1] <= A[c2])
                    {
                        C[cnt] = A[c1];
                        c1++;
                    }else
                    {
                        C[cnt] = A[c2];
                        c2++;
                    }
                }
                cnt++;
            }

            for(int i = 0; i < cnt; i++)
            {
                A[l + i] = C[i];
            }
        }

RUST勉強中、10/9の積み上げ

前回の続きで、Rust側の実装を行って行きます。

[package]
name = "mandelbrot"
version = "0.1.0"
authors = ["taki"]
edition = "2018"

[lib]
crate-type = ["cdylib", "rlib"]

[features]
default = ["console_error_panic_hook"]

[dependencies]
js-sys = "0.3.60"
wasm-bindgen = "0.2.63"

# The `console_error_panic_hook` crate provides better debugging of panics by
# logging them with `console.error`. This is great for development, but requires
# all the `std::fmt` and `std::panicking` infrastructure, so isn't great for
# code size when deploying.
console_error_panic_hook = { version = "0.1.6", optional = true }

# `wee_alloc` is a tiny allocator for wasm that is only ~1K in code size
# compared to the default allocator's ~10K. It is slower than the default
# allocator, however.
#
# Unfortunately, `wee_alloc` requires nightly Rust when targeting wasm for now.
wee_alloc = { version = "0.4.5", optional = true }

[dependencies.web-sys]
version = "0.3.60"
features = [
    'CanvasRenderingContext2d',
    'Document',
    'Element',
    'HtmlCanvasElement',
    'ImageData',
    'Performance',
    'Window',
]

[dev-dependencies]
wasm-bindgen-test = "0.3.13"

[profile.release]
# Tell `rustc` to optimize for small code size.
opt-level = "s"
mod utils;
mod logic;

use wasm_bindgen::prelude::*;
use wasm_bindgen::{Clamped, JsCast};
use web_sys::ImageData;

// When the `wee_alloc` feature is enabled, use `wee_alloc` as the global
// allocator.
#[cfg(feature = "wee_alloc")]
#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;

#[wasm_bindgen]
extern "C" {
    #[wasm_bindgen(js_namespace = console)]
    fn log(a: &str);
}

macro_rules! console_log {
    ($($t:tt)*) => (log(&format_args!($($t)*).to_string()))
}

macro_rules! measure_elapsed_time {
    ($t:tt,$s:block) => {{
        let window = web_sys::window().expect("should have a window in this context");
        let performance = window
            .performance()
            .expect("performance should be available");
        let start = performance.now();
        let result = { $s };
        let end = performance.now();
        console_log!("{}:{}[ms]", $t, end - start);
        result
    }};
}

#[wasm_bindgen]
pub fn generate_mandelbrot_set(
    canvas_w: usize,
    canvas_h: usize,
    x_min: f64,
    x_max: f64,
    y_min: f64,
    y_max: f64,
    max_iter: usize,
) -> Vec<u8> {
    measure_elapsed_time!("generate:wasm\telapsed:", {
        logic::generate_mandelbrot_set(canvas_w, canvas_h,
            x_min, x_max, y_min, y_max, max_iter)
    })
}

#[wasm_bindgen]
pub fn draw_mandelbrot_set() {
    const CANVAS_ID: &str = "canvas_wasm";
    let document = web_sys::window().unwrap().document().unwrap();
    let canvas = document.get_element_by_id(CANVAS_ID).unwrap();
    let canvas: web_sys::HtmlCanvasElement = canvas
        .dyn_into::<web_sys::HtmlCanvasElement>()
        .map_err(|_| ())
        .unwrap();
    let context = canvas
        .get_context("2d")
        .unwrap()
        .unwrap()
        .dyn_into::<web_sys::CanvasRenderingContext2d>()
        .unwrap();
    let canvas_w = canvas.width() as usize;
    let canvas_h = canvas.height() as usize;
    const X_MIN: f64 = -1.5;
    const X_MAX: f64 = 0.5;
    const Y_MIN: f64 = -1.0;
    const Y_MAX: f64 = 1.0;
    const MAX_ITER: usize = 64;

    let mut result = measure_elapsed_time!("generate:wasm\telapsed:", {
        logic::generate_mandelbrot_set(canvas_w, canvas_h,
            X_MIN, X_MAX, Y_MIN, Y_MAX, MAX_ITER)
    });
    measure_elapsed_time!("draw:wasm\telapsed:", {
        let data = ImageData::new_with_u8_clamped_array_and_sh(
            Clamped(&mut result),
            canvas.width(),
            canvas.height(),
        );
        if let Ok(data) = data {
            let _ = context.put_image_data(&data, 0.0, 0.0);
        }
    })
}

マジ疲れたわ。

JavaScript側でスペルミスがあって、うまくJS側からRustの処理を呼び出せないというミスをやらかして、

スペルミスに気がついて対処して動かすまでに1時間ぐらいかかったかな?

原因を探るためにWinMargeをインストールして、サンプルプログラムと書いたコードを比較して、と言う作業をやっていました。

【数学】【PYTHON】三角関数を使って円を描画する

import matplotlib.pyplot as plt
import numpy as np

#角度
th = np.arange(0, 360)

#円周上の点Pの座標
x = np.cos(np.radians(th))
y = np.sin(np.radians(th))

#描画
plt.plot(x, y)
plt.axis('equal')
plt.grid(color='0.8')
plt.show()

角度0~360に対して

x座標をコサインで、y座標をサインで計算します。

このとき、引数の角度はラジアンで与える必要があります。

RUST勉強中、10/2の積み上げ?

前回の続き

www/index.htmlを書いていきます。

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>Hello wasm-pack!</title>
  </head>
  <body>
    <noscript>This page contains webassembly and javascript content, please enable javascript in your browser.</noscript>
    <button id="render">render</button>
    <div>
      <canvas id="canvas_wasm" height="1200" width="1200"></canvas>
      <canvas id="canvas_js" height="1200" width="1200"></canvas>
      <canvas id="canvas_hybrid" height="1200" width="1200"></canvas>
    </div>
    <script src="./bootstrap.js"></script>
  </body>
</html>

www/index.js

'use strict'

function draw(ctx, canvas_w, canvas_h, data) {
    let img = new ImageData(new Uint8ClampedArray(data), canvas_w, canvas_h);
    ctx.putImageData(img, 0, 0,);
}

const X_MIN = -1.5;
const X_MAX = 0.5;
const Y_MIN = -1.0;
const Y_MAX = 1.0;
const MAX_ITER = 64;

console.log("start loading wasm");
const mandelbrot = import('../pkg').catch(console.error);

Promise.all([mandelbrot]).then(async function([
    {generate_mandelbrot_set,draw_mandelbrot_set}
]) {
    console.log("finished loading wasm");
    const renderBtn = document.getElementById('render');
    renderBtn.addEventListener('click', () => {
        draw_mandelbrot_set();
        let wasmResult = null;
        {
            const CANVAS_ID = "canvas_hybrid";
            let canvas = document.getElementById(CANVAS_ID);
            let context = canvas.getContext("2d");
            const canvasWidth = canvas.width;
            const canvasHeight = canvas.height;

            const generateStartTime = Date.now();
            wasmResult = generate_mandelbrot_set(canvasWidth, canvasHeight,
                X_MIN, X_MAX, Y_MIN, Y_MAX, MAX_ITER);
            const generateEndTime = Date.now();
            const drawStartTime = Date.now();
            draw(context, canvasWidth, canvasHeight, wasmResult);
            const drawEndTime = Date.now();
            const elapsed = generateEndTime - generateStartTime;
            console.log(`\tgenerate:wasm\tgenerate_elapsed:${elapsed} [ms]`);
            console.log(`\tdraw: js\tdraw_elapsed] ${drawEndTime - drawStartTime} [ms]`);
        }
    })
})

処理の呼び出し側のコードなんだけど、Rustのコード書いてねー!