Data Structures: Vectorを試す

PHP

f:id:Qsk:20181202164814p:plain

はじめに

この記事は 2018年 Shinjuku.LTアドベントカレンダー の10日目の記事になります！

9日目の記事はこちら qiita.com

11日目の記事はこちら xxx

Shinjuku.LTってなに？って方はこちら → Shinjuku.LT

概要

  • Data Structures: Vectorを試した
  • 試すついでにChaosGameを書いた

動作環境

Data Structures

PHP: Data Structures - Manual

  • PHP Extension
  • いい感じの配列

導入

  • DataStructureを使うための諸々を入れる
  • GDも使うのでついでに入れる
    • GD使うのにいろいろコマンド必要らしいのでdockerfile作ります
FROM php:7.2-fpm

# GD入れる
RUN apt-get update && apt-get install -y \
        libfreetype6-dev \
        libjpeg62-turbo-dev \
        libpng-dev \
    && docker-php-ext-install -j$(nproc) iconv \
    && docker-php-ext-configure gd --with-freetype-dir=/usr/include/ --with-jpeg-dir=/usr/include/ \
    && docker-php-ext-install -j$(nproc) gd

# Data Structures入れる
RUN pecl install ds

RUN cp /usr/local/etc/php/php.ini-development  /usr/local/etc/php/php.ini

# iniに利用するモジュール追記する
RUN echo extension=ds >> /usr/local/etc/php/php.ini

# 入ってるモジュール確認する
RUN php -m
$ docker build -t ds_php .
# 略
Step 6/6 : RUN php -m
 ---> Running in 44713bcac661
[PHP Modules]
Core
ctype
curl
date
dom
ds            # これと
fileinfo
filter
ftp
gd            # これ使う
hash
iconv
json
libxml
mbstring
mysqlnd
openssl
pcre
PDO
pdo_sqlite
Phar
posix
readline
Reflection
session
SimpleXML
sodium
SPL
sqlite3
standard
tokenizer
xml
xmlreader
xmlwriter
zlib

カオスゲームで描画にかかる時間を配列と比較する

実装

array

<?php
ini_set('memory_limit', -1);

$time_start = microtime(true);

$width = 5000;
$height = 5000;
$iterations = 4000000;

$triangle = [
    [$width / 2, 0],
    [0, $height],
    [$width, $height]
];


$vertex_points = $triangle;
$factor = 0.5;
$img = imagecreate($width, $height);
imagecolorallocate($img, 255, 255, 255);

$pixels = [];
$last_point = ['x' => $width / 2, 'y' => $height / 2];
foreach (range(0, $iterations) as $i) {
    $chosen_vertex = $vertex_points[mt_rand(0, count($vertex_points) - 1)];
    $last_point = ['x' => ($last_point['x'] + $chosen_vertex[0]) * $factor, 'y' => ($last_point['y'] + $chosen_vertex[1]) * $factor];
    $pixels[] = $last_point;
}

$color = imagecolorallocate($img, 0, 0, 0);
foreach ($pixels as $v) {
    imagefilledellipse($img, $v['x'], $v['y'], 1, 1, $color);
}

imagepng($img, 'out.png');

$time = microtime(true) - $time_start;
echo ' microtime: '.$time.PHP_EOL;
echo ' memory: '.memory_get_peak_usage(true).PHP_EOL;
exit;

vector

<?php
ini_set('memory_limit', -1);

$time_start = microtime(true);

$width = 5000;
$height = 5000;
$iterations = 4000000;

$triangle = [
    [$width / 2, 0],
    [0, $height],
    [$width, $height]
];


$vertex_points = $triangle;
$factor = 0.5;
$img = imagecreate($width, $height);
imagecolorallocate($img, 255, 255, 255);

$pixels = new \ds\vector();
$last_point = ['x' => $width / 2, 'y' => $height / 2];
foreach (range(0, $iterations) as $i) {
    $chosen_vertex = $vertex_points[mt_rand(0, count($vertex_points) - 1)];
    $last_point = ['x' => ($last_point['x'] + $chosen_vertex[0]) * $factor, 'y' => ($last_point['y'] + $chosen_vertex[1]) * $factor];
    $pixels[] = $last_point;
}

$color = imagecolorallocate($img, 0, 0, 0);
foreach ($pixels as $v) {
    imagefilledellipse($img, $v['x'], $v['y'], 1, 1, $color);
};

imagepng($img, 'out_vector.png');

$time = microtime(true) - $time_start;
echo ' microtime: '.$time.PHP_EOL;
echo ' memory: '.memory_get_peak_usage(true).PHP_EOL;
exit;

比較

$ docker run -it -v $(pwd):/php ds_php /bin/bash
$ cd /php

# 配列
root@478845784aca:/php# php chaosgame.php
 microtime: 2.5700869560242
 memory: 1818238976

# vector
root@478845784aca:/php# php chaosgame_vector.php
 microtime: 2.7375340461731
 memory: 1765449728

ちなみに出来上がる画像はこんな感じ f:id:Qsk:20181207231125p:plain

  • 圧倒的に無意味な計測をしてしまった気がする
  • 単純な出し入れだと配列のほうが早いっぽいスネ
  • 使うメモリはdata structureのほうが少なさげだけど

補遺

ドキュメントからもリンクされてるけど medium.com を見たほうがいろいろ理解できると思います。 ちなみに上記の計測、無意味にunshiftとか使うと如実に差が現れる、

所感

圧倒的に無意味な計測をしてしまった気がする。 Data Structuresが長期記憶に入ったと思うのでまあそれでいいか。 Data Structuresには今回試したVector以外にもSequenceとかMapとか色々あるので時々に応じて適切なクラス使えばいろいろ効率化できそう。