|
× [PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。 |
 |
|
javaでflatMapを覚えてから奇妙だなと思っていた。
これって何に使うのだろうかと。 結論から言うと直積を求めたいときに使うのである。 もし、組み合わせを求めたい場合、どのように求めるだろうか。 ■pythonソース teams = range(5) [(x, y) for xi, x in enumerate(teams) for yi, y in enumerate(teams) if xi < yi]■python結果 [(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 実はこれと同じことをflatMapでも行える。 ■javascriptソース range = (x)=>function*(){ for(var i = 0;i<x;i++) {yield i;}};
teams = range(5);
Array.from([[]])
.flatMap(x=>Array.from(teams()).map(y=>x.concat(y)))
.flatMap((x, xi)=>Array.from(teams()).filter((y,yi)=>xi<yi).map(y=>x.concat(y)))
■javascript結果(10) [Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2), Array(2)] 0: (2) [0, 1] 1: (2) [0, 2] 2: (2) [0, 3] 3: (2) [0, 4] 4: (2) [1, 2] 5: (2) [1, 3] 6: (2) [1, 4] 7: (2) [2, 3] 8: (2) [2, 4] 9: (2) [3, 4] length: 10 __proto__: Array(0)おもしろいなあ。
PR |
|
|
グラフを作りたかったので、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];
}
正攻法ではない気がするけど、まあ良しとしよう。
|
|
|
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)
#１項目め降順、２項目め昇順
print(sorted(arr, key=Keys.of((False, True))))
#１項目め２文字目昇順、１項目め１文字目昇順
print(sorted(arr, key=Keys.of((True, False), keymap=lambda x:(x[0][1], x[0][0]))))
うん、素晴らしい。
|
|
|
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.001score4個分で20秒から6秒にその後、8個に増やしても増えませんでした。。。 なかなかのパフォーマンスなり。
|
|
|
SECCON令和CTFへ参加したなり。なんとか2問（1問サービス問題）解けて423位/858。まずまずかなー。
解けた１問の解き方。 ■問題 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))
|
|
|
忍者ブログ [PR] |
