1 - 22 件 / 22件
タグ検索の該当結果が少ないため、タイトル検索結果を表示しています。
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、(別の記事を Qiita とかで検索するよりも)この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ(など)を受け取ってアルゴリズムの計算回数(など)を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
1998年にラリー・ペイジ氏とともにGoogleを創業したセルゲイ・ブリン氏は、2019年にGoogleの社長を退任しました。しかし、アメリカ・ロサンゼルスで開催された「All-In Summit」の中でブリン氏は「ほぼ毎日」Googleで働いていることや、近年のAI技術の進歩について語っています。 In conversation with Sergey Brin | All-In Summit 2024 - YouTube Sergey Brin says he's working on AI at Google 'pretty much every day' | TechCrunch https://techcrunch.com/2024/09/10/sergey-brin-says-hes-working-at-google-pretty-much-every-day-on-ai/
◆だいやまーく二分決定グラフは集合の集合を圧縮して表現することができるデータ構造です。これまで最悪時間計算量が未知であった二分決定グラフの多数の演算について、入力のサイズに対して演算の実行に指数的に時間がかかる事例が存在することを示しました。 ◆だいやまーく本発見は今後二分決定グラフを用いた応用において、正しく計算量を見積もるのに役立ちます。 ◆だいやまーく計算機科学に関する著名な教科書であるThe Art of Computer Programming(TAOCP)の記述の誤りを指摘するものであり、研究チームからの修正案が承諾され改訂予定です。 日本電信電話株式会社(本社:東京都千代田区、代表取締役社長:島田 明、以下「NTT」)は、論理関数を表現する著名なデータ構造である二分決定グラフにおける長年の未解決問題を解決しました。 二分決定グラフは集合族(※(注記)1)、つまり集合の集合を表現するデータ構造として、回路設計や通信ネット
「プロになるJava」ボツ原稿、今回は「13章 処理の難しさの段階」に入れようと思っていた、「アルゴリズムと計算量」の話です。 こういう話題でよくでる「こんな難しいプログラム組まないのでは?」という疑問についても最後にまとめています。 プロになるJava―仕事で必要なプログラミングの知識がゼロから身につく最高の指南書 作者:きしだ なおき,山本 裕介,杉山 貴章技術評論社Amazon アルゴリズムと計算量 ここまでいろいろな処理の計算手順について紹介しました。こういった計算手順のことを アルゴリズム といいます。 同じ処理をするアルゴリズムはいろいろ考えられます。そのとき気になるのは実行性能の問題です。 ただ、実行性能はコンピュータによってクセがあるので、アルゴリズムそのものについてを考えるときにはそういったクセを取り除いて考えたいものです。 そこで、アルゴリズムの性能について考えるときに
本当の本当にただの自分向けのメモです。メモだけど、見られて困る内容じゃない。なら、他の人も見れる方がよい。そんな思考でブログにしている。 書くのはSNS界隈では定期的にマウント取りに使われる*1二分探索の計算量について。定期的に忘れてはいちいち理屈から考えるを繰り返している*2ので、もうメモにしておくことにする。ちなみに結論だけ言うと二分探索の計算量はだ。 指数と対数 二分探索の計算量を考えるにあたってこれが必要。いや、それ抜きにしても指数対数は重要なんだがそれはおいておき...なんで指数と対数が出てくるかというと、二分探索の計算量は対数的に増加するからだ*3。そして対数を説明するにはセットで指数を説明する必要がある。なのでこの順番で説明する*4。 それぞれひとことで説明するとこんな感じ。さすがに指数は分かるだろう。が、普段意識しない対数は忘れがち。 指数 = xをk回かけたらnになる。n =
結論を述べる。ソフトウェアエンジニア、特に高負荷環境のゲームエンジニアやバックエンドエンジニアにとって有用な教養となる。 数列数の列数が並んでいるものを数列(numerical sequence)という。 $$ 1,5,5,6,3,4,2, \cdots $$ 適当に並べたが数は自然数でも実数でも複素数でもなんでも良い。適当に並べるとあまり意味がないので、この数列に何らかの法則性がある場合を考える。 等差数列「1年目の預金が5万円、2年目から毎年3万円預金し続けた場合、7年目の預金額は?」。書き出してみよう。 $$ 5,8,11,14,17,20,23\cdots $$ 答えは$${23}$$。では、書き出さないで求める方法は?おそらく脳内でこういう計算をしたと思う。 $$ 5 + 3 * (7 - 1) = 23 $$ これを抽象化する。$${n}$$番目の値を$${a_n}$$と定義す
Google Colaboratory(Google Colab)は、Googleが機械学習の教育や研究用に提供しているサービスで、ローカルにインストールすることなくPythonや機械学習の環境を構築できます。このGoogle Colabの有料版であるGoogle Colab Pro/Pro+におけるGPUの使用量がクレジット制に移行するというメールが運営から送られてきたと、ソーシャルニュースサイトのHacker Newsに投稿されて話題となっています。 Google Colab Pro is switching to compute credits | Hacker News https://news.ycombinator.com/item?id=32656200 機械学習や深層学習の演算にはGPUが使われますが、Google Colabでは基本無料でGPUを使った計算が可能です。ただ
はじめに この記事では基本的なアルゴリズムの一つである、ソートアルゴリズムを例にとってアニメーションを使って、アルゴリズムの計算量をみることを目的としています! アルゴリズムを勉強していく中で、計算量という言葉を目にすることが多いと思います。 しかしながら、計算量について実際に、アルゴリズムごとでどの程度違うのか、ということは直感的に分かりにくいと思います。 そこで! 直感的に分かりやすいように、ソートアルゴリズムをこのようにアニメーションを使って可視化させてみたので、勉強の参考であったり、通勤中の暇つぶしなどに活用してみてください! アニメーション例(クイックソート)↓ 最初に計算量について解説するので、アニメーションだけ見てみたいという方は 実際に比較してみる 全体比較 をご覧ください! ソートアルゴリズムについて ソートアルゴリズムとは、名前の通り「ソート(並び替え)」を行うアルゴリ
これは ミライトデザイン Advent Calendar 2021 の 14 日の記事です 最近ふぐひれ酒が飲みたくて仕方ない ほげさん ( zenn ) です 今日は計算量について超ゆるふわに紹介してみようと思います 「競技プログラミングとかやらんし」「Web サービス作るのにいらんし」などと思った方! 大量リクエストの対応やバッチ処理など、案外役に立つかもしれないですよ! どういうときに計算量を考えるか 計算量とは、処理の効率などを示す尺度のことです この記事では処理時間についてのみ紹介します まずはサンプルコードと実行結果を見ながら、代表的なケースとインパクトを見てみましょう データ構造をちょっとだけ気にする ロジックをちょっとだけ気にする アルゴリズムをちょっとだけ気にする の三本立てでサクサクいきますよ ケース 1: データ構造をちょっとだけ気にする 最後の要素を取得するのは、配
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに この記事は Qiita Engineer Festa 2022「アルゴリズム強化月間 - 楽しいアルゴリズムの世界を紹介しよう -」に向けて書いた記事です。 メインの部分は以下の2つの論文の結果となります。 A model classifying algorithms as inherently sequential with applications to graph searching Depth-first search is inherently sequential また、次の本も参考にしました。 Limits to
DOMツリー最適化でブースト! 高速・効率的なWebページへの鍵を握ろう 2023年4月24日 著者: 竹洞 陽一郎 はじめに 今回は、Webパフォーマンスの基礎となる、HTMLの解析において特に重要なDOMツリーについて解説します。 HTMLのDOMツリーは、多くの人が用語として知っているでしょう。 しかし、木構造の複雑度がCSSやJavaScriptなどの後続処理の時間計算量に大きな影響を与えることについて、十分理解している人は意外と少ないかもしれません。 この記事では、DOMツリーがどのように構築され、その複雑度がWebパフォーマンスにどのような影響を及ぼすかを説明します。 また、効果的なDOMツリー最適化の方法や、それによって得られる恩恵についても触れていきます。 Web開発者は、これらの知識を活用して、より高速で効率的なWebページを提供することができるでしょう。 今回の記事で扱
はじめに エラトステネスの篩とは、$n$ 以下の自然数について素数判定表を生成するアルゴリズムです。 計算量 $O(n\log\log n)$ で1予め表を生成してしまえば 1ドル<k\le n$ の範囲の整数は定数時間で判定が行えるので、一定の範囲の整数について大量に素数判定を行う場合(素数の個数を数える、素因数分解を行うなど)は個々の数を素数判定するのに比べ非常に高速になります。 しかし、この $O(n\log\log n)$ という計算量は素数の逆数の総和が $O(\log\log n)$ に漸近していくという定理を用いているなど、かなり非直感的です。 本記事では計算量の実験的な確認を行うとともに他のアルゴリズムとの比較を行いました。2 手法 エラトステネスの篩のPythonによる実装 エラトステネスの篩の基本的なアルゴリズムは擬似コードで以下のように書けます。
競プロ er はよく計算量の見積もりをします。「これこれの計算量は $O(\dots)$ なので十分高速である」といった具合で上から抑えることが多いです。 また、「これこれの計算量は $\Omega(\dots)$ なので TLE しそう」といった具合で下から抑えることもしばしばあります。 note:「これこれの計算量は $O(2^{2^n})$ なので TLE しそう」といった記号の使い方($O$ で下から抑えようとする)は、不正確な用法なので気をつけましょう。知らずに使っていた人はちゃんと勉強しましょう。 「下から抑える」について 下から抑えるというのは、見積もりたい値はこれ以上であるという値(下界かかい と呼ばれます)を求めるという意味の言い回しです。 ある $a$ を使って $a\le x$ と書けたら「$x$ は $a$ で下から抑えられる」と言います。 逆に、$x\le b$
米OpenAI(オープンAI)が2024年9月12日(米国時間)にリリースした「OpenAI o1」は、科学やコーディング、数学に関する難しい問題が解けるAI(人工知能)だ。AIに新しい競争軸をもたらす存在になりそうだ。 これまで大規模言語モデル(LLM)には、機械学習モデルのサイズやトレーニングに投入する計算量、トレーニングデータの量を大きくすればするほど性能が向上する「スケーリング則」が働くことが知られていた。それに対してo1においては、モデルの推論に投じる計算量が大きければ大きいほど、より難しい問題が解けるようになるという新たな「法則」が示されている。 GPTとは異なる「新シリーズのLLM」 オープンAIが新たに追加したo1は、論理的思考(reasoning)を強化した新しいLLMである。ChatGPTに使われているLLMであるGPT(Generative pre-trained t
3つの要点 ✔️ Attentionのレイヤー毎の特徴を再現することで,計算量の削減を達成 ✔️ Sliding Window Attenion、Dilated Sliding Window Attention、Global Attentionという3つのAttentionを使ってTransformernの計算量を削減した ✔️ 計算量を削減しただけではなくて,当時のSOTAを達成している. Generating Long Sequences with Sparse Transformers written by Rewon Child, Scott Gray, Alec Radford, Ilya Sutskever (Submitted on 23 Apr 2019) Comments: Published on arxiv. Subjects: Machine Learning (c
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か 〜 文系理系問わず楽しめる精選 6 問 〜 アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
Attentionを爆速にした論文Transformers are RNNsを解説 こんにちはYosematです! 今回は長いこと計算時間が問題になっていたAttentionが爆速になってしまったという論文Transformers are RNNsを解説していきます。 今後も論文解説を続けていきますのでぜひTwitterとQiitaをフォローしてください!モチベ上がります! 忙しい人向け Attentionの計算に内積を使うのをやめてカーネル関数を使う Self-Attentionの計算オーダーが**$O(n^2)>>O(n)$**になった 計算は爆速になったけどパフォーマンスはcompetetive! Attention Transformerでお馴染みのAttention。最初は自然言語の王様でしたが、最近は画像の認識や生成タスクでも猛威を奮っている様子で、次世代のDNNの基本的な構成
『.NET 5は、.NET Core 3.1の次期バージョンであると同時に、.NET Framework 4.8の移行先でもある。』 そんなことを.NET 5の破壊的変更リスト一覧にある「Complexity of LINQ OrderBy.First{OrDefault} increased」から感じました。 この投稿では、その破壊的内容と背景を紹介します。 破壊的変更の概要 .NET 5の破壊的変更である「Complexity of LINQ OrderBy.First{OrDefault} increased」の概要説明文は以下の通りです。 The implementation of OrderBy.First<TSource>(IEnumerable<TSource>, Func<TSource,Boolean>) and OrderBy.FirstOrDefault <TSour
pythonの文字列操作のうち、連結、先頭要素の削除、最後の要素の削除について計算量を検証してみました。 これらの操作の計算量が$O(n)$であることを検証します。 きっかけ ABC298 D問題にて、$N$回のループのなかで長さが$O(N)$の文字列の連結(一文字追加)を行なうと、TLEとなりました。 文字列の代わりにcollections.dequeを使うと制限時間に間に合いました。 今回の検証前は、pythonの文字列は双方向リスト的なもので実装されており、先頭と最後に一文字加える操作では$O(1)$でできるのではないかというイメージを持っていました(事実とは異なります)。 pythonの文字列はイミュータブル pythonの文字列はイミュータブルであり、文字列オブジェクトに対して他の文字列との連結や要素の削除を行うことはできません。 オブジェクトが mutable かどうかはその型
挿入ソート、バブルソート、選択ソート この3つのソートは、「ソート済みの部分と未ソート部分に分ける」という共通方針がある。 部分的に分けた後、どのように未ソート部分をソートしていくのかがそれぞれ異なる。 >>【図解】挿入ソート:アルゴリズム【C言語のサンプルコート付き】 >>【図解】選択ソート:アルゴリズム【C言語のサンプルコード付き】 >>【図解】バブルソート:アルゴリズム【C言語のサンプルコード付き】 シェルソート シェルソートは、一定の間隔\(n\)だけ離れた要素からなる集合に対して、挿入ソートを繰り返し行うアルゴリズムである。 \(n\)は、最初は大きい値から始め、挿入ソートを繰り返すごとに小さくしていく。 シェルソートの最悪計算時間は\(O(n^2)\) であるが、最初からある程度整列されたデータに対して高速に動作するという特徴がある。 マージソート マージソートは、配列を\(n
ヤフー株式会社は、2023年10月1日にLINEヤフー株式会社になりました。LINEヤフー株式会社の新しいブログはこちらです。LINEヤフー Tech Blog こんにちは、ヤフーの音声認識エンジン「YJVOICE」の研究開発を担当している藤田です。 今回のブログでは、ヤフーにおける音声認識技術の研究開発の最新の取り組みを紹介します。具体的には、前回のブログでご紹介した新しい音声認識処理を、長時間の録音にも対応可能にした研究をご紹介いたします。長時間録音に対応するためには音声区間検出という処理が必要になるのですが、1つのモデルで音声区間検出と音声認識を処理可能な手法を提案し、従来法に比べて高い精度を短い処理時間で実現しました。なお、この研究は難関国際会議INTERSPEECH 2021に投稿し、採択されました。論文はこちらで公開されていますので、詳細が気になる方はぜひご覧ください。 Non
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く