タグ

アルゴリズムと開発に関するmohnoのブックマーク (19)

  • 時代がstaticおじさんに追いついてきた(追記あり) - きしだのHatena

    この文章みてください。 オレはもう20年以上システム業界にいるけどな、その長い経験から言うと、オブジェクト指向なんてものは、理論としては面白いけど、およそ実用的とは言い難いものだな。まぁ、例えばGUIのコンポーネントとかはオブジェクト指向に基づいて作られているようだから、そういうツールとかを作る人には必要なものなのかもしれない。しかし君たちがいずれ作ることになる業務アルゴリズムにはまったく無縁のものだと思ってもらって間違いない。どうもこの業界、オブジェクト指向でなければダメ、というような風潮がまかりとおっているけどな、オブジェクト指向なんか当に使っている人はほとんどいないよ。オレも少し勉強してみたけど、カプセル化とかポリ何とかとか、どうにも利点が理解できなかったね。実際、実業務で使ったことなどないしな…… 「またお前、オブジェクト指向の話をしてるのか」と思ったかもしれませんが、2010年

    時代がstaticおじさんに追いついてきた(追記あり) - きしだのHatena
    mohno
    mohno 2024/02/08
    「オブジェクト指向」←なんつーか、フィボナッチ数列には要らんだろうけど(むしろ再帰すら使わん)、業務アプリの開発には必要というか、普通にフレームワーク使うよね。
  • きれいなコードは互いに似通っているが、クソコードはどこもその趣が異なっている - きしだのHatena

    先日のJJUG CCC 2023 Fallの懇親会でクソコードを研究しているという学生がいたのだけど、クソコードの研究は難しいという話をした。 人工的にクソコードを再現しても、あの野生のクソコードのクソさには全く足りないわけで。 トルストイが言うように「すべてきれいなコードは互いに似通っているが、クソコードはそれぞれにクソの趣を異にしているものである」なので、なかなか「これがクソコード」のように類型化するのも難しい。 典型的なクソコードを書いてみても、なんだかきれいなクソコードができてしまう。 クソコードはネットに出回らないので、資料の収集もまた難しい。ネットにないということは、ネットの情報に基づいている「AI」もホンモノのクソコードには触れていないことになる。 クソコード収集サイトをつくっても、実際のクソコードは業務固有処理も含まれるので、掲載できる形に整理していくと来のクソさが薄れて

    きれいなコードは互いに似通っているが、クソコードはどこもその趣が異なっている - きしだのHatena
    mohno
    mohno 2023/11/17
    「なぜそれが書けてqsortが呼び出せないんだ!」←覚えはいくらでもあるな、そういうこと。今なら「この手の処理は絶対誰かが書いてるだろ」と思って参考情報を検索するけど、昔はそういう手段もなかったし。
  • オセロの必勝法が見つかった件 | やねうら王 公式サイト

    すごいニュースが飛び込んできた。オセロの必勝法が見つかったのだ。正確に言うとオセロが弱解決された。まずはその論文を紹介する。 Othello is Solved : https://arxiv.org/abs/2310.19387 「弱解決(weakly solved)」を簡単に言うと、初期局面からの双方最善手を打つ時の結論(勝敗)がわかったと言う意味である。8×8のオセロの結論は引き分けなのだそうだ。「必勝法が見つかった」と記事のタイトルで書いたが、その結果として双方最善を尽くした時のオセロの結論が引き分けだったことが判明したので正しくは「必勝法(必ず勝てる方法)が存在しないことが証明された」とでも言うべきか。 今回は、初期局面から到達できるあらゆる局面についての結論(勝敗)がわかったわけではない。こちらは「強解決(strongly solved)」と呼ばれる。 弱解決と強解決とでは、

    mohno
    mohno 2023/11/07
    AIじゃないだろ、というのは分かる。「今回、オセロの結論が引き分けだと判明したが、後手勝ちの局面数の方が圧倒的に多いはずで(昔から人間同士の対局だと後手の方が勝率が高い」←そういうことか。
  • Othello is Solved 論文解説 (私見) - Qiita

    今朝起きたら、とんでもない論文を見つけました。 Othello is Solved ゲームの オセロが"解かれた(弱解決)" というのです。飛び起きました。それで、16時まで二度寝してから読みました。 注意すべきは、この論文が査読を経て公開されているわけではないこと、つまり形式上特にチェックを受けたものではないことです。ただ、タイトルからして非常に衝撃的ですので、個人的に読んでみました。この記事では、私がこの論文(およびソースコード)を読んでわかったことを、なるべくわかりやすくまとめます。随時更新します。 余談ですが、このタイトルはどうやら、チェッカーというゲームが以前弱解決された際の論文"Checkers Is Solved"のオマージュだろうという話です。 この記事には専門用語が出てくるので、最後の方に基礎知識として重要な用語や知識をまとめました。 お詫びと訂正 この記事の内容は、私が

    Othello is Solved 論文解説 (私見) - Qiita
    mohno
    mohno 2023/11/06
    「オセロは長らく、引き分けが答えだろうと言われてきました」「分散メモリ環境で独立して探索できるタスクを非常に多く用意したこと」「私自身、オセロの弱解決の一番乗りを狙っていた経緯があり、正直悔しいです」
  • イーロン・マスク氏、自身のツイート優先でアルゴリズムの変更指示-報道

    ツイッターのオーナーであるイーロン・マスク氏は12日夜に行われた米プロフットボールNFLの王者決定戦「スーパーボウル」に関する自身の投稿の閲覧数に不満を示し、自分のツイートが優先されるようアルゴリズムの変更をエンジニアに指示したと、ニュースサイトのプラットフォーマーが報じた。その結果、13日にはユーザーのフィードがマスク氏のツイートであふれたという。 プラットフォーマーによれば、マスク氏の指示を受け、ツイッターはユーザーのタイムラインを向上させるためのフィルターから除外することで同氏のツイートを人為的に1000倍に増やしたという。スーパーボウルの翌日にマスク氏の投稿が大量に表示されたことについて、ユーザーからは不満の声が聞かれていた。 Please stay tuned while we make adjustments to the uh .… “algorithm” — Elon Mu

    イーロン・マスク氏、自身のツイート優先でアルゴリズムの変更指示-報道
    mohno
    mohno 2023/02/15
    公的な性格を持つプラットフォームとしては“ない”話だけど、5兆円も払ったんだから、それくらい要求してもええやろ、くらいには思ってそう。「マスク氏はツイッターと同社の機能性について気ままにツイート」
  • 計算複雑性理論を知らないやつが何をやらかすか教えてやろう。 ある業務用..

    計算複雑性理論を知らないやつが何をやらかすか教えてやろう。 ある業務用Webシステムは検索結果の表示件数を5/10/20件から選べるようになっててて,URLのパラメーターで「?n=20」とかやって送ってた。メニューからは三つの値しか選べないが手で書き換えれば100とか200とか選べる穴が空いてた。 で,よりによってメモリ使用量がO(n^2)になるコードを書いていやがった。n=500でOutOfMemoryError。リモートから面白いようにサービスを落とせた。 CSを知ってるやつなら,コードを書いた瞬間から「これnの上限チェック入れないとまずいな」とわかるんだよ。というか,普通にこのコードはまずいと考えてアルゴリズムをなおして,O(1)でDBレコード全件持ってきても落ちないコードにできてたはず。

    計算複雑性理論を知らないやつが何をやらかすか教えてやろう。 ある業務用..
    mohno
    mohno 2022/11/30
    「計算複雑性理論」←マジレスすると、この言葉は知らんかった(そして忘れそう)。あくまで入力チェックの話で、昨今は計算量/メモリー使用量を気にしないケースも多いみたいだけどね(←あまり好きではない)
  • 50分で学ぶアルゴリズム / Algorithms in 50 minutes

    スライドでは、有名なアルゴリズムを概観し、アルゴリズムに興味を持っていただくことを目標にします。 第 1 部:アルゴリズムとは 第 2 部:学年を当ててみよう 第 3 部:代表的なアルゴリズム問題 第 4 部:コンピュータとアルゴリズム

    50分で学ぶアルゴリズム / Algorithms in 50 minutes
    mohno
    mohno 2021/12/01
    大学1年でこれとは、さすが東大生。↓昔から活躍されている方なのか。/「1秒に約10億回しか四則演算を」←四則だと除算も入るので、演算くらいにしておく方がよい気が。/四則の間を取ればそれくらい、という指摘あり。
  • できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記

    計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、(別の記事を Qiita とかで検索するよりも)この記事の一番下の 参考文献 にあるを読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ(など)を受け取ってアルゴリズムの計算回数(など)を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは

    できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
    mohno
    mohno 2021/10/14
    いや、ここまでの話は答えられない(というか、長くて読んでない) あと、たぶん面接官もそこまで聞いてないと思う。
  • そのシャッフル、本当にシャッフルですか?何気ない落とし穴にハマった話 - BASEプロダクトチームブログ

    こんにちは、BASEのフロントエンドチームでエンジニアリングマネージャーをやっている松原(@simezi9)です。 私は最近ではマネージャーとしてコードを書くことよりもチームの編成や採用などをメインに業務を行っているのですが、 そんな中でチラっと書いたコードで見事に落とし穴にハマって失敗をしたのでその共有記事です まえがき BASEのフロントエンドチームは現在15名ほど(うち業務委託5名)で運営されています。 この人数は今後もどんどん増えていく予定なのですが、目下全社的にリモートワークになっている事情も手伝ってメンバー同士の関係性が希薄になってしまう懸念を持っていました。 BASEの中では常に複数のプロジェクトが走っているのですが、それぞれのプロジェクトフロントエンドエンジニアは2〜3名ずつ配置されています。 そんななかでアサインされた人同士がフロントエンドエンジニア同士であるにも関わら

    そのシャッフル、本当にシャッフルですか?何気ない落とし穴にハマった話 - BASEプロダクトチームブログ
    mohno
    mohno 2021/03/10
    いや、むしろ、こんなシャッフル思いつかないぞ。乱数なんてソートの前提(推移律)が成立しないじゃん。「フィッシャーイェーツのアルゴリズム」←定番だよね。
  • N番目の素数を求める - すぎゃーんメモ

    SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m

    N番目の素数を求める - すぎゃーんメモ
    mohno
    mohno 2021/02/06
    「エラトステネスの篩」←フラグで管理しないパターンなんてはじめて見た。「アトキンの篩」←知らなかったが、オーダーは変わらないような気が。
  • プログラミングというかITが理解できない。

    1.具体的な事が分からないプログラミングで主にやる事は下記の2つ。 ①IFでAかBを選択させてどっちかの設定を実行 ②Whileで決められた回数分繰り返す これでやりたいことは分かる。分かるけれどこれでどうやって動画や音楽のエンコードをしたり 画像処理をしたりするソフトウェアになるのかというのがよく分からない。 あるいはWordとかExcelとかがどうやってこんなので作られているのかが分からない。 プログラミング入門書を読んでも、一般的に知られているソフトウェアの作り方みたいな事が 書いてないので、ゴールが見えてこない。だからうんざりしてくる。 入門書を読むと、判定と繰り返しとあとどこかからかそういうプログラムが既に作られている フレームワークだとかよく分からないものを持ってきて使ってくださいってなっている。 だからそのフレームワークがどういう風になっているのかって説明からして欲しいって思

    プログラミングというかITが理解できない。
    mohno
    mohno 2020/12/01
    「これでどうやって動画や音楽のエンコードをしたり画像処理をしたりするソフトウェアになるのかというのがよく分からない」←「アセンブラ買ったんですけど、1-2-3の作り方を教えてください」って話を思い出した。
  • The Algorithms

    You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. Dismiss alert

    The Algorithms
    mohno
    mohno 2020/10/06
    言語ごとのアルゴリズム実装集。なかなか面白いんだけど、実装が統一されているわけでもなさそうなのと、やや雑な実装がみかけられるので、あくまで参考程度かな。
  • 高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を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 つの条件を満たす道路

    高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
    mohno
    mohno 2020/02/17
    ちょっと何を言っているのか分からない。碁盤じゃなくていい(建物のための区画を無視していい)なら、だだっぴろい原っぱにしてどの点からどの点へも直線で行けば一番効率的なんじゃないの?(←そうじゃない)
  • 最短経路問題総特集!!!~BFSから拡張ダイクストラまで~ - Qiita

    的アルゴリズム(幅優先探索など)から応用(経路復元、拡張ダイクストラなど)まで、最短経路問題に関するアルゴリズムを総特集しました。 基的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれか。 始点を固定して他のすべての頂点との対について最短経路問題を解く場合や、任意の2頂点の対について解く場合などが実際には多いです。 実社会とも強く密着した問題のため、古くからたくさん効率的な解法が考えられてきました。 今回はそれらを紹介しつつ、細かいテクニ

    最短経路問題総特集!!!~BFSから拡張ダイクストラまで~ - Qiita
    mohno
    mohno 2020/01/22
    「基本的アルゴリズム(幅優先探索など)から応用(経路復元、拡張ダイクストラなど)まで、最短経路問題に関するアルゴリズムを総特集しました」
  • 軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita

    ざっくり言うと リスト構造のデータに対してランダムアクセスはしちゃだめだぞ。お兄さんとの約束だ! 発端 数年前に他部署の支援で作ったJavaのシステムに、ちょっとデカめのデータを突っ込んだらありえないほど遅いので助けてくれ、と連絡が入った。 まぁクエリとかインデックスをちょっと見れば直るっしょ・・・と鼻をほじりながら支援に向かった。 処理内容 遅い部分の処理は以下のようなものであった。 処理対象のデータをListで受け取る。 それをforループで1件ずつ前処理する。 処理結果をオブジェクトに格納し、ORマッパーでDBにINSERTする。 これだけ? そう、これだけだ。並列処理なんて高級なことはもちろんやってない。 インフラ調査 処理中のサーバのようすを調査する。今回のインフラは典型的な3層3サーバ構成。 WEBサーバはなにもかもが余裕。 APサーバではCPUを1つ使い切っている。 14コア

    軽い気持ちでLinkedListを使ったら休出する羽目になった話 - Qiita
    mohno
    mohno 2018/02/20
    これ「ほぼINSERTしかやってないような処理」になんで LinkedList を使ったの?という話じゃないのかな←コメントで指摘されてた^_^;/LinkedList にインデックスアクセスあるのか。というか.NETと違うんだ。(そりゃ違うか)
  • アルゴリズムパズル

    大学で計算機科学を教える著者が、「パズルを解くことで、アルゴリズム的思考を鍛える」というコンセプトに基づいて、古今東西150の「アルゴリズム的」な数学パズルを収録。優れたアルゴリズム設計戦略と分析テクニックを通して、アルゴリズム的思考と柔軟な発想を育てます。また、近年では、入社試験にパズル的な難問を出す企業も増えており、その対策としても役立つ一冊です。 質問形式の序文 謝辞 パズル一覧 チュートリアルのパズル 編のパズル 墓碑銘パズル 第1章 チュートリアル 一般的なアルゴリズム設計戦略 魔方陣(Magic Square) nクイーン問題(The n-Queens Problem) 有名人の問題(Celebrity Problem) 数当てゲーム(Number Guessing)(別名20の扉(Twenty Questions)) トロミノ・パズル(Tromino Puzzle) アナグ

    アルゴリズムパズル
    mohno
    mohno 2014/04/15
    これは面白そうだな。
  • 5次魔方陣を一般的なコンピュータで10分で実行したという記事に対しての考察 : mswinvksの忘備録

    [急いで打ったので文がぐちゃぐちゃですし強調等もないです。すみません。] [定期的に記事の一番下にこっそりと僕のコメントを追加しています。一応ご確認ください] このような記事を発見しました。 スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C++) 魔方陣の総数を求める、ということを、僕はスーパーコンピュータT2K-Tsukubaで約2時間30分で計算しましたが、この記事では一般的なコンピュータで10分で計算した、というものです。挑発的ですね。 僕のプログラムを1コア上で実行すると約200時間かかりました。(2012年ごろのAMD Opteron) (TODO:スパコンでの実行時間から1コア上での実行時間を割り出すと、200時間からかけ離れてるけどなんでだろう?) そして、この記事での実行環境は12コアなので、1コア換算すると実行時間は10分*12コア=

    5次魔方陣を一般的なコンピュータで10分で実行したという記事に対しての考察 : mswinvksの忘備録
    mohno
    mohno 2014/03/16
    アルゴリズムとビット演算の差なのかな。クイックソートも数がまとまらないとバブルソートより遅いし。
  • スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C ) | 配電盤

    魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、(「数」を求めるだけだとしても)GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します(Xeon Phiなら簡単なのでしょうか→追記参照)。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します(schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します)。変数iは上の図の緑の部分(カンで5個にしました)を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います(1つのマスに入る数を1バイトで表現

    スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す(C ) | 配電盤
    mohno
    mohno 2014/03/16
    アルゴリズムの問題?やってみようと思ったところが凄い。
  • Microsoft Word - 今関

    mohno
    mohno 2013/05/23
    「「アルゴブロック」は,体感・体験型エデュメントシステムとしてNECより1994 年から販売が開始され,2005 年既に生産終了」「NECと相談し,8月下旬から常設展示の一つとして展示」←おお。
  • 1