FLoCとはなにか - ぼちぼち日記
1. はじめに Google がChrome/89よりトライアルを開始しているFLoC (Federated Learning of Cohorts)技術に対して、現在多くの批判が集まっています。 批判の内容は様々な観点からのものが多いですが、以前より Privacy Sandbox に対して否定的な見解を示してきたEFFの批判「Google Is Testing Its Controversial New Ad Targeting Tech in Millions of Browsers. Here’s What We Know.」が一番まとまっているものだと思います。 これまで Privacy Sandbox 技術に関わってきた身としては、各種提案の中でFLoCは特にユーザへの注意が最も必要なものだと思っていました。しかし、これまでのド直球なGoogleの進め方によって、FLoCのトラ
HackerRankのアルゴリズム厳選20問でコーディング面接を対策する【Pythonコード付き】 - honawork
HackerRankのCracking the Coding Interview https://www.hackerrank.com/domains/tutorials/cracking-the-coding-interviewwww.hackerrank.com HackerRankという、世界中のハッカー（＝ソフトウェアエンジニア・機械学習エンジニアなど）が、プログラミング課題を解決するサイトがあります。 そこに「Cracking the Coding Interview」といういかにもコーディング面接対策といった風情のチュートリアルがあるのですが、初心者がプログラミングのためのアルゴリズムを学ぶのに素晴らしい教材だと感じたので紹介します💁♂️ HackerRankのCracking the Coding Interview Cracking the Coding Intervi
【連載記事】JavaScriptでプログラミングを学ぶ その5：データ構造とアルゴリズム
プログラミングにおいて、値（データ）の扱いはとても重要です。今度は、値をどう管理すべきか、値をどう処理すべきかについて学んでみましょう。 連載目次 基礎と文法 関数 配列とオブジェクト オブジェクト指向 データ構造とアルゴリズム（この記事） HTMLとDOM（予定） 未定 今回学ぶ内容 プログラミングというのものは、極端なことを言うと、値の操作の集まりです。なので、値をどう上手に扱うか、という一点が重要になってきます。値の扱いが上手ければ、処理が高速に終わるかもしれません。また、少ないメモリ消費で動くかもしれません。 今回はそういった「処理効率」に焦点を当てていきます。そして高い処理効率を実現するには、データ構造とアルゴリズムの知識は必要不可欠です。 値を保持するデータ構造は様々存在します。データ構造が違うと何が違うのか、それぞれどんなメリットがあるのか、どんなデメリットがあるのか、いくつ
みんなのデータ構造 - ohbarye
C++のstd::copyのような、resize時に各要素を新しい配列にfor loopでcopyするのではなく、高速にコピー可能な機械語の命令に変換される機能を使うことで高速化される
二分木 | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第７章
トップページ – アルゴリズムとデータ構造編 この章の概要 🔗 この章の概要です。 木構造 二分木 再帰的な性質 走査 まとめ 練習問題 参考リンク 更新履歴 木構造 🔗 この章では、木構造（ツリー）というデータ構造を紹介します。連結リスト（第３章）と同様に、非常に重要なデータ構造です。 まず、木構造の概念図を見てください。 木構造 この概念図において、○ の部分を節（ノード）と呼びます。各節が線で結ばれていることが分かると思いますが、この線の部分を枝と呼びます。この概念図で、上下を逆さまにしてみれば、木のような形をしていることが分かると思います。これが木構造と呼ばれる理由です。 ここで、ある節から見て、その１つ下にある節のことを子と呼び、逆に１つ上の節を親と呼びます。 この辺りの用語は、家系図を見るように考えればいいです。兄弟、従弟、先祖、子孫などの用語もあります。ちなみに「兄弟」は
本当は遅い「似非エラトステネスの篩」の罠
この記事は？ インターネット上でエラトステネスの篩の実装を検索すると、かなりの割合で、エラトステネスの篩とよんでいいのか怪しい「似非エラトステネスの篩」とでも称すべきものがみられます。 この記事では、「試し割り」「似非エラトステネスの篩」「エラトステネスの篩」の3つのアルゴリズムを比較して、その違いを解説します。 3つのアルゴリズムの比較 1. 試し割り 実装 まず他のアルゴリズムに対する評価基準として、試し割りのアルゴリズムを示します。 試し割りは、nが素数であるかを判定するために\sqrt{n}以下の全ての素数で割って確認するアルゴリズムです。 import sys # limit 以下の全ての素数を返す def list_primes(limit): primes = [] for i in range(2, limit + 1): is_prime = True for p in
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
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック
競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)
さるでもわかるアルゴリズム — DEV Community Profile
Four Year Club This badge celebrates the longevity of those who have been a registered member of the DEV Community for at least four years. Got it Writing Debut Awarded for writing and sharing your first DEV post! Continue sharing your work to earn the 4 Week Writing Streak Badge. Got it Three Year Club This badge celebrates the longevity of those who have been a registered member of the DEV Commu
Pythonで実装する素数判定アルゴリズムと実行効率の比較 - Szarny.io
はじめに ごり押し判定法 説明 ソースコード ちょっと改善した判定法 説明 ソースコード 素数の性質を利用した判定法 説明 ソースコード フェルマーの小定理を利用した判定法 説明 ソースコード エラトステネスの篩 説明 ソースコード 実行時間の比較 説明 実験用のソースコード 実行結果 はじめに Pythonで5種の素数判定アルゴリズムを実装します． 後で効率を比較するために，各関数は の範囲において，各数が素数であるかを計算します．そして，その範囲における素数の総数を戻り値として設定します． ごり押し判定法 説明 ある数 が素数かどうか判定するために，の範囲において約数が存在するかどうか調べます． もし，その範囲内に約数が存在しないなら，素数であると判断します． ソースコード def normal(limit): n = 0 for k in range(2, limit+1): fac
フィボナッチ数絡みの競プロの問題を解いてみた（Typical DP Contest T） | 雑記帳
この間、フィボナッチ数を計算する記事を書いていたら、@fetburner氏にこういう問題を教えて頂いた： T: フィボナッチ – Typical DP Contest | AtCoder フィボナッチ数列の各項は直前の2項（隣接3項間の漸化式）によって定まる\[a_{n+2}=a_n+a_{n+1}\]が、それを「直前の\(K\)項」に一般化したものを高速に計算しなさい、ということだそうだ。\begin{align*}a_1&=a_2=\cdots=a_K=1,\\a_i&=\underbrace{a_{i-1}+\cdots+a_{i-K}}_{K\text{項}}\quad(i>K)\end{align*} 競技プログラミングにはあまり興味はない（制限時間があって他の人と競って〜という形式は好きではない）が、フィボナッチ数列の計算について熱弁した後に「わからん！w」と言って逃げるわけに
『みんなのデータ構造』でデータ構造の基礎を学んだ - valid,invalid
データ構造とアルゴリズムの学習の一環として『みんなのデータ構造』を読んだ。これまでで最も良いデータ構造の学習になった。 みんなのデータ構造 作者:Pat Morin発売日: 2018/07/20メディア: 単行本（ソフトカバー） 日本語訳がWebで公開されているので気になる方は無料で読める。が、著者や訳者や出版社応援の意味も込めて購入すると良いと思います。また、ラムダノート社のサイトから買うと紙書籍と電子書籍のセットがお得。 内容 データ構造とアルゴリズムに関連する本はアルゴリズム寄りのものが多いが、データ構造に焦点を当て続けていることが本書の特色。 内容の依存関係 p.21より 大学の教科書のように、正確性を優先したハードコアな内容。 アルゴリズムの内容も少しだがある。「11章 整列アルゴリズム」ではそれまでの章で学んだデータ構造がどのように使われるかを一瞥でき、「12章 グラフ」では深
算数の教養がほとんどないプログラマが1年間AtCoderをやった結果の振り返り｜きりみんちゃんノート
こんばんみんみん。 バーチャル幼女プログラマーという肩書でインターネットをやっているきりみんちゃんというものです。 去年の7月に競技プログラミングのAtCoderを始めてだいたい1年くらい経ったので、勉強したこととかを振り返りたいと思います。 で、誰？YouTubeでAtCoderの過去問を解く配信をしたり、Twitterで無限にAtCoderについてつぶやいたりしているVTuberです。 普段の仕事での専門分野はAndroidアプリ開発です。 半年くらい前にAtCoderを普通の社会人エンジニアに布教するエントリを書きました。 また、技術書典で「AtCoderの歩き方 -数学が得意じゃないエンジニアにこそ競技プログラミングを布教したい！-」という本を出したりもしました。 現在のAtCoderコミュニティの中心層は理系の学生やもともと数学がかなり好きなタイプの人たちです。 一方きりみんちゃ
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】 - Qiita
0. はじめに --- グラフ探索の動機 現代ではコンピュータはとても身近なものになりました。コンピュータの用途としては シミュレーションなどの大規模計算を行う 人工知能をつくる アプリを開発する などなど多様なものが考えられますが、「探索」もまた、コンピュータを用いるモチベーションとして、最も基本的かつ重要なものの一つだと思います。探索とは、与えられた対象の中から、目的に合うものを見つけ出したり、最良のものを見つけ出したり、条件を満たすものを列挙したりする営みです。 世の中における様々な問題は、探索によって、考えられる場合を調べ尽くすことによって原理的には解決できるものが多いです。例えば、現在地から目的地まで最速でたどり着く方法を求める問題は、原理的には、現在地から目的地へ到達する経路をすべて列挙することで解決できます1。将棋やオセロの必勝法を求める問題は、原理的には、考えられる局面と
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Lecture Videos | Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
Microsoft PowerPoint - 05_2011_0519_A.pptx
アルゴリズムビジュアル大事典
クックパッドマートのエンジニア採用試験｜クックパッドマートの採用