HackerRankのアルゴリズム厳選20問 - ゆとりSEですがなにか
honawork.hatenablog.com 上記の記事を見て是非やろうと思ったら、Cracking the Coding Interviewのリンクがなくなり、どれが厳選20問か分からなくなっていた。 自分用のメモとして、リンクを貼っておく。 データ構造 配列：左回転をする Arrays: Left Rotation | HackerRank 文字列：アナグラムをつくる Strings: Making Anagrams | HackerRank ハッシュ：身代金要求 Hash Tables: Ransom Note | HackerRank 連結リスト：循環を見つける Linked Lists: Detect a Cycle | HackerRank スタック：括弧のバランスをとる Stacks: Balanced Brackets | HackerRank キュー：ふたつのスタックの
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
できるだけ嘘を書かずに計算量やオーダーの説明をしようとした記事 - えびちゃんの日記
計算量についてのお話です。対象は、プログラミング経験はあるが計算量のことを知らない初心者から、計算量のことを知っているつもりになっている中級者くらいです。 数式を見たくない人にとっては読むのが大変かもですが、深呼吸しつつ落ちついて読んでくれるとうれしいです。 それから、この記事が自分には合わないな〜と思ったときは、（別の記事を Qiita とかで検索するよりも）この記事の一番下の 参考文献 にある本を読むことをおすすめします。Amazon の試し読みで無料で読めます*1。 TL; DR 関数の増加度合いのことをオーダーと呼ぶよ 計算量は、入力サイズ（など）を受け取ってアルゴリズムの計算回数（など）を返す関数だよ その関数のオーダーについての議論がよく行われるよ オーダーを上から抑えるときは \(O\)、下から抑えるときは \(\Omega\) を使うよ オーダーを上下両方から抑えたいときは
Binary search with modern processors
第16回 StringBeginners での発表資料
「遺伝的アルゴリズムで最高にエッチな画像を作ろう！」がGoogleに怒られた話｜群青ちきん
「そらとぶあざらしさん」を遊んで頂くと、大体の温度感がご理解いただけるかと思います。 制限がされたページ今年の1月10日に、noteタイトルにもある「遺伝的アルゴリズムで最高にエッチな画像を作ろう！」というページを公開しました。 内容はタイトルの通りです。 ランダムに生成された2枚の画像から「エッチ」な方を選んでいくと、アルゴリズム学習によってだんだんとエッチな画像になっていくというものです。 遺伝的アルゴリズムで最高にエッチな画像を作ろう！ (エッチな画像が見れるとは言っていない) より このページには、筆者のささやかな収入源として、GoogleAdSenseの広告を貼っていました。 GoogleAdSenseとは、大企業であるGoogleが運営している個人クリエイター向けの広告プログラムです。 AdSenseのポリシーとして、「性的に露骨なコンテンツ」(Sexually explici
WHATWG Living StandardとHTMLパーサ - Qiita
この記事はドワンゴ Advent Calendar 2020 最終日の記事です。年の瀬ですね。 はじめに 本記事は、WHATWG Living Standardに準拠することを目的としたHTMLパーサである「gammo」の紹介を目的としている。gammoが実現していることを詳細に伝えるため、単なるgemの紹介に留まらず、HTMLの歴史や昨今のHTMLを取り巻く状況を簡単に解説し、WHATWG Living StandardにおけるHTML文書の解析アルゴリズムについて、実例と共に紹介する。 本記事で紹介するgammoの開発に取り掛かった理由は、主に以下の二点が挙げられる。 WHATWG Living Standardに準拠したHTMLパーサをRubyGemsの中から見つけられなかったため。 現在HTMLパーサの機能を持つライブラリの中で、最も利用されていると考えられるNokogiriと比較
様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
AtCoderで水色になるまでにやったこと - naoppyの日記
naoppyです。4/21にAtCoderで水色になることが出来ました。 一つの節目として、やってきたこととかをまとめます。 レート変移 水色時点での自分 使えるアルゴリズムとテク Twitterがやめられない 精進方法 AtCoderProblemsで過去問を解く TwitterのDMで優しい人に聞きまくる チーター本を読む スライドやQiitaの記事を読む 解くときのテク まとめ レート変移 これを見てわかるのは、まあ僕に特別な才能や強い考察力がないことぐらいでしょう。 31回も参加してます。 水色時点での自分 実力と言っても色々パラメーターがあるので、難しいですが、僕のスペックを並べます。 プログラミング歴1年、Java使い 競プロ歴は始めたのが去年(2017)の7月中旬、それなりに本気でやり始めたのが12月ぐらいです 1月ごろに300点問題は完全に安定、水色になった時点で400点が
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
【ハードコアな勉強会 開催Tips】アルゴリズム勉強会を二ヶ月、計7回にわたって開催しました。 - クラウドワークス エンジニアブログ
こんにちは、エンジニア、業務委託の深山 @kenzan100 です。 突然ですが、皆さんは「アルゴリズム」と言われて何を想像しますか？ アルゴリズムというと、とっつきにくい技術分野/難しそう、という印象があるかと思います。しかし、「期待する成果を出すための、一連の手順に沿ったプロセス」という意味であれば、私たちは無意識のうちに様々なアルゴリズムを使いながら生活していると言えます。 会社までの通勤経路アルゴリズム、目玉焼きを上手に焼くアルゴリズム、歯磨きをするアルゴリズム... もしかしたらエンジニアであっても、アルゴリズムを意識しながらコードを書く機会はそう多くないのかもしれません。ライブラリやフレームワークが充実している言語であればなおさらです。 アルゴリズムを学ぶ意義 それでも、私はアルゴリズムを学ぶ意義は大きいと思います。 私にとっての最大のモチベーションは、「利用者から開発者へ、一
乱数のたのしい話と遺伝アルゴリズム - きしだのHatena
金曜日の「プログラマのための数学勉強会＠福岡」で乱数の話をしてきました。 プログラマのための数学勉強会@福岡 #3 - connpass で、乱数の生成だとか、クイックソートや素数判定などの乱択アルゴリズムの話とかをしました。 乱数タノシイヨ 乱数のたのしい話 from なおき きしだ その中で、遺伝アルゴリズムで巡回セールスマン問題(TSP)を解くというのをやってみました。遺伝アルゴリズム、すいぶん昔から名前は知ってて、どういうアルゴリズムかも知ってて、実装もそんな難しくないと知りつつ、書く機会がありませんでした。なので、この機会に書いてみようと。 とりあえず最初に完全にランダムでTSPを解いてみます。 TSP with random ぐちゃぐちゃですね。 下部のグラフはその時点での最短距離。最初に距離が短いものをみつけていくけどだんだんみつかりにくくなる、という感じになっています。 1
ポルノ写真投稿対策として肌色フィルタ作った話 - Konifar's WIP
写真投稿系のアプリだと必ず問題になると思うんですが、ユーザーが増えてくると ポルノを投稿をするユーザーが0.7〜1.0%くらいは出てくるんですよね。 本業のTaptripは海外のユーザーが99%以上なんですが、やはりポルノを投稿するユーザーが1%くらいいます。中でも中東地域のユーザーが投稿するポルノ写真は結構ヤバくて、 中学生が見たらトラウマになっちゃうんじゃないかってレベルです。 Googleの提唱するFamilySafetyの理念にも反しますし、電車の中でいきなり表示されると気まずいということもあって、昨年 『肌色フィルタ』というのを作って暫定対応しました。 ですが、最近もっと良い対策を入れたことで肌色フィルタは役割を終えることになったので、供養を兼ねてまとめておこうと思います。 先に言っておくと、AIやディープラーニングみたいな技術的なチャレンジはやっていません。あくまで工数かけずに
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
手元に置いておくと安心できる、情報系の人向けな日本語の本のリスト - EchizenBlog-Zwei
最近、人に本を薦める事が多くなった。とりあえずこの辺を読むといいですよ的なリストを作っておくと便利だと思ったので作ることにした。 以下、「事前知識のいらない入門本」「事前知識はいらないけど本格的な本」「事前知識がないと何言ってるかわからないけど有益な情報が満載な本」の3つにわけて列挙する。 事前知識のいらない入門本 数式少なめ、脳負荷の小さめな本をいくつか。何をやるにしてもデータ構造、アルゴリズム、数学はやっておくと幸せになれるよ。 情報検索と言語処理 データマイニングとか自然言語処理とかやりたい人にはとりあえずこれ。さすがに古い話が多くなってきたのでそろそろ新しい入門用情報検索本がでないかなあと思っている。 図解・ベイズ統計「超」入門 伝説のベイジアン先生がベイズの基礎を教えてくれる本。ベイズやりたい人はこれ。 珠玉のプログラミング データ構造とかアルゴリズムとかの考え方の基礎を教えてく
お手軽PerlでSuffixArrayに挑戦
試しにPERLでSuffixArrayついでにソートの勉強 下記のページを参考にしている http://www.namazu.org/~satoru/unimag/9/ ここに記述されているコードは、実験のために書かれているので、 へんなところはご容赦を... インデックスを作ってみる Cで書かれたサンプルをperlでかいてみた。 PERLでもquicksortの関数はあるが、一応PERLでかいてみた。 バイナリー形式でインデックスファイルを書き出している。 テストのためのサンプルプログラムなので、書き出したあとよみだして表示している。 pushを使って配列を拡大しているが、これってスピード的にいいのだろうか？ pack,unpack関数はいろいろ使いでありそう！！ 1: #!/usr/bin/perl 2: 3: #2003/03/14 4: #UNIXマガジン2002 10月号 横着プ
Tumblr
「JPEG Tilt」というページを公開しました。MotionJPEG Builder を作った時に、JPEG のヘッダを読み込む処理を作ったので（結局これは使わなかったんですが）圧縮データの読み込み部分も作ってみようか、という気になって作ったのがこれです。JPEG ファイルで画像が圧縮される様子を視覚的に表現する…… という目標だったのですが、どうでしょうか。まあ内容が内容なので説明無しではさすがに意味が分からないと思います。 ということで、JPEG Tilt の見方を以下で簡単に説明します。 図1は、JPEG Tilt の画面です。画像が iTunes の CoverFlow のように並んでいますが、これの左側は画像の低周波成分のみを抜き出した物で、右に行くとより高周波の成分も含めるように並んでいます（低周波、高周波という言葉の意味はこの先で出てきます） 画像の上にマウスカーソルを乗せ
頻出典型アルゴリズムの演習問題としてよさげなやつ - 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
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
NUPSC招待講演：アルゴリズムで広がる世界
IK.AM