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
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
Compiling Rust is NP-hard
Compiling Rust is NP-hard July 7, 2021 · 11 minute read ...though it's not the flagship borrow checking that's at fault. What I noticed, and would like to share with you today, is that the exhaustiveness checking performed by the Rust compiler on match patterns is a superset of the SAT problem. Exhaustiveness checking Consider the following code (playground): fn update_thing(old_thing: Option<Thin
Sorting colors in JavaScript
Sorting colors in JavaScriptJune 22, 2021How to sort colors in JavaScript? Let me tell you a story first. In the project I'm working on right now we used to have 134 colors in use! WTF?! you say. Once I discovered that I thought I'm going to show that to my colleagues, and we will address the problem. Unfortunately, I'm a very visual person (so to say) and I couldn't stand the very random order of
Compressing JSON: gzip vs zstd – Daniel Lemire's blog
JSON is the de facto standard for exchanging data on the Internet. It is relatively simple text format inspired by JavaScript. I say “relatively simple” because you can read and understand the entire JSON specification in minutes. Though JSON is a concise format, it is also better used over a slow network in compressed mode. Without any effort, you can compress often JSON files by a factor of ten
optimizing hashmaps even more
optimizing hashmaps even more — 2021-05-08 hashmaps and hashing algorithms enums as keys static strings as keys hybrid static + dynamic keys looking ahead conclusion In our last post we took a look at possible ways we could improve the ergonomics of Rust's refcounting APIs. In this post we'll be looking at Hashmap: how it's currently implemented, how we could optimize it further, and finally direc
Ruby Garbage Collection Deep Dive: Compaction
So far in this series, we’ve discussed GC::INTERNAL_CONSTANTS, the Tri-Color Mark and Sweep algorithm, Generational GC and Incremental GC. We’ll build on what we’ve learned in this post about the newest addition to Ruby’s GC: compaction. Fragmentation Before we dive into compaction, we need to learn about fragmentation. Fragmentation is the term we use to describe memory when it’s allocated non-co
Slack、1月の大規模障害の原因を説明。「AWS Transit Gateway」がトラフィックの急上昇に対応できず、AWSはアルゴリズムを見直すと
Slack、1月の大規模障害の原因を説明。「AWS Transit Gateway」がトラフィックの急上昇に対応できず、AWSはアルゴリズムを見直すと AWSのネットワーク基盤の一部が飽和していた 1月4日、サービス内部のエラー率上昇によって始まったSlackの障害は、太平洋標準時の午前6時ごろからはSlackのWeb層の負荷が高まり、パケットロスを発生しはじめるなど徐々に深刻化。7時頃にはついにサービス停止にまで発展してしまいます。 負荷の解消のためにWeb層をスケールアウトさせるなどの対処を行い、なんとかサービスが復旧し始めたころに、AWSから障害の引き金となった現象についての報告が次のようになされたとのこと。 「Slack’s Outage on January 4th 2021」から引用します。 By the time Slack had recovered, engineers
A new hash algorithm for Git [LWN.net]
The Git source-code management system is famously built on the SHA‑1 hashing algorithm, which has become an increasingly weak foundation over the years. SHA‑1 is now considered to be broken and, despite the fact that it does not yet seem to be so broken that it could be used to compromise Git repositories, users are increasingly worried about its security. The good news is that work on moving Git
論文｜snmalloc: A Message Passing Allocator (ISMM 2019)
「snmalloc: A Message Passing Allocator」という論文を読んだのでその紹介です。本論文は ISMM (International Symposium on Memory Management) 2019 に採択されており、論文とソースコードは GitHub (microsoft/snmalloc) で公開されています。リポジトリ名から分かる通り、著者の多くが Microsoft Research に所属しています。 免責 読み間違えている可能性があります。正確な情報が欲しい方は必ず論文を読んでください。誤りの指摘や補足、議論などは GitHub Issue や Twitter へお願いします。 更新履歴 2019/07/08 bump pointer と free list の next entry pointer を判定する方法について追記 2019/0
15パズル
最近, 高木貞治先生の「数学小景」を眺めていたら, その中に「十五の駒遊び」という題で15パズルの話があった. ところで, 最近知った15パズルの面白い解き方は, 福岡教育大学の藤本さんの提案する「回転型操作」によるものだ. 2件の論文がある. 情報処理学会研究報告にある「スライドパズルにおける回転型操作とアクセスビリティ」と, 近着の数式処理にある「Loop generatorによる15パズルの最適アルゴリズムとGod's numberについて」. 私は明解な手順には関心があるが, 最短手順には興味がないので, 後の論文は眺めた程度であった. 前の論文も解法は数式処理しシステムGAPを使って記述してあるので, GAPに馴染まぬ凡人にはとんと理解し得ぬ. 以下では私がSchemeで書いたプログラムの考え方を述べる. この回転操作(英語ではloop generatorというらしい)は, 前回
コンピュータを進化させてきた偉大なるアルゴリズムまとめ
By Kai Schreiber IT技術の進化のスピードには目を見張るものがありますが、それを支えているのはアルゴリズムと呼ばれる処理方法(技術的アイデア)です。さまざまなアルゴリズムの中でも、コンピュータの進化に革命的な影響をもたらしたとされる偉大なアルゴリズムは以下の通りです。 Great Algorithms that Revolutionized Computing http://en.docsity.com/news/interesting-facts/great-algorithms-revolutionized-computing/ ◆ハフマン符号(圧縮アルゴリズム) Huffman coding(ハフマン符号)は、1951年にデービッド・ハフマン氏によって開発されたアルゴリズム。頻出頻度の大小によって対戦するトーナメントツリーを考えて、ブロックごとに0と1の符号をもたせる
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
過去の水害データを基にAIで浸水範囲を推定 東北大学の研究グループがアルゴリズムを構築