Pythonで省メモリに大量の文字列を扱う工夫 - MNTSQ Techブログ
たくさんの文字列（や離散的な符号列）をメモリに載せないといけないんだけど、いろんな制約があって通常のList[str]では載らない…ということありませんか？（まぁあんまりなさそうですね） たまたまそういうことがあったので、その際に検討した内容をまとめておきます TL;DR メモリをもっと増やしましょう 富豪的に解決できるならいつでもそれが最高です しかし、世の中それでなんとかならんこともたくさんあります 用途があうのであれば専用のデータ構造を採用する 例えばもし共通のprefixやsuffixが存在し、順序に興味がなければtrie treeなどが使えます 例えば、弊社であれば、法人名をメモリに持ちたいなんてときもあります。そういうときに法人名の辞書をtrieで持ったりすることがあります 「株式会社」「一般財団法人」や「銀行」といった共通語がたくさんでてくるのでtrie treeでごりごり削
シンプルかつ高速な文字列照合アルゴリズムを紹介します - エムスリーテックブログ
こんにちは！ エンジニアリンググループ マルチデバイスチーム 新卒1年目の小林です。 エムスリーでは、2週間に1度、Tech Talkという社内LT会（現在はリモートで）が開催されています。これは、とある回の発表テーマリストです。 Tech Talkのとある回の発表テーマリスト このように、最近エムスリーでは文字列が流行っている（？）ようなので、その勢いに乗って私も文字列照合アルゴリズムについて書きたいと思います！（業務とは全然関係ない話です） Knuth-Morris-PrattやBoyer-Mooreアルゴリズムは解説記事がたくさん出ていると思うので、この記事ではシンプルかつ高速なQuick-SearchとQuite-Naiveアルゴリズムについて説明し、速度比較を行った結果についてご紹介します。 文字列照合アルゴリズムとは テキストとパターンという文字列が与えられたときに、中に出現す
mrubyの文字列結合のパフォーマンスを改善する | ten-snapon.com
先日、来る下記のイベントの資料でmrubyの文字列結合におけるメモリパフォーマンスについて記述し、それを社内で共有したところ、それをみた @matsumotory がmrubyにおける文字列結合は + での結合より、破壊的ではあるが <<のほうがパフォーマンスが良いということに気づいた。 valgrindで測定すると下記のような具合である。 # new.rb a = "aaa" b = "bbb" 100000.times do |n| a += b end $ sudo valgrind ./mruby new.rb ... ==2374== HEAP SUMMARY: ==2374== in use at exit: 0 bytes in 0 blocks ==2374== total heap usage: 102,786 allocs, 102,786 frees, 15,002,
【20選】俺が唸ったOSS・GitHubリポジトリ！Web企業で働くエンジニア達に聞きました - エンジニアHub｜Webエンジニアのキャリアを考える！
【20選】俺が唸ったOSS・GitHubリポジトリ！Web企業で働くエンジニア達に聞きました さまざまな企業のエンジニア20人に、リポジトリの中から「これは素晴らしい」「他のエンジニアにもぜひ使ってほしい」と思うものを紹介してもらいました！ GitHub上に存在するリポジトリや、その他の場所に存在するものまで、オープンソースソフトウェア（以下、OSS）は世の中に星の数ほど存在します。利便性の高さから世界中の開発者が利用していますが、反面その種類の多さから、どれを使ったらいいのかわからないという方もいるでしょう。 そこで本企画では、企業のエンジニア20人に、さまざまなリポジトリの中から「これは素晴らしい」「他のエンジニアにもぜひ使ってほしい」と思うものを紹介してもらい、その理由を解説していただきました。 使って便利なだけでなく、コードを読んで技術研鑽に活用するもよし。ぜひご一読あれ。 ※各カ
Java9 でも String クラスがリファクタリングされていました （JEP 254: Compact Strings 編） - 地平線に行く
本日、ついに JavaSE 9 がリリースされました！ そこで、かねてから噂になっていた JEP 254: Compact Strings がどのように実装されているのか調べてみました。 Compact Strings の概要 これまで String クラスや StringBuilder クラスなどの内部では、文字列を UTF-16 でエンコードして char 配列で保持していました。 つまり、一文字あたり*1常に char ひとつ = 2バイト分のメモリを使っていました。 しかし、これだと 1 バイトで表せる LATIN1（ASCII コード ＋ ラテン文字）の文字列の場合、その半分が 0x00 になるという無駄がありました。 そこで、内部表現を変更し、文字列が LATIN1 のみで構成されるときは 1 文字を 1 バイトで保持するようにリファクタリングされました。 ちなみに、LATIN
Java9 で String クラスがリファクタリングされていました。（replace メソッド編） - 地平線に行く
前々からこの実装はどうなの！？と言われていた String クラスの CharSequence を引数に取る replace メソッド。 これがついに Java 9 でリファクタリングされていました！ 今まであった問題 String クラスの replace (CharSequence target, CharSequence replacement) メソッドは、文字列を置換する処理です。 これが、Java 8 までのバージョンでは正規表現を使って実装していました。 public String replace(CharSequence target, CharSequence replacement) { return Pattern.compile(target.toString(), Pattern.LITERAL).matcher( this).replaceAll(Matcher
❄️frozen_string_literal - 弥生開発者ブログ
こんにちは、mzpです。最近はBuckleScriptで、OCamlをJavaScriptに変換して遊んでいます。 先日、Misoca開発チームでfrozen_string_literal を有効にするようにしたので、そのときの話を紹介したいと思います。 🔥有効にする前に起きたこと Ruby 3.0からfrozen_string_literalが標準で有効になるという話もあって、一部のコードに # frozen_string_literal: true が登場するようになりました。 次第に、 # frozen_string_literal: true を書いてないと、レビューで指摘が入るようになりました。 🚓 Rubocopの設定変更 機械的にチェックできる項目をレビューで指摘するのは好きではないので、RubocopのStyle/FrozenStringLiteralCommenteを
パーサコンビネータを高速化した - Object.create(null)
例のアレです. 式年遷宮したときの話はこちら. github.com 最初は軽い気持ちで細々とした最適化をしていたんです. switch を if に変えるとかいう小手先のアレで 10 % も高速化してウケてる— ボノボ (@susisu2413) 2017年3月13日 インライン化も同時にしてたから 10 % は言い過ぎか、でも高速化はしてる— ボノボ (@susisu2413) 2017年3月13日 ちなみにどう最適化するかというと V8 のプロファイラを使って適当に遅そうなところに目星をつけて色々試します. そんなこんなで Parsimmon*1 より妙に遅い原因を探していたら, ap, left, right (Parsec*2 でいうところの <*>, <*, *>) の実装の効率が悪く, これが主な原因であることがわかりました. ｱｯｱｯ 30 % 高速化しました— ボノボ (
BM法による文字列マッチング学習メモ - $shibayu36->blog;
grepで文字列マッチングしている時の仕組みを学ぶために、BM法などの文字列マッチングについて調べていた。調べたことをメモしておく。特にまとまってはいない。 参考になった文献は以下。 文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！ アルゴリズムの基本（7）（3/4 ページ） - ＠IT BM法をJSで実装している とりあえずイメージ掴むのには分かりやすい サービス終了のお知らせ BM法や、その亜種のHorspool のアルゴリズムとQuick-Searchを解説している ちょっとわかりづらいけど、一番ちゃんと書かれている すごく雑にイメージすると、 パターンの方に前処理を加えて、ある文字がパターンの中のどの位置にあるかを保存しておく パターンマッチングしていきマッチしなかった場合に、前処理で作った位置情報を使っていい感じにスキップする という感じ。雑すぎる。 BM法関連
どれだけ速く文字列からスペースを削除できるのか | POSTD
時によってプログラマは文字列から不要な文字を取り除きたい場合があります。例えば、テキストの一部からすべての行の末尾文字を削除したいとします。 その時、全スペース(‘ ‘)や改行コード(‘\n’および‘\r’)を削除する問題を考えてみましょう。 効率的に実行するにはどのような方法がいいのでしょうか。 size_t despace(char * bytes, size_t howmany) { size_t pos = 0; for(size_t i = 0; i < howmany; i++) { char c = bytes[i]; if (c == '\r' || c == '\n' || c == ' ') { continue; } bytes[pos++] = c; } return pos; } 上記のコードはUTF-8でエンコードされた文字列で動作します。UTF-8がASCII
#Anthony Calandra / モダンC++の機能 | POSTD
(注：2017/10/25、いただいたフィードバックを元に翻訳を修正いたしました。修正内容については、 こちら を参照ください。) (注：2017/02/07、タグが誤っていたので修正いたしました。) C++11/14/17 概要 C++11/14/17に関する記述や例の多くは、様々なリソース（詳しくは謝辞の項目をご覧ください）を参考にしており、それらを自分の言葉でまとめてみました。 C++17には、以下の新しい言語機能が導入されています。 クラステンプレートに対するテンプレート引数の推論 autoによる非型テンプレートパラメータの宣言 フォールド式 かっこ付き初期化リストを持つauto推論の新しい規則 constexprラムダ インライン変数 入れ子になった名前空間 構造化されたバインディング 初期化子によるステートメントの選択 constexpr if C++17には、以下の新しいライ
Crochemore-Perrin アルゴリズム - Qiita
どうも、文字列大好き @hdbn です。「文字列アルゴリズム Advent Calendar 2016」 には間に合いませんでしたが、1月10日は「糸 (string) の日」ということで文字列 (string) アルゴリズムの記事を書くことにしました。この記事では文字列照合アルゴリズムの中で最も美しいアルゴリズムの１つである Crochemore-Perrin のアルゴリズムを紹介します。 アルゴリズムの正しさの証明はほぼ元の論文をなぞっていますが、説明を簡単にするために計算量に影響を与えない範囲でオリジナルのアルゴリズムから少し変更しています。計算量の概念など、アルゴリズムの基礎的な知識があれば読めるような内容にしているつもりですが、分かりにくいところなどあれば補足しますのでコメントください。 それでは文字列の周期性が織り成す不思議ワールドをご堪能ください。 概要 解く問題は以下の文字
文字列アルゴリズムの学びかた - Hatena Developer Blog
こんにちは！はてなアプリケーションエンジニアの id:takuya-a です。 みなさんは、このような疑問をもったことはありませんか？ grep はどのように文字列を検索しているのか？ MeCab はどうやって辞書を高速にルックアップしているのか？ パーサやコンパイラを作りたいけど、何から始めればいいのか？ 本稿では、「文字列アルゴリズムとはどんなものなのか？」「なぜ重要なのか？」「何を知っておくべきか？」「どうやって勉強すればいいのか？」といった疑問にお答えしていこうと思います。 文字列アルゴリズムの意外な応用や、モチベーションを保ちやすい勉強のしかた、文字列アルゴリズムを勉強するために行った社内での取り組み、実装するときのコツといったトピックについても触れています。 このエントリは、はてなエンジニアアドベントカレンダー2016の22日目の記事です。昨日は id:syou6162 さんに
sprint という Java の string formatter を書いた - その手の平は尻もつかめるさ
sprint という Java 向けの String formatter を書いた． Maven Central にも置いてある． http://search.maven.org/#search%7Cgav%7C1%7Cg%3A%22net.moznion%22%20AND%20a%3A%22sprint%22 sprint は Sprint#ff() というメソッドを提供している．使い方としては以下の様な感じ． final Sprint sprint = new Sprint(); System.out.Println(sprint.ff("Hello: {}!", "John")); // => Hello: John! 処理としては，template を parse して placeholder とそれ以外とを検出して，その検出した placeholder に変数を埋めつつ文字列を生
Python 3誕生の理由 ― つまり、なぜunicode/str/bytesの仕様は変更されたのか | POSTD
12月、私は PuPPy(the Puget Sound Python users group)の会合でQ&A セッション を行いました。そこでようやくPython 3が誕生した理由と、string/bytesに関する全てを説明しました。Python 3が作られた理由をユーザはもう知っているはずだと思っていたので、私はこの説明で称賛を得たことに、ちょっと驚きました。後で考えてみると、Pythonに詳しい人もそうでない人も含めて大多数の人が、その理由を探すように言われたり、好奇心からその理由を探し当てられるなどと考えた私が愚かでした。ですから、このブログの記事で、Python 3が存在する理由をわかりやすく説明します。後方互換性の全くない unicode / str / bytes の仕様変更は、Python 3のコードの移植の中でも本当に難解な部分ですので、私たちがその仕様変更を選択した理
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
【 Haskell 自作関数 】文字列関数（編）〜 文字列 が、パターン文字列 を 部分文字列 として含むか否か を、 boolean値（True | False） で 返す 関数 - Qiita
GitHub - moznion/sprint: Fluent, small and fast String formatter for Java
to_string is not a member of std, says g++ (mingw)
Apache HttpClient で Content-Body を String として得る - tokuhirom's blog
Text can be null · jenkinsci/acceptance-test-harness@7c33feb