Why and How Does Python Use Bloom Filters in String Processing?
In our last discussion we learned all about bloom filters. It’s a unique data structure that provides membership queries in constant time while using a minimal quantity of memory. Primarily, you will find them being used in large scale and streaming applications where it is infeasible to keep all the data in memory. Examples include NoSQL databases, CDNs, load balancers, etc. However, it also has
Python言語による実務で使える100+の最適化問題 | opt100
指針 厳密解法に対しては、解ける問題例の規模の指針を与える。数理最適化ソルバーを使う場合には、Gurobi かmypulpを用い、それぞれの限界を調べる。動的最適化の場合には、メモリの限界について調べる。 近似解法に対しては、近似誤差の指針を与える。 複数の定式化を示し、どの定式化が実務的に良いかの指針を示す。 出来るだけベンチマーク問題例を用いる。OR-Libraryなどから問題例をダウンロードし、ディレクトリごとに保管しておく。 解説ビデオもYoutubeで公開する． 主要な問題に対してはアプリを作ってデモをする． 以下，デモビデオ： 注意 基本的には，コードも公開するが， github自体はプライベート そのうち本にするかもしれない（予約はしているが， 保証はない）． プロジェクトに参加したい人は，以下の技量が必要（github, nbdev, poetry, gurobi); ペー
N番目の素数を求める - すぎゃーんメモ
SNSなどで話題になっていたので調べてみたら勉強になったのでメモ。 環境 Pythonでの実装例 例1 例2 例3 エラトステネスの篩 Rustでの実装例 試し割り法 エラトステネスの篩 アトキンの篩 おまけ: GMP Benchmark 高速化のテクニック 上限個数を見積もる Wheel factorization オチ Repository References 環境 手元のMacBook Pro 13-inchの開発機で実験した。 2.8 GHz Intel Core i7 16 GB 2133 MHz LPDDR3 Pythonでの実装例 例1 最も単純に「2以上p未満のすべての数で割ってみて余りが0にならなかったら素数」とする、brute force 的なアプローチ。 import cProfile import io import pstats import sys def m
ルービックキューブを解くプログラムを書いてみよう(中編:IDA*探索) - Qiita
はじめに この記事はSpeedcubing Advent Calendar 2019の17日目の記事です。 [連載]ルービックキューブを解くプログラムを書いてみよう(前編) の続きをやっていきます。 前編では、ルービックキューブの状態/操作を表現するクラスを作り、状態を操作するメソッドを書きました。 これで、キューブをプログラム的に自由に回せる状態になったので、探索を進めていきましょう。 中編では単純な総当りで探索するので、計算量的な問題でまだ任意の状態のルービックキューブの解を見つけられるようにはなりませんが、ピラミンクスや2x2x2キューブなどの小さいパズルならこの方法でも解くことができます。 追記: 後編を書きました ルービックキューブを解くプログラムを書いてみよう(後編:状態のindex化, Two-Phase-Algorithm) 環境 環境については、前編と同様Python3.
ルービックキューブを解くプログラムを書いてみよう(前編:キューブを操る実装) - Qiita
はじめに この記事はルービックキューブ Advent Calendar 2018 の14日目の記事です。 昨日の記事は望月さんの「ラノベで覚えよう！目隠しキューブ。「恋するイヤーマフ」」でした。 本連載では、ルービックキューブを解くプログラムをPythonで実装しながら、その仕組みを勉強します。 ルービックキューブを解くプログラムと言っても、どれくらい頑張って高速化・効率化するかなどあると思うので、今回の記事では、大体1秒位 & 20手強くらいで解くプログラムを書くのを目標に、コードのわかりやすさ重視でやっていきましょう。 ルービックキューブを効率よく解くアルゴリズムとしてTwo-Phase-Algorithmというものが広く使われています。 本連載でも、Two-Phase-Algorithmを実装します。 まだ、前編しか書けていないので、内容は変わるかもしれませんが、 前編と中編では、実
非再帰型Segment TreeのPythonによる実装 - Qiita
はじめに タイトルのとおり、この記事ではPythonによる非再帰型Segment Treeの実装を紹介したいと思います。 前提知識を「ほぼ」1 必要としないようにSegment Treeの説明から入るので、もう知ってるという方は読み飛ばしてください。→非再帰型Segment Treeの実装 Segment Treeとは 通称セグ木、セグメント木などと呼ばれているデータ構造で、長さ $N$ の配列{$a_i$}$_{i=0}^{N-1}$に対して、モノイド $(S,•)$ に関する次の2つの操作がどちらも時間計算量が $O(logN)$ で行えます。 $update(i, x)$: $a_i$ を $x$ に変更する $query(l, r)$: 半開区間 $[l,r)$ に対して $a_l•a_{l+1}•$…$•a_{r-1}$ を返す モノイドとして、一般的な足し算を考えると、$q
Python の dict の実装詳解 : DSAS開発者の部屋
@methane です。 最近 Python の dict をハックしているので、その紹介をしたいと思います。 ですが、まずこの記事では現在 (Python 3.6a2) の dict の実装を詳解します。 データ構造 基本となる構造体は3つです。(Python 3.6a2 のソースより引用) typedef struct _dictkeysobject PyDictKeysObject; typedef struct { PyObject_HEAD Py_ssize_t ma_used; PyDictKeysObject *ma_keys; PyObject **ma_values; } PyDictObject; typedef struct { /* Cached hash code of me_key. */ Py_hash_t me_hash; PyObject *me_key;
強くなるためのプログラミング -様々なプログラミングコンテストとそのはじめ方- - ぴよぴよ.py
みなさんは何のためにプログラミングをしていますか？ 仕事のため、何かをつくるため。 それも良いけれど、「強くなる」ためにプログラミングしてみませんか。 様々なジャンルのプログラミングコンテストとまだ見ぬライバルたちがあなたを待っています。 今回はアルゴリズム/AI/機械学習/セキュリティ等の様々なジャンルのコンテストとその始め方について紹介したいと思います。 ※これはPyConJPでの発表を文字におこしたものです。が、Pythonの話は殆どないです。 プログラミングコンテストとは？ すべてのコンテストに共通する、「コンテストに参加する利点」 1. 自分と同じ問題を解いた、他の人の解法を知ることができる 2. 同じコンテストに出ていた、たくさんのライバルと知り合える アルゴリズムのコンテスト 問題1 問題2 TopCoder Single Round Match CodeForces AtC
Directed graph traversal, orderings and applications to data-flow analysis - Eli Bendersky's website
When traversing trees with DFS, orderings are easy to define: we have pre-order, which visits a node before recursing into its children; in-order, which visits a node in-between recursing into its children; post-order, which visits a node after recursing into its children. However, for directed graphs, these orderings are not as natural and slightly different definitions are used. In this article
Of Levenshtein automata implementations
Thanks to Ken Hironaka for kindly taking a lot of time to read and fix countless errors in this blog post! Back to Tokyo It’s been such a long time since my last post, and so much have happened. I moved to Tokyo in November 2014 and started working for Indeed Japan. I’m still kind of foreign to the dev community in Japan, so if you are also in Tokyo and you have some good tips about tech/startup e
Introduction to Monte Carlo Tree Search - Jeff Bradberry
The subject of game AI generally begins with so-called perfect information games. These are turn-based games where the players have no information hidden from each other and there is no element of chance in the game mechanics (such as by rolling dice or drawing cards from a shuffled deck). Tic Tac Toe, Connect 4, Checkers, Reversi, Chess, and Go are all games of this type. Because everything in th
The Welch-Berlekamp Algorithm for Correcting Errors in Data
This article was ported from my old Wordpress blog here, If you see any issues with the rendering or layout, please send me an email. In this post we’ll implement Reed-Solomon error-correcting codes and use them to play with codes. In our last post we defined Reed-Solomon codes rigorously, but in this post we’ll focus on intuition and code. As usual the code and data used in this post is available
FuzzyFinder - in 10 lines of Python
Introduction:FuzzyFinder is a popular feature available in decent editors to open files. The idea is to start typing partial strings from the full path and the list of suggestions will be narrowed down to match the desired file. Examples: Vim (Ctrl-P) This is an extremely useful feature and it's quite easy to implement. Problem Statement:We have a collection of strings (filenames). We're trying to
Levenshtein automata can be simple and fast
A few days ago somebody brought up an old blog post about Lucene’s fuzzy search. In this blog post Michael McCandless describes how they built Levenshtein automata based on the paper Fast String Correction with Levenshtein-Automata. This proved quite difficult: At first he built a simple prototype, explicitly unioning the separate DFAs that allow for up to N insertions, deletions and substitutions
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Talks -Algorithmic ideas, engineering tricks, and trivia behind CPython's new sorting algorithm
A minimal version of Yannakakis's algorithm for mostly plain Python
GitHub - sweeneyde/multimerge: A faster multi-way merge algorithm interchangeable with heapq.merge
https://louisabraham.github.io/notebooks/suffix_arrays.html
「この中で最初に見つけた3つの単語」は、どうやって作っているのか - Qiita
GitHub - csvoss/retroactive: Fun with time travel: Implementing retroactive data structures in Python
