strlen() の深淵 - Qiita
あらまし strlen() という関数がある。御存知の通り、文字列の長さを算出する標準 C ライブラリの関数だ。 やってることは単純で、例えば以下のように実装できる。 size_t strlen_simple(const char* str) { const char* p = str; while (*p) ++p; return size_t(p - str); } '\0' が見つかるまでポインタを進め、初期位置との差分を返すだけだ。これで機能的には std::strlen() と同等である。 では、速度的にはどうだろう？適当にベンチマークを書いて MSVC 2022 でコンパイル＆実行するとこうなった。
徐々に高度になるリングバッファの話 - Software Transactional Memo
リングバッファのイメージ図 1. リングバッファとは何か 機能的にはFirst In First Out (FIFO)とも呼ばれるキューの一種であるが、リング状にバッファを置いてそれの中でReadとWriteのインデックスがグルグルと回る構造をとる事によって容量に上限ができることと引き換えに高速な読み書き速度を得たものである。キューを単に実装するだけなら山ほど方法があって線形リストを使ってもいいしスタックを2つ使っても原理的には可能だ。その中でもリングバッファを用いた方法の利点はひとえに性能の高さでありメモリ確保などを行わないお陰でシステム系の様々な場所で使われている。 これの実装自体は情報系の大学生の演習レベルの難度であるが少し奥が深い。まずリングバッファのスタンダードなインタフェースと実装は以下のようなものである。 class RingBuffer { public: explicit
Pythonコードを35000倍に高速化したい
はじめに Pythonは世界的にも人気のあるプログラミング言語ですが、実行速度については課題があります。Pythonの実行速度を高速化したい、という要求は根強く、これまでにも様々な処理系が開発されています。 この記事はPythonで書かれたコードを35000倍に高速化するにはどのような方法があるかについてまとめたものです。 この記事は： Pythonで書かれたアルゴリズムを35000倍に高速化する 事前コンパイル、並列化、SIMD演算を駆使する 最終的に44000倍まで高速化できた なぜ35000倍？ 2023年5月2日にModular社よりPythonの使いやすさとC言語の性能を兼ね備える新しいプログラミング言語、Mojoの開発について発表がありました。低レベルのハードウェア向けにコンパイル可能なこと、文法的にはPythonを踏襲しており、既存のPythonライブラリを利用可能であること
シンプルかつ高速な文字列照合アルゴリズムを紹介します - エムスリーテックブログ
こんにちは！ エンジニアリンググループ マルチデバイスチーム 新卒1年目の小林です。 エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。 Tech Talkのとある回の発表テーマリスト このように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です） Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。 文字列照合アルゴリズムとは テキストとパターンという文字列が与えられたときに、中に出現す
アルゴリズム本、書きました！ - Qiita
最後に、17 章で PとNPに関する話題を解説し、世の中には「効率的に解くアルゴリズムを設計することができそうにない難問」が多数あることを見ます。18 章で、これらの難問に取り組むための方法論をまとめます。 競プロをやっている方向け 扱っている題材の難易度については、こんな感じのイメージです！ チーター本 < 本書 = 螺旋本 < 蟻本 難易度が近い螺旋本は、スタンスが異なる部分もありますので、よい形で共存できたら、という想いです。 螺旋本と比べると、「動的計画法」「貪欲法」「二分探索法」などの設計技法に関する話題をより重視しています 螺旋本は「ライブラリを揃えていく」という思想なので、設計技法よりもライブラリになるものを重視する立場です 本書では、紙面の都合で「計算幾何学」と「整数論」には触れられませんでしたが、これらは螺旋本には載っています 2-2. 本書の対象読者 本書は、「アルゴリ
再帰関数を学ぶと、どんな世界が広がるか - Qiita
0. はじめに 再帰関数は初めて学ぶときに壁になりがちで なんとなくわかった...けれど どんな場面で使えるのだろう...いい感じの例を探したい！ という気持ちになりがちです。再帰関数は、なかなかその動きを直感的に想像することが難しいため、掴み所が無いと感じてしまいそうです。 そこで本記事では 再帰関数の動きを追いまくることで、再帰関数自体に慣れる 再帰的なアルゴリズムの実例に多数触れることで、世界を大きく広げる！ ことを目標とします。特に「再帰関数がどういうものかはわかったけど、使いどころがわからない」という方のモヤモヤ感を少しでも晴らすことができたら嬉しいです。なお本記事では、ソースコード例に用いるプログラミング言語として C++ を用いておりますが、基本的にはプログラミング言語に依存しない部分についての解説を行っています。 追記 1. 再帰関数とは 再帰の意味はとても広いです。自分自
小学生でもわかる累積和と中学生でもわかるBinary Indexed Tree - anctgcc’s diary
こんばんは、リューです。 今日はテスト３日目でした。留年への新たな一歩を踏み出した気がします。 JOI予選も近いですし、今日は競技プログラミングでたまによく使われるアルゴリズムとデータ構造である累積和とBinary Indexed Tree（通称BIT)の考え方についてのお話をしようと思います。プログラミングを知らない方にも理解できることを目標に書きました。ただし、私の技量では小学生に説明できないので、計算量の詳細や実装のお話はしていません。サンプルコードを追加しました。 その辺の話はググって調べてください。 序章 突然ですがこんな場合を想像してみたください。 あなたはよくA駅やB駅から電車に乗ります。A駅～J駅まであり、行先は様々ですが運賃は駅間ごとに決まっています。 ある日の駅間ごとの運賃は以下の通りでした。 A駅～B駅：118円 B駅～C駅：191円 C駅～D駅：410円 D駅～E駅
Binary Indexed Tree のはなし
Binary Indexed Tree のはなし 保坂 和宏 (東京大学理学部数学科) 第 13 回 JOI 春合宿 2014/03/19 概要 Binary Indexed Tree とは 何ができる？ 何が嬉しい？ 具体的な実装 応用範囲 区間に足す問題 多次元 二分探索 目標 実装できるようにする 「普通に Binary Indexed Tree を使うだけ」の部 分で詰まらないようになる 補助的な道具としてぱっと使えるように Binary Indexed Tree とは Binary Indexed Tree Binary Indexed Tree (Fenwick Tree) Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables" (199
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
