Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article?

はじめに こんにちは。データ本部 AI 技術開発部で nagiss というハンドルネームで活動している者です。 先日行われた HACK TO THE FUTURE 2023 予選(AtCoder Heuristic Contest 016) において 1 位を獲得することができましたので、その解法を紹介します。 HACK TO THE FUTURE とは HACK TO THE FUTURE は、 フューチャー株式会社 が AtCoder 上で 2018 年から毎年開催しているプログラミングコンテストです。 コンテストでは、問題がただひとつ出されます。 参加者は、この問題に対しどれだけ高いスコアを獲得できるプログラムを書けるかを競います。 (いわゆる"マラソン (ヒューリスティック) 形式"のコンテストです。) 一昨年まで予選の制限時間は 8 時間でしたが、昨年からは 1 週間程度の長さと
tl;dr: Don’t write a Rust linked list library: they are hard to do well, and usually useless. Use VecDeque, which is great. If you actually need more than VecDeque can do, use one of the handful of libraries that actually offer a significantly more useful API. If you are writing your own data structure, check if someone has done it already, and consider slotmap or generation_arena, (or maybe Rc/Ar
全永続 Queue とは? 永続データ構造とは、過去のバージョンにアクセス可能なデータ構造のことである。ふつうデータ構造を更新すると、更新元は破壊的に変更されてアクセスできなくなる。しかし、永続データ構造では更新の際に元のデータ構造を全く変更せず、新たに更新後のデータ構造を作成する。永続データ構造のうち、過去のバージョンを更新できるものを全永続、できないものを半永続という。例えるなら、半永続は過去を見る能力、全永続は過去に戻り、パラレルワールドを作る能力(元の世界は不変)である。永続でないデータ構造を短命データ構造という。 この記事で目標とする銀行家の Queue は各操作がならし O(1) の全永続 Queue である。つまり次のような問題を処理するデータ構造である。 問題(永続 Queue):\(Q_0\) を空の Queue とする。以下の \(T\) 個のクエリをそれぞれならし O
Explains how Protocol Buffers encodes data to files or to the wire. This document describes the protocol buffer wire format, which defines the details of how your message is sent on the wire and how much space it consumes on disk. You probably don’t need to understand this to use protocol buffers in your application, but it’s useful information for doing optimizations. If you already know the conc
良い話を含むので概要の最初だけでも読んでもらえると幸いです。この話が実用的かと言うと多分全然実用的ではないので理解しても仕方ないかなと言う気がします。 概要 ファイルフォーマット gzip 10-byteのヘッダ 拡張ヘッダ ファイル本体 フッタ(trailer) zip ローカルファイルヘッダ Data descriptor セントラルディレクトリエントリ セントラルディレクトリの終端レコード gzipからzipへの変換 gzipヘッダの処理 gzipファイル本体の処理 gzip trailerの処理 複数gzipファイルの連結 PoC まとめ 概要 先日Dirty PipeというLinuxカーネルの脆弱性が公表されました。 dirtypipe.cm4all.com この脆弱性の原理自体も面白いのですが、その前に報告者の組織で行っているGzipとZIPの処理で引っかかったのでまず先にそち
はじめに 正規表現が文字列にマッチするかどうかを判定するプログラムを作るにあたっては、以前の記事で紹介したようにVMを用いたり、または正規表現と等価なオートマトンを用いたりする。この記事ではこれらとは別の方法として「正規表現の微分(regular expression derivative)」を用いた方法について説明し、さらにこの方法を使うことで今までの方法では触れていなかった、正規表現のある一部にマッチした文字列を抽出するサブマッチングについても紹介する。 また、この記事で紹介するコードは次のGitHubリポジトリから入手できる。 https://github.com/y-yu/PosixRegex 正規表現の抽象構文木 まずは、正規表現の抽象構文木を表す代数的データ型を次のように定義する。 sealed trait Regex object Regex { case class Var
こんにちは。LegalForce Researchで研究員をしている神田 (@kampersanda) です。 LegalForce Researchでは現在、高速なパターンマッチングマシン Daachorse(ダークホース)を開発・運用しています。文字列処理の基礎である複数パターン検索を提供するRust製ライブラリです。以下のレポジトリで公開されています。 github.com 本記事はDaachorseの技術仕様を解説します。具体的には、 複数パターン検索に関係する基礎技術(トライ木・Aho–Corasick法・ダブル配列) Daachorseの実装の工夫と性能 を解説します。 以下のような方を読者として想定します。 文字列処理アルゴリズムやデータ構造に興味のある方 自然言語処理の要素技術に興味のある方 Rustライブラリに興味がある方 Daachorseについて 複数パターン検索の基
Googleが開発したSwisstableと呼ばれるハッシュテーブル実装がAbseilとして公開されて、Rustの標準のHashMap実装にもその移植であるhashbrownが採用されました。 Swisstable の面白いところは、8または16要素をグループ化して、グループ内の各要素のハッシュ値のうち7bitをそれぞれ1byteに格納した8または16バイトの配列を作り、その配列に対して一気に並列でマッチングを行うことです。 この並列マッチングにはSSE2もしくはビット演算が使われます。この記事ではこの並列マッチング部分について解説します。 SSE2を使う場合 SSE2を使う場合は、グループのサイズは16になります。ハッシュ値を格納する配列のことを control と呼ぶことにすると、 control は char control[16] になります。control の各バイトの状態は次の
数値が小数第四位まで与えられるとする。例えば、 1234.5678 のような形式である。 それらの数値を使って計算をしたいのだが、何も考えないと計算機上ではこれらの数値は double 型などで保持され、誤差が発生することは有名だろう。 >>> 1001.0000 * 1.1000 == 1101.1000 False >>> 1001.0000 * 1.1000 1101.1000000000001 誤差が発生するのは嫌なので、入力を 10000 倍して整数として扱いたくなる。例えば、 1234.5678 は 12345678 に変換したい。 しかし、この操作にも注意が必要である。 https://qiita.com/mod_poppo/items/910b5fb9303baf864bf7 で解説されている通り、 10000 倍したり、 int を取ったりするだけではうまくいかない。 >
絶対に勝てない6x6リバーシを作りました。あなたは黒番、AIが白番です。 絶対に勝てない6x6リバーシを作りました! ぜひ挑戦してみてくださいhttps://t.co/Ul5n3q9jMp— Yusuke Endoh (@mametter) December 30, 2021 これは何? 6x6の盤面のリバーシは後手必勝 *1 であることが知られています。 このAIは白番(後手)で完璧にプレイします。つまり黒番のあなたは絶対に勝てません。無力感を楽しんでください。 技術的な話 このAIはWebAssemblyになっているので、全部あなたのブラウザの上で動いてます。真のサーバーレスです。 AIのソースコードはRustで書きました。わりと堅実なゲーム木探索になってます。UIは普通にTypeScriptとthree.jsで実装しました。 github.com 作った順に説明します。 盤面の表現
複数の条件をすべて満たすときだけ、処理を継続したいということはよくあると思う。例えば以下のようなコード。 fn some_function(x: &Hoge) { if !check0(x) { return; } if !check1(x) { return; } if !check2(x) { return; } if !check3(x) { return; } // x に対する処理 } このとき、 check0 から check3 をどのような順番でチェックするのが一番効率がいいだろう? 直感的には、一番通りにくいチェックを最初にやっておいたほうが、残りの処理をスキップできて効率がいいように思える。しかし、それぞれのチェックにある程度時間がかかってしまうときにはどうだろうか? 例えば、処理するデータのうち各チェックが NG となる割合と、チェックに要する時間が以下の表のとおりだっ
TL;DR In this article, we'll train the car to do self-parking using a genetic algorithm. We'll create the 1st generation of cars with random genomes that will behave something like this: On the ≈40th generation the cars start learning what the self-parking is and start getting closer to the parking spot: Another example with a bit more challenging starting point: Yeah-yeah, the cars are hitting so
数日前にTwitterで, JavaScriptのオブジェクトに対する===の挙動が初心者には難しいみたいな話を見かけた. 発端や周辺の議論をちゃんと追いかけてないからとくに出典は貼らない. たぶん元々の話は「へぇ, こういう挙動なんだ, 簡単ではないね」くらいの話だったのかもしれない. 自分のタイムラインの観測範囲では「そうだそうだ, (参照の同一性ではなく)同値性にしとけばいいのに」と思っている人もそれなりにいそうに見えた. 個人的にも同値性が簡単に確認できるとよい気はするものの, 「なんでそうしないんだ, オブジェクトの中身を確認していくだけだろ!」みたいな簡単な話ではないことも知っているため, 以下のようなツイートをしたのだった. JavaScriptのオブジェクトの同値性、再帰的な構造とか作るとぜんぜん自明じゃないんだよなぁ。リンクの構造は違うけどプロパティを辿ったときのパスはど
Squircle centred on the origin (a = b = 0) with minor radius r = 1: x4 + y4 = 1 A squircle is a shape intermediate between a square and a circle. There are at least two definitions of "squircle" in use, one based on the superellipse, the other arising from work in optics. The word "squircle" is a portmanteau of the words "square" and "circle". Squircles have been applied in design and optics. In a
最近,量子コンピュータの話題をニュースや新聞で見かけることが増えてきました. その中で気になってきたのが,組合せ最適化と量子コンピュータ(特に量子アニーリング)に関する怪しい言説.私自身は(古典コンピュータでの)組合せ最適化の研究をやってきて,量子コンピュータを研究しているわけではないのですが,さすがにこれはちょっと・・・と思う言説を何回か見かけてきました. 最近の「量子」に対する過熱ぶりは凄まじいので,こういう怪しい言説が広まるのは困りものです.すでにTwitter上には,“組合せ最適化は今のコンピュータでは解けない”とか“でも量子なら一瞬で解ける”という勘違いをしてしまっている人が多数見られます*1. さすがに危機感を覚えてきたので,この場できちんと指摘しておくことにしました. 今北産業(TL;DR) “古典コンピュータは組合せ最適化を解けない” → 古典コンピュータで組合せ最適化を解
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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く