問題タブ [lookup-tables]

システムでサイン/コサイン値を計算するルックアップ テーブルを実装しました。逆三角関数 (arcsin/arccos) が必要になりました。

私のアプリケーションは、プログラム メモリが限られているため、arcsin の 2 番目のルックアップ テーブルを追加できない組み込みデバイスで実行されています。したがって、私が考えていた解決策は、サイン ルックアップ テーブルを参照して、対応するインデックスを取得することでした。

このソリューションは、数学標準ライブラリからの標準実装を使用するよりも効率的かどうか疑問に思っています。
誰かがすでにこれを実験しましたか？

LUT の現在の実装は、0 から PI/2 までの正弦値の配列です。テーブルに格納された値は 4096 で乗算され、アプリケーションに十分な精度を持つ整数値のままになります。1/4096 の解像度のルックアップ テーブルで、6434 個の値の配列が得られます。次に、引数として4096を掛けたラジアンの角度をとる2つの関数正弦と余弦があります。これらの関数は、指定された角度を第 1 象限の対応する角度に変換し、表の対応する値を読み取ります。

私のアプリケーションは dsPIC33F で 40 MIPS で動作し、C30 コンパイル スイートを使用しています。

次のように宣言された構造体があるとします。

今、私がやりたいのは、これを別の構造体の中から呼び出すことですが、その方法を手がかりにする必要があります。私がやろうとしていることは（私の心の中で）次のようになります：

私の最終目標は、オブジェクトのインスタンスを作成せずに、次のようなコードを使用することです。

したがって、この「ルックアップテーブル」は別のプロジェクトで作成されてビルドされ、メインプロジェクトからdllとして呼び出されます。他の場所でdllをビルドして呼び出しているので、dllを一度メモリにロードして、メインプロジェクトからそのメモリを参照できるようにしたいと思っています。次に、メモリの割り当てられた部分が1つあり、コードはそれを参照するだけで、このルックアップテーブルの個々のインスタンスを作成する必要がなくなります（したがって、メモリの割り当てと新しいインスタンスの保存にかかる時間のオーバーヘッドが回避されます）。私が節約した時間は長期的には非常に有益であるため、これを何らかの形で機能させることができると期待しています。

これがあまり混乱しないことを願っていますが、説明が必要な場合はお知らせください。

編集 これはWebサイトで使用されているため、実際には、すべての接続にわたって存続し、コードが最初にロードされたときに1回作成されるオブジェクトが必要です。同じ考えですが、おそらくそれはより簡単な解決策になりますか？

私のデータベースでは、多くのテーブルに「状態」フィールドがあり、特定のエンティティが陥る状態を表しています。この種のものにはルックアップ テーブルを使用するように言われましたが、正確なメカニズムはわかりません。誰かがこれらの点を明確にすることができますか?

1. 整合性はどのように維持されますか? (つまり、状態テーブルの値のみが他のテーブルに移動するようにするにはどうすればよいですか?)

2. 州名は他のテーブルに入りますか、それとも州テーブルの州 ID は他のテーブルに入りますか?

Access でルックアップ テーブルを作成する必要があります。すべての略語は値に関連付けられており、(メイン テーブルの) 略語が null の場合は、"不明" と表示したいと考えています。

値が機能するようになりましたが、ヌルが表示されないようです。

私のルックアップテーブルは次のようになります。

しかし、要求によってカウントを行うと、A と D の値のみが表示されますが、そこにもいくつかの空白があることはわかっています。

私は何を間違っていますか？

学生のAccessテーブルにルックアップフィールド（寮）があります。MailMergeでそのテーブルを使用すると、Wordでは、ルックアップフィールドが寮ではなく数字として表示されます。MailMergeで関係が失われたかのようです。ルックアップテーブルを使用してMailMergeを実装できるかどうか、そして可能であればどのように実装できるかを誰かが知っていますか？

GetName()質問の最後の例を考えると、関数が呼び出されるたびにマップ オブジェクトが作成されますか?
それとも、作成が最適化されてルックアップ テーブルとして作成されるのでしょうか?

一連のデータ (場所の名前のみ) がありますが、25k 以上あります。このデータを検索し、ユーザー入力に基づいてこのデータから値を返す方法があるかどうか (常にあります) と尋ねられました。

現在、私のスキルは XHTML と CSS にあり、JSP と JQuery にも手を出すことができますが、これに対する最善のアプローチはわかりません。私たちは：

1. アクセス データベースにデータを格納し、ユーザー入力に基づいて値を選択するクエリを作成しますか? この出力は、Web ページに表示する必要があります。しかし、これはどの言語で行う必要がありますか?

2. 優れていると思う JQuery 'Quicksearch' プラグインを見つけました ( http://lomalogue.com/jquery/quicksearch/super_table.html )

JQueryで行われているので、2）のアイデアが好きですが、特にページが巨大になるので、このサイズのデータ​​には適していないと思います（一部のデータは隠されている可能性がありますが）. もっと簡単なアプローチはありますか？何か不足していますか？

これが漠然としていると見なされる可能性があることを理解してください。申し訳ありませんが、最善のアプローチが何であるかはわかりません。

ありがとう

ルックアップ日付の選択 (実際の値、またはルックアップ インデックス) を格納するための最良の方法は何ですか? 私の場合、iPhone アプリケーションの CoreData です。オプションは次のようです。

1) 実際の値 (整数や浮動小数など) を格納します。ただし、ユーザーが値のルックアップ リストから現在の値を変更しようとすると、コードはこれが最初のものであるかを判断する必要があります。ルックアップ値の現在のリスト内の値。

