超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 - Qiita
1. はじめに ～メインを読むための準備～ まず、大きな数の計算の話をする前に、少しコンピューターと計算回数について話しましょうか。 コンピューターは、現代ではソフトウェアやアプリケーションの開発に使われていますが、これには重要な背景があります。これは「計算がめっちゃ速いこと」です！人間なんかと比べたら、圧倒的な計算スピードを誇ります。 1-1. 人間の計算速度はどのくらい？ まず人間はどのくらいの速度で計算できるでしょうか？速い人も遅い人もいると思います。 例えば、$628 \times 463$ の計算を、今やってみましょう。10 秒以内で計算できたらかなり速い方でしょう。この計算では、次のように「単純計算」を合計 28 回もしていることになります。 9 回の 1 桁 × 1 桁の掛け算 6 回の 1 桁 × 1 桁の足し算 13 回の繰り上がり計算 もし $628 × 463$ が
超高速！多倍長整数の計算手法【後編：N! の計算から円周率 100 万桁の挑戦まで】 - Qiita
4-1. N! の高速な計算 $N! = 1 \times 2 \times 3 \times 4 \times \cdots \times N$ を計算してみましょう。 $N!$ は場合の数を求める問題でよく出てきて、こんな感じのものが求まります。 $1, 2, ..., N$ が書かれたトランプのカードが 1 枚ずつあるとき、これを一列に並べる順番は何通りあるか？ 例えば、$N = 13$ の場合 $13! = 6,227,020,800$ 通り、のように計算できます。 また、$N!$ は二項係数 $_NC_K$ を求めるのにも使われます。 $N!$ が求まれば、$_NC_K = N! \div K! \div (N-K)!$ で掛け算・割り算するだけで計算できますね。 $N$ 個の区別できるボールから $K$ 個を選ぶ方法は何通りか？ これが $_NC_K$ になります。例えば、$N
高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
バレンタインデーにquadsortがやってきた・・・けど - Qiita
quadsortとは？ それはバレンタインデーにやってきた 「なんか、qsortよりも良い結果がでたっぽいんだけど！」という話がでてきて、みんな色々検証をしていた。 もとスレッドは「モダンってなんだよ！」とか「それならこっちのアルゴリズムとか見たほうが良いんじゃ？」とか、なかなかエキサイティングしているっぽい。 ソースコードとか技術的な説明はこちら。 性能検証結果 quadsort: sorted 1000000 elements in 0.074616 seconds. (random order) qsort: sorted 1000000 elements in 0.101402 seconds. (random order) quadsort: sorted 1000000 elements in 0.000912 seconds. (forward order) qsort: s
GitHub - scandum/quadsort: Quadsort is a branchless stable adaptive mergesort faster than quicksort.
機械学習・アルゴリズム関連まとめ - Qiita
損失関数・不均衡 不均衡データにおけるsampling ランク学習のListNetをChainerで実装してみた 不均衡データへの決定打となるか！？「Affinity loss」の論文を読む、実装する 不均衡データを損失関数で攻略してみる 解説編：オーバーサンプリング手法解説 (SMOTE, ADASYN, Borderline-SMOTE, Safe-level SMOTE) LightGBMでランキング学習 半教師あり学習のこれまでとこれから Struggling with data imbalance? Semi-supervised & Self-supervised learning help! 深層学習 転移学習：機械学習の次のフロンティアへの招待 ディープラーニングの判断根拠を理解する手法 [DNC (Differentiable Neural Computers) の概要
Z-algorithm詳解と具体例 - Senの競技プログラミング備忘録
新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのような印象を受けました。 そこで、この記事でZ-algorithmに絞った説明、実際の挙動の説明、実装例を紹介します。 以下のページ、PDFを参考にしてます。 snuke.hatenablog.com 文字列アルゴリズム from HCPC: 北海道大学競技プログラミングサークル www.slideshare.net Z-algorithmで何ができるか？ 文字列Sに対して、S[i : j]という記号を、Sのi番目からj番目(いずれも0-idx)までの連続部分文字列とします。 例えば、S="abcde"で S[1 :
【決定版】スーパーわかりやすい最適化アルゴリズム -損失関数からAdamとニュートン法- - Qiita
オミータです。ツイッターで人工知能のことや他媒体で書いている記事など を紹介していますので、人工知能のことをもっと知りたい方などは気軽に@omiita_atiimoをフォローしてください！ 【決定版】スーパーわかりやすい最適化アルゴリズム 深層学習を知るにあたって、最適化アルゴリズム(Optimizer)の理解は避けて通れません。 ただ最適化アルゴリズムを理解しようとすると数式が出て来てしかも勾配降下法やらモーメンタムやらAdamやら、種類が多くあり複雑に見えてしまいます。 実は、これらが作られたのにはしっかりとした流れがあり、それを理解すれば 簡単に最適化アルゴリズムを理解することができます 。 ここではそもそもの最適化アルゴリズムと損失関数の意味から入り、最急降下法から最適化アルゴリズムの大定番のAdamそして二階微分のニュートン法まで順を追って 図をふんだんに使いながら丁寧に解説 し
二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）
Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。 しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。 この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。 第1回は、最もシンプルな木構造である 二分木 を
50年来の信号処理に関する謎が解かれる、逆高速フーリエ変換がついに一般化 - fabcross for エンジニア
アメリカのアイオワ州立大学電気コンピューター工学科准教授のAlexander Stoytchev氏と博士課程学生のVladimir Sukhoy氏は、信号処理の肝と言われる高速フーリエ変換（Fast Fourier transform：FFT）と逆高速フーリエ変換（Inverse Fast Fourier transform：IFFT）のアルゴリズムの研究を進め、50年間にわたり謎であったIFFTアルゴリズムを解明したと発表した。研究成果は『Scientific Reports』に論文「Generalizing the inverse FFT off the unit circle」として2019年10月8日に発表されている。 FFTアルゴリズム自体は1965年に公開され、その4年後には汎用性の高い一般化されたバージョンであるチャープZ変換（CZT）も開発されてきた。しかし、IFFTアルゴ
「ループ・再帰・gotoを使わず1から100までの数値を印字する」Conner Davis 氏の回答の考察 - Qiita
2019年6月に以下の記事が投稿されました。 ループ、再帰、gotoを使わずに1から100までを印字するC++プログラムは書けますか？に対するIchi Kanayaさんの回答 - Quora 英語版の記事「How to print 1 to 100 in C++ without a loop, goto or recursion - Quora」から興味深い回答を抜き出して、それにランク付けをしながら和訳してくださっている記事です。 初級や中級は「まぁあるよね（C++知らないけれど……）」という感じですが、 上級とされた「マイクロソフト社のデータサイエンティスト Conner Davis 氏」の回答が面白かった ので、ご紹介を兼ねてその発想の源泉を推測してみることにしました。 Conner Davis 氏の回答 以下に Conner Davis 氏の回答の和訳を引用します。 マイクロソフト
様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
[論文紹介]グラフニューラルネットワークによる推薦アルゴリズム - Qiita
はじめに 昨今、サービスに推薦システムを導入することでUXを向上させることが多くなり、様々な推薦アルゴリズムが取り入れられております。学術界でも推薦は大きなテーマであり、様々なアルゴリズムが提案されております。 本記事では、推薦をする際に、「メディア上で、どんな人とと繋がっているか、どのアイテムにライクをしたか、どんなページを閲覧しがちか」など、人やアイテムとのつながりを重視して推薦するSocial Recommendationの最新論文であるGraphRec[1]を紹介します。GraphRecは2019年にWeb系のTop Coferenceの一つであるWWWで採択された論文です。 GraphRecは、近年グラフ界隈を盛り上げているグラフニューラルネットワーク(以下GNNs)を用いております。GNNsでは、あるノードiの特徴量に近傍ノードの特徴量を足し合わせること(aggregation
![[論文紹介]グラフニューラルネットワークによる推薦アルゴリズム - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/2689e3bc55ea104cd84d54fe0fe5952d22e11921/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9JTVCJUU4JUFCJTk2JUU2JTk2JTg3JUU3JUI0JUI5JUU0JUJCJThCJTVEJUUzJTgyJUIwJUUzJTgzJUE5JUUzJTgzJTk1JUUzJTgzJThCJUUzJTgzJUE1JUUzJTgzJUJDJUUzJTgzJUE5JUUzJTgzJUFCJUUzJTgzJThEJUUzJTgzJTgzJUUzJTgzJTg4JUUzJTgzJUFGJUUzJTgzJUJDJUUzJTgyJUFGJUUzJTgxJUFCJUUzJTgyJTg4JUUzJTgyJThCJUU2JThFJUE4JUU4JTk2JUE2JUUzJTgyJUEyJUUzJTgzJUFCJUUzJTgyJUI0JUUzJTgzJUFBJUUzJTgyJUJBJUUzJTgzJUEwJnR4dC1hbGlnbj1sZWZ0JTJDdG9wJnR4dC1jb2xvcj0lMjMxRTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmcz1jNTYxYzYwMTQ1OGU3NDIwNWM2MTVkOWYxYmIyY2NmMQ%26mark-x%3D142%26mark-y%3D57%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBza2hpdWsmdHh0LWNvbG9yPSUyMzFFMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT0zNiZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZzPTRlZTYyOWE5MTQxMjFhZjJmZTZjMjc0NDI1OTE4Mzkx%26blend-x%3D142%26blend-y%3D486%26blend-mode%3Dnormal%26s%3D1be5c5645fbf0d63b270ed560854dc6e)
「FINAL FANTASY XVの人工知能」がなかなか面白かったので書評 - Stimulator
- はじめに - このブログの人気シリーズの一つ、「献本されて読んだら良かったので書評で作者に媚を売ろうシリーズ」です。 今回は、あるきっかけで「FINAL FANTASY XV の人工知能 - ゲームAIから見える未来」（以下 FF本）という本を頂く形になりました。 FINAL FANTASY XV の人工知能 - ゲームAIから見える未来 作者: 株式会社スクウェア・エニックス『FFXV』AIチーム出版社/メーカー: ボーンデジタル発売日: 2019/06/04メディア: 大型本この商品を含むブログを見る 私自身の専門もあって、普段はこの手の「人工知能本」と私が認識しているジャンルの本、例えば「よくわかる人工知能」「人工知能ビジネス徹底解説」といった旨の本を手に取る事はほぼなく、ましてや誤った知識を流布する事が多いジャンルでもあると認識していたが、このFF本はまた別の楽しみ方が出来たの
論文｜snmalloc: A Message Passing Allocator (ISMM 2019)
「snmalloc: A Message Passing Allocator」という論文を読んだのでその紹介です。本論文は ISMM (International Symposium on Memory Management) 2019 に採択されており、論文とソースコードは GitHub (microsoft/snmalloc) で公開されています。リポジトリ名から分かる通り、著者の多くが Microsoft Research に所属しています。 免責 読み間違えている可能性があります。正確な情報が欲しい方は必ず論文を読んでください。誤りの指摘や補足、議論などは GitHub Issue や Twitter へお願いします。 更新履歴 2019/07/08 bump pointer と free list の next entry pointer を判定する方法について追記 2019/0
低解像度ビデオもすぐに高解像度に変換できる超解像アルゴリズムTecoGANがすごい
3つの要点 ✔️ 低解像から高解像へ変換 ✔️ 時間的に一貫したフレームを生成するために双方向損失関数を採用 ✔️ 超解像度へ変換するTecoGANを提案 Learning Temporal Coherence via Self-Supervision for GAN-based Video Generation Temporally Coherent GANs for Video Super-Resolution (TecoGAN) written by Mengyu Chu, You Xie, Jonas Mayer, Laura Leal-Taixé, Nils Thuerey (Submitted on 23 Nov 2018 (v1), last revised 21 May 2020 (this version, v4)) Comments: Published by arXi
競技プログラミングで使う有名グラフアルゴリズムまとめ
0. はじめに AtCoderなどでは、グラフを扱った問題が多く出るが、その度に一から実装していると時間が掛かりすぎてしまうため、有名なものをあらかじめ持っておく必要がありそう。そこで、Pythonを用いて、ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法を実装した。 コメント、意見等ある方は是非! お待ちしてます! 1. ダイクストラ法 1.1. ダイクストラ法(defaultdictで実装) defaultdictで実装すると、リストで実装するよりも、ノード数$N$が大きい際には高速に動作する。ただし、経路復元の関数は、うまく書けなかった......。 (2019/7/6 追記)結局できました。1.1.1. を参照してください。 import collections import heapq class Dijkstra: def __init__(se
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://research-er.jp/articles/view/86365
