積の和典型 - Shirotsume の日記
最近積の和典型が話題になっているので書きます。 N個のマス目が横一列に並んでいる状況を考えます。初め、全部のマスは白色です。このうち K 個のマスを選んで黒く塗った時にできるマスの状態は何通りでしょうか？ これを こうする これは 通りです。 これを応用すると、次のような問題が解けます。 長さが N であって、総和が M である非負整数列の個数を求めよ。 非負整数列というのは、各要素が負の数でない整数からなる数列です。[1, 2, 3, 4, 5] とか [0, 0, 1, 4, 3] とかです。これの個数を数えるのに、先ほどのマスの数え方を使うことができます。 まず、 M + N - 1 個の白いマス目を用意します。そのあと、そこから N - 1 マス選んで塗ります。こうしたとき、必ず M 個のマスが白いままで残っています。また、マスの両端や黒マスを境目として考えると、白いマスが連続する
正規表現の脆弱性 (ReDoS) を JavaScript で学ぶ
先日、このようなツイートを書いたところ、かなりの反響がありました。 JavaScript の正規表現の脆弱性の例でいうと、例えば /\s+$/ は脆弱性があると言える console.time(); /\s+$/.test(" ".repeat(65536) + "a"); console.timeEnd(); 結構時間がかかるのがわかる。でも /\s+$/ を見て「これは危険だな」と理解出来る人はそんなにいない。JavaScript に限らないけれど。 — Takuo Kihira (@tkihira) February 17, 2022 これは一般に ReDoS (Regular expression Denial of Service) と呼ばれる脆弱性です。正確に理解するのが難しい脆弱性なので、少し解説してみたいと思います。 結論 長い記事になるので、最初に「とりあえずこれだけ知っ
FLoCとはなにか - ぼちぼち日記
1. はじめに Google がChrome/89よりトライアルを開始しているFLoC (Federated Learning of Cohorts)技術に対して、現在多くの批判が集まっています。 批判の内容は様々な観点からのものが多いですが、以前より Privacy Sandbox に対して否定的な見解を示してきたEFFの批判「Google Is Testing Its Controversial New Ad Targeting Tech in Millions of Browsers. Here’s What We Know.」が一番まとまっているものだと思います。 これまで Privacy Sandbox 技術に関わってきた身としては、各種提案の中でFLoCは特にユーザへの注意が最も必要なものだと思っていました。しかし、これまでのド直球なGoogleの進め方によって、FLoCのトラ
2億資金調達してから二年、結構量子コンピュータ頑張った結果 - Qiita
はじめに 2008年に起業してからコツコツやっていましたが、2014年くらいから量子コンピュータの研究開発をがんばりました。資金調達もしてある程度技術に目処がついたのと、若者から起業したいという相談をよくもらうので、まとめておきます。 経営は大事 簡単にいうとベンチャーをやろうとしたら技術よりもキャッシュが大事です。なので、財務や経営感覚がついてから技術をつけないと結構大変と思います。特に1年目は慣れない事務に忙殺されますし、二年目以降はキャッシュが厳しくなります。 あとは、最初は経営に夢見て舞い上がりがちなので、その気持ちがおさまって厳しさが一通り身についたところからが本番です。 調達の前に譲渡 2008年から10年くらいはコツコツ会社をやっていた上、そんなに頑張るタイプでもなかったのですが、たまたま2014年からやっていた量子コンピュータのニュースが巷で新聞に載るようになってから、周辺
今更だけど、データ圧縮についてまとめてみたい | 株式会社PLAN-B
bz2, xz, Deflate, gzip, zip, snappy, …データ圧縮に関しての名前です。 なんとなく見覚えがあるだけのものから、普段使いしているものまで色々あって、なんとなく使ってはいるけれど、それぞれどのような意図を持って使い分けたら良いのでしょうか。そもそもどんな違いがあるのでしょうか。 この違いがちゃんとわかっていたら、なんとなくかっこいい気がしませんか？というわけで、今回は圧縮アルゴリズムの歴史と、特性を追っていきたいと思います。 可逆圧縮と非可逆圧縮の違い圧縮をまず大きく大別すると、可逆圧縮と非可逆圧縮に分けられます。その名の通り、元に戻せる圧縮方法と、元には戻せない圧縮方法です。非可逆圧縮の用途には音声、画像や動画などの圧縮があります。 データとしてはわざと欠落させるけれど、人間の認識には影響の少ないようにするものがあります。用途、画像でよく使われるJPEGや
再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに 再帰関数は初めて学ぶときに壁になりがちで なんとなくわかった...けれど どんな場面で使えるのだろう...いい感じの例を探したい！ という気持ちになりがちです。再帰関数は、なかなかその動きを直感的に想像することが難しいため、掴み所が無いと感じてしまいそうです。 そこで本記事では 再帰関数の動きを追いまくることで、再帰関数自体に慣れる 再帰的なアルゴリズムの実例に多数触れることで、世界を大きく広げる！ ことを目標とします。特に「再帰関数がどういうものかはわかったけど、使いどころがわからない」という方のモヤモヤ感を少しでも晴らすことができたら嬉しいです。なお本記事では、ソースコード例に用いるプログラミング言語として C++ を用いておりますが、基本的にはプログラミング言語に依存しない部分についての解説を行っています。 追記 1. 再帰関数とは 再帰の意味はとても広いです。自分自
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
分散ロックという名の過ち - Software Transactional Memo
 TL;DR; 「分散ロック」が分散システムの設計図に登場した時 だいたいその設計は間違っていて本当に必要なものはトランザクションだ 並行システムを実装する際にロックを用いるのはとても自然なことだ。 僕も普段はロックフリー系のアルゴリズムに詳しいと言われがちだが知識量でいったら実はロック系の方が多く蓄えているかも知れない。 分散システムは並行システムであることが多いので、その中にロックが登場するのはとても自然な発想である。 よく「分散」「並行」「並列」の言葉の定義がごっちゃになっているケースがあり、この記事の主題にしたいわけではないので深くは言及しないが、分散システムは環境などの要因で突如として参加者が音信不通になったり復活したりする点で並行システムと大きく異なる。 並行システムと同じノリで分散システムを設計しようとした際に陥る頻出の過ちが「分散ロック」である。そのアイデアはとても簡単で
