忍者ブログ
  • 2019.11
  • 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
  • 2020.01
C++のboostでgraphviz+dotを使ってみた
グラフを作りたかったので、graphvixを使ってみました。

【参考】Boost.Graph Graphviz形式で重みを出力

#include <fstream>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
struct EdgeWithInfo
{
    int nodeS;
    int nodeE;
    int weight;
    std::string name;
};

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
                              boost::no_property, boost::property<boost::edge_all_t, EdgeWithInfo>>
    Graph;
typedef std::pair<int, int> Edge;

enum
{
    A,
    B,
    C,
    D,
    E,
    N
};

const std::string name[] = {"A", "B", "C", "D", "E"};

int main()
{
    const std::vector<EdgeWithInfo> edgeWithInfo =
        {
            {A, B, 3, "→B"},
            {A, C, 1, "→C"},
            {A, D, 4, "→D"},
            {B, E, 2, "→E"},
            {C, E, 5, "→E"},
            {D, E, 6, "→E"}};

    std::vector<Edge> edges;

    std::transform(edgeWithInfo.begin(), edgeWithInfo.end(), std::back_inserter(edges),
                   [](auto ei) {
                       return std::make_pair(ei.nodeS, ei.nodeE);
                   });

    const Graph g(edges.begin(), edges.end(), edgeWithInfo.begin(), N);

    std::ofstream file("test.dot");
    boost::write_graphviz(file,
                          g,
                          boost::make_label_writer(name),
                          [](auto &graph_) {
                              return [&graph_](std::ostream &out, auto edge) {
                                  const EdgeWithInfo &ewi =
                                      *reinterpret_cast<const EdgeWithInfo *>(&boost::get(boost::edge_all, graph_, edge));
                                  out << "[";
                                  out << "weight=" << ewi.weight << ",";
                                  out << "label=" << ewi.name;
                                  out << "]";
                              };
                          }(g));
}

digraph G {
0[label=A];
1[label=B];
2[label=C];
3[label=D];
4[label=E];
0->1 [weight=3,label=→B];
0->2 [weight=1,label=→C];
0->3 [weight=4,label=→D];
1->4 [weight=2,label=→E];
2->4 [weight=5,label=→E];
3->4 [weight=6,label=→E];
}
正攻法ではない気がするけど、まあ良しとしよう。
PR
【2019/05/04 09:22 】 | C/C++ | 有り難いご意見(3)
                                    
超万能なsorted
Pythonでの不満。Python2にあったsorted関数のcmpがなくなって、keyになった。
なぜ、cmpはなくなったのだろうか?考えてみた。

まず、sortedへの不満として、複数キーの昇順・降順ができなくなった。というものがあった。
誤りである。
どうやらkeyにタプルを返すと勝手に複数キーの昇順としてソートしてくれるようだ。
つまり、文字は反転。数字はマイナスにすることで、それらしきものができる。
c=[('a', 1), ('a', 2), ('b', 2), ('b', 1)]
sorted(c, key=lambda x: (tuple(map(lambda z:(0xff-z), x[0].encode("cp932"))), -x[1]))
[('b', 2), ('b', 1), ('a', 2), ('a', 1)]
ここで気づいた。この比較用キーの作成はcmpの場合、ソート方法に依存してしまう。O(2*NlogN)の頻度で比較用キーが作成されてしまうのだ。
この点、key指定だと比較用キーはO(N)のみの作成となる。
すばらしい

ただし、文字列の降順としては可変長の場合、前述の方法は使えない。なので、classを作ってみた。
class Keys:
    def __init__(self, v, isAscs):
        self.v = v
        self.isAscs = tuple(isAscs)

    def __lt__(self, other):
        for i, s, isAsc, o in zip(range(len(self.isAscs)-1, -1, -1), self.v, self.isAscs, other.v):
            lt = [lambda p1, p2: p1 > p2, lambda p1, p2: p1 < p2][isAsc]
            ret = lt(s, o)
            if ret or i and lt(o, s):
                break
        return ret

    @staticmethod
    def of(isAscs, keymap=lambda x:x):
        return lambda item: Keys(keymap(item), isAscs)


if __name__ == "__main__":
    arr = [("a", 2), ("b", 1), ("a", 1), ("b", 2)]
    print(arr)
    #1項目め降順、2項目め昇順
    print(sorted(arr, key=Keys.of((False, True))))
    #1項目め2文字目昇順、1項目め1文字目昇順
    print(sorted(arr, key=Keys.of((True, False), keymap=lambda x:(x[0][1], x[0][0]))))
うん、素晴らしい。
【2019/05/02 08:43 】 | Python | 有り難いご意見(0)
                                    
