タグ

関連タグで絞り込む (26)

タグの絞り込みを解除

algorithmに関するcaffephiliaのブックマーク (5)

  • [速習] 配列から欠けている数字を見つける「XORトリック」の深い理論と実践 - Qiita

    皆さんは『配列から欠けている数字を見つけろ』と言われたら、どう答えますか？ 多くの方は「HashSetで解けばいい」と考えるでしょう。しかし、1000万個の要素で実測したところ、Pythonのsetは945MBもの追加メモリを消費し、処理に2.3秒かかりました。一方、XORを使った解法は追加メモリゼロ、C言語なら1ミリ秒で完了します。 なぜこれほどの差が生まれるのか？ XORには単なるトリック以上の深い理論があり、配列の欠損値検出だけでなく、RAID 5のデータ復元やネットワークのエラー検出など、実務で幅広く応用されているのです。 追記: ネットワーク転送時のパケットロスやノイズによるデータ欠損、さらには宇宙線がメモリに衝突してビットが反転する「ソフトエラー」により、配列から要素が失われることがあります。 本記事では、Florian Hartmannの「That XOR Trick」1を基

    [速習] 配列から欠けている数字を見つける「XORトリック」の深い理論と実践 - Qiita
    caffephilia
    caffephilia 2025/07/07
    「まず『配列から欠けている数字を見つけろ』とはどういう意味ですか？」って聞く。いやマジで「配列から欠けている数字を見つける」って何？配列中の最小値と最大値の間の欠けている数字を見つける？（読んでない）
    リンク

  • MySQL(InnoDB)のSQLパフォーマンスチューニングのエッセンス

    はじめに MySQL(InnoDB)でSQLのパフォーマンスチューニングをするときに役に立つ知識をエッセンスとしてまとめました。結合(JOIN)やB-treeインデックスの探索の仕組み、実行計画の基本的な見方を紹介します。 想定する読者は、SQLのパフォーマンスを改善する必要があるが実行計画をみてもいまいちピンと来ない方です。インデックスの作成の経験や、複合インデックスやカーディナリティの知識があることを前提にしています。目標は、実行計画の内容がよく分からない読者が、実行計画をみただけでクエリが実行される様子をイメージでき、自信を持ってクエリの改善にあたることができるようにすることです。 ストレージエンジンはInnoDBを前提としています。また、インデックスはB-treeインデックスを想定しています。全文検索の転置インデックスや空間検索のR-treeインデックスについては触れません。 イン

    MySQL(InnoDB)のSQLパフォーマンスチューニングのエッセンス

  • MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond

    MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ 端的に言うと性能が良いからです。 これを理解するにはバッファプールへの理解が必要です。ディスク指向のデータベースの上では有限のメモリを最大限活用することでメモリに入り切らない巨大なデータ群に対して良好な参照性能を出す必要があります。バッファプールとはディスク上のデータの羅列を固定サイズのページ（InnoDBの場合16KB）の羅列であるとして読み書きに必要な分だけをメモリに移し取り複数の書き込みをできる限りメモリ内で受け止めて後でまとめてディスクに書き戻すという、ライトバック型のキャッシュのような機構です。 この中においてバッファプールは有限のサイズしか無いので適宜プール内のデータを書き戻して入れ替えながら上手くやっていく必要があります。 さてB+treeとB-treeの最大の違いは木のリ

    MySQLのインデックスですが、B-treeではなくB+treeを使用するのはどうしてなのでしょうか？ | mond

  • [追記]プログラマーにコンピュータ・サイエンスは必要なんだろうか

    この疑問はもう俺の中で何十年もくすぶっているんだが、未だにその答えは見つかっていない。 そもそも俺はコンピュータサイエンスというものをよくわかっていないというのもあるんだが、プログラマーをやっていてコンピュータ・サイエンスの素養がなくて困ったことがない。 学生が言うところのコンピュータ・サイエンスが社会に出て何の役に立つんだよっていう話がしたいんじゃない。 ここに吐き出しつつ自分なりに問題を噛み砕いてみたい。 フラフラ思いつくままに書いているから頭悪い文章になることだけは先に宣言しておく。 仕事をしているうえでなんで困らないのかまずコレが最も重要なポイントだと思うんだが、仕事でプログラム書いていて、コンピュータ・サイエンスの素養がなくて困ったことがない、例えばコンピュータ・サイエンスのボキャブラリがないと会話すらままならないなんて言うことは起きたことがない。 更に言うならば要件定義をコード

    [追記]プログラマーにコンピュータ・サイエンスは必要なんだろうか
    caffephilia
    caffephilia 2022/11/30
    「CSやれ」と言われた事ないが「情報の関わる緒問題に対し（実験と観測を軸とする）科学的態度で臨める様になろう」的な意味か？（計算量やらDBスキーマの正規化とかはセンスでよろしくやっちゃうのがかなりいるし）
    リンク

  • テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum

    テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を

    テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
  • 1

お知らせ

もっと読む

公式Twitter

  • @HatenaBookmark

    リリース、障害情報などのサービスのお知らせ

  • @hatebu

    最新の人気エントリーの配信

はてなブックマーク

公式Twitter

はてなのサービス

  • App Storeからダウンロード
  • Google Playで手に入れよう
Copyright © 2005-2025 Hatena. All Rights Reserved.