アルファ・ベータ法 - Wikipedia
アルファ・ベータ法（アルファ・ベータほう、alpha-beta pruning）は完全情報ゲームにおける探索アルゴリズムの1つである。基本的にミニマックス法と同じであり、同じ計算結果が得られるが、ゲーム木において、計算しなくても同じ計算結果になる部分を枝刈りしている。 アルファ・ベータ法の擬似コードを以下に示す。alphabeta関数がアルゴリズムの実装であり、minimax関数はミニマックス法とインタフェースを揃えるためのラッパーである。 function minimax(node, depth) return alphabeta(node, depth, -∞, +∞) function alphabeta(node, depth, α, β) if node が終端ノード or depth = 0 return node の評価値 if node が自分のノード foreach ch
Trying to invent a better substring search algorithm - moao's blog
To start, calculate the sum of the first window naively: First sum is 15. For the rest, reuse the previous sum, subtract the removed element and add the new one: Second = First + 6 - 0 = 21. Third = Second + 7 - 1 = 27. Fourth = Third + 8 - 2 = 33. Fifth = Fourth + 9 - 3 = 39. And so on... That's O(N) for all windows, and addition is, of course, fast as hell. The algorithm Let's preprocess the sum
PentominoをBitboardを使って解く - すぎゃーんメモ
子どもが百均で買ってきたパズルをやってみたら、全然うまく出来なくて悔しかったのでプログラムで解を探すことにした。 Pentominoとは 探索アルゴリズムと実装 計算量概算 効率的な探索の方針 backtracking Bitboardによる検索と判定 候補の事前計算 実装と実行結果 反転・回転での重複の除外 高速化 短辺から埋める X を最初に配置する Bitboardの反転/回転 Delta Swap による手法 巨大テーブルによるループ効率化 もう一方のループ効率化 孤立点検出による枝刈り その他の実装・手法 WebAssembly化してWebAppで使う 参考 まとめ Pentominoとは 調べるまで知らなかったが、このような 5つの正方形を繋げて作られる12種類のピースを使って敷き詰める、というパズルを Pentomino(ペントミノ) というらしい。 en.wikipedia
Binary Trees To Hash Array Mapped Tries, Step by Step - Vaibhav Sagar
Posted on 7 October 2023 Tags: programming, haskell Hash Array Mapped Tries (HAMTs) are a persistent data structure used to implement hashmaps. They’re heavily used in Clojure and used to be the backbone of Haskell’s aeson library until relatively recently. I’ve written about HAMTs before but wanted to try a different approach: starting with a binary tree (or something close to it) and then making
1€ Filter
1€ Filter Géry Casiez1,2,3 Nicolas Roussel3 and Daniel Vogel4 1LIFL, 2University of Lille, 3Inria Lille and 4Cheriton School of Computer Science, University of Waterloo This page implements the "1€ Filter" in different languages. See our CHI 2012 paper (PDF). The name "1€" is an homage to the $1 recognizer. Algorithm1€ Links and Downloads Our CHI 2012 1€ paper (PDF) Data corresponding to figure 1
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
AlphaDev discovers faster sorting algorithms
Impact AlphaDev discovers faster sorting algorithms Published 7 June 2023 Authors Daniel J. Mankowitz and Andrea Michi New algorithms will transform the foundations of computing Digital society is driving increasing demand for computation, and energy use. For the last five decades, we relied on improvements in hardware to keep pace. But as microchips approach their physical limits, it’s critical t
Fast(er) binary search in Rust
Intel Core i7-1068NG7 CPU @ 2.30GHz32Gb LPDDR4X 3733 MHzDarwin Kernel Version 22.4.0 In practical terms, the performance of binary search starts to drop when the dataset becomes larger than the size of the on-core cache (L2), which in my case is 512KB or 128K u32 elements. Eytzinger Layout Link to headingOne way to address the memory access predictability problem is to use the Eytzinger layout. It
Twitter's Recommendation Algorithm
Twitter aims to deliver you the best of what’s happening in the world right now. This requires a recommendation algorithm to distill the roughly 500 million Tweets posted daily down to a handful of top Tweets that ultimately show up on your device’s For You timeline. This blog is an introduction to how the algorithm selects Tweets for your timeline. Our recommendation system is composed of many in
Building a Fibonacci Heap — Kurt Lawrence
A Fibonacci heap is a heap data structure which leverages laziness to obtain a few favourable time complexities. A Fibonacci heap is used as a priority queue, usually used in graph algorithms to find the shortest path, such as A* or Dijkstra's algorithm. Compared to a binary heap, a Fibonacci heap has an amortised time complexity for inserts and key decreases of O(1) versus a binary heap's O(log n
The World's Smallest Hash Table | orlp.net
This December I once again did the Advent of Code, in Rust. If you are interested, my solutions are on Github. I wanted to highlight one particular solution to the day 2 problem as it is both optimized completely beyond the point of reason yet contains a useful technique. For simplicity we’re only going to do part 1 of the day 2 problem here, but the exact same techniques apply to part 2. We’re go
「競技プログラマーハンドブック」和訳される | スラド デベロッパー
Antti Laaksonen氏の作成した「競技プログラマーハンドブック（原題：Competitive Programmer’s Handbook）」が和訳され、1月7日からGithub上にて公開されている。同書は、競技プログラミングの入門のために執筆されたもので、アルゴリズムを学んでおり、国際情報学オリンピック（IOI）や国際大学対抗プログラミングコンテスト（ICPC）に参加したいと考えている学生を対象とした内容となっている（Akira KANAI氏のツイート、競技プログラマーハンドブック[PDF]、GitHub - recuraki/cphb-ja: (JA)Competitive Programmer's Handbook）。 翻訳をおこなったAkira KANAI氏のツイートによると、基本的テーマから発展的テーマが300ページ超に渡って触れられている内容で、『「こんなのあるんだ!」
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
A Lock-Free Vector
What is HyperLogLog and how to build yours in Rust
Build your own CountMinSketch in Rust
Build your own Counting Bloom Filter in Rust
Surprising Weak-Ref Implementations: Swift, Obj-C, C++, Rust, and Vale
Raft
GitHub - orlp/glidesort: A Rust implementation of Glidesort, my stable adaptive quicksort/mergesort hybrid sorting algorithm.
和暦を正しく扱うための暦の話
