raxLowWalk , divide and conquer instead of linear scan

オープン
#24 コメント 1 件 リアクション 0 件 担当者 0 名 GitHub で見る

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

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
25/100
issue の種類
リファクタリング
明瞭さ
説明が足りない
活発さ
停滞
技術スタック
c
領域
performance

調査の方向性

まず、raxLowWalk と、v および s に対して示されている線形スキャンを見つけます。提案されている divide-and-conquer lookup を既存の動作と比較し、大きな h-size 値でパフォーマンスが向上するか測定します。検索の正しさを維持しながら、意味のある改善を実証できれば完了です。

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

説明

what about something like:
int bleh = h->size;
do{
bleh/=2;
if (v[j] < s[i])
{
j+=bleh;
}
else if (v[j] > s[i])
{
j-=bleh;
}
else
{
//got hit
}
}while (bleh>1);

divide and conquer scanning instead of linear?

        /* Even when h->size is large, linear scan provides good
         * performances compared to other approaches that are in theory
         * more sounding, like performing a binary search. */
        for (j = 0; j < h->size; j++) {
            if (v[j] == s[i]) break;
        }
主要言語
C
スター
1.3k
フォーク
175
PR マージ指標
30日以内にマージされた PR はありません

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

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

antirez/rax のほかの issue

antirez/rax の issue をすべて見る

似ている issue

C の issue をもっと見る

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

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