Reservoir sampling - Wikipedia
Reservoir sampling is a family of randomized algorithms for choosing a simple random sample, without replacement, of k items from a population of unknown size n in a single pass over the items. The size of the population n is not known to the algorithm and is typically too large for all n items to fit into main memory. The population is revealed to the algorithm over time, and the algorithm cannot
大量のテキストからランダムに少数の行を抽出したい - Reservoir Sampling - 唯物是真 @Scaled_Wurm
前に以下のような記事を書きましたが、大量のテキストではうまくいかなかったので新たに書きました ファイルからランダムにN行取り出す(shufコマンド) - 唯物是真 @Scaled_Wurm 上の記事ではテキストをランダムに\(k\)行取り出したい時"shuf -n k"コマンドでランダムにシャッフルした\(k\)行を取り出していました ところが非常に大きなテキストファイルに対して上のコマンドを実行すると、一度にデータを全部メモリに読み込み始めているのか、すごい勢いでメモリを消費していきました(sort -Rでも) そこでメモリをあまり使わずにランダムに\(k\)行取り出す方法について調べました まず基本的な非復元抽出のアルゴリズムは以下の記事の発展手法とか追記のあたりの話がわかりやすいと思います 非復元抽出の高速かつ実装が簡単な方法を考える - 睡眠不足？！ この記事の話も一度全部の要素を
6x6リバーシの神 - まめめも
絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。 絶対に勝てない6x6リバーシを作りました！ ぜひ挑戦してみてくださいhttps://t.co/Ul5n3q9jMp— Yusuke Endoh (@mametter) December 30, 2021 これは何？ 6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番（後手）で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。 技術的な話 このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。 AIのソースコードはRustで書きました。わりと堅実なゲーム木探索になってます。UIは普通にTypeScriptとthree.jsで実装しました。 github.com 作った順に説明します。 盤面の表現
型安全で高速な連鎖行列積の計算
この記事は Haskell Advent Calendar 2021 の22日目の記事です。 次のような３つの行列の積を考えてみましょう。 ABC = \begin{pmatrix} a_{00} & a_{01} & a_{02} \\ a_{10} & a_{11} & a_{12} \\ a_{20} & a_{21} & a_{22} \\ a_{30} & a_{31} & a_{32} \\ \end{pmatrix} \begin{pmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \\ b_{20} & b_{21} \\ \end{pmatrix} \begin{pmatrix} c_{00} & c_{01} & c_{02} & c_{03} & c_{04} \\ c_{10} & c_{11} & c_{12} & c_{13}
【VSCode】Undo/Redoに革命を起こしたい - Qiita
この記事は、東京大学工学部電子情報工学科/電気電子工学科の後期実験「大規模ソフトウェアを手探る」のレポートとして作成されました。 Undo/Redo の履歴が消える悲しみ 編集系のソフトウェアで誰もがお世話になっているであろう Undo/Redo 機能ですが、このような悲しみに襲われたことはないでしょうか？ 「以前の状態に戻したいのに、履歴が消えて戻せない〜〜〜」 講義室でアンケートを取ったところ、8 割以上の方がこの悲しみを経験されていたようです。 といっても、ピンとこない方がいると思うので、具体的にどういう問題があるのか説明していきます。 テキストエディタを例にとります。まず、操作 A, B, C を行います。ここでいう「操作」は、文字列の入力や Back space など、Undo/Redo 以外でエディタの編集状態を変えるものを指します。 続いて Undo を行います。 続いて操作
Python言語による実務で使える100+の最適化問題 | opt100
はじめに 本書は，筆者が長年書き溜めた様々な実務的な最適化問題についてまとめたものである． 本書は，Jupyter Laboで記述されたものを自動的に変換したものであり，以下のサポートページで公開している． コードも一部公開しているが，ソースコードを保管した Github 自体はプライベートである． 本を購入した人は，サポートページで公開していないプログラムを 圧縮ファイル でダウンロードすることができる． ダウンロードしたファイルの解凍パスワードは<本に記述>である． 作者のページ My HP 本書のサポートページ Support Page 出版社のページ Pythonによる実務で役立つ最適化問題100+ (1) ―グラフ理論と組合せ最適化への招待― Pythonによる実務で役立つ最適化問題100+ (2) ―割当・施設配置・在庫最適化・巡回セールスマン― Pythonによる実務で役立つ
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
はてなブックマークの破滅的人気コメントを表示する - Qiita
何があったか はてなブックマークは、コメント表示改善の一環として、Yahoo! JAPANの「建設的コメント順位付けモデルAPI」を導入し、攻撃的であったり不謹慎であるなど穏当でないコメントが人気コメントに掲載される問題を抑制する取り組みを開始しました。 実は、公式の発表が知れ渡る前にAnonymousDiaryというサービスで話題になり、喧喧囂囂の大騒ぎとなったのです。 誉れ高い増田市民としては、旧来の破滅的コメント順位を望みます。 Pythonによる解決 googleのcolabで作業してました。 記事の情報をAPIで入手 記事jsonからブクマした各ユーザの「コメント情報のURI」を生成する スター取得APIでコメントURIを指定し、スター数を算出 各コメントのスター数を出し、上位10個を表示 後述するjsonの概要を見るとイメージがつきやすいかもしれません。 import json
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
Dammアルゴリズム - Wikipedia
Dammアルゴリズムは、誤り検出の一種であるチェックディジットのアルゴリズムであり、全ての1桁入力誤りと全ての隣り合う2桁の入れ替え誤りを検出することができる。2004年にH. Michael Dammによって発表された[1]。 利点と欠点[編集] Dammアルゴリズムは、Verhoeffアルゴリズムと同様に、最も頻繁に起こる2種類の誤り、すなわち1桁の入力誤りと、（末尾に付け足されたチェックディジットとその直前の数字の入れ値替えを含む）隣り合う2桁の入れ違えの、2種類の誤りを検出できる[1][2]。しかしDammアルゴリズムは、Verhoeffアルゴリズムと異なり、実行に際し、専用に構成された置換表と位置に応じた冪乗表を必要としない。さらに、逆元の表も演算表の主対角成分が0の時は必要ない。 Dammアルゴリズムは10種を超えるチェックディジットを出力しないため、（ISBN10のチェックデ
テキシコー | NHK for School
この番組は、思わず頭の中で手順を組み立て、先を予想したくなるような興味深い実験、手順の組み合わせを改善していく楽しさを伝えるアニメーション、さまざまな仕事や物の中にプログラミング的思考が活かされていることを伝えるコーナーなどで構成されています。番組の中では、実際にコンピューターを使ったプログラミングを体験するシーンは出てきません。コンピューターへの苦手意識やICT 環境を問わず、誰でも楽しくプログラミング的思考を育めます。コンピューターを使ったプログラミングへの導入としてはもちろん、実際のプログラミング体験をした後でも、活用できる番組です。
ルービックキューブを解くプログラムを書いてみよう(前編:キューブを操る実装) - Qiita
はじめに この記事はルービックキューブ Advent Calendar 2018 の14日目の記事です。 昨日の記事は望月さんの「ラノベで覚えよう！目隠しキューブ。「恋するイヤーマフ」」でした。 本連載では、ルービックキューブを解くプログラムをPythonで実装しながら、その仕組みを勉強します。 ルービックキューブを解くプログラムと言っても、どれくらい頑張って高速化・効率化するかなどあると思うので、今回の記事では、大体1秒位 & 20手強くらいで解くプログラムを書くのを目標に、コードのわかりやすさ重視でやっていきましょう。 ルービックキューブを効率よく解くアルゴリズムとしてTwo-Phase-Algorithmというものが広く使われています。 本連載でも、Two-Phase-Algorithmを実装します。 まだ、前編しか書けていないので、内容は変わるかもしれませんが、 前編と中編では、実
クイックソートは半順序でもソート可能であることをCoq/SSReflectで証明する - Qiita
はじめに 前回の記事で、全順序が仮定されているからこそうまくいくソートアルゴリズムを半順序で使用するとどうなるかを見ました。結果としてクイックソートなら半順序でもうまくソートできることを見ましたが、本記事では、これを定理証明支援系Coqを用いて、形式的に証明していきます。 定理証明支援系Coqに関して軽く説明しておくと、プログラムが正しく動くことを、数学的に検証できるツールとして使えるものです。 クイックソートを定義 SSReflectのpathライブラリには、標準のソート関数sortが定義されていますが、このアルゴリズムはマージソートなので、前回の記事で検証したように半順序では使えません。 そこでCoqでクイックソートを定義します。 まず定義の前に、ソートを行う要素の集合Tと、半順序関係Rを宣言しておきます。実際にはTは型で、RはただのT上の二項関係T -> T -> boolとして定義
数学はアートを創るか？―Processingによる実践
Моделювання на ЕОМ. Теоретичні питання моделювання.
『みんなのデータ構造』発売および予約開始のお知らせ – 技術書出版と販売のラムダノート
ご来店ありがとうございます。 本日より、新刊『みんなのデータ構造』の発売を開始しました。紙書籍の発送は7月25日前後を予定しています。電子書籍は購入後すぐにお読みいただけます。 『みんなのデータ構造』は、Pat Morin氏による “Open Data Structures” を翻訳して書籍として出版するものです。Pat Morin氏による原文は、クリエイティブコモンズ継承ライセンス（CC BY）で公開されており、誰でも自由に教材として活用できるだけでなく、内容に手を入れて別のライセンスで再配布したり、販売したりできるようにされています。堀江氏、陣内氏、田中氏による翻訳と、ラムダノート株式会社による編集も、すべてCC BYで公開しており、同様に自由に利用していただくことが可能です。 書籍版『みんなのデータ構造』（紙書籍および電子書籍）につきましては、クリエイティブコモンズライセンスではなく
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
「遺伝的アルゴリズムで最高にエッチな画像を作ろう！」がまるで意思があるかのように1日で大きな変貌を遂げてしまう→その原因も判明する
アルゴリズムビジュアル大事典
GitHub - qulacs/quantum-native-dojo: 量子コンピュータ初学者のための自習教材
https://docs.google.com/presentation/d/1LHplQ8nqNJNxaqY7DL4eM329jZKfO-E15XHoadYeLfE/mobilepresent?slide=id.g240ca7fffa_0_15369