2) ルックアップ インデックスを保存します。ただし、ルックアップ リストの値の範囲を変更したい場合は、不一致エラーが発生する可能性があります。

別のオプションを逃した場合の最善のアプローチ、または別のアプローチに関する提案はありますか?

PS たとえば、ルックアップが「3.1、3.2、および 3.3 kg から重量を選択するためのものであった場合、これが選択された重量である場合、オプション (1) 3.1 を格納できますが、オプション (2) の場合は 0 を格納するだけです (つまり、インデックス) を使用して、ユーザーが希望する最初の選択であることを示します。

ほとんど非正規化された既存のテーブルがあります。リストのステータス、タイプ、国などのルックアップ テーブルはありません。この元の設計は、データベースへのアプリケーションのアクセスを簡素化するためだけに行われたため、この非正規化にはパフォーマンス上の理由はありませんでした。

これにより、大量の重複データを含むテーブルが作成されました。さまざまなステータス/タイプ/国列のルックアップ テーブルを導入して、適切に正規化したいと考えています。

クライアントに対して透過的なままであるデータベース (oracle) でこれを行うことができるものはありますか? アプリケーションは引き続き挿入を行いますが、データベースはバックグラウンドで物事を適切なルックアップ テーブルにマップします。

私は、マッピングを行うビューとトリガーの組み合わせを実験してきましたが、これを行うためのより自動的な方法があるべきだと感じています。

指定された文字列キーの整数を返す必要がある、次のシグネチャを持つ検索関数を考えてみましょう。

さらに、キーと値のマッピング (番号 N) は、関数のソース コードが記述されているときに事前にわかっていることを考慮してください。たとえば、次のようになります。

したがって、上記の入力に対する関数の有効な (ただし完全ではない!) 実装は次のようになります。

また、特定のキーごとに関数が実行時に呼び出される正確な回数 (C>=1) も事前にわかっています。例えば：

ただし、そのような呼び出しの順序は不明です。たとえば、上記は実行時に次の一連の呼び出しを記述することができます。

呼び出し回数が一致する場合、またはその他のシーケンス。

制限 M もあり、最も便利な単位で指定され、 で使用できるルックアップ テーブルやその他のヘルパー構造体のメモリ上限を定義しますGetValue(構造体は事前に初期化されます。その初期化は複雑さに対してカウントされません)。関数の）。たとえば、M=100 文字、または M=256 sizeof(オブジェクト参照) です。

GetValue問題は、可能な限り高速になるように の本体を記述する方法です。つまり、すべてのGetValue呼び出しの合計時間 (上記のすべての合計数を知っていることに注意してください) は、与えられた N、C に対して最小です。そしてM？

アルゴリズムは、M の妥当な最小値を必要とする場合があります (例: M >= ) char.MaxValue。また、M を何らかの合理的な境界に揃えることも必要になる場合があります。たとえば、2 のべき乗のみである場合などです。また、M が特定の種類の N の関数でなければならないことも必要になる場合があります (たとえば、有効な M=N、または M=2N、...; または有効な M=N、または M=N^2、 ...;など)。

アルゴリズムは、適切な言語またはその他の形式で表現できます。生成されたコードのランタイム パフォーマンスの制約については、生成されたコードGetValueが C#、VB、または Java であると仮定します (実際には、文字列が文字の不変配列として扱われる限り、つまり O(1) の長さと O (1) 索引付け、事前に計算されたその他のデータなし)。また、これを少し単純化するために、すべてのキーに対して C=1 であると仮定する回答は有効と見なされますが、より一般的なケースをカバーする回答が優先されます。

可能なアプローチについてのいくつかの熟考

上記に対する明白な最初の答えは、完全なハッシュを使用することですが、完全なハッシュを見つけるための一般的なアプローチは不完全なようです。たとえば、上記のサンプル データに対して Pearson ハッシュを使用して最小限の完全ハッシュのテーブルを簡単に生成できますが、その場合、 を呼び出すたびに入力キーをGetValueハッシュする必要があり、Pearson ハッシュは必然的に入力文字列全体をスキャンします。しかし、すべてのサンプル キーは実際には 3 番目の文字が異なるため、文字列全体ではなく、3 番目の文字のみをハッシュの入力として使用できます。さらに、M が少なくともchar.MaxValueである必要がある場合、3 番目の文字自体が完全なハッシュになります。

別のキーのセットでは、これはもはや当てはまらないかもしれませんが、正確な答えを得る前に考慮される文字の量を減らすことはまだ可能かもしれません. さらに、最小限の完全なハッシュが文字列全体を検査する必要がある場合は、ハッシュを非最小限にすることで、ルックアップをサブセットに減らすか、そうでなければ高速化することができます (たとえば、より複雑でないハッシュ関数?)。 (つまり、M > N) - 速度のためにスペースを効果的に犠牲にします。

また、従来のハッシュは最初からあまり良い考えではない可能性もありますGetValue。一連の条件として本体を構造化する方が簡単であり、最初に「最も可変性のある」文字 (全体的に変化する文字) をチェックするように配置されます。ほとんどのキー)、正しい答えを決定するために、必要に応じてさらにネストされたチェックを行います。ここでの「分散」は、各キーが検索される回数の影響を受ける可能性があることに注意してください (C)。さらに、ブランチの最良の構造がどのようなものであるべきかは、常に容易に明らかであるとは限りません。たとえば、「最も変化しやすい」文字では、100 個のキーのうち 10 個のキーしか区別できず、残りの 90 個のキーについては 1 回の追加チェックが必要になる場合があります。それらを区別する必要はありません。「最も変化しやすい」キャラクターから始めないでください。目標は、チェックの完全な順序を決定することです。