徐々に高度になるリングバッファの話、をRustで試した - Qiita
上記のうちRingBuffer0,1,2,3の実装をしました。 RingBuffer0,1は特に実装の違いはありません。 RingBuffer2はマルチスレッド化のためProducerとConsumerの構造体を追加しています。 RingBuffer3はアライン調整のために_paddingフィールドを追加しました。 MultiThreadはもとのコードはcpuset(0,1)決め打ちだったので、それに合わせたものとcore idが違う(0,2)も実施しました。 実行結果 リファレンス(AMD Ryzen 7735HS) リファレンスとなるkumagiさんのコードをg++ -O2でビルドしました。 RingBuffer0_single: 1000000000 ops in 939 ms 1064962.726 ops/ms RingBuffer1_single: 1000000000 ops
真のパスワード強度を測定する5つのアルゴリズム | 株式会社ヌーラボ(Nulab inc.)
Webサービスでアカウントを登録する際、パスワードを入力する度にその安全度を表してくれる強度メーター。皆様もおそらく目にしたことがあるのではないでしょうか。GoogleやFacebook、Twitterのような大規模なサービスでも、サインアップ画面等に設置されています。 このUIの要素は、MSR(Microsoft Research)の論文によると類推されづらいパスワードを促してサービスの安全性を高めることに効果的だということが証明されています。 お客様自身の大事な情報を守る上でとても重要なパスワード。ヌーラボアカウントでも、類推されにくいより強度の高い設定を促すためにパスワード強度メーターを設置しました。 この記事では、パスワード強度メーターを設置するに当って得た知見をもとに、その裏側の仕組みをご紹介させていただきます。 パスワード強度ってなに ？ そもそもパスワード強度とはなんなのか。
1988年
1988年5月1日，私は PC-VAN の SIG SCIENCE（私が SIGOP をしていたところ） の第1ボード「オムニバス・ボード」（現「科学一般」）に次の書き込みをしました。 #1073/2867 オムニバス・ボード ★タイトル (SCIENCE ) 88/ 5/ 1 15:39 ( 49) ＬＺＳＳ法によるデータ圧縮プログラム／奥村 ★内容 依然ある雑誌にＰａｓｃａｌで何かということで書いたのですが、その雑誌が休 刊中なので、ＴｕｒｂｏＣで書き直したものをアップします。 特徴は、圧縮率が非常に良いことと、符号化が非常に遅いことです。２分木など を使えば符号化は１桁速くなりますが、ＬＺＳＳ法そのもののアルゴリズムをはっ きりさせるために、できるだけシンプルに作りました。符号化に時間がかかっても、 アップやダウンの電話代を考えれば、少しでも圧縮率の良いもののほうが良いとい う考え方
珍しいSHA1ハッシュを追い求めて - プログラムモグモグ
「SHA1ハッシュってあるだろう？」 放課後、いつものように情報処理室に行くと、高山先輩が嬉しそうな顔でそう言った。 「ええ、SHA1、ありますね」 「SHA1って何桁か覚えているかい？」 「えっと…」 一年下の後輩、岡村が口を開いた。 「50桁くらいはありましたっけ…？」 先輩はパソコンに向かって何かを打ちはじめた。 現在、情報部の部員は三人しかいない。部長の高山先輩と、二年の自分と、後輩の岡村だ。いや、正確に言うと、先輩の学年にはもう少しいたのだが、もうほとんど部室に来ることはなくなってしまった。無理もない、この季節になると先輩たちは受験勉強で忙しくなる。 「例えば、こういうふうに… 適当なSHA1の長さを…」 echo -n | openssl sha1 | awk '{print length}' 部長だけは今も部活に来てこうやって色々なことを教えてくれている。本人曰く、普通に勉強
Golangの新しいGCアルゴリズム Transaction Oriented Collector（TOC）
http://golang.org/s/gctoc Goの新しいGCのProposalが出た．まだProposal段階であり具体的な実装はないが簡単にどのようなものであるかをまとめておく． GoのGCはGo1.5において単純なStop The World（STW）からConcurrent Mark & Sweepへと変更され大きな改善があった（詳しくは“GolangのGCを追う”に書いた）．先の記事に書いたようにGo1.5におけるGCの改善は主にレイテンシ（最大停止時間）に重きが置かれいた．数値目標として10msが掲げられGo1.6においては大きなヒープサイズ（500GB）においてそれを達成していた． GCの評価項目はレイテンシのみではない．スループットやヒープの使用効率（断片化の対処）なども重要である．Go1.6までのGCではそれらについて大きく言及されていなかった（と思う）．例えばスル
自動お絵かきロボを作る（その2） | fladdict
作成中の自動絵画プログラム。どうやら、みんなは「フォトショのフィルター的なモノ」を想像してるみたい。実はこのお絵かきロボ、一筆づつ丁寧に色を乗せていったりする。むっちゃ時間かかる。 アルゴ的には、遺伝アルゴリズムとA/Bテストの中間のようなロジックで動いてます。無数のパターンを一筆ごとに総当たりし、うまい感じに色がのった場合のみ採用みたいな。そんなわけで800px程度の大きさでも、1毎仕上げるのに2-6時間ぐらいかかります。 先にざっくり全体を下塗りしていくようにチューニング。 こちらが最新バージョン。ついに「主題でない部分に塗り残しや、筆跡などを多めに残す：チューニングが完成。 静物画の写真を、油絵に変換したもの。油絵っぽい写真を変換すれば、油絵になる。 ニワトリ。ちょっと目のコントラストが薄くて検出できなかった・・・失敗。それ以外はいい感じ。 サル。毛の質感はもう文句がない。あとは粗密
マルコフ連鎖を使ってブログの記事を自動生成してみた - karaage. [からあげ]
マルコフ連鎖による文章自動生成 ちょっと文章の自動生成に興味が湧いたので、試してみることにしました。まずは事前調査したところ、既にやっている例がたくさんみつかりました。記事末の参考リンクにまとめましたので興味ある方は参照ください。Deep Learningやマルコフ連鎖を使うのがトレンド（？）のようです。本当はDeep Learningでやってみたかったのですが、何度か環境変えてチャレンジしたのですが、悉くエラーが出て失敗したため(chainerのバージョンアップの影響？）、諦めてマルコフ連鎖で実現することにしました。マルコフ連鎖に関してはここでは詳細は説明しませんので、興味ある方は自分で調べてみて下さい。自分もちゃんと理解できませんでした。イメージ的には、元となる文章の文章の流れのようなものを解析して、その解析した流れを元に、ある単語から順番に連想ゲームのように単語を並べていって文章を生
![マルコフ連鎖を使ってブログの記事を自動生成してみた - karaage. [からあげ]](https://cdn-ak-scissors.b.st-hatena.com/image/square/1ad790dd78c936d38f8d2eb0256360a313006692/height=288;version=1;width=512/https%3A%2F%2Fcdn.user.blog.st-hatena.com%2Fdefault_entry_og_image%2F13239%2F1531150570465621)
クーポンコードの打ち間違えを防ぐために工夫した話 - クックパッド開発者ブログ
こんにちは。会員事業部ビジネス開発グループの高田です。 クックパッドは今年、株主優待制度として、プレミアムサービス一年間無料クーポンを贈呈しました。本エントリではクーポンコードを打ち間違えて、意図せず他の人のクーポンコードを使用するのを防ぐために工夫した話をご紹介します。 はじめに クーポンコードは入力のしやすさを優先して数字だけの文字列にしました。はじめは rand 関数を使って生成しようとしていたのですが、数字の打ち間違えや順序間違いで、意図せず誤使用してしまうのを防ぐためにチェックサムを加えるのがいい、と同僚から助言をもらいました。 いくつか調べて見たところ、Luhn アルゴリズムが上記を満たしていたので利用することにしました。 Luhn アルゴリズムの利用 Luhn アルゴリズムとは、誤り検出のためのチェックサム符号で、1 桁の間違いや隣接する数字の順序間違いを検出できるという特徴
C++: 構造体を格納したSTLコンテナに対してソート・探索・削除などのアルゴリズムを適用する
C++に慣れている人にとっては当たり前のことかもしれないけど、あまりC++に親しんでいない場合、構造体を格納したSTLコンテナに対してアルゴリズム<algorithm>を有効に活用していないかもしれない。そこで、構造体を格納したvectorなどのSTLコンテナでソートや探索、削除などのアルゴリズムの利用方法を書いておく。 struct A { int n; int* p; }; 上記のような構造体はよく見かける形だと思う。構造体Aに整数型変数のnとポインタ型変数のpがあり、例えばnに配列の要素数、pにその配列を確保したりする。こういった構造体を以下のようにvectorなどのSTLコンテナを使って格納することは多々ある。 vector<A> A_list; これで構造体Aをコンテナに格納できるわけだ。ところで、STLコンテナを使用する一つの理由として便利なアルゴリズムが利用できることが挙げら
QuickDrawはどのように素早く円を描いていたのか？ - ザリガニが見ていた...。
かつてのMac OS9までの描画エンジンの主役はQuickDrawが担っていた。GUIなOSでは、文字も含めてすべてをグラフィックとして扱うので、画面に見えているすべてのもの*1はQuickDrawによって描かれていたことになる。描画エンジンは、GUIなOS開発の要となる技術である。その出来が、GUIなOS開発の成否を分けるとも言える。 そして、最初期のQuickDrawは、ビル・アトキンソンがたった一人で開発したそうである。 当時（25年以上前）のCPUは、動作クロックが8MHzという性能だった。（現在は2GHz=2000MHzかつ、複数コアが当たり前） そのような性能であっても、違和感なくマウスで操作できるOS環境にするために、斬新な発想や試行錯誤を重ね、相当な努力の末に開発されたのがLisaやMacintoshであった。 Amazon.co.jp： レボリューション・イン・ザ・バレー
Every Byte is Sacred - 書評 - ガベージコレクションのアルゴリズムと実装 : 404 Blog Not Found
2010年03月20日04:30 カテゴリ書評/画評/品評Lightweight Languages Every Byte is Sacred - 書評 - ガベージコレクションのアルゴリズムと実装 著者より献本御礼。 ガベージコレクションの アルゴリズムと実装 中村成洋 / 相川光 / 竹内郁雄監 これほど地味かつ即実務に役立たない、しかし確実にプログラマーの滋養になる本が出版される日本の出版界に乾杯!世界で二番目(著者調べ)、国内で初のGC本は、実に滋味豊かだ。 とはいえ、本書はこの話題に関してMECEというわけでもない。というわけで本entryでは本書に何が書いていないかを主に紹介していく。何が書いてあるかは本書で確認すればよいのだから。 本書「ガベージコレクションのアルゴリズムと実装」は、コンピューターの資源管理の技術の一つ、ガベージコレクション(以下GC)についてまるまる一冊を費
ガベージコレクションの実装法と評価
1.はじめに プログラミング言語とはシステム化する対象物を抽象化し、コンピュータで処理可能なコードを記述するために用いる人工言語である。プログラミング言語はコンピュータの機械語と一対一の対応をもったアセンブラから始まり、コンパイラを用いて機械語に翻訳することを前提としたコンパイラ言語、インタプリタと呼ばれるプログラムがソースコードを解釈し実行するスクリプト言語と、記述できる抽象度を高める方向へと進化してきた。 プログラミング言語はその存在理由から、より抽象度の高い記述が行えること、すばやい開発を行える事が求められる。抽象度の高い記述とは、プログラムがどういう処理を行うか(HOW)ではなく何の処理を行うか(WHAT)を記述しやすい構文、機能を持っていることを、すばやい開発とは記述性の高さ、コードの密度の高さ、バグの発生しにくい構文、機能を持っていることをさす。 この抽象度の高い記述、すばやい
ゲーマーでなくても仕組みぐらいは知っておきたいアルゴリズムx40
高校生の時、数学の先生がこう言いました。 ゲームなんて、開発者が作ったルールの上で遊ばれるだけだ。 と。 その時、ゲーマーな自分はこう思いました。 ゲーマーは、開発者が作ったルールの上で遊ばれたい。 と。 というわけで、普段何気なくプレイしているゲームには、どのようなルール（アルゴリズム）があるのか。それを知るために、いろいろなゲームのアルゴリズムなどを解析しているページへのリンク集を作りました。 ほとんどのゲームのアルゴリズムは正式に発表されていないので、ユーザーの手による逆解析だったり、大学の研究による真面目な考察だったりします。（リンク先には、一部アルゴリズムと呼べないものも含まれています） 各種ゲームのプログラム解析 ドラクエ、FF、ロマサガのプログラム解析 DQ調査報告書（リンク切れ） ドラクエの物理ダメージ計算式は本質的にどれも同じだが、細かい部分で微妙に違う RPG INST
高速なロスレス画像圧縮技術、NECが開発 JPEG2000の数十倍
NECは7月25日、圧縮速度を高速化したロスレス画像圧縮技術を開発したと発表した。JPEG2000など既存の規格と同等の圧縮率を保ちながら、数十倍の速さで圧縮できるのが特徴。宇宙航空研究開発機構（JAXA）の金星探査計画で衛星画像処理に採用される予定。 一般に使われているJPEGなどの画像圧縮方式は、ファイルサイズが小さくなる分、元画像から画質が劣化する。 これに対しロスレス（lossless）画像圧縮は、画像の圧縮時に画質の劣化がないため、科学関連や医療画像、高品位デジタルカメラといった高精細な画像を扱う分野での利用が期待されてきた。ただ、圧縮時の演算量が増えて処理が重くなるため、低電力デバイスへの搭載が難しいなどの課題がある。 新開発の方式では、対象画像を写真や自然画像に限定し、独自の画素予測方式を考案することで演算負荷を軽減。JPEG-LSやJPEG2000の可逆モードと同等の圧縮率
エンカウントについて考えてみる
【はじめに】(2004/08/22) ＲＰＧで敵に遭遇するのをエンカウントと言います。エンカウント方法は単純なように思えて、実は奥深いです。そこでこのページではエンカウントに付いてあれこれ考えてみたいと思います。 ちなみに、以前書いた「レトロゲームにおける確率論」も多少関係するので、興味ある方は読んでみて下さい。 【エンカウント方法】(2004/08/22) ■ルーレット方式■ 一歩進むたびにルーレット（もしくはサイコロ）を回し、アタリならエンカウントする方法です。正しい呼び方じゃないかも知れませんが、一応ここではルーレット方式と呼ぶ事にします。 この方式は誰もがすぐに思いつくものですが、確率を計算してみると非常にバランスが悪い事が分かります。例えば、６面体のサイコロで赤ピンが出たらエンカウントすることにしたとします。この時、何歩歩いたらエンカウントするかを求めると、次のようになりま
Expired
Expired：掲載期限切れです この記事は，ロイター・ジャパンとの契約の掲載期限（30日間）を過ぎましたので本サーバから削除しました。 このページは20秒後にNews トップページに自動的に切り替わります。
良い乱数・悪い乱数
Ｃ言語標準ライブラリの乱数rand( )は質に問題があり、禁止している学会もある。 他にも乱数には様々なアルゴリズムがあるが、多くのものが問題を持っている。 最も多くの人に使われている乱数であろう Visual Basic の Rnd の質は最低である。 そもそも乱数とは 乱数とは、本来サイコロを振って出る目から得られるような数を意味する。 このような乱数は予測不能なものである。 しかし、計算機を使って乱数を発生させた場合、 次に出る数は完全に決まっているので、予測不能とはいえない。 そこで、計算機で作り出される乱数を疑似乱数(PRNG)と呼び区別することがある。 ここでは、特にことわらない限り乱数とは疑似乱数のことを指すとする。 計算機でソフト的に乱数を発生させることの最大のメリットは、 再現性があることである。 初期状態が同じであれば、発生する乱数も全く同じものが得られる。 このことは
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Printing 1 to 1000 without loop or conditionals
Amazon.co.jp: ガベージコレクションのアルゴリズムと実装: 中村成洋 (著), 相川光 (著), 竹内郁雄 (監修), 竹内郁雄 (読み手): 本
Technical documentation
