昇順に並べたいクイックソートと降順に並べたい挿入ソートが殴り合う動画です pic.twitter.com/YxsN1aSI0A— ABA (@abagames) 2020年1月18日 コードとライブデモはこちら。 アルゴリズムの王道ソートアルゴリズムでコードバトリングをしてみたかったので作った。左（赤）のコードが昇順に、右（青）のコードが降順に同一の配列をソートしようとして戦う。昇順に揃ったら左の勝ち、降順に揃ったら右の勝ち。 コードは普通のJavaScriptとして書く。以下の2つの特殊な関数がある。 get(i): 配列からi番目の要素を取得する swap(i, j): 配列のi番目とj番目の要素を交換する setはできない。setを許すとコード内のメモリに配列を逃しておいてソート、一気に書き込むというインチキができるから。右の降順側のgetは要素のマイナスの値が帰ってくるので、右のコ
プレスリリース Gunosyの研究論文が推薦システムに関する国際会議「RecSys 2019」にて採択 株式会社Gunosy（本社：東京都港区、代表取締役CEO：竹谷祐哉、以下、Gunosy）は、Gunosy内の「Gunosy Tech Lab（読み：グノシー テック ラボ、以下、同ラボ）」にて、「推薦システムのためのマルチリービング手法の提案」（原題：Greedy Optimized Multileaving for Personalization）の研究結果を発表した論文が、推薦システムに関する国際会議 The ACM Conference Series on Recommender Systems (RecSys 2019)にShort Paperとして採択されたことをお知らせいたします。 RecSysは、推薦システムにおいて最も権威ある国際会議と言われております。第13回目となる2
俺は OCaml が好きだ。俺は Reason が好きだ。Algebraic Effects はもっと好きだ。 最高のリポジトリEffects bibliography: https://github.com/yallop/effects-bibliography もうこれだけあればいいんじゃないか？ってくらい言語実装と論文がまとまってる。あとは「OCaml Weekly News」とかにEffect関連の発表とか論文が紹介されてたりする。ICFPもEffect関連増えてる。 論文・An Introduction to Algebraic Effects and Handlers by Matija Pretnar Effを作った人。Computational Effectsの導入にあたって、Effect Handlerを扱えるようなコンパクトな追加の言語仕様を定義してそれをもとに入出力と
コンセンサスアルゴリズムというのをざっくり言うと、故障の発生し得るノードの集合が、整合性を持ったグループとして 1 つの値を決定する仕組みを指します。 wikipedia:en: Consensus (computer science) このアルゴリズムの具体的な例として、Paxos と Raft が挙げられます。 一方で Consul は、その一部に Raft を使っている こともあり、今日はこの Raft を追ってみました。 Raft の論文は、Raft: In search of an Understandable Consensus Algorithm になります。 ちなみにですが、概要の概要だけ掴みたいっていう人は、以下のサイトで Step by Step で追っていくのも良いかなと思います。 Raft Paxos との関係 Raft のアルゴリズム リーダー選出 ログレプリケー
はじめまして。freee株式会社の浅羽です。普段はSREや情シス等のエンジニアリングマネージャーをしつつ、エンジニアの新卒採用も担当しております。 昨年の話になりますが、機会がありまして早稲田大学の清水先生が担当されている「アルゴリズムとデータ構造」の特別講義を2コマ(12/15, 22)させていただきました。 対象は情報系の大学2年生 C言語でアルゴリズムとデータ構造を学習 データベースの授業はまだ行われていない 一コマは90分 学生さんはマシンを持参して課題をその場で解くことが可能 資料や練習問題等を公開しましたので、せっかくなのでどういう内容の講義だったかを紹介したいと思います。 講義内容をどうするか？ 当然ですが大学の先生が知識や教え方のプロです。1エンジニアがアルゴリズムとデータ構造の講義を普通にやっても、普段の講義のクオリティを超えるのは難しいと思いました。 一方でWebサービ
撮影することでURLなどを読み取れる正方形の模様、QRコード。スマホなどから利用するのが一般的ですが、どうしてもスマホが取り出せないときは、どうやって読み取ればいいのでしょうか。 ご存じの通り、人間にも目というカメラがあります。実は文明の利器なんて使わなくても、人力で解読できるのです。それでは、QRコードリーダーをあなたの脳にもインストールしてみましょう。 今回はこのQRコードを自力で読んでみましょう（CMANで作成） QRコードの基本構造を知ろう！ QRコードの構造。緑色部分は位置補正に必要なパターン、赤色部分はQRコードの読み取りに必要な情報（矢印の向きに読む） 内容を読み取る前に、そのための準備作業から始めましょう。 まず着目してもらいたいのが、QRコードの隅などにある四角形の模様です。これはカメラで読み取ったときの角度の違いを補正するためのもの。これ自体は読む必要がありませんが、周
いろいろなソフトウェアで、大きいランダムな値をユニークな値とみなすということが行われている。例えばユニークな識別子としてよく使われるUUIDはただの122ビットの乱数だ。gitもSHA-1ハッシュ値が160ビットの乱数のように扱えることを期待して、それをユニークな識別子として使っていた。実際にはランダムな2つの値が同じになる確率はゼロではないのに、なぜこれが安全なやり方だと言えるのだろうか？ それについてちょっと説明してみよう。 あるシステムが、乱数で生成された識別子の衝突のなさに依存しているとして、仮に衝突が発生した場合、相当悪い結果、例えば復旧不可能な形でデータベースが壊れてしまうとしよう。これはどれくらい危険なのだろうか？ 数学の問題で、学校のクラスの中で同じ誕生日の人が1組以上いる可能性は思ったより高いという話を聞いたことがあると思う。あるランダムに生成された値が衝突する確率という
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
情報検索の分野において、tf–idf (または、 TF*IDF、TFIDF、TF–IDF、Tf–idf)は、term frequency–inverse document frequencyの略であり、コーパスや収集された文書群において、ある単語がいかに重要なのかを反映させることを意図した統計量（数値）である[1]。また、tf-idfは情報検索や、テキストマイニング、ユーザーモデリング（英語版）における重み係数（英語版）にもよく用いられる。ある単語のtf-idfの値は文書内におけるその単語の出現回数に比例して増加し、また、その単語を含むコーパス内の文書数によってその増加が相殺される。この性質は、一般にいくつかの単語はより出現しやすいという事実をうまく調整することに役立っている。今日、tf-idfはもっとも有名な語の重みづけ(term-weighting)手法である。2015年に行われた研究
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに この記事は第2のドワンゴ Advent Calendar 2017の9日目の記事である。 2015年からはじめた公平なガチャという研究テーマは、“コミットメント”といった暗号技術を利用する方針で研究が進んだ。一方でコミットメントではなくブロックチェーンを利用した公平なガチャを実装しようという研究がSCIS 2017で佐古さんらによって提案された。またCSS 2017において江原さんらはEthereumを利用した方法を提案した。この記事ではこれまでのコミットメントを利用した公平なガチャについておさらいしつ、江原さんらの論文に基づ
セッションIDやアクセストークン、はたまた業務上で使う一意の識別子など、いろんなところで一意のIDを生成しなきゃいけないケースが存在します。 そこで世間で使われているIDの生成方法について調べてみました。 選択基準 ID生成における要求として、以下の観点が上げられるかと思います。 生成の速度 大量にデータを短期間で処理し、それらにIDを付与する場合、ID生成そのものがボトルネックとなることがあります。 推測困難性 IDを機密情報と結びつける場合、IDを改ざんされても、機密データが見れないようにできている必要があります。 順序性 採番した順にデータをソートする必要がある場合は、IDがソートキーとして使えないといけません。 それぞれについて各生成手段を評価します。 ID生成の手段 データベースの採番テーブル 採番用のテーブルを作り、そこで番号をUPDATEしながら取得していくやりかたです。古い
CONSIDER USING BLAKE3, faster than BLAKE2, see https://github.com/BLAKE3-team/BLAKE3 BLAKE2 is a cryptographic hash function faster than MD5, SHA-1, SHA-2, and SHA-3, yet is at least as secure as the latest standard SHA-3. BLAKE2 has been adopted by many projects due to its high speed, security, and simplicity. BLAKE2 is specified in RFC 7693, and our code and test vectors are available on GitHub,
It is more about the equality than the differences A good diff algorithm will attempt to identify as much equality as possible. Everything else qualifies as differences. The metric for quality and precision is a smaller count of captured differences. The smaller this number the better, presuming differences aren't escaping undetected. False negatives, which is allowing differences through without
4. 総LRUD数72187 81749 72303 8177850005,6,12=E4D9HIF8=GN576LOABMTPKQSR0J6,5,238=I67E9MBC1AF05HJKRLNGPDQSTO4,6,94827601A3BCD5JGMEFNHLKI6,5,82935=174ABCD=RHTNJKFLI0PQSOGM5,5,13O7D69E0ABC524LGJIFMN8HK6,5,2395OI1AHB4C07KT6SJR8F=M=QEDGL3,3,168452=305,5,1245A9I7JN03HDO6GCKF8BLEM6,4,7154N=D23GMIJ=8L09KFAHBC5,6,B61D5H=42C0398A=IPRJESKMNLQOTF5,6,C35AF184=D=627JGN0SEQLI=HMRTPK5,5,7143506F9NC28JABIMDKGLOEH6,3,
Zstandard is a fast compression algorithm, providing high compression ratios. It also offers a special mode for small data, called dictionary compression. The reference library offers a very wide range of speed / compression trade-off, and is backed by an extremely fast decoder (see benchmarks below). Zstandard library is provided as open source software using a BSD license. Its format is stable a
5. • その暗号技術がどのぐらい安全かを表す大雑把な指標 • nビットセキュリティは2 𝑛 回攻撃が必要 • 1回あたりの攻撃コストはあまり気にしない • 𝑂 2 𝑛 という表記 セキュリティビット 𝑛 直線 :𝑂(𝑛) 3次関数 : 𝑂(𝑛3 ) 指数関数 : 𝑂(2 𝑛) 𝑂(log 𝑛) 5 / 21 6. • 第二原像計算困難性（弱衝突耐性） • 𝑚1に対して𝐻 𝑚2 = 𝐻 𝑚1 となる𝑚2 ≠ 𝑚1が分からない • 同じじゃなくてもいいから何か一つ見つけるのが困難 • 𝑂(2 𝑛 )回トライ ; nビットセキュリティ • 衝突困難性（強衝突耐性） • 𝐻 𝑚1 = 𝐻(𝑚2)となる𝑚1 ≠ 𝑚2を見つけるのが困難 • 𝑂(2 𝑛/2 )回トライ ; 𝑛/2ビットセキュリティ • 第二原像を見つけるのは単なる衝突より2
分散システムの形式化と証明について ＠情報システム特別講義D 2016年度筑波大学
quorumとは分散システムにおいて、分散トランザクションが処理を実行するために必要な最低限の票の数である。quorumベースの技術は分散システムにおいて、処理の整合性をとるために実装される。 分散データベースシステムにおいて、トランザクションは複数サイトにおいて処理を実行している場合がある。アトミック性は全ての分散トランザクションがアトミックであることを要求するため、そのトランザクションも全てのサイトにおいて、コミットあるいは中止のいずれかの結末に至らなければならない。ネットワークパーティショニングの場合、サイトはパーティションに区分され、パーティション同士は通信可能ではない可能性がある。ここでquorumベースの技術が用いられる。基本的な考え方は、過半数のサイトがトランザクションの実行に投票した場合、そのトランザクションは実行される、というものである。 システム内の全てのサイトは票Vi
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
