Hacktoberfest 2026：メンテナが10月に向けて印を付けた、オープンで初心者向けの issue。 Hacktoberfest の issue を見る

boost::histogram::axis::variant, allow users to choose between sorted_array+std::lower_bound and eytzinger_layout+eytzinger_binary_search

オープン
  • 何か問題がありますか？
#369 コメント 14 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

  • #372 @HDembinski による — マージされずにクローズ

評価

難易度
5/5
見積もり時間
1週間以上
初心者へのやさしさ
30/100
issue の種類
機能追加
明瞭さ
おおむね明確
活発さ
停滞
技術スタック
cpp
領域
performance

調査の方向性

まず boost::histogram::axis::variant と issue で参照されているテストを見つけ、現在どのように std::upper_bound を使用しているかを確認します。提案されている 2 つの検索レイアウトを比較し、ユーザーがどのようにそれらを選択するのかを判断します。既存の動作を変更せずに選択肢が公開され、関連するテストまたはベンチマークで両方のオプションがカバーされれば完了です。

索引モデルが issue の本文から書いたものです。

説明

According to the test,

(boost::histogram::axis::variant is currently using std::upper_bound.)

comparison (x86-64 gcc (trunk), -std=c++23 -O3 -Wall -pedantic -pthread):

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

constexpr size_t n = (1<<20);
constexpr size_t block_size = 64 / sizeof(int); // = 64 / 4 = cache_line_size / sizeof(int)
alignas(64) int a[n], b[n+1];

constexpr size_t query_count=(1<<20);
int targets[query_count];
int results_eytzinger[query_count];
int results_lower_bound[query_count];

int eytzinger(int i = 0, size_t k = 1) {
    if (k <= n) {
        i = eytzinger(i, 2 * k);
        b[k] = a[i++];
        i = eytzinger(i, 2 * k + 1);
    }
    return i;
}

int search(int x) {
    size_t k = 1;
    while (k <= n) {
        __builtin_prefetch(b + k * block_size);
        k = 2 * k + (b[k] < x);
    }
    k >>= __builtin_ffs(~k);
    return k;
}

int main()
{
    std::random_device rd;  //Will be used to obtain a seed for the random number engine
    std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
    std::uniform_int_distribution<> distrib(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
    for (size_t i = 0; i != n; ++i)
    {
        a[i]=std::round(distrib(gen));
    }
    std::sort(std::begin(a),std::end(a));

    eytzinger();

    for (size_t i = 0; i != query_count; ++i)
    {
        targets[i]=std::round(distrib(gen));
    }

    {
        auto start = std::chrono::steady_clock::now();
        for (size_t i = 0; i != query_count; ++i)
        {
            results_eytzinger[i]=search(targets[i]);
        }
        auto end = std::chrono::steady_clock::now();
        std::chrono::duration<double> elapsed_seconds = end-start;
        std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
    }
    {
        auto start = std::chrono::steady_clock::now();
        for (size_t i = 0; i != query_count; ++i)
        {
            results_lower_bound[i]=std::lower_bound(std::begin(a),std::end(a),targets[i])-std::begin(a);
        }
        auto end = std::chrono::steady_clock::now();
        std::chrono::duration<double> elapsed_seconds = end-start;
        std::cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
    }
    for (size_t i = 0; i != query_count; ++i)
    {
        assert(a[results_lower_bound[i]]==b[results_eytzinger[i]]);   
    }
}

image

主要言語
C++
スター
334
フォーク
76
30日以内にマージされた PR はありません

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

boostorg/histogram のほかの issue

boostorg/histogram の issue をすべて見る

似ている issue

C++ の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。