問題タブ [radix]

このアルゴリズムに時間をかけましたが、どこで何か間違っているのかまだわかりません。「Radix Sort」のロジックを手伝ってくれる人はいますか?次のコードを正しく使用している場合は、行:arr[sortedIndex] = tempArray[j][k];

基数ソートを使用して数値のリストをソートするプログラムに取り組んでいますが、無限ループであると思われるものにはまり続けています。それは私のメインのソート機能かカウント機能のどちらかだと思います。私が間違っていることについてのアイデアはありますか?

非常に簡単に動作する C コードを実行する組み込みシステムがあります。シリアル接続を介して文字を読み取り、受信した文字を 16 進数として解釈し、受信内容に応じて別の処理に進みます。ただし、受信した文字が 16 進数ではなく 10 進数であるという非常に特殊なケースが 1 つあります。このケースは非常にまれであるため (エラー ケースのエラー ケースのようなもの)、実際の文字受信を変更して、受信した値を 10 進または 16 進のどちらとして解釈するかを決定するのではなく、簡単なアルゴリズムを数値を 10 進数に変更する場合の処理​​。

これを行う最も速い方法は何だと思いますか? ソフトウェアは小さな MCU で実行されているため、不要な #include をこれ以上追加したくないため、C ライブラリ関数はオプションではありません。そのため、純粋に数学的なアルゴリズムを探しています。

明確にするために、0x45 -> 12 月 69 のように基本的な 16 進数から 10 進数への変換を行う最も簡単な方法を尋ねているわけではありませんが、私がしたいのは、たとえば変換することです。0x120 を 10 進数の 120 に変換します。

前もって感謝します！

EDIT：申し訳ありませんが、より詳細に説明しようとします。実際のコードは長すぎるので、ここに貼り付ける必要はないと思います。したがって、次のようになります。

最初に、シリアル ラインから受信した番号を読み取ります。たとえば、「25」としましょう。次に、それを 16 進数に変換すると、読み取り値を持つ変数ができます。たとえば、X = 0x25 とします。これはすでに正常に機能しており、これを変更したくありません。この非常に特殊なケースで私が今やりたいことは、X == 0x25 の代わりに X==25 になるように変数の解釈を変更することです。16 進数の 0x25 は 10 進数の 25 に変わります。プロセッサ固有の命令やライブラリ関数を必要とせずに、このような変更を行うにはある種の数式が必要ですか?

基数ソートを理解するのに苦労しています。基数 2 または基数 10 で動作するコードの実装に問題はありません。ただし、基数を指定するコマンド ライン引数が必要な割り当てがあります。基数は 2 ～ 100,000 の範囲です。この問題を理解するのに約 10 時間費やしました。これは宿題なので、直接の回答は求めていません。ただし、誰かがこれに光を当てることができる場合は、してください。

わからないことがいくつか。ベースが 100,000 であることのポイントは何ですか? それはどのように機能しますか。アルファベットのすべての文字、または 1 ～ 9 のすべての数字にベースがあることを理解しています。私はこの概念に頭を包むことができないようです。

十分に具体的でなかったら申し訳ありません。

このトピックに関するいくつかの情報源を読みました。ただし、これらの式が何を意味するのかを正確に理解するのに苦労しています。b = n の場合、Radix Sort は Linear のようです。これは、ベースを配列の長さに設定する必要があるということですか?

0 から 10 億の範囲の 1 億個の整数の配列がある場合、基数 1 億を選択する必要がありますか?

これが正しくない場合は、私のためにそれを馬鹿にしてみてください。私が見つけることができる基数ソートのほとんどの例は、基数が 10 または基数 2 しかないため、それぞれ 10 または 2 より大きい配列では遅いか、単に取得できません。

助けてくれてありがとう。

IPv6 のホワイトリスト / ブロックリストを作成する必要があります。

IPv6 でホストごとまたはネットワークごとに情報を維持するために、どのようなメモリ内オプションがありますか?

私は現在HashTable<UInt32>、IPv4 に を使用していますが、サブネット トラッキングや CIDR などを実際にマスターしたことはありません。

そうは言っても..そのようなブロックリスト/ホワイトリストを作成するための最も効率的な方法（検索速度、またはメモリ内のコンパクトさ）は何ですか?

TL;DR 質問

• UInt128a が list/btree/hashtable にあるかどうかを調べるにはどうすればよいですか? これに適したデータ構造はどれですか?

• 互いに「近い」IP を見つける方法を教えてください。これは通常 CIDR と呼ばれますが、BigInt の値比較として表現することもできます。

ちょうど私の頭に浮かんだ 1 つのアプローチは、暗号アキュムレータがどのように機能するかです。おそらく、アキュムレータの「メンバーシップ」機能を活用して、数値がセットのメンバーであるかどうかを判断する必要があるかもしれません

引用符で囲まれたテキストは、私の問題を理解するために必要な場合に備えて、プログラムの背景を少し示しています。読みたくない場合は、最後に引用されていないもので完全に理解できるかもしれません。

私は C++ でのソートの共通プロジェクトに取り組んでおり、現在基数ソートを行っています。私はそれを関数として持っており、文字列のベクトル、最大桁数を保持する整数、および数値の基数/基数を持つ整数: (numbers, maxDigits, radix)

プログラムは基数が異なる数値を文字列として受け取るため、stoi を使用してそれらを基数 10 の整数に変換し、プロセスを一般化しやすくしています。アルゴリズムの簡単な要約は次のとおりです。

• 値 0 から 9 を保持する 10 個のキューを作成します
• 各桁を反復します (maxDigit 回)
  
  • ベクトル内の各数値を反復処理します (ここでは基数 10 に変換されます)
  • 見ている現在の数字に基づいてそれらをキューに入れます
  • キューから番号を最初から最後まで引き出してベクトルに戻します

私が頭を抱えようとしている問題については、maxDigit 値 (ユーザーが入力した基数に関係なく) を base 10 に変換した後に maxDigit 値に変更したいと考えています。つまり、ユーザーが使用したとしますコード

最大桁数8と基数2の数値のベクトルをソートします。数値の基数を10に変換するので、それが理にかなっていれば、maxDigitsも変更するアルゴリズムを見つけようとしています。

試行錯誤しながら簡単な方法を見つけようとして、これについてたくさん考えてみました。ヒントや正しい方向への助けを得ることができれば、それは大きな助けになるでしょう.

トライ木の高さを求めるアルゴリズムを書くのに苦労しています。どうやって始めればいいのか、どうすればできるのかわかりません。これが「初心者」の質問である場合は申し訳ありませんが、私は試行にかなり慣れていないため、これが私の割り当てに欠けている唯一の部分です。

とにかく、トライツリーの構造は次のとおりです。

基本的に、「a」が 1 つの子の場合、chidren[0] に Trie があり、「b」が子でない場合、children[1] は NULL になります。ご覧のとおり、文字はリンク インデックスによって暗黙的に定義されており、過去のノードの文字が現在のノードまでの単語を形成する場合、'Boolean IsItAWord' は true になります。

これで私に光を与えてもらえますか？私が知っている唯一のことは、高さは最長の単語の長さ + 1 で定義できるということです。しかし、それを行う方法がわかりません。私は本当に解決策が欲しいので、このトライの高さを見つける方法は大歓迎です。

ありがとうございました。