仕組みが分かれば、スマホなどいらぬ……ッ！ 肉眼のみで解読するQRコード講座
撮影することでURLなどを読み取れる正方形の模様、QRコード。スマホなどから利用するのが一般的ですが、どうしてもスマホが取り出せないときは、どうやって読み取ればいいのでしょうか。 ご存じの通り、人間にも目というカメラがあります。実は文明の利器なんて使わなくても、人力で解読できるのです。それでは、QRコードリーダーをあなたの脳にもインストールしてみましょう。 今回はこのQRコードを自力で読んでみましょう（CMANで作成） QRコードの基本構造を知ろう！ QRコードの構造。緑色部分は位置補正に必要なパターン、赤色部分はQRコードの読み取りに必要な情報（矢印の向きに読む） 内容を読み取る前に、そのための準備作業から始めましょう。 まず着目してもらいたいのが、QRコードの隅などにある四角形の模様です。これはカメラで読み取ったときの角度の違いを補正するためのもの。これ自体は読む必要がありませんが、周
ランキング設計はどうあるべきか？ その2｜深津 貴之 (fladdict)｜note
前エントリで論じられた、正しいランキング設計の考察の続き。第2回は、ランキングの収奪性、格差の固定性を軽減する手段を、具体的に論じてみる。 前回の記事へのTwitter上のフィードバックは、Togetterにまとめてある。こちらもご興味があれば、一読の価値がある。いくつか被ってしまったものもあるけれど、諸々の後半記事。 「ランキング」以外の名称を用いるこれはほぼ確定。ランキングという名前は、「noteとして競争原理を推奨する」という強いメッセージを発する。noteの全てのユーザーが、競争原理で動いているわけではないので、これは望ましくない。 おそらく最終的には「注目」「人気」などの名称を使うことになるかと思われる（「オススメ」はパーソナライズ用にとっておく）。また、「ランキング」という名称やスタンスをやめることで、後述するようないくつかの公平性のための施策を行う余地が生まれる。 時間による
最強ソフトの言うことの真逆をやると最弱になるのか検証してみた - コンピュータ将棋 Qhapaq
今や将棋研究のお供の定番である将棋ソフトですが、その裏で初心者の練習相手としても定番になりつつあるようです。駒の動かし方を覚えた人が次にやるべきなのが数練習をすることであり、数をこなす為のモチベーションを維持する際に、無限に遊んでくれてしかも負けてくれる将棋ソフトにニーズがあるようです。 どのぐらいニーズがあるかというと、絶対王者のponanzaさえも弱いソフトを作ることに一石投じる程度にはニーズがあるようです。 将棋ウォーズにある史上最強に弱いPonanzaの話｜山本 一成@Ponanza｜note 曰く、クッソ強いponanzaの評価値を反転すればクッソ弱いソフトが出来る。 成る程。ponanzaが全力で悪くなる局面を探してくれるなら、確かに弱くなりそうだ。しかし私はこの記事を見て「ソフト同士が負けることに全力を尽くした場合、果たしてどのくらいまで弱くなるのか」が気になりました。 ここ
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ - エンジニアHub｜若手Webエンジニアのキャリアを考える！
HashDoS脆弱性との戦い！ Rubyコミッター・卜部昌平が明かすプログラム堅牢化のノウハウ 過去、HashDosの影響を受けたRuby。言語開発者はいかにしてこうした問題に対応してきたのでしょうか。コミッターである卜部氏の貴重な記録を公開します。 2011年の末頃、HashDoSという脆弱性が公表され、Rubyもこの影響を受けた。本稿の筆者である卜部昌平（うらべ・しょうへい／@shyouhei／以下、卜部）は、報告当初からRuby側のチームメンバーとしてプログラム本体の修正を担当した。以下はその記録である。言語開発者たちが普段どのようなことを考え、どういった技術を用いて開発やバグフィックスを行っているのか。その概要を知ってもらえれば幸いだ。 オブジェクト指向スクリプト言語 Ruby HashDoSの概要 なぜ約6年後の今、修正内容を公開するに至ったか？ 前史：すでに内包されていたリスク
ID生成大全 - Qiita
セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い
C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った - Qiita
インクルードするだけで使えるNon-movingで正確なGCをC言語用に作りました。 行数がコメントを除いて100行に満たない非常に小さなライブラリです。 GCのアルゴリズムとしてはCheneyのコピーGCを採用しています。 通常のCheneyのコピーGCではメモリ空間のうち半分が無駄になってしまいメモリ効率が悪かったり、 GC発生時にオブジェクトが移動してしまいC言語のようなポインタを直接触れる言語との相性が悪いという欠点がありました。 今回はヒープ全体を二重連結リストとして管理することでそのような問題を解決しています。 ちなみにこれはTreadmill GCのアイデアと同じです。(が、アルゴリズム自体はTreadmill GCではありません。) APIはLinuxのlist.hに非常に近い見た目になっています。 ある構造体をgcで管理したい場合はstruct gc_head型のメンバを
B TreeとB+ Treeの違い - Carpe Diem
概要 インデックスに対してMongoDBはB Treeを採用し、MySQLのInnoDBはB+ Treeを採用しています。 どうして採用しているアルゴリズムが違うのだろう？と思って調べてみました。 主な違い B+ TreeはほとんどB Treeと同じですが、以下の点が異なります。 リーフノードとリーフノードを結ぶポインタがある データはリーフノードのみに保持する 具体例 言葉だけだと分かりにくいので、Visualizeするツールを使って具体例を表示します。 [1, 2, 3, 4, 5, 6, 8, 10, 15, 18]という数列に対し、Order: 3で作ってみます。 Orderは１ノードから出る枝の数のことです。 B Tree B-Tree Visualization B+ Tree B+ Tree Visualization 先程のB Treeと違って、データはリーフノードに持つの
アリの行動に学ぶ、より多くの脱出を可能にする非常出口の設計手法とは
多くの人が集まったり一定の広さを持つ部屋には、万が一の事態にも安全に脱出できる非常出口の設置が法律で定められています。効率的な避難路を確保するために非常口の周辺には障害となる物を置かないことが必要とされていますが、アリを使って特定の条件下で行われた一連の実験の結果では、非常出口の前に障害物を置いたほうが、脱出のスピードが速くなるという意外とも言える結果が明らかになりました。 Want to Get Out Alive? Follow the Ants - Issue 13: Symmetry - Nautilus http://nautil.us/issue/13/symmetry/want-to-get-out-alive-follow-the-ants これらの実験の対象となったのは、アリ科の中でも大型に分類されるキューバアリで、その生態を観察することで検証が進められました。実験を行っ
Big Sky :: レーベンシュタイン距離を使ったあいまい grep コマンド「lsdgrep」作ってみた
元ネタはずいぶんと昔の記事なのだけど。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー ■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン... http://d.hatena.ne.jp/naoya/20090329/1238307757 思い付きはまったく関係ない所から。 mp3 が数千ファイル入ってるフォルダで何かの手違いで同じ曲が入ってしまう事が結構あって重複取り去る作業してた。ID3が違ってるとMD5も違うのでレーベンシュタインの文字列距離を使ってファイル名が似てるの調べたら422ファイル消せる事が分かった。 — Vim芸人 (@mattn_jp) February 25, 2017 これを
私たちはいかにして環状線で”悪さをする列車”を捕まえたか | プログラミング | POSTD
文：Daniel Sim 分析：Lee Shangqian、Daniel Sim、Clarence Ng ここ数ヶ月、シンガポールのMRT環状線では列車が何度も止まるものの、その原因が分からないため、通勤客の大きな混乱や心配の種となっていました。 私も多くの同僚と同じように環状線を使ってワンノースのオフィスに通っています。そのため、11月5日に列車が止まる原因を調査する依頼がチームに来た時は、ためらうことなく業務に携わることを志願しました。 鉄道運営会社SMRTと陸上交通庁（LTA）による事前調査から、いくつかの電車の信号を消失させる信号の干渉があり、それがインシデントを引き起こすことが既に分かっていました。信号が消失すると列車の安全機能である緊急ブレーキが作動するため、不規則に電車が止まる原因となります。 しかし8月に初めて発生した今回のインシデントは、不規則に起こっているように見えるた
西川善司の3DGE：知られざるPS4 Proの秘密（2）明らかになった「4Kレンダリングのレシピ」
西川善司の3DGE：知られざるPS4 Proの秘密（2）明らかになった「4Kレンダリングのレシピ」 ライター：西川善司 SIEの取締役副社長 兼 ハードウェアエンジニアリング＆オペレーション本部長である伊藤雅康氏（左）と，リードシステムアーキテクトであるMark Cerny（マーク・サーニー）氏（右）。今回の技術セミナーでは約9割をCerny氏が担当した 2016年11月10日に発売となった「PlayStation 4 Pro」（以下，PS4 Pro）の秘密に迫る本シリーズ。前編では主にスペック周りを掘り下げたが，後編となる今回はさらに深いところへ切り込んでいきたいと思う。 今回のテーマは「レンダリング」である。 9月のPS4 Proの発表時点で筆者は，当時の限られた情報を基に「PS4 Proの4Kグラフィックスは，リアルな4K解像度レンダリングではなく，アップスケール表示になる」とお伝え
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
アルゴリズムビジュアル大事典