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による実務で役立つ
量子コンピュータでも解読できない暗号技術、東大らが開発
東京大学と九州大学マス・フォア・インダストリ研究所、日本電信電話（NTT）の研究チームは11月24日、量子コンピュータでも解読できない新たなデジタル署名「QR-UOV署名」を開発したと発表した。 この署名は、既存の技術よりも署名と公開鍵のデータサイズが小さいのが特徴。多項式の割り算の余りを使って新しい足し算や掛け算ができる代数系「剰余環」を公開鍵に使うことで、安全性とデータの軽減を両立しているという。 現在普及している暗号技術には、 Webブラウザに使われる「RSA暗号」や、画像の著作権保護や暗号資産に使われる「楕円曲線暗号」がある。これらは、大規模な量子コンピュータが実現した場合、解読されるリスクがあるという。そのため、量子コンピュータが大規模化した時代でも安全に利用できる技術の開発が進んでいた。 中でも、1999年に提案され、20年以上にわたり本質的な解読法が報告されていない「UOV署
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
カルマンフィルターが自動運転の自己位置推定で使われるまで - TIER IV Tech Blog
はじめまして、ティアフォー技術本部 Planning / Controlチームで開発を行っている堀部と申します。 今回は状態推定の王道技術「カルマンフィルター」が実際に自動運転で用いられるまでの道のりやノウハウなどを書いていこうと思います。 みなさんはカルマンフィルターという言葉を聞いたことがありますでしょうか。 カルマンフィルターとは「状態推定」と呼ばれる技術の一種であり、自動運転においては現在の走行状態、例えば車速や自分の位置を知るために用いられます。 非常に有名な手法で、簡単に使えて性能も高く、状態推定と言えばまずカルマンフィルターと言われるほど不動の地位を確立しており、幅広いアプリケーションで利用されています。 使い勝手に定評のあるカルマンフィルターですが、実際に自動運転のシステムとして実用レベルで動かすためには多くの地道な作業が必要になります。 この記事では、カルマンフィルターが
はてブ人気コメント算出アルゴリズム変更と自由で公平な表現の場 ／ ʕ•̫͡•ʔワンクリック入力用Chrome拡張機能を作った件 - ドサンピン茶
目次 目次 はてブ人気コメント算出アルゴリズム変更と自由で公平な表現の場 ʕ•̫͡•ʔワンクリック入力用Chrome拡張機能を作った件 はてブ人気コメント算出アルゴリズム変更と自由で公平な表現の場 ここのところ、立て続けに表現の自由*1に関連して苛立ちを感じる出来事が続出することが続いており、なんだか私とても苛立っております（リアル鬼ごっこ構文） 具体的には、小林賢太郎氏の解任のキッカケになったアレとか、藤本タツキ氏の読切作品の登場人物に関するアレとかです。*2 表現の自由に関する個人的見解については以前記事を書いたことがありますので（ゾーニングは規制か？ - ドサンピン茶）今回は細かく語りませんが、個人がネットを介して群れとなることで公権力に比するパワーを持ち得る現代においては、こうした市民自身の手から表現の自由を保護するための新たな仕組み（法規制等）作りも真剣に検討する必要があるのでは
はてブのコメントが大幅に仕様変更されて不評らしいけど、これって、かつ..
はてブのコメントが大幅に仕様変更されて不評らしいけど、これって、かつて行われた「歌舞伎町浄化作戦」みたいなものだよね ぶっちゃけ今のはてブって「５ちゃんねる@はてブ板」ってくらい閉鎖的で偏った傾向の人達のたまり場になってしまっていて、それでも板の中に籠もってよろしくやってるのならともかく、外部サイトだろうが無差別に一言書き捨てていくのが当たり前の文化だから外部からはすこぶる評判が悪い しかも活発に書き込んで上位にランクされる人ほど、ブックマークされた側にとって不愉快なコメントが多い 一番の解決方法ははてなブックマークそのものをサービス停止する事なんだろうけど、さすがにそれはできないからコメント評価のアルゴリズムそのものを変えてしまう戦略をとったんだろう この件で文句たらたら言ってる人達、運営から「Not For You(あなたのために提供しているサービスではない)」と暗に言われてる事に気付
はてなブックマークの破滅的人気コメントを表示する - Qiita
何があったか はてなブックマークは、コメント表示改善の一環として、Yahoo! JAPANの「建設的コメント順位付けモデルAPI」を導入し、攻撃的であったり不謹慎であるなど穏当でないコメントが人気コメントに掲載される問題を抑制する取り組みを開始しました。 実は、公式の発表が知れ渡る前にAnonymousDiaryというサービスで話題になり、喧喧囂囂の大騒ぎとなったのです。 誉れ高い増田市民としては、旧来の破滅的コメント順位を望みます。 Pythonによる解決 googleのcolabで作業してました。 記事の情報をAPIで入手 記事jsonからブクマした各ユーザの「コメント情報のURI」を生成する スター取得APIでコメントURIを指定し、スター数を算出 各コメントのスター数を出し、上位10個を表示 後述するjsonの概要を見るとイメージがつきやすいかもしれません。 import json
はてブの「人気コメント」に Yahoo! の「建設的コメント順位付けモデルAPI」を導入
ⓘ人気コメント算出アルゴリズムの一部にヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています さっきまでは無かったのでここ１時間～数十分くらいで変更されたのか 「建設的コメント順位付けモデルAPI」ってのはこれか Yahoo!ニュース、不適切コメントへの対策として導入している深層学習を用いた自然言語処理モデル（AI）のAPIを無償提供開始 - ニュース - ヤフー株式会社 Yahoo!ニュース、不適切コメントへの対策として導入している 深層学習を用いた自然言語処理モデル（AI）のAPIを 「NewsPicks」、「攻略大百科」、「ママスタコミュニティ」へ無償提供開始 - ニュース - ヤフー株式会社
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました． その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました． 最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1． さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました． 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://twitter.com/Idesan/status/1564393355743723523
食べログ、裁判でアルゴリズム「異例」の開示 評価透明化なるか | 毎日新聞
建設的APIハック会場A
『建設的APIが導入されて10年、ブクマカがAPIハックを繰り返した結果、新しい言語がʕ•̫͡•ʕ•̫͡•ʔ•̫͡•ʔ•̫͡•』へのコメント
はてブの人気コメントの算出方法が変わるらしいけど、はてなさんそれはや..