Beautiful Branchless Binary Search
I read a blog post by Alex Muscar, “Beautiful Binary Search in D“. It describes a binary search called “Shar’s algorithm”. I’d never heard of it and it’s impossible to google, but looking at the algorithm I couldn’t help but think “this is branchless.” And who knew that there could be a branchless binary search? So I did the work to translate it into a algorithm for C++ iterators, no longer requir
はじめに - アルゴリズムとデータ構造大全
はじめに このドキュメントは，主に競技プログラミングで出題される問題を解く際に利用できるアルゴリズムやデータ構造をまとめたものです．特定の問題にはあまりフォーカスしないため，問題を解く際の考察の仕方等の内容はありません．詳しく，正確に，分かりやすく書いていこうと思っています． このドキュメントは執筆途中です． 想定する読者 C++を用いたプログラミングに慣れている方を読者として想定しており，C++言語の仕様や，文法にはあまり触れません．また，計算量という用語についても説明しません．ただし，償却計算量など，計算量の見積もりが複雑なものについては必要に応じて説明します． コードについて このドキュメントで登場するコードは，可読性向上のため，以下のようなコードがファイルの先頭に記述してあることを前提としています．また，適切な問題を用いてコードの検証がなされている場合は，コード周辺にのように，検証
2のべき乗サイズの配列は危ないという話 via 行列積 - elkurin’s blog
こんにちは。労働者です。とあるプログラムで学生さんの課題を添削していたら面白い話に出会いました。 僕は今、主に学部生向けのインターン研修的なプログラムでメンターなるものをやっています。メンターとしての仕事は、学生さんの課題へフィードバックを返し、Office Hourというセッションを毎週設けて質問受けやCSに関するトークを行うといった内容になっています。今回話題に取り上げるのはその中の課題の1つ、「行列積のプログラムを書いて時間を計測せよ」という何気ない話で、続く課題たちのいわば前座のようなものです。こういったところに沼は隠されているものですね。 担当している学生さんたちが細かい実験を行ってくれて以下のような疑問が提示されました。 「行列積の計算が N = 1024のときだけ N = 1023, 1025のときに比べて3倍遅いのはなぜ？」 配列のサイズが2のべき乗になるのは避けるべきとい
C++からRustに移行して1年経って思ったこと - Qiita
はじめに この記事は「プログラミング技術の変化で得られた知見・苦労話【PR】パソナテック Advent Calendar 2020」のために書かれたものです。 僕は去年の11月から一念発起してRustの勉強を初めて趣味で同人ゲームを開発しています。元々C++を4年程使っていて「C++最高、みんなC++使おう」とか友人に布教していました。しかし、C++プログラマは「一番自分たちの言語の批判に対して強くなる」と言われるほどC++はよくディスられます。もちろん僕も例外ではありませんでした（笑）。 一応僕もPythonを適当に使うようになってからC++のcppとhppを組み合わせるようなCの名残を感じるところや他言語と比べたときの標準ライブラリの貧弱さ、コードが冗長になりやすい点など使いにくいなあと思いはじめましていました。ですがPythonはあくまでも適当に使ってただけでしたし、一通り書けるJa
C++標準化委員会、ついに文字とは何かを理解する: char8_t - Qiita
C++ Advent Calendar 2018 この記事はC++ Advent Calendar 2018 15日目の記事です。 14日目: VTKライブラリ 16日目: C++のエラー処理との付き合い方 当初見積もりよりも大幅に長い記事となり、投稿したのは12/22で1週間遅刻です。すみません。 お知らせ cpprefjpにchar8_t型追加について解説を書きました。ぎゅぎゅっとコンパクトに、また査読を受けて中立的な表現で書いていますので、よければどうぞ。 UTF-8エンコーディングされた文字の型としてchar8_tを追加 - cpprefjp C++日本語リファレンス 追記 全ての開発者が知っておくべきUnicodeについての最低限の知識 - GIGAZINE Unicodeについて簡潔にまとまってるいい記事を見つけました。 Caution この文章には以下の要素が含まれます。苦手
江添亮のC++入門
序 本書はプログラミングの経験はあるがC++は知らない読者を対象にしたC++を学ぶための本である。本書はすでに学んだことのみを使って次の知識を説明する手法で書かれた。C++コンパイラーをC++で書く場合、C++コンパイラーのソースコードをコンパイルする最初のC++コンパイラーをどうするかというブートストラップ問題がある。本書はいわばC++における知識のブートストラップを目指した本だ。これにより読者は本を先頭から読んでいけば、まだ学んでいない概念が突如として無説明のまま使われて混乱することなく読み進むことができるだろう。 C++知識のブートストラップを意識した入門書の執筆はなかなかに難しかった。ある機能Xを教えたいが、そのためには機能Yを知っていなければならず、機能Yを理解するためには機能Zの理解が必要といった具合に、C++の機能の依存関係の解決をしなければならなかったからだ。著者自身も苦し
ISUCON6予選をC++で参加して予選通過した話
チーム名「Anago」で @iwiwi, @zuisou, @imos の 3 人で ISUCON6 予選に参加し，幸運にも 1 日目 3 位で通過することができました．@iwiwi が「ISUCON に C++ で参加したい！」と言っており，それを全力バックアップをしようと思ったのがきっかけの参加でした． 前日までにやったこと C++ で全てを書けば最速になるのは自明なのですが，C++ は参考実装として与えられていないだけではなく，HTTP サーバを書くことを想定していない言語のため準備には苦労しました． C++ で HTTP サーバを書く方法は，既存の Web サーバ (e.g., nginx, Apache, H2O) のプラグインを書いて実装するか，FastCGI として実装するか，フルスクラッチで書くかの選択肢が考えられますが，プロセス間通信を避けて爆速にしたかったので，事前に
GitHub - google/styleguide: Style guides for Google-originated open-source projects
Every major open-source project has its own style guide: a set of conventions (sometimes arbitrary) about how to write code for that project. It is much easier to understand a large codebase when all the code in it is in a consistent style. “Style” covers a lot of ground, from “use camelCase for variable names” to “never use global variables” to “never use exceptions.” This project (google/stylegu
Windows 10 のアクティブウィンドウを別の仮想デスクトップに飛ばすアプリを作ったよ - tmytのらくがき
Windows 10 でアクティブなウィンドウを別の仮想デスクトップに飛ばすアプリが完成したのでご報告します http://t.co/bOy8LoDFbU— ぐらばく (@Grabacr07) 2015, 9月 14 このアプリ、「作りかけたけど XXX が原因でダメだった」というブログを書いたら、それを見たつもりんが「できるんじゃね？」ってなってそのまま 2 人で共闘して完成したので情報発信大事ですね— ぐらばく (@Grabacr07) 2015, 9月 14 作ったよ、と言ってもほとんどは@Grabacr07 が作ったので僕がやったのはC++&Win32でいろいろするライブラリと、それをCLRに接続するラッパー周りを作っただけです。 なにしてるの このアプリ作る上で問題となったのが先のブログエントリでも言及されているとおり 他プロセスのウィンドウは、他の仮想デスクトップに移動させるこ
整数を可逆スクランブルする - C Sharpens you up
2年前につぶやいた内容の詳しい説明。 32ビット整数をとりあえずスクランブルするすごく簡単な方法に気付いてしまった。なにか奇数をかけると、それにかければ元の数に戻るような奇数が必ずひとつあるから、それを力任せで見つけてしまえばいいんだ。ビット回転→奇数をかけるを3回繰り返すとほぼバラバラ。— ゆば大好き (@yuba) October 18, 2011 整数を、暗号ライブラリ使うほどじゃないんだけどスクランブルしたいことってあるんですよね。たとえば、IDを連番で振ってるんだけど連番だってことがユーザーにわかってしまうと具合が悪いとか。そういうときの簡単なスクランブル方法です。ただし、符号なし整数でしか使えないのでこの時点でJavaは対象外ごめんなさい。 まず32ビット整数版のC,C++,C#で動くコードです。 uint Scramble(uint v) { // 奇数その1の乗算 v *=
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Kosaraju's Algorithm for Strongly Connected Components