6

私は128ビットの文字列を持っていますが、上司から、それらの128ビットを多項式として表すように求められました。これは彼が書いていた紙のスキャンです：

ビットを多項式に変換する

彼の考えは、これらのビットから0を削除しているため、すべてのビットで作業する場合よりもはるかに高速に次の操作（ほとんどはビット/多項式間のXOR）を実行できるようになるというものです。

私は要件が何であるかを理解しており、紙やアプリケーションでもそれを行うことができます。しかし、私のやり方では、パフォーマンスを向上させるという彼の目標は達成されません。彼は実際にこれを行う図書館がすでにあると言ったが、残念ながら私はそれを見つけることができなかった。私が見つけた唯一のものは、多項式を評価する多項式クラスでしたが、これは私が望んでいるものではありません。

では、パフォーマンスを向上させるためにこれをどのように実装できるか知っていますか？コード/スニペット/記事は大歓迎です。

違いがあれば、アプリケーションはJavaで書かれています。

ありがとう、

モタ

アップデート：

私の上司は、このCライブラリがそのタスクを実行すると言っています。それがどのように機能し、どのようにこれを行うのか理解できませんでした。

4

4 に答える 4

7

上司はに精通していBitSetますか？128ビットは16バイトであり、2として格納できますlongs。ただし、BitSetを使用すると、2の組み合わせを処理することを心配する必要はありませんlongs。BitSetは、すべての一般的なビット演算のメソッドも提供します。これよりも良い解決策を見つけるのはかなり難しいと思います。

多項式アプローチはかなりクールなアイデアですが、実用的というよりは理論的だと思います。

于 2011-12-17T20:40:45.167 に答える
6

彼が提案しているのは、Monomialあなたが構成できるものですPolynomial-複合パターンを考えてください。両方（加算、減算、乗算、除算）と、必要と思われるその他の演算（微分や積分など）の両方について、通常のすべての数学演算を定義します。

多項式はx^1000 + 1、2つの項でキャプチャできるため、のような場合に非常に役立ちます。

本当の質問は、あなたの上司はあなたが節約していると何を想像していますか？数ビット？スピード？開発時間？私はziesemerに同意します-あなたはよりもはるかにうまくやるのは難しいでしょうBitSet。彼が考えている節約は、私にはマイクロ最適化のように思えます。これは、アプリケーションのプロファイルを作成した場合には表示されないようなものです。

しかし、彼/彼は上司です...それは議論の価値がありますか？

たぶん、あなたはこの詳細を抽象化して、2つをプロファイリングすることができます。

于 2011-12-17T20:47:28.087 に答える
1

XOR が必要な文字列が複数ある場合、実際にはパフォーマンスのオーバーヘッドが発生します。これは、重みを一致させる必要があるためです。

それはすべて、何と XOR するか、およびこのアプローチを取る利点を計算するためにこれを何回行う必要があるかによって異なります。

私はziesemerのソリューションを使用します。

于 2011-12-17T21:12:02.700 に答える
1

128 ビット文字列で何らかのメリットが得られるとは思えません。128 ビットは 16 バイトです。どのオブジェクトも少なくとも 40 を必要とするため、(ほとんど) サポートする構造は、格納するデータよりも高価になります。

それでも、これは既存の方法に関する優れた調査と、有益な場合もあれば有益でない場合もある新しい方法の 1 つです。それがあなたの質問への答えであるかのようではありませんが、ziesemer のソリューションがそのような膨大な数に最適であることに同意しますが、視野を広げたい場合は、見てください。

于 2011-12-17T22:01:28.623 に答える