How to shuffle songs? - Spotify Engineering
At Spotify we take user feedback seriously. We noticed some users complaining about our shuffling algorithm playing a few songs from the same artist right after each other. The users were asking “Why isn’t your shuffling random?”. We responded “Hey! Our shuffling is random!” So who was right? As it turns out, both we and the users were right but it’s a bit more complicated than that. It also tells
テキストエディタで使われがちなデータ構造 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 を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
Google、「人による人のための」結果と「まともなレビュー」を優先する検索改善
米Googleは8月18日（現地時間）、英語でのグローバルな検索で実施する「helpful content update」（役立つコンテンツ更新）の概要を説明した。いわゆる「クリックベイト」を排除し、検索結果に「人間が人間のために書いた、より独創的で役立つコンテンツが表示されるようにする」ための取り組みの一環だ。向こう数週間中に展開する。 まず、「読者に情報を提供するのではなく、クリックを獲得することを目的としたように見えるコンテンツ」や「オリジナルではない低品質のコンテンツ」が上位に表示されないようにする。特に、オンライン教育資料、エンターテインメント、ショッピング、テクノロジー関連のコンテンツで効果が見られるようになるとしている。 例えば、新作映画について検索した場合、従来は「他のサイトに掲載されたレビューを寄せ集めた記事が表示されたかもしれない」が、この更新により「独自の信頼できる情
The tar archive format, its extensions, and why GNU tar extracts in quadratic time - Mort's Ramblings
Date: 2022-07-23 Git: https://gitlab.com/mort96/blog/blob/published/content/00000-home/00014-tar.md (If you're here from Google and just need help with tar being slow: If you trust the tar archive, extract with -P to make tar fast.) A couple of days ago, I had a 518GiB tar.gz file (1.1 TiB uncompressed) that I had to extract. At first, GNU tar was doing a great job, chewing through the tar.gz at a
パズルとアルゴリズムのコラボ本を書きました！ - けんちょんの競プロ精進記録
1. はじめに お久しぶりです！ けんちょん本のけんちょんです。 最近はアルゴリズムがとても盛り上がっていますね。今回新たなアルゴリズム本を上梓させていただくことになりました！ 発売予定日は 2022/4/20 です。一部大型書店では、もうすでに並んでいるはずです。今回の記事では、この本を通してお届けしたいメッセージや、想定読者、内容などについて簡単に紹介させていただきます。 amazon ページへのリンク 2. 本書の内容と対象読者 2-1. 本書の内容 百聞は一見に如かずということで、まずは目次構成をお見せします！ 第 1 章：アルゴリズム入門 第 1 話：「テンパズル」 〜 力まかせ探索 第 2 話：「小町算」 〜 再帰関数 第 3 話：「虫食算」 〜 枝刈り 第 II 章：グラフアルゴリズム 第 4 話：「数独」 〜 深さ優先探索 1 第 5 話：「覆面算」 〜 深さ優先探索 2
40年越しにTCPの仕様(RFC793)が改訂される RFC9293 - ASnoKaze blog
2022/08/09 追記 「RFC 9293 Transmission Control Protocol (TCP)」として正式なRFCが出ました TCPのコア部分の仕様は1981年に発行された「RFC793 TRANSMISSION CONTROL PROTOCOL」で標準化されています。 この、RFC793の改訂版となる「Transmission Control Protocol (TCP) Specification」は、2013年からIETFのTCPM WGで議論されてきましたが、4月4日にIESGによって承認されました(参考URL)。現在はRFC出版の準備に入っています(新しいRFC番号はこの後正式に決まります) www.ietf.org 改めてTCPの仕様を読みたい場合はこのドキュメントを読むのが良さそう。 概要 この改訂版の仕様(通称 rfc793bis)は、RFC793が
GitHub - wolfgarbe/SymSpell: SymSpell: 1 million times faster spelling correction & fuzzy search through Symmetric Delete spelling correction algorithm
Spelling correction & Fuzzy search: 1 million times faster through Symmetric Delete spelling correction algorithm The Symmetric Delete spelling correction algorithm reduces the complexity of edit candidate generation and dictionary lookup for a given Damerau-Levenshtein distance. It is six orders of magnitude faster (than the standard approach with deletes + transposes + replaces + inserts) and la
徹底解剖 TLS 1.3 | 翔泳社
wolfSSLをもとに、SSL/TLSの正しい利用法と仕組みを理解する 暗号化された安全な通信は、ネットワークを使う全てのアプリケーションにとって、 考慮すべき重要な課題です。 セキュアな通信を実現するために用いられる技術SSL/TLSの最新版がTLS 1.3であり 各種SSLライブラリも対応してきています。 ただ、ライブラリだけが最新のものになっても、仕組みを知り、 正しく使わなければ、安全は担保されません。 そこで本書は、そんなTLS 1.3の基礎的なプロトコルの流れから、 暗号化・認証の仕組み、アプリケーション実装のベストプラクティスを 組み込みシステム向けの軽量＆高機能なライブラリwolfSSLを例に 解説していきます。 さらに、ライブラリコードの解説を含め、内部実装にまで踏み込んだ解説も行い、 SSLライブラリを徹底的に理解できる一冊です。 Part 1：TLSの技術 ・Chap
MPEG-5 EVCコーデックメモ - Qiita
https://mpeg.chiariglione.org/standards/mpeg-5/essential-video-coding 正式名称「MPEG-5 Part 1 Essential Video Coding」 ISO/IEC 23094-1 Essential video coding 特許問題により普及しないH.265/HEVCコーデックの代替を狙った、ライセンス・フレンドリ(licensing-friendly)な動画像コーデック。 目的 ロイヤリティフリー(RF; Royalty-Free)な枯れた技術1のみを用いる Baseline Profile と、特許技術を用いてより高効率を目指す Main Profile という2オプションを提供する。 ロイヤリティフリー・コーデック運用ができるよう、任意の Main Profile 向け符号化ツールは選択的に無効化可能。
「Googleのソフトウェアエンジニアリング」を読んだ - wyukawa's diary
www.oreilly.co.jp 目次はこちら 第1部 主題 1章 ソフトウェアエンジニアリングとは何か 第2部 文化 2章 チームでうまく仕事をするには 3章 知識共有 4章 公正のためのエンジニアリング 5章 チームリーダー入門 6章 スケールするリーダー 7章 エンジニアリング生産性の計測 第3部 プロセス 8章 スタイルガイドとルール 9章 コードレビュー 10章 ドキュメンテーション 11章 テスト概観 12章 ユニットテスト 13章 テストダブル 14章 大規模テスト 15章 廃止 第4部 ツール 16章 バージョンコントロールとブランチ管理 17章 Code Search 18章 ビルドシステムとビルド哲学 19章 GoogleのコードレビューツールCritique 20章 静的解析 21章 依存関係管理 22章 大規模変更 23章 継続的インテグレーション 24章 継続的
Googleが過去1年で検索アルゴリズムをどう変更したのか＆どんな影響があるのかを可視化するとこうなる
Googleはユーザーエクスペリエンス(UX)改善のため、常に検索エンジンのアルゴリズムを進化させています。アルゴリズムの変更によりGoogle検索結果の順位が変更されることも多く、「Googleがいつ・どんなアルゴリズム変更を行ったのか」は、ウェブサイトの流入分析に役立ちます。そんなGoogleのアルゴリズム変更について、2021年1月から12月までの内容をまとめた図が公開されました。 An Overview of Google's Algorithm Updates in 2021 [Infographic] | Social Media Today https://www.socialmediatoday.com/news/an-overview-of-googles-algorithm-updates-in-2021-infographic/617013/ 以下がGoogleが20
ロスレス画像圧縮: QOI(Quite OK Image) format
QOI(Quite OK Image) format 2021年11月にDominic Szablewski氏(@phoboslab)の手による新しいロスレス画像圧縮「QOI(Quite OK Image) format」がアナウンスされました。 C言語のヘッダオンリー・ライブラリとしてわずか300行たらずで実装され、PNGフォーマットに近いデータ圧縮性能でありながら、20～50倍のエンコード速度、3～4倍のデコード速度を実現しています（作者自身によるアナウンス記事より）。 アナウンス記事: Lossless Image Compression in O(n) Time ソースコード: GitHub phoboslab/qoi ベンチマーク結果: QOI Benchmark Result この記事ではQOIフォーマットに関する個人的評価と、その画像圧縮アルゴリズムをざっくりと解説します。
クリエイティブコーディングの教科書
ゲームエンジンや3Dソフトウェアを利用して高度な表現ができるこの時代でも、プリミティブな描画や動き、アルゴリズムから学べることは多い。それらをJavaScriptで書くクリエイティブコーディングという形で学べる手引書が本書となる。
Rustでつくる詰将棋Solver - すぎゃーんメモ
ついカッとなって先週からRustで詰将棋ソルバを書き始めてしまい、ようやくdf-pnで何らかの解答を出せるようになったところ。ここからもうちょっと調整していくぞ、、 pic.twitter.com/XM9iPJqocv— すぎゃーん💯 (@sugyan) November 2, 2021 というわけで突然Rustで詰将棋ソルバを作りたくなり、作った。 github.com 現時点ではまだ完成度は低くて6割ほどかな…。 とはいえそこらの素直な詰将棋問題なら普通に解けると思う。 冒頭の画像は看寿賞作品の3手詰「新たなる殺意」を2秒弱で解いたもの。 先行事例 将棋プログラムの多くはC++で書かれていて 最近はRustも増えてきているのかな？ しかし「詰将棋を解く」ことに特化しているものはあまり多くはなさそうだった。 なかでもRustで書かれているものはna2hiroさんによるものくらいしか無さ
ソフトウェアエンジニア採用におけるコーディングテストのススメ - MAYAH
先日、某VC投資先の方々に対して、「ソフトウェアエンジニアの採用時にコーディングテストをやりたいがどうしたら良いか？」ということについて語ってきたので、こちらにもエッセンスをまとめたいと思います。 コーディングテストの目的 なぜ我々はコーディングテストをやるのでしょうか？ もちろん、第一目的はソフトウェアエンジニアの採用候補者のスキルを見極めるためです。 過去に、経歴も良さそう、技術的な議論もスムーズにできる、なのにコードが書けない候補者に、私は何度か出会っています。「コードが書けない」のレベルは、（ある程度易しい）論理をプログラムに翻訳できず、まともな if 文が書けないというレベルを言っています。熟練者でもド・モルガンの法則をうっかり間違えるぐらいはあると思いますが、そういう話ではありません。コードが書けない候補者は、そもそも条件が書き下せません。このような候補者を雇ってはいけません。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
【連載】Let’s 競技プログラミング! E8さんが教える アルゴリズム発想のキホン
30 分でわかる！アルゴリズムの基本
数理最適化ことはじめ / Introduction to Mathematical Optimization
Sha256 Algorithm Explained
アルゴ式
