「量子」と組合せ最適化に関する怪しい言説 ―とある研究者の小言― - むしゃくしゃしてやった，今は反省している日記
最近，量子コンピュータの話題をニュースや新聞で見かけることが増えてきました． その中で気になってきたのが，組合せ最適化と量子コンピュータ（特に量子アニーリング）に関する怪しい言説．私自身は（古典コンピュータでの）組合せ最適化の研究をやってきて，量子コンピュータを研究しているわけではないのですが，さすがにこれはちょっと・・・と思う言説を何回か見かけてきました． 最近の「量子」に対する過熱ぶりは凄まじいので，こういう怪しい言説が広まるのは困りものです．すでにTwitter上には，“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1． さすがに危機感を覚えてきたので，この場できちんと指摘しておくことにしました． 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
うわっ…私のpandas、遅すぎ…?って時にやるべきこと（先人の知恵より） - Lean Baseball
※あくまでもイメージです（適当） 仕事じゃなくて、趣味の方の野球統計モデルで詰まった時にやったメモ的なやつです.*1 一言で言うと、 約19万レコード（110MBちょい）のCSVの統計処理を70秒から4秒に縮めました. # 最初のコード $ time python run_expectancy.py events-2018.csv RUNS_ROI outs 0 1 2 runner 0_000 0.49 0.26 0.10 1_001 1.43 1.00 0.35 2_010 1.13 0.68 0.32 3_011 1.94 1.36 0.57 4_100 0.87 0.53 0.22 5_101 1.79 1.21 0.50 6_110 1.42 0.93 0.44 7_111 2.35 1.47 0.77 python run_expectancy.py events-2018.c
Pythonで省メモリに大量の文字列を扱う工夫 - MNTSQ Techブログ
たくさんの文字列（や離散的な符号列）をメモリに載せないといけないんだけど、いろんな制約があって通常のList[str]では載らない…ということありませんか？（まぁあんまりなさそうですね） たまたまそういうことがあったので、その際に検討した内容をまとめておきます TL;DR メモリをもっと増やしましょう 富豪的に解決できるならいつでもそれが最高です しかし、世の中それでなんとかならんこともたくさんあります 用途があうのであれば専用のデータ構造を採用する 例えばもし共通のprefixやsuffixが存在し、順序に興味がなければtrie treeなどが使えます 例えば、弊社であれば、法人名をメモリに持ちたいなんてときもあります。そういうときに法人名の辞書をtrieで持ったりすることがあります 「株式会社」「一般財団法人」や「銀行」といった共通語がたくさんでてくるのでtrie treeでごりごり削
100万倍速いプログラムを書く - Qiita
この記事はなんなの プログラミングを始めたばかりで高速化の大枠が全くわからず意味不明なことをしていた在学時、こんな資料があったら良かったのになあ、と思って書いたもの。 書いて、在学時研究室に押し付けた後紛失したと思われていたものが発掘されたもの。 要約 ライブラリがあるならそれを使う。 ライブラリが無ければ、ボトルネック部分を探してそこだけ高速な言語で書きなおすか、可能なら事前コンパイルする。 最初から全てを Low-Level な言語で書くと大変、でも結果のプログラムは速い。 以下の時間の計測ではインポートにかかる時間は除いています。 使用するもの Python（3系） Numba Scipy Line Profiler Fortran（gfortran） QUADPACK QUADPACK以外の導入方法の説明は色んな所にあるので各自でお願いします。上3つに関しては、個人的にはAnaco
Perlが30倍速くなるかもしれないSPVMの開発版をリリースしました。 - Perl入門ゼミ
Perlが30倍速くなるかもしれないSPVMの開発版をリリースしました。 SPVM(CPAN) かもしれないと書いたのはベンチマークをまだとってないからで、理論的にはJava VMの速度まで、近づけることができるんじゃないかなと思うから。 開発版なので、まだ機能が足りないのだけれど、CPANにリリースして、CentOS, FreeBSD, Windowsで動かすところまでやったので、ここで公開します。Macを持っていないので、Macの方は、CPANからインストールできるか確認していただけるとありがたいです。 SPVMはPerlに似た新しいプログラミング言語で、バーチャルマシン上で動き、関数をPerlから簡単に呼び出すことができる。 完全な静的型を持ち、Javaと同じデータ型、byte, short, int, long, float, doubleを持つ モジュールを書いてすぐに実行できる
straceがどうやってシステムコールの情報を取得しているか - ローファイ日記
興味があって調べていたら、少しだけ分かったのでまとめておきます。当然間違った箇所もある、あと考慮が漏れている箇所もあるかと思いますのでツッコミをお願いします… ptrace(2) システムコール strace の核となるシステムコールは ptrace(2) である。ptrace(2)を用いることで、あるプロセスを別のプロセスから監視し、シグナルごとに停止してレジスタやメモリの状態を観察したり変更したりできる。gdbのようなデバッガのブレークポイント、あるいはまさにstraceのような目的で利用される。 大まかな利用方法としては、親プロセスの ptrace(PTRACE_ATTACH, pid, ...) （または子プロセスの ptrace(PTRACE_TRACEME, 0...)）によりトレースが開始し、wait()などで停止を待ってから様々な設定を親から送り、 ptrace(PTRAC
RunKeeperやNike+並みのパフォーマンスを実現する高精度位置情報フィルターの作り方 — 位置情報を正確にトラッキングする技術 in Android (第3回)
前回までのサンプルアプリを実機にインストールして色々なところを移動してみると高いビルに囲まれた路地裏や、木が茂っている公園の中、または厚い雲に覆われた天気で自分の位置とずれたところにパスが描かれることがあるのがわかります。 実はこのように普通にLocationManagerを使っただけでは綺麗な位置情報の軌跡をとることはできないことがあります。 Uberのように一時的に車が少し道路よりずれた場所に表示されてもいいアプリのケースもありますがもしNike+のようにユーザーの行動の軌跡を美しくマップ上に描画し、なおかつ走った距離も正確でなければいけないアプリは高い精度の位置情報だけを取り続ける必要があります。 この回では高い精度の位置情報だけを取り続けるためのフィルターの作り方について説明します。
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
高速化のためのPython Tips - のんびりしているエンジニアの日記
皆さんこんにちは お元気ですか？私は元気です。 Pythonにおける高速化手法を掲載してみます。 簡単なコード並びに索引のような感じで引けるようなイメージで作成しました。 本日の目次です。 Pythonにおける高速化の必要性 Pythonの高速化 高速化の手順 Profiling 基本的な条件 計測コード Pythonの基本的な書き方部分 rangeよりxrangeを（Python2.7） リストの生成 文字列結合 Import文のコスト 関数呼び出しのコスト ドットを避ける yieldを使う Numpyに関するTips Numpyを使用して基本演算を高速化する Numpyの要素にアクセスする演算をしない Numbaで手早く高速化 その他高速化ツール Cython Dask PyPy 感想並びに展望 参考文献 Pythonにおける高速化の必要性 PythonはC++やJavaと比較すると非
データ指向設計
こんにちは、Cygames Research の多胡です。これまで10年以上コンソールゲーム開発を行ってきていて、最近ではハイエンドゲームエンジンを制作しておりました。Cygames でもハイエンドゲームエンジンの開発に携わることになりました。 ゲームエンジン開発を行う上で重要な考え方にデータ指向設計 (Data Oriented Design) というものがあります。今回はこのデータ指向設計を例を交えながら紹介させていただきます。 背景 データ指向設計の考え方は 2009年頃から有名になりました。 この 30年で CPU の性能は1万倍以上になりましたが、メモリの転送速度は10倍にもなっていません。そのため、プログラムのボトルネックはメモリ帯域となることが多くなりました。ゲームにおいても CPU はほとんどの時間がメモリからのデータの転送待ちになっています。CPU の性能を引き出すために
システムプログラミング会 - 兼雑記
すごい久々にイベントの(共同)主催的なことをしました http://connpass.com/event/34995/ イメージとしては言語雑談会的な感じで、closedに人集めてウダウダやるつもりだったんですが、途中でPFNさんに場所貸していただけるということで、不特定な人を呼ぶことになって、当初想定してたより大袈裟な会になりました。適当に募集すると人が集まって自己顕示欲が満たされるとか、普段得られない種類のフィードバックが得られたり交流ができる、てのがあるわけですが、めんどくさいのとグダグダ雑談がしにくいのが難点ですね。まあ自分自身が一般的に募集されてる会で勉強した面もあるわけで、そういうのの恩返しになるかもという面もあり、まあ色々。 まとめとしてはkoieさんのブログやtogetterがまとまってそう http://blog.livedoor.jp/hkoie/archives/55
SQLデータベースに正しインデックスを作るのは 誰の役割？
SQLのパフォーマンス問題は、SQLそのものと同じぐらいの歴史がある―― ある人は、SQLはそもそも遅いものだとすら言うかもしれません。これは、SQLの歴史が始まった頃は正しかったかもしれませんが、今となっては全く 当てはまらないでしょう。にもかかわらず、SQLのパフォーマンス問題は今も一般的でよくあることです。どうしてそうなってしまうのでしょうか？ SQL言語は、恐らく最も成功した第4世代言語(4GL)でしょう。その最大の利点は、「何を」と「どのように」 を分離できることです。SQL文は、どのようにそれを実行するかを記述せずに、単純に 何を必要としているかのみの記述になっています。以下のような例を考えてみましょう。 SELECT date_of_birth FROM employees WHERE last_name = 'WINAND'SQLのクエリは、データを要求する英語の文として読
sprintf を最大10倍以上高速化するプリプロセッサ「qrintf」を作った
最近H2OというHTTPサーバを書いているのですが、プロファイルを取ってみるとsprintfが結構な時間を食っていて不満に感じていました。実際、sprintfは数値や文字列をフォーマットするのに十徳ナイフ的に便利なので、HTTPサーバに限らず良く使われる（そしてCPU時間を消費しがちな）関数です。 では、sprintfを最適化すれば、様々なプログラムが より高速に動作するようになるのではないでしょうか。ということで作ったのが、qrintfです。 qrintfは、Cプリプロセッサのラッパーとしてソースコードに含まれるsprintfの呼出フォーマットを解析し、フォーマットにあわせたコードに書き換えることで、sprintfを高速化します。 たとえば、以下のようなIPv4アドレスを文字列化するコード片を sprintf( buf, "%d.%d.%d.%d", (addr >> 24) & 0xf
まずコードの可読性を最適化しよう | POSTD
最近では 最適化 という言葉を使う場合、GPUメモリ消費やネットワークトラフィックの最適化、などと明示的に言わない限りは、 実行時間の最適化 という意味で使われるケースがほとんどです。 自分が何を最適化しようとしているかを知ろう 私がプログラムを始めた頃、プロセッサの処理能力は遅く、メモリサイズもとても限られていて、キロバイト単位で計算されていました。ですからメモリ容量をよく考え、メモリ消費を上手に最適化しなくてはなりませんでした。大学では最適化について2つの極論を教わりました。 メモリを犠牲にして実行スピードを最適化する。 または何度も計算を繰り返して、メモリ消費を最適化する。 最近では誰もメモリについては大して気にしていません（デモシーン製作者、組み込みシステムのエンジニア、一部の携帯電話ゲームのディベロッパなどは別です）。RAMだけでなく、ハードディスクの容量についても同様です。 W
x86/x64最適化勉強会5 レポート - Cybozu Inside Out | サイボウズエンジニアのブログ
こんにちはサイボウズ・ラボの光成です。 今回は3月30日に開催された「x86/x64最適化勉強会5」の模様についてお伝えします。 x86/x64最適化勉強会会場 プログラム開発においては、開発の段階において早すぎる最適化は悪、本当に必要になってから最小限だけ行いなさいと言われています。 また今どきのコンパイラは優秀なので、下手な小細工はせずにコンパイラに任せておくのがよいとも言われています。 もちろん一般的にはそれは正しいのですが、普段動画や音声を利用するときに使われているコーデック、ネット上での決済時に利用される暗号ライブラリなどは、人の手によるアセンブリ言語で開発されていることが多いのもまた事実です。 私が主催しているこの勉強会はそういう下回りのライブラリを開発するときに必要な技術や情報の交換のために行っています。 ustreamで過去の会の動画も含めてみることができます。 以下、やや
頻出典型アルゴリズムの演習問題としてよさげなやつ - kyuridenamidaのチラ裏
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
Kazuho@Cybozu Labs: MySQL のボトルネックを統計的に監視・解析する方法
MySQL のチューニング、と言った場合には、サーバーパラメータの調整や EXPLAIN コマンドを利用したクエリ実行計画の最適化が話題に上ることが多いです。しかし、発行する全ての SQL について、いちいち EXPLAIN コマンドを使って確認していては、いくら時間があってもたりません。チューニングを効率的に進めるには、まず、ボトルネックとなっている SQL クエリを特定し、次にその最適化を行うべきです。 ではどのようにして、ボトルネックを特定するのか。MySQL Conference & Expo 2009 のキーノートにおいて Mark Callaghan 氏は、Google では SHOW PROCESSLIST コマンドを使った統計的アプローチを使っていると述べていらっしゃいます (参照: MySQLConf 09: Mark Callaghan, "This is Not a
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
配信講義 計算科学技術特論A (2017) (4月13日～7月27日) | 理化学研究所 計算科学研究センター(R-CCS)
実行時におけるJVMバイトコード最適化手法
qaa.ath.cx is offline