ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium
基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要
テープが擦り切れるまで聞いた Rebuild.fm 厳選オススメ回 4選
私はソフトウェアエンジニア、宮川達彦さんが運営するポッドキャスト Rebuild.fmの大ファンです。当時の同僚に勧められて初めて聞いた2014年から今まで聞いていない回はおそらくなく、何度も繰り返し聞いた回がいくつもあります。 自身で書いたブログなどでもRebuild.fmを参照させてもらったことも多く、2021年に翔泳社さん運営のWebメディア BizZineにプロダクトマネジメントに関する記事を投稿した際にも、記事内でRebuild.fmの回に触れ、放送回のタイトルを記事タイトルに引用させていただきました。 ビジネス寄りの媒体であるBizZineにRebuild.fmへのリンクが貼られているのは私の記事だけではないかと自負しています。
Linuxカーネルが難しい？Rustで実装できそう！
「ついに、RustでLinuxカーネルを実装できる！」 待ち望んだ感を出してみましたが、2年前に記事を書いてから、すっかり忘れていました。LinuxカーネルのRustサポートについての意見を求められたら、「技術的には面白いけど、実用レベルではないね。」と、上から目線の回答でエンジニアレベルの高さをアピールするつもりでしたが、2年間の間、誰にも聞かれませんでした。 近々、LinuxカーネルにRustサポートが取り込まれそう、ということで、デバイスドライバを実装してみました。 Rust対応カーネルのコンパイルまずは、Rust対応を有効にしたLinuxカーネルをコンパイルする必要があります。「カーネルってコンパイルするものなの？」という読者は、ネットの長老たちに叡智を求めましょう。「インストール直後に、メモリ削減のために不要な機能を無効にして、カーネルコンパイルしたんじゃ。」というような、太古の
Rustが遅すぎる？プロファイリングで性能向上！
「開発プロセスにプロファイリングを組み込むのはどうだろう？」 ミーティングで、プロファイリングの重要性を発言するだけで、みんながあなたの深い知見、意識の高さに驚くことでしょう。もちろん、あなたは、プロファイリングのやり方を知っている必要はありません。開発の終盤に、性能目標が達成されず、解析が実施される頃には、誰もあなたの発言は覚えていません。しかし、万が一、あなたの意見が採用されても困らないように、この記事を参考にしてください。 Goは、CPU、メモリ、block、mutexなど、使いこなせないほどの種類をサポートするプロファイリングツールpprofを標準機能として提供します。一方、Rustは、そんな機能を提供しません。Rustへの愛が揺らぐかもしれませんが、Rustへの愛は、見返りを求めない純愛です。愛の見返りに何かが与えられると期待してはいけません。 Rustでもpprofあなたは、す
踏み台EC2を廃止してSession Manager接続に置き換えました
こんにちは、エウレカ SRE チームの原田です。 今年 (2021年) エウレカでは、公開鍵認証で接続するEC2の踏み台サーバを廃止し、代わりに各サーバへの接続をIAMで認証できるSSM Session Managerへのリプレースを行いました。本記事ではそのモチベーションや、実装のポイントを紹介していきたいと思います。 旧来の踏み台サーバ 旧来の踏み台サーバエウレカで長く運用されていた踏み台サーバ (Gateway) は以下のようなものでした。 各開発者は、自分の秘密鍵を使って踏み台サーバへSSHを行う ( 踏み台サーバ上には各開発者の個別ユーザーおよび公開鍵が登録されている )踏み台上では、接続が許可されているSSH対象のサーバの秘密鍵がユーザー毎に配置されており、その鍵で各サーバにSSHするMySQL / Elasticsearch / Redis など、Private Subnet
完全マネージドな k8s ! GKE Autopilot を解説する
Kubernetes / GKE ファンの皆様こんにちわ。Google Cloud の Kazuu (かずー) です。GKE Autopilot が GA になりました。弊社公式ブログに続きまして、GKE Autopilot を日本語で解説していきたいと思います。 本記事は以下、3 部構成となります。 GKE Autopilot 概要GKE Autopilot を試してみるGKE Autopilot がハマりそうなユースケースは？ 1. GKE Autopilot 概要GKE Autopilot は GKE の新しいモードです。Control Plane に加えて、Node が完全マネージドになります。これまでの GKE では Node はユーザー自身が必要台数分作成し、以後の Day 2 オペレーション (e.g. アップグレード) 等も気に掛ける必要がありました。GKE Autopil
DockerとPodmanの比較 [Container Runtime Meetup #3]
Container Runtime Meetup #3 発表資料 「DockerとPodmanの比較」PodmanとはPodmanは、Red Hat社を中心とするコミュニティが開発している、Docker互換のコンテナエンジンです。RHEL、CentOS、Fedora などの Linuxディストリビューションに標準で付属しています。 Podmanの使い方は、コマンド名が docker ではなく podman である点を除けば、Docker とほぼ同じです。(例: podman run -p 80:80 --name nginx docker.io/library/nginx ) “Podman”は “Pod Manager” を意味しますが、Podmanを用いてKubernetesのPodを管理することは、基本的にはできません。ただし、CRIランタイムとしてCRI-Oを用いている場合に限り、
![DockerとPodmanの比較 [Container Runtime Meetup #3]](https://cdn-ak-scissors.b.st-hatena.com/image/square/95dd437ee47af8a6787c1a615e75b7d301b636ba/height=288;version=1;width=512/https%3A%2F%2Fmiro.medium.com%2Fv2%2Fresize%3Afit%3A640%2F1%2AVD87-YoAC4PnLKoVHhC6iA.png)
RustのgRPCがGoよりも遅い？
夏のある日、GoのgRPCが、Rustよりも2倍早いという記事を見つけました。「おいおい、測定ミスだろ」と強がっていましたが、日々、不安は高まっていきます。真実の愛であれば、疑うことは許されませんが、エンジニアの言語への愛など、所詮、状況に応じて使い分けるような打算的な愛。確認してみました。 性能測定結果上記の記事と同じく、gRPCのサーバソフトウェアは、Goはgrpc-go、Rustはtonicのgreeterの性能を、gRPCのクライアントソフトウェアghzを使って、測定しました。ハードウェアは、AWSを利用し、サーバはc5a.8xlarge(32 vCPU/64 GiB)インスタンス、クライアントはc5a.16xlarge(64 vCPU/128 GiB)インスタンスを使いました。 1台のクライアントインスタンスは、同時に3,000個のgRPCクライアントを立ち上げ、合計で6,000
Benchmarking gRPC in Rust & Go
Some backgroundIf you’re a developer looking to build a reliable, memory safe, high performance application today, Rust & Go are surely your options. If you’re looking to get even more performance out of your internal applications, you might also want to look at using gRPC instead of a normal REST api. All these are solutions to reducing your computational overhead. I try to compare various librar
「Infrastructure as Codeに疲れたので、僕たちが本来やりたかったことを整理する」を１年掛けて整理した
こんにちわ。rwle1212です。 本記事は JAWS Days 2020 で話す予定でしたが、昨今の事情によりオンライン開催となったため、登壇予定の内容を記事にしたものになります。 登壇していれば諸般の事情により左手首を骨折したネタが使えたのですが、ブログでは伝わらないので非常に残念な思いをしております。という話はどうでも良いので本題に入ります。 50分の登壇内容なので少々長くなりますが、お付き合いください。 JAWS Days 2019で登壇した内容の振り返り昨年の JAWS Days 2019 で「Infrastructure as Codeに疲れたので、僕たちが本来やりたかったことを整理する」という内容で登壇しました。 まずは上のリンクに添付されているスライドを5分位で読めると思うので一読頂いて、下の文に進んで頂ければと思います。 そもそもInfrastructure as Cod
ミルクボーイがアジャイルを説明したら
序章駒場「最近、うちのおかんがシステム開発に興味を持っててなぁ、名前は忘れたらしいんやけど、迅速に開発できて、仕様変更にも対応できる、素晴らしい開発手法を取り入れてるところがあるらしいんやわ〜。」 内海「そんなもんアジャイルに決まってるがなぁ〜! 今やシステム開発と言えば、アジャイル。素早く変化に対応できるってゆーのが特徴なんよ。そもそも名前が “迅速” を意味する英語やねんから、アジャイルに決まってるがなぁ〜。」 チームの人数駒場「最初、オレもそう思たんやけどな、なんでも 40 人ぐらいで開発してるらしいんやわぁ〜。」 内海「ほなぁ、アジャイルちゃうかぁ…。アジャイルでは 5〜9 人ぐらいが推奨されてるからなぁ〜。40 人もおったら、とてもやないけど、コミュニケーションが成立するとは思われへんなぁ〜。効率の悪い伝言ゲームになるのは目に見えてるからなぁ〜。おかん、他にもなんか言うてなかった
Windowsでの開発は WSL + FluentTerminal が決定版
2020/07/22 追記: ありがたいことにこの記事へのアクセスが今でも多数あります。現在はFluent TerminalよりWindows Terminalがおすすめですし、私も毎日そっちを使っています。 使う際はぜひ useAcrylic: true の設定をお忘れなきよう! (背景がすりガラスみたいになるやつです) 5ヶ月ほど前に、YogaBook (Windows)を買いまして。メインの開発環境をMac → Chrome OS → Mac → Windowsと移行することになりました。それに際してWindowsでの開発環境を整えて、やっと落ち着きそうなので紹介することにしました。 我ながら結構気に入ってます。というより、やっっと不自由なく開発できるようになりました。 tl;drWSLオンにしてUbuntuをMicrosoft Storeから入れる 参考:
WebAssemblyとは
こんにちは、HashHubエンジニアの白井です。 本日のTech Blogは「WebAssemblyについてゆーるく調べてみた」です！ ブロックチェーン業界にいる方であれば、Ethereum 2.0ではWebAssembly（WASM）でコントラクトが書けるということを聞いたことがあるかと思います。 今回はブロックチェーンのことは少なめで、そもそもWebAssemblyって何ってことを説明しようと思います。 WebAssemblyとはプログラミング言語やライブラリの名前ではなく、ブラウザでプログラムを高速実行するための、「ブラウザ上で動くバイナリコードの新しいフォーマット(仕様)」です。 Google, Microsoft, Mozzila, Appleによって仕様が策定され開発が進められています。 WebAssembly (abbreviated Wasm) is a binary in
Docker 19.03新機能 (root権限不要化、GPU対応強化、CLIプラグイン…)
NTTの須田です。2019年7月23日に公開された、Docker 19.03の新機能をお伝えします。2018年11月8日にリリースされたDocker 18.09以来、8ヶ月ぶりのリリースです。 root権限不要化従来のDockerは、ホストのroot権限でデーモン(dockerd)を動作させる必要があったため、脆弱性や設定ミスを突かれると、ホストのroot権限を奪われる恐れがありました。 Docker 19.03では、非rootユーザでデーモンを実行できるようになりました(Rootlessモード)。 Rootlessモードを有効化することで、万一Dockerに脆弱性や設定ミスがあっても、攻撃者にホストのroot権限を奪取されることを防ぐことが出来ます。ただし、現時点ではcgroupを利用できないなどの制約があります。 RootlessモードのDockerは， curl -fsSL http
60 Extensions to Supercharge Visual Studio Code
Photo by Joshua Aragon on UnsplashAll of my articles are now available for free here, without the need for a subscription to Medium! Visual Studio Code is absolutely awesome. Even out of the box, the editor can already do so much, especially for web developers. One of the major reasons that it’s so popular is that it has this unique ability to go from a strict text editor to a near full-blown IDE.
コンテナ技術を捨て、 WASIを試す
こんにちは、NTTの藤田です。 Dockerfileを書くのに疲れた？イメージサイズの縮小で1日が終わった？コンテナの起動が遅すぎる？コンテナ技術と悪戦苦闘する皆様のための新技術、アーキテクチャに依存しないポータブルなバイナリフォーマットと数十μsで起動するsandbox環境を実現する、WebAssembly System Interface（WASI）を試してみました。 WebAssembly System InterfaceとはWASIは、 WebAssembly（WASM）をウェブブラウザ以外の環境で実行するため、 ホストのファイルやネットワークなどの資源に安全にアクセスさせるための仕様です。 具体的には、POSIXに似たAPIが定義されており、WASMのバイナリが、OSが管理する資源にアクセスできるようになります。 WASMは、ネイティブコードなみの速度で動作する、ポータブルなバイ
RootlessモードでDockerをより安全にする [DockerCon発表レポート]
NTTの須田です．Moby (≒Docker)，BuildKit，containerdなど，コンテナ関連のオープンソースソフトウェアのメンテナ (開発委員．コミッタとも．)を務めています．また，Docker Meetup Tokyoの企画・運営も行っています． 2019年4月29日～5月2日にかけて， Docker公式のカンファレンスである DockerCon が サンフランシスコにて開催されました． Dockerをより安全に使うための技術「Rootlessモード」に関して発表してきましたので，紹介します． RootlessモードとはRootlessモードは，Dockerデーモン及びコンテナを，非rootユーザで実行する技術です．Rootlessモードを用いることにより，万一Dockerに脆弱性や設定ミスがあっても，攻撃者にホストのroot権限を奪取されることを防ぐことが出来ます． 須田は
![RootlessモードでDockerをより安全にする [DockerCon発表レポート]](https://cdn-ak-scissors.b.st-hatena.com/image/square/53ca4ade2119fbcb507335b89ec4b342e7a3e1a1/height=288;version=1;width=512/https%3A%2F%2Fmiro.medium.com%2Fv2%2Fda%3Atrue%2Fresize%3Afit%3A638%2F0%2AEJxWr4P_uyg5UFm1)
Kubernetesでステートフルなゲームサーバを動かした思い出
とあるスマートフォン向けMMORPGのプロジェクトで、アプリケーションサーバをほぼすべてGKE(Google Kubernetes Engine)に乗っけて動かしていました。 このゲームは、モバイル向けながら、複数プレイヤ間でそこそこリアルタイム性の高い同時プレイができるものでした。同じフィールドを誰かが歩けば、自分が見ている画面でもほぼ同時にそいつが歩いて横切っていく、同じ敵と皆で一緒に戦えば、誰かが繰り出した攻撃が参加者全員の画面に即同期される、もちろんチャットもできる、そんな具合です。今ではさほど珍しくないのかもしれませんが、PCのオンラインゲームのような機能を搭載した、リアルタイム性の高いモバイルゲームでした。 さて、こうなってくると、オーソドックスなWebサーバのような、HTTP/1でリクエスト/リプライを捌く、というサーバだけでは要件を満たすことができません。 複数プレイヤ間で
Vueを昔触った後Reactをどっぷり触ってもう一回Vueを触ってReactに戻って得た感想
最近ReactとVueをどっちも触る機会があったり、「ReactとVueどう選定するの？」という問いを投げられ、スッと答えられなかったな、と後悔があったりしていたので、Vueを触って得られた感想をまとめてみる。 結論としてなにか新しいことを発見したというものではなく、世間で言われている事を自分なりに再構築しただけの結論になったと思う。 TL; DRVueからは全体的に優しさ（Gentleさ）を感じる事が多く、良い点だと感じた大規模になるときReactの堅牢さは魅力的。Vueが大きくなった時に支えられ設計が出来るかは個人的には懐疑的。「こうだったらVue、こうだったらReact」みたいな分岐点があるというわけではないので、最終的には好みになってくると思う。ぞうさんが好きかきりんさんが好きか。これまでのフレームワーク遍歴今回の話をするにあたって、僕と各フレームワークの付き合いをまとめておくと、
BigQuery に関する１２の誤解の真相を明らかにする
この記事は Busting 12 myths about BigQuery の著者の許可を得た上で @yutah_3 が日本語訳、補足したものです。個人的に気になった話等を含めて “訳者注” を入れながら翻訳します。 割と最近、 Forrester Research のレポート The Forrester Wave™: Insight Platforms-As-A-Service, Q3 2017 では Google Cloud は Leader のポジションとして位置付けられました。 BigQuery がこの中で果たした功績は間違いなく大きいでしょう。 私達は日々、スタートアップから大企業のお客様に至るまで、多様な Google BigQuery をお使いのお客様と、お客様の分析やデータウェアハウスに関する課題を解決するために一緒に取り組んでいます。多くの場合、私達のお客様は BigQu
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
