学会の公開資料でいろいろな主題について勉強するのは有効なことが多いです。 最適化問題についてはOR学会の過去資料がうまくまとまっていますので有効活用できたらいいですね
こんにちは、最近ハマっている初期化配列について紹介したいと思います。 はじめに 皆さんプログラミングをする時に配列を使ってますか?使ってない人はほとんどいないのではないでしょうか? 長さNの固定長配列AはN個の要素を格納でき、かつ任意の位置に保存された要素A[i]を最悪定数時間(以下、定数時間)で読み書き可能な最も基本的なデータ構造の一つです。配列の様々な操作の中で読み書きについで頻出する重要な操作が、配列の全ての要素を指定した値に書き換える初期化操作です。配列の初期化は配列長に対して線形な時間がかかるため、配列長が長い場合や、初期化が頻出する処理では配列の初期化操作が大きなボトルネックとなります。この問題を解決するデータ構造が初期化配列です。本記事ではシンプルな初期化配列の実装法、folkloreアルゴリズムを紹介したいと思います。 初期化配列とは通常の読み書きに加え、配列の全ての要素を
It’s a bit lumpy, though. One might try changing the 1/8ths to 1/16ths to draw a rounder circle — but they’ll get an octagon instead: There’s an important point easily missed here: in the pseudocode above, we update x, and then the next line uses the new value of x to update y. This is key to the stability of the algorithm. We can say that this integer-based circle-drawing algorithm is parameteriz
Googleが無料で提供する「最適化問題」ソルバー 本日は、Googleが無料で公開(Apache License 2.0)している最適化問題ソルバー「Google Optimization Tools」を取り上げます。こちら、昨今話題の pokemon GO でも、このRouting使えるんじゃないか、と(ごく一部の特定層の間で)盛り上がっていたりもします。 Google Optimization Tools (=or-tools)は、「software suite」と表現されています。「Problem Solver(ソルバー)」の集合体と考えるのが良いかなと思います。※少し長いのですが、以下にOverviewを引用しておきます。(英語です。読み飛ばしてもOKです。)色々書かれてますが、要は「いろんな最適化問題を解く為のソルバーだよ」「簡単に使えて、オープンソースだよ」という感じです。
元ネタはずいぶんと昔の記事なのだけど。 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー ■ 編集距離 (Levenshtein Distance) 昨日 最長共通部分列問題 (LCS) について触れました。ついでなので編集距離のアルゴリズムについても整理してみます。 編集距離 (レーベン... http://d.hatena.ne.jp/naoya/20090329/1238307757 思い付きはまったく関係ない所から。 mp3 が数千ファイル入ってるフォルダで何かの手違いで同じ曲が入ってしまう事が結構あって重複取り去る作業してた。ID3が違ってるとMD5も違うのでレーベンシュタインの文字列距離を使ってファイル名が似てるの調べたら422ファイル消せる事が分かった。 — Vim芸人 (@mattn_jp) February 25, 2017 これを
If you are not redirected automatically, follow this link to the article..
JS 実装をしようかな、と思い立ち、 まずは型推論の知識をしっかり取得するところから初めようと考えています. そもそも、型推論とはなんぞや、というところからおさらいしてみます. 私が型推論について知りたいことの一番の目的は、 「型推論を行うことで動的言語の事前コンパイルを可能にしプログラムの実行を早くすることができるのではないか」, ということになりますので、それに特化した内容になっています. もちろん型推論には、プログラムを早くするという以外の目的もありますが、 ここではそれらは取り上げないことにします. 型推論(type inference)とは、簡単に言うと、 var muda = 7 というコードがあったら、 「変数 muda って Int 型(整数型)じゃね?」 とコンパイラがよろしく変数の型を決定してくれる(推測してくれる)機能になります. 静的な関数型言語(Ocaml, Ha
これはNextremer Advent Calendarの23日目の記事です。 現在、株式会社Nextremerでは早稲田大学の田中宗様と量子アニーリングに関する共同研究を行っております。 はじめに 量子アニーリングは組合せ最適化問題を解くための有効なアルゴリズムと言われています。 本記事では、量子モンテカルロ法による量子アニーリングを用いて、代表的な組合せ最適化問題であるTSP(巡回セールスマン問題)に対して解を求めたいと思います。 量子論の基礎 TSPの議論に入る前に、少しだけ量子論の基礎的なことに触れておきます。 物理量(エネルギーや運動量など)は、量子の世界では演算子というものに対応します。例えば、エネルギーという物理量に対応するものはハミルトニアン($\hat{H}$と表します)という演算子です。 このハミルトニアン $\hat{H}$ という演算子は、ある量子状態 $\psi$
So there I was, implementing a one element ring buffer. Which, I'm sure you'll agree, is a perfectly reasonable data structure. It was just surprisingly annoying to write, due to reasons we'll get to in a bit. After giving it a bit of thought, I realized I'd always been writing ring buffers "wrong", and there was a better way. Array + two indices There are two common ways of implementing a queue w
数年前に圧縮配列を作ってgithubで公開していました。 この度そのライブラリを一から書き直してリニューアルしました。 github.com 元々圧縮配列ライブラリであることをメインに作っていたのですが、今回のリニューアルで簡潔データ構造のライブラリとしても使えるようになっています。 圧縮配列とは 大量のデータを配列に格納しないといけないとき、あまりにデータが大きすぎてメモリに乗り切らないことはありませんか?圧縮配列は情報を圧縮状態でメモリに格納するためのものです。圧縮されているためそのまま格納するより省メモリですみます。当然通常の配列に比べて速度は落ちますが、ランダムアクセスリードが可能です。yunomiでは、Kimmo Fredriksson and Fedor Nikitinの論文に記載してあるFibonacciコーディングによる圧縮配列を実装しています。詳細を知りたい方は参考文献に
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが,どうしてかと言われると意外と難しいものです. というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです.実装を知っていないと答えられません. 一般論として,1つ要素を追加するとき,配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります.コピーのコストは O(n) だから,追加コストも O(n) になるという議論が混乱の元になっています. こういうときは,要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです.一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです. さて,s
国際学会 KDD 2016 に論文が採択されました.KDD はデータマイニング分野の最も有名な会議です.発表は 8 月にサンフランシスコです.オーラル発表有りの採択です. 今回の論文は "Compact and Scalable Graph Neighborhood Sketching" というタイトルで,私が主著であり,研究室で特任技術専門員としてお手伝いしてもらっていた矢野さんとの共著です.内容はグラフ向けデータ構造 All-Distances Sketches の実用上の問題点である空間使用量を大幅に削減するための新しいデータ構造の提案です.以前に「大規模グラフのコンパクトでスケーラブルな全距離スケッチ」というタイトルで人工知能学会の人工知能基本問題研究会にて議論させて頂いていたものです. 背景:All-Distances Sketches とは? All-Distances Ske
講義でソートアルゴリズムを教えることになったので,改めてソートアルゴリズムの勉強をしなおした.僕がソートアルゴリズムをちゃんと勉強したのは1990年代前半で,教科書はニクラウス・ヴィルト「アルゴリズムとデータ構造」(第2版)だった.サンプルコードがModula-2で書かれているアレだ. N. ヴィルト「アルゴリズムとデータ構造」C++ STL の解説を読むなどしてソートアルゴリズムの改良が進んでいるのは知っていたが,再勉強してはじめて,未だに新発明があることを知った.例えば図書館ソートなど,恥ずかしながら名前さえ知らなかった.勉強は大事だ. とは言え,そもそもソートアルゴリズムの中身をどのぐらいまで知っておけば,コンピュータサイエンティストとして十分なのだろう,あるいはエンジニアとして十分なのだろうという疑問は残る. 例えば,超優秀なC++プログラマでもGNUの std::sort の中身
Platform AI Platform The platform for generative and predictive AI. Learn more Documentation Pricing What’s New Demo Hub Explore Generative AI Product Offering Operate Confidently scale AI and drive business value with unparalleled enterprise monitoring and control. Deploy and Run Learn and Optimize Observe and Intervene Govern Unify your AI landscape, teams, and workflows for full visibility and
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く