kenju's blog

About Programming and Mathematics

algorithm

Programming Contest: 数字をローマ数字に変換する

exercism.io をやっていて、http://exercism.io/tracks/ruby/exercises/roman-numerals という問題に出くわした。数字が渡されたときに、ローマ数字(String)に変換するメソッドを実装しろ、というものだ。 Problem Specの一部抜粋は以下のような感じ。 def…

"Weighted Random Sampling (2005; Efraimidis, Spirakis)"

ランダムサンプリングのお話。 課題 配列の中から、ランダムに値を選択したい。 その際、必要に応じて重み付けしたい。 実用例 広告配信サーバーにおいて、ランダムにクリエイティブを選択したいときとか。 解決策の一つ "Weighted Random Sampling (2005; E…

MurmurHashとは何か

背景 RubyのHashTableの実装が知りたくて、ソースコードを読んでいた時に、"MurmurHash"という単語に出会った。何かよくわからなかったので、調べて見た。 https://github.com/ruby/ruby/blob/c08f7b80889b531865e74bc5f573df8fa27f2088/st.c: /* This hash …

Zip Fileの構造詳細と分割の仕組みについて

tl;dr Zip Fileを分割してユーザーに送信する仕組みを実装した際に、そもそもZip Fileは分割できるのか、なぜ分割できるのかについて理解するために調べた Zip Fileを操作する時の基本的なLinux Commands例をメモ 構造 Zip Fileは、主に以下の3つの要素によ…

PostgreSQLのSort実装アルゴリズムのコードを読んでみた

tl;dr PostgreSQLでORDER BY句などでSortをする時、Disk I/Oの発生するMerge SortかインメモリでのQuick Sortが選択される 背景 https://www.slideshare.net/MikiShimogai/postgre-sql-explain を読んでいて下記スライドを発見したので、現在の実装を確認し…

『アルゴリズムクイックリファレンス』を読んで

アルゴリズムクイックリファレンス 第2版作者: George T. Heineman,Gary Pollice,Stanley Selkow,黒川利明,黒川洋出版社/メーカー: オライリージャパン発売日: 2016/12/24メディア: 単行本(ソフトカバー)この商品を含むブログ (5件) を見る tl;dr 疑似コー…

アルゴリズム問題を解いてみるの巻:階段飛び越しステップ数問題

github.com 問題 以下の場合について、 N=5が与えられたときのXの値は? N=6が与えられたときのXの値は? Nに大きい数が入力されても現実的な実行時間で解答できる有効なアルゴリズムを考えよ You can go up the stairs by 1, 2, or 3 steps at once. If N i…

各社サービスのランキングアルゴリズムロジックの検討

tl;dr HN, Reddit, Stack Overflow, Qiitaのランキングアルゴリズムを調査した ただし、必ずしも最新のロジックが以下の記事に基づいているとは限らない Hacker News medium.com シンプルにUpvoteに対して1時間単位での時間減衰があるアルゴリズムとなってい…