C++17でモンテカルロを並列化してみた。(GNU Version)
C++17でモンテカルロを並列化してみた。に触発されて、GNU版で作ってみました
■コンパイル
$ g++ test.cc -Wall -march=native -std=c++17 -O3  -fopenmp
■ソース
#include <parallel/algorithm>
//#include <execution>
#include <atomic>
#include <mutex>
#include <iostream>
#include <random>
#include <array>
#include <stdlib.h>
int main(int argc, char *argv[])
{
    static int const NUM = 1000000000;
    static int threads = 8;
    static_assert(std::atomic<int>::is_always_lock_free);
    if (argc >= 2)
    {
        threads = atoi(argv[1]);
    }
    auto nums = std::vector<int>(threads);
    for (auto &num : nums)
    {
        num = NUM / threads;
    }
    __gnu_parallel::_Settings s;
    s.algorithm_strategy = __gnu_parallel::force_parallel;
    __gnu_parallel::_Settings::set(s);

    std::atomic counter = {0};

    __gnu_parallel::for_each(nums.begin(), nums.end(), [&counter](int num) {
        std::random_device rnd;
        thread_local std::mt19937 mt(rand());
         std::uniform_real_distribution<double> score(0.0, 1.0);
        for (auto &&no = 0; no < num; ++no)
        {
            auto &&x = score(mt);
            auto &&y = score(mt);
            if ((x * x + y * y) < 1.0)
            {
                counter++;
            }
        }
    });

    std::cout << "PI = " << 4.0 * counter / NUM << std::endl;
}
■結果
$ time ./a.out 1
PI = 3.14155

real	0m27.461s
user	0m27.469s
sys	0m0.001s
$ time ./a.out 2
PI = 3.14159

real	0m29.238s
user	0m58.008s
sys	0m0.016s
$ time ./a.out 3
PI = 3.14151

real	0m28.447s
user	1m24.458s
sys	0m0.000s
$ time ./a.out 4
PI = 3.14155

real	0m32.101s
user	2m5.238s
sys	0m0.020s

なぜか延べ時間(user)が増えるだけでreal時間が減りません。。。
そこでソースを修正してみました。
■ソース修正後
#include <parallel/algorithm>
//#include <execution>
#include <atomic>
#include <mutex>
#include <iostream>
#include <random>
#include <array>
#include <stdlib.h>
int main(int argc, char *argv[])
{
    static int const NUM = 1000000000;
    static int threads = 8;
    static_assert(std::atomic<int>::is_always_lock_free);
    if (argc >= 2)
    {
        threads = atoi(argv[1]);
    }
    auto nums = std::vector<int>(threads);
    for (auto &num : nums)
    {
        num = NUM / threads;
    }
    __gnu_parallel::_Settings s;
    s.algorithm_strategy = __gnu_parallel::force_parallel;
    __gnu_parallel::_Settings::set(s);

    std::atomic counter = {0};

    __gnu_parallel::for_each(nums.begin(), nums.end(), [&counter](int num) {
        std::random_device rnd;
        thread_local std::mt19937 mt(rand());
        int _counter = 0;
        std::uniform_real_distribution<double> score(0.0, 1.0);
        for (auto &&no = 0; no < num; ++no)
        {
            auto &&x = score(mt);
            auto &&y = score(mt);
            if ((x * x + y * y) < 1.0)
            {
                _counter++;
            }
        }
        counter += _counter;
    });

    std::cout << "PI = " << 4.0 * counter / NUM << std::endl;
}

■結果
$ time ./a.out 1
PI = 3.14155

real	0m20.263s
user	0m20.255s
sys	0m0.000s
$ time ./a.out 2
PI = 3.14159

real	0m10.117s
user	0m20.223s
sys	0m0.000s
$ time ./a.out 3
PI = 3.14151

real	0m7.409s
user	0m22.209s
sys	0m0.000s
$ time ./a.out 4
PI = 3.14155

real	0m6.129s
user	0m24.492s
sys	0m0.001s
core4個分で20秒から6秒にその後、8個に増やしても増えませんでした。。。
なかなかのパフォーマンスなり。
【2019/05/01 17:11 】 | 未選択 | 有り難いご意見(1)
                                    
SECCON令和に参加してみました
SECCON令和CTFへ参加したなり。なんとか2問(1問サービス問題)解けて423位/858。まずまずかなー。
解けた1問の解き方。
■問題
nc zerois-o-reiwa.seccon.jp 23615

■答え
pythonで実装。他の人のwrite upみたらもっとスマートなのたくさんねー。
#mkfifo testfifo
#cat testfifo | nc zerois-o-reiwa.seccon.jp 23615 | python test.py > testfifo
import re
import sys
while True:

    try:
        x = input()
    except EOFError as e:
        break
    sys.stderr.write("{}\n".format(x))
    if x[0:2] == "0=":
        m = re.findall("([+-]?[*?/0-9]+)", x[2:])
        z = 0
        #print(m)
        for x in m:
            #print("x={}".format(x))
            if x.find("?") >=0:
                y = eval(x.replace("?", "1"))
                #print("y={}".format(y))
            else:
                z += eval(x)
                #print("z={}".format(z))
        if float(y)==0:
            ans = "0"
        else:
            ans = "{}\n".format(int(-float(z)/float(y)))
        sys.stderr.write("{}\n".format(ans))
        sys.stdout.write("{}\n".format(ans))
【2019/05/01 10:24 】 | その他 | 有り難いご意見(2)
                                    
TSURUGIを入れてみた
令和SECCONに参加するのでTSURUGI Linuxを入れてみました。

fluxboxに切り替えて「fbmenugen」を使ったら「Other」に「TSURUGI」メニューが全て入ってカテゴリが分からなくなってしまいました。
fluxboxを入れた直後
仕方がないのでpythonでmateからfluxboxのmenuに変換するプログラムを作成、すっきりしましたとさ。
menuを修正後
■変換用python
import sys
from xml.dom import minidom
from os import path
from collections import OrderedDict

APP_Directory = None
DIR_Directory = None
def main():
    global APP_Directory
    global DIR_Directory

    if len(sys.argv)!=2:
        print("Using: {} mate.conf".format(sys.argv[0]))
        return
    fileName = sys.argv[1]
    APP_Directory = path.abspath(path.dirname(fileName)+"/../applications")
    DIR_Directory = path.abspath(path.dirname(fileName)+"/../desktop-directories")
    print(fileName)

    with open(fileName, "r", True, "UTF-8") as r:
        x = "\n".join(r.readlines())
    myDom = minidom.parseString(x)
    
    recurseDict(myDom, 0, [])

def recurseDict(dic, layer, stack):
    #dic = minidom.parseString("")
    layer+=1
    if sum(1 for x in dic.childNodes if not isinstance(x, minidom.Text)):
        if dic.nodeName != "Layout":
            for d in dic.childNodes:
                if not isinstance(d, minidom.Text):
                    recurseDict(d, layer, stack)

    else:
        if dic.nodeName == "Directory":
            lidx = 0
            for lidx in range(len(stack), 0, -1):
                if layer > stack[lidx-1][0]:
                    break
            for _ in range(lidx, len(stack)):
                stack.pop()
                print("{}[end]".format(" "*(len(stack)*2)))
            
            v = readFile(DIR_Directory+"/"+dic.childNodes[0].nodeValue)
            print("{}[submenu] ({}) <{}>".format(" "*(len(stack)*2), v["Name"], v["Icon"]))
            stack.append((layer, v))

        if dic.nodeName == "Filename":
            v = readFile(APP_Directory+"/"+dic.childNodes[0].nodeValue)
            print("{}[exec] ({}) {{{}}} <{}>".format(" "*(len(stack)*2), v["Name"], v["Exec"], v["Icon"]))

    if layer==1:
        for _ in range(len(stack)):
            stack.pop()
            print("{}[end]".format(" "*(len(stack)*2)))

def readFile(fileName):
    with open(fileName, "r", True, "UTF-8") as r:
        rec=dict()
        while True:            
            line = r.readline()
            if line=="":
                break
            line = line[:-1]

            pos = line.find("=")
            if pos >=0:
                key = line[0:pos]

                if ["Icon", "Name", "Exec"].count(key):
                    rec[key] = line[pos+1:]

        return rec


if __name__ == "__main__":
    main()
■fbmenugenにinclude機能を追加
diff --git a/fbmenugen b/fbmenugen
index 84e268b..fa5e784 100755
--- a/fbmenugen
+++ b/fbmenugen
@@ -401,6 +401,14 @@ ITEM_WITH_ICON
 ITEM
 }

+sub prepare_include {
+    my $path= shift() =~ s/\)/\\)/gr;
+
+    return <<"EOF"
+  [include] ($path)
+EOF
+}
+
 sub begin_category {
     $with_icons
       ? <<"MENU_WITH_ICON"
@@ -479,6 +487,9 @@ foreach my $schema (@$SCHEMA) {
     elsif (exists $schema->{item}) {
         $generated_menu .= prepare_item(@{$schema->{item}});
     }
+    elsif (exists $schema->{include}) {
+        $generated_menu .= prepare_include(@{$schema->{include}});
+    }
     elsif (exists $schema->{sep}) {
         $generated_menu .= "[separator]\n";
     }
diff --git a/schema.pl b/schema.pl
index 18a824a..50ae0dd 100644
--- a/schema.pl
+++ b/schema.pl
@@ -5,6 +5,7 @@
 =for comment

     item:      add an item inside the menu               {item => ["command", "label", "icon"]},
+    include:   add include another file               {include => ["path"]},
     cat:       add a category inside the menu             {cat => ["name", "label", "icon"]},
     sep:       horizontal line separator                  {sep => undef}, {sep => "label"},
     raw:       any valid Fluxbox menu entry               {raw => q(...)},
【2019/04/25 22:29 】 | linux | 有り難いご意見(4)
                                    
<<前ページ | ホーム | 次ページ>>