2で割ることと3で割ること - Qiita
この記事でお題にするのはCPUレジスタ上の整数除算です。以下、単に除算とも書きます。 除算は非常に高コストな演算なため、コンパイラは最適化によって、できるだけ整数除算を別の計算に置き換えようとします。 最適化ができる場合の一つとして、割る数が定数である場合があります。頭のいいコンパイラは、除算を乗算とビットシフト等を駆使した演算に置き換えます。この記事では、そういった最適化の背景にある理屈を部分的に解説します。 計算機環境としてはモダンなx86 CPUを仮定します。したがってレジスタは32/64ビットであり、負数は2の補数表現になっています。ある程度は他の命令セットでも通用する話になっているかもしれません。 そもそも整数の除算とは プログラミングにおける整数の除算の定義について確認します。整数$n$を整数$d$で割るとき $$ n = q \times d + r $$ が成り立つように除
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalid
データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。 みんなのデータ構造 作者:Pat Morin発売日: 2018/07/20メディア: 単行本（ソフトカバー） 日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。 内容 データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。 内容の依存関係 p.21より 大学の教科書のように、正確性を優先したハードコアな内容。 アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
低解像度ビデオもすぐに高解像度に変換できる超解像アルゴリズム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
プログラマだったら当然知ってるよね？という知識一覧
2019年11月11日追記 ただのタイトルで煽ってるだけの記事に半年経っても未だに大量のアクセスがあるので追記しておきます。 ここで言いたいことは、「プログラマならコンピュータサイエンスを勉強してると役に立つよね」、ということ だけ です。 この一文以上に有用な言葉は以降の文章では出てきません。みなさんの時間を無駄にしないために注意書きをしました。 それでも良いという人は読んでみてください。 Twitterで「〇〇ができるという人が面接に来たけど、『じゃあXXXやYYYって知ってます？』というと知らないという人が多いんだよねぇ」とかいうツイートを見かけて、私はXXXやYYYってのを知らなかったので調べた見たところ、常識とまでは言えない概念だったり、名前は知らなくても誰もが知ってる概念だったり、むしろもっと良いアプローチがあるのではという思想だったりでなんだかなぁと思っていたところ、半日くら
プログラマの採用面接で聞かれる、データ構造とアルゴリズムに関する50以上の質問 | POSTD
情報科学科の卒業生やプログラマの中には、UberやNetflixのような新興企業や、 Amazon 、 Microsoft 、 Google のような大企業や、InfosysやLuxsoftのようなサービスを基本とする企業で、プログラミング、コーディング、ソフトウェア開発の仕事に就きたいと考える人が大勢います。しかし、実際にそういった企業で面接を受ける場合、大半の人が プログラミングに関してどのような質問をされるか 見当もつきません。 この記事では、 新卒生からプログラマになって1〜2年までの 経験値が異なる人たち向けに、それぞれの プログラミングの面接でよく聞かれる質問 をいくつか紹介していきます。 コーディングの面接では、主に データ構造とアルゴリズムに基づいた質問 がされますが、 一時変数を使わずにどのように2つの整数をスワップするのか 、というような論理的な質問もされるでしょう。
エレベータに見るアルゴリズムの性能と公平性のバランス｜Rui Ueyama
現実世界でもコンピュータの中でも、何らかの性能指標だけを追求すると参加者にとって極端に不公平になってしまうことがある。例えばエレベータとHDDは共通点がありそうに思えないが、この2つは性能特性的にとてもよく似ていて、リーズナブルな性能と公平性を両立させるために同じ制御方法が使われている。これについてちょっと説明してみよう。 1基しかない場合のエレベータの動き方は単純だ。一度上に動き出すと、上で待ってる人や降りる人がいる限り上昇し続ける。同じように、一度下に動き出すと、下で待っている人や降りる人がいる限り下降し続ける。これ以外の動き方をするエレベータはまず存在しないので、これが唯一の制御方法のように思えるけど、別にこうしなければいけないというルールはない。 エレベータの平均待ち時間を最適化することを考えてみよう。そうすると、一方向に動き続ける代わりに、エレベータが現在存在する階に一番近い人の
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
せめてはっきり言おうではないか. Googleは無能であると - yuko-hirom’s blog
デマや偽情報の拡散問題において,WELQの問題でDeNAは叩いても結局Googleを叩く人は少なかった. 私はここでまたもや大きなる権威の前では日本人はおとなしい奴隷となると言う実例を見てしまった.日本人にはGoogleほど巨大な存在に対しては盲目的に追従するのだ. bylines.news.yahoo.co.j 上記のニュース *1は見方によればGoogleはデマ情報を重要な情報としてそのリンクを編集してwebページを作成してるとも言える.ただそうしてるのがアルゴリズムか人かがDeNAやNaverまとめとの違いである. これらのサービスによって得られる負の側面はほとんど本質的には変わらないではないか？ なぜアルゴリズムがやったことは責められず、人間が直接編集したことは責められるのだろうか？人間がやったのだからその馬鹿な人間が悪く,そのような分別のない人間は許されないと人は言う. しかし分
天才プログラマーと自分との実力差をカンタンに測定する方法 - ベルリンのITスタートアップで働くジャバ・ザ・ハットリの日記
天才プログラマーと自分との実力差をカンタンに測定する方法を発見しましたよ、という話。 結論から言うと、いろんなところで過去に開催されたプログラミングコンテストの入賞者の結果を見て、その問題を同じ条件で解いてみること。 あるウェブサイトに２０１５年に開催されたプログラミング・コンテストの結果が載っていた。（本記事の末尾にそのプログラミング問題の日本語訳を載せた） 入賞者は１位の人が１５分、２位が２２分、３位が２４分、となっていた。 プログラミングの問題をザッと眺めていたら、実装すべきアルゴリズムがパッと思いついた。「これはひょっとして１位の人は超えられなくても３位入賞ぐらいはいけそうじゃね？」などと考えてしまった。 それでそのウェブサイトが用意しているエディタを使って、コードを書きだした。 １５分経過：「あれ？もう１５分も経った？まー１位にはなれなくてもトップ集団には入るわ」 ２０分経過：「
もう、アルゴリズム自分で書いてる場合じゃない？機械学習が開発手法を変える─de:code 2016セッションレポート
もう、アルゴリズム自分で書いてる場合じゃない？機械学習が開発手法を変える─de:code 2016セッションレポート 白石 俊平（HTML5 Experts.jp編集長） de:code 2016に参加中の、編集長の白石です。 今回は、編集部のメンバーそれぞれが興味あるセッションに参加してセッションレポートを書こう、ということになってまして、ぼくは「Big Data/機械学習がソフトウェア開発手法を変える! 〜静的アルゴリズム生成から動的アルゴリズム生成への道〜」というセッションを聴講しました。 スピーカーである田丸健三郎さんの語り口が心地よく、機械学習についてはかじったことくらいしかないぼくにとってはレベル感もちょうど良く、知らなかったことも数多く学べてとても満足でした。 以下に、簡単なセッションレポートを掲載します。機械学習については素人の、Webエンジニアによるレポートではありますが
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
グーグル、黒人を誤って「ゴリラ」とタグ アルゴリズムの限界か
This copy is for your personal, non-commercial use only. Distribution and use of this material are governed by our Subscriber Agreement and by copyright law. For non-personal use or to order multiple copies, please contact Dow Jones Reprints at 1-800-843-0008 or visit www.djreprints.com. http://jp.wsj.com/article/SB10468926462754674708104581082773456994848.html
競技プログラミング特有の変な実装テク - ichyo.jp
初めに この記事はCompetitive Programming Advent Calendar 2014の15日目の記事です． 競技プログラミングでは，アルゴリズムをひらめく力や，数学やアルゴリズムの知識量などが強さを決める大きな要素ではありますが， もちろん，プログラミングを使った競技である以上は，コードの実装力が勝敗を分けることもあります． 例えば，ICPC系のコンテストでは，アルゴリズムを考える能力よりも，実装量の多いプログラムをいかにバグなく高速に実装するかが重要な 問題セットが与えられることが時々あります． 競技プログラミングと無縁なプログラマーは，実装力と聞くと， クラスの構造をうまく設計したり，変更に強い美しいコードを実装する能力だと想像する人がいるかもしれません． ですが，プログラミングコンテストに必要な実装力は，そうした保守性や拡張性ではなく， 「目的の処理をシンプルな
自然言語処理に新風を巻き起こしたWord2Vecとは何か - 日経BigData
言語データの分析と応用のために自然言語処理と呼ばれる分野で長年研究が行われて来た。同分野が昨年から大きく沸き立っている。米グーグルの研究者であるトマス・ミコロフ氏らが提案した手法「Word2Vec」が、いくつかの問題について従来のアルゴリズムよりも飛躍的な精度向上を可能にしたのだ。 この手法によって得られるベクトル空間には、今まで定量的に捉えることの難しかった言葉の「意味」を極めて直接的に表現しているかのような性質が認められている。今年9月、当社がスポンサー参加した自然言語処理系の研究発表会「NLP若手の会 第9回シンポジウム」でも、多くの研究がWord2Vecに関連したテーマについて取り上げていた。今後、意味解析、文書分類、機械翻訳など様々な分野でWord2Vecの応用が期待されている。 「意味ベクトル」の驚異的な性質 Word2Vecは、その名前の表す通り、単語をベクトル化して表現する
バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート - Line 1: Error: Invalid Blog('by Esehara' )
はじめに 恐らく、プログラマの中で配列内の要素を整列させたりするソートにお世話にならなかった人、というのは余り考えられないのではないでしょうか。しかし、とはいえ、大抵はソートを自前で実装せず、組み込み関数であったり、あるいは何らかのライブラリで済ませることが殆どだと思う。 車輪の再発明というよりも、バグとか、自分が考慮していなかった挙動などを避けるために、自前でソートを組むことは余りないのですが、とはいえ、自分なりにソートを実装して見ると、それがどういう特徴を持ったソートであるか、というのがわかりますし、また、ソートというのはいったいどういう操作で実現されるのかという洞察が深まってくるなあ、という実感があったりする。 なので、今回はあるソート二つについての話を書くのが趣旨です。 最高のアルゴリズムはある、だが最悪のアルゴリズムは何か 一口にソートといったところで、ソート自体にも銀の弾丸があ
プログラムの難しさの階層 - きしだのHatena
プログラムを理解するのは、まあ難しいです。 でも、その難しさには階層があります。 よく、変数は箱だとか箱じゃないとか議論になりますが、何人か初心者に教えた感じでは、変数自体でつまづくことはあまりないので、実際はそんな例えをしなくても「変数は変数だ」で充分だったりします。 デバッガでステップ実行しながら変数の内容を見ればいい。 で、条件分岐くらいは結構つまづくことはなくて、単純な演算と条件分岐だけが必要なプログラムであればまあそれなりに書けるようです。 ぼくも、一番最初に自分の意図で作ったプログラムは input "ワカレミチガアル。ドウスル？ 1:ミギ 2:ヒダリ"; a if a = 1 then print "ガケニオチテシニマシタ" else print "ライオンニカマレテシニマシタ" みたいなものでした。こういった条件分岐をたくさん並べてアドベンチャーゲームっぽいものを作った人は
巨大数：アッカーマン関数のC++実装 - clock-up-blog
本記事の概要 巨大数と、実直な実装と、スタック使いつぶしへの対策。 C++というかほぼCライクなC++にて。 補足 少し誤解が生まれそうなので補足しておきますが、寿司の小林銅蟲と当ブログのkobakeは別人です。苗字被ってますが血縁関係もありません。交流はあります。 巨大数という謎の数学分野 数学マニア達が嗜む分野のひとつとして 巨大数 という謎の領域があります。 数式とか関数とかでひたすらデカイ数を表現するという、よく分からない分野です。 何を思ったのか漫画で解説を試みている例があるので紹介しておくと、裏サンデー の 寿司 虚空編 (作：小林銅蟲) という作品があります。分かりやすいかどうかは分かりません。個人的な感想としては1～2話はなんとなく理解できましたが3話はよく分かんないですね。 先日、小林銅蟲先生に肉を焼いてもらいつつ巨大数の解説をしていただく機会があり、なんとなく理解が進み
高専のカリキュラム! 情報工学を体系的に学ぶために高専のカリキュラムをまとめる。 - nigoblog
今回は「情報工学を体系的にやりてぇな...」という方のために 情報工学を体系的に学べるような記事を書きます。 内容は高専のカリキュラムを時系列にまとめ、参考になった教科書などを! というわけで1年目から書いていきます~ もちろん思い出しながらなのでヌケモレが有りそうですが… 1年目 ここではぶっちゃけ専門はほとんどありませんでした。 やったことは コンピュータ・リテラシー 情報数学 コンピュータ・リテラシー 色々Linuxに触れてみよう的な感じの授業。 最初にセットアップして、Emacsとかコマンドラインとか徹底的にやりました。 バッファの概念とか当時はさっぱりだった気が。 とにかくコマンドラインを使いまくったのでその時やっといて本当に良かったなと。 情報数学 何が情報数学なのだかようわからなかったけど、 数列 証明 2進数 不等式 集合論 なんかをやりました。他にも合った気がするけど。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ヒトの細胞がプログラミング可能に：米研究チームが109通りの「論理回路」の作製に成功