「速く計算するには多くのメモリが必要」という50年来の常識を覆す？ 米MIT教授が新理論 査読前論文を発表
このコーナーでは、2014年から先端テクノロジーの研究を論文単位で記事にしているWebメディア「Seamless」（シームレス）を主宰する山下裕毅氏が執筆。新規性の高い科学論文を山下氏がピックアップし、解説する。 X： ＠shiropen2 米国マサチューセッツ工科大学（MIT）のライアン・ウィリアムズ教授が発表した論文「Simulating Time With Square-Root Space」は、コンピュータが計算処理を行う際の「時間」と「空間」の関係性について、従来の理論を大幅に改善するという研究報告（査読前のプレプリント）である。速く計算するには多くのメモリが必要という50年来の常識を覆す可能性を示す。 計算機科学で「時間」とはコンピュータが実行する処理ステップの数を意味し、「空間」とは計算に必要なメモリ使用量を指す。 約50年前の1970年代、チューリングマシンが時間tを要する
NTTがグラフ探索の高速化アルゴリズム開発 スパコン富岳のBFS世界1位に貢献
NTTは、2024年6月25日、グラフ探索を高速化するアルゴリズムを開発したことを発表した。 多くの情報は事物のネットワーク構造として解釈可能であり、そのつながりを「頂点」と「辺」で表現するグラフは、都市インフラやAI、セキュリティ、創薬などの分野で重要視されている。 このグラフデータの活用に向け、同社ではグラフ処理における基礎的な要素技術であるBFS（幅優先探索）の研究を続けてきた。BFSは、グラフ全体の頂点を近い順に辿る計算方法となる。 木構造の事前分離により BFS木構築を高速化 今回NTTが確立したのは、「Forest Pruning」という、始点から近い順に頂点を辿るための「BFS木」の構築を高速化するアルゴリズムだ。 まず、事前計算でグラフの一部（木構造部分）を分離。始点が与えられた際に、残ったグラフで頂点を辿って部分的なBFS木を構築する。そこに分離しておいた木構造部分を接合
正規分布に従う疑似乱数を生成する方法は？速度は？調べてみました！
この文書は 応用情報 Advent Calender 2020 に投稿した PDF の記事 の Web ページ版です。 はじめに こんにちは。応用情報 Advent Calender 2020 も9日目に突入しましたが、みなさまいかがお過ごしでしょうか。知的情報処理研究室 M1 の生田です。 正規分布は自然現象を良く表現する 1 ことから、数値シミュレーションをはじめとした工学上の応用が数多くあります。また、正規分布からのサンプリングは、他の確率分布（t分布やベータ分布など）に従う乱数の生成にも用いられるため、直接的に正規分布を用いないシミュレーションでも、間接的に正規分布が必要になることがあります。私たちの研究室でも、ニューラルネットワークの重みの初期値など、正規分布は至るところで活躍しています。 しかし、現在広く使われている疑似乱数生成アルゴリズム（線形合同法やメルセンヌ・ツイスターな
Marathon Match 147 SurfaceReconstruction 参加記 - simanのブログ
問題 www.topcoder.com 提出コード https://gist.github.com/siman-man/2218aee9a4a99e3bc6c780dbb72066ba 方針 N と A の値からサンプリングの回数を決定 クエリーの投げる位置を焼きなましで調整 クエリーの結果からグリッドを生成している方程式のパラメータを焼きなましで求める N と A の値からサンプリング回数を求める サンプルの個数から大体これぐらいの mse スコアが出るよというのを事前に計算しておいて、ちょうどいい感じのサンプル個数を求める。 mse の推測値が悪かったのか N < 40 のケースだとうまくいかなかったので場合分け。もっと細かく調整できたと思うけど多分そんなスコア改善しないし面倒なのでやってない。（cover_rate は sample_count * 9 / (N * N) で計算して
ビームサーチをライブラリ化する【基礎編】 - 競技プログラミング学習
7/30 追記：一部の実装を変更して高速化しました。(ビームサーチ内で毎回配列を定義するコストが無視できなかったため、一度だけ定義して毎回中身を全て消去する形にしました) ヒューリスティックコンテストでよく用いられるビームサーチという手法があります。山登り/焼きなまし法と並んで必ずと言っていいほど紹介されるビームサーチですが、実装が大変と感じている方も多いと思います。 この記事ではビームサーチを既に知っている方向けに、ライブラリ化の指針を提供したいと考えています。ビームサーチ自体については簡単に説明する程度ですのでご了承ください*1。 今回は基礎編と題して、一般に広く用いられていると思われる実装方法を紹介します。応用編*2ではrhooさんの記事などで解説されている他の実装方法を紹介したいと考えています。本記事中のソースコードは自由に利用していただいて構いませんが、万一何らかの不利益が生じて
燃やす埋める問題とProject Selection Problemの整理 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 2021年3月から毎日問題が公開されている「競プロ典型90問」、皆さま解いていらっしゃいますでしょうか？ 一昨日、第40問として公開された「Get More Money」が解説を読み、その後いろいろな記事を見ても理解が難しかったので整理してみました。 当然のことながらこの問題の解法に触れますので、問題に挑戦したい方はこの記事は後からお読みいただくことをお勧めします。 AtCoder常設ジャッジ 問題画像 公式解説 何が理解できなかったのか 公式解説にもある通り、この問題はいわゆる「燃やす埋める問題」というタイプの問題です。公式解説は紙面
この木なんの木？ モンテカルロ木と最良優先MiniMax木の"間"に存在する名もなき木々 - ヴァルの開発記
概要 この記事ではまだ名前が無いと思われるゲーム探索木をいくつか紹介します。この記事では具体的な実装は示さず、概念の紹介にとどめます。 この記事を読むために必要な知識は以下です。 ・モンテカルロ木探索＋UCB1 ・MiniMax探索 ・ボンバーマンの基本的なルール 名のある木々 名もなき木々を紹介する前に、まずは名のある木々を紹介します。 MCTS モンテカルロ木探索。簡単に言えば、評価関数を使わず、ランダム試行を繰り返して勝率の平均が高い手を調べる手法です。 有名な木なので、検索するとたくさん解説がヒットするのでこの記事では説明を割愛します。 一応参考として、私が初めてMCTSを実装したときに参考にした論文を載せておきます。 →A Survey of Monte Carlo Tree Search Methods 最良優先MiniMax 最良優先MiniMax探索についてはこちらの論文が
最適化AIでサービス生み出すリクルート、領域と技術の「かけ算」が奏功
人工知能（AI）というと機械学習や深層学習が注目されがちだが、実はそれはAIの半分にすぎない。あとの半分、いわば「アナザーAI」は企業の生産計画や物流などで重要な役割を果たす「最適化AI」だ。最適化AIを実現するための技術が、「焼きなまし法」や「ビームサーチ」などの「ヒューリスティックアルゴリズム（メタヒューリスティクス）」である。この連載では、競技プログラミングサービスを提供しているAtCoderの高橋直大社長が、アルゴリズムに対する深い知識を生かし、最適化AIを活用している企業を訪ねて取り組みを探っていく。 今回は、飲食や美容などさまざまな領域で消費者向けや企業向けのサービスを提供しているリクルートを訪問した。データ関連技術を統括する同社プロダクト統括本部 プロダクト開発統括室 データ推進室 データテクノロジーユニットの阿部直之ユニット長に、最適化AIを使ったサービスの取り組みを聞いた
IEEE浮動小数点数における平方根演算の精度に関する覚書 - よーる
IEEE浮動小数点数における演算では、丸め誤差が不可避です。特に、複数回の演算を繰り返すと丸め誤差が積もっていき、正確な値と大きく離れた答えを得てしまうことがあります。しかし、次の演算については、（数学的に）正確な値を求めた後、一回だけの丸めが発生することが、IEEE標準で規定されています。 四則演算 積和演算 Fused multiply add (FMA) 平方根演算（正の平方根を求める*1） 浮動小数点数演算のできるCPUであれば、普通、四則演算や積和演算を行う命令を持っています。 しかし、平方根を正確に計算する命令を持たない命令セットも存在します。 そのような場合、平方根関数はライブラリ実装となるわけですが、どのように実装すれば要求を満たせるのでしょうか？ C++のstd::sqrtは正確に計算しているのか？ 結論 しています。 標準の丸めモード、つまり最近接丸め（ぴったり半分なら
[追記]プログラマーにコンピュータ・サイエンスは必要なんだろうか
この疑問はもう俺の中で何十年もくすぶっているんだが、未だにその答えは見つかっていない。 そもそも俺はコンピュータサイエンスというものをよくわかっていないというのもあるんだが、プログラマーをやっていてコンピュータ・サイエンスの素養がなくて困ったことがない。 学生が言うところのコンピュータ・サイエンスが社会に出て何の役に立つんだよっていう話がしたいんじゃない。 ここに吐き出しつつ自分なりに問題を噛み砕いてみたい。 フラフラ思いつくままに書いているから頭悪い文章になることだけは先に宣言しておく。 仕事をしているうえでなんで困らないのかまずコレが最も重要なポイントだと思うんだが、仕事でプログラム書いていて、コンピュータ・サイエンスの素養がなくて困ったことがない、例えばコンピュータ・サイエンスのボキャブラリがないと会話すらままならないなんて言うことは起きたことがない。 更に言うならば要件定義をコード
![[追記]プログラマーにコンピュータ・サイエンスは必要なんだろうか](https://cdn-ak-scissors.b.st-hatena.com/image/square/b1638cdb5807a4788e4ba3c1109a984166e095fc/height=288;version=1;width=512/https%3A%2F%2Fanond.hatelabo.jp%2Fimages%2Fog-image-1500.gif)
動的計画法の実例: QRコードの最適なエンコードを求める - Qiita
はじめに 最近、実生活で競技プログラミングが役に立ちました。 趣味の一環で長方形のQRコードであるrMQRコードを生成するPythonパッケージを作成しています。その中で「ビット列が最も短くなるようにデータをエンコードする」という処理に動的計画法を用いました。大学時代に競技プログラミングをやっていた身としては「競プロが役に立った！」と嬉しかったので、実例として共有したくてこの記事を書いています。動的計画法のDPテーブルの定義から遷移のしかた、解の復元までを図や実装とともに説明しています。動的計画法自体は説明していません。実装の全体はこちらでご覧いただけます。 この記事に出てくるrMQRコードの仕様に関する記述はISO規格1に基づいています。最適なエンコードを求めるアルゴリズム自体は仕様に含まれるものではなく、オリジナルのものになります。 ※QRコードは(株)デンソーウェーブの登録商標です。
【Unity】ソートアルゴリズム12種を可視化してみた - Qiita
はじめに ソートアルゴリズムの学習として、12種のソートアルゴリズムを実装して可視化してみました。 Unityにはあまり関係がなさそうな話題ですが、Unity上で作ったのでUnityタグをつけます。 バブルソート バブルソートのアルゴリズムは以下のような感じです。 配列の要素を最初から最後まで見ていき、順序が逆の要素があれば入れ替える 全ての要素の順序が正しくなるまで 1.を繰り返す. void BubbleSort(int[] a) { bool isEnd = false; int finAdjust = 1; // 最終添え字の調整値 while (!isEnd) { bool loopSwap = false; for (int i = 0; i < a.Length - finAdjust; i++) { if (a[i] < a[i + 1]) { Swap(ref a[i],
メルカリを退職してロンドンのMetaに転職します 〜 外資Big Tech転職活動体験記｜松岡玲音｜note
この度、3年半に渡って勤めたメルカリを2022年5月に退職し、この夏からロンドンのMetaにSenior Machine Learning Engineerとして転職することが決まりました！わいわい✌('ω')。その過程で、東京およびロンドンのBig Tech合計5社を数ヶ月かけて対策をし面接に臨んだので、そこで得たノウハウをここで共有できたらと思います。面接を受ける際にNDA（Non Disclosure Agreement）にサインするので具体的な面接の詳細には触れられませんが、伝えられる範囲でできる限り記述しています。 また、Metaから最終的に提示されたオファー条件を最後に記載してあります。なにぶん日本においては給与の話は燃えやすいということもあり、その部分だけ某日本の有名エンジニアに倣って有料にしてあるのですが、ご興味のある方は是非ご購入いただければと思います（1コイン分の金額で
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
AHC035解説
https://x.com/torus711/status/1795448269687947463?s=12&t=YpIPcsjKfoTpmECNdRL-uw
https://twitter.com/drken1215/status/1687322120702066688?s=12&t=YpIPcsjKfoTpmECNdRL-uw
https://twitter.com/lotz84_/status/1608353263203803138
QDくん⚡️Python x 機械学習 x 金融工学 on Twitter: "ソートアルゴリズムの計算量の違いをわかりやすく可視化した記事 【Unity】ソートアルゴリズム12種を可視化してみた https://t.co/SBT4Xo42ku https://t.co/Cv7GfOvAF2"
Chokudai Searchっぽい探索手法が書かれた文献をちょっと調べた
Home — Memory Management Reference 4.0 documentation