パフォーマンスを向上させるためにビットの代わりに多項式を使用する方法？

Question

私は128ビットの文字列を持っています。私の監督は私にこれらの128ビットを多項式として表現するように頼んでいます。

彼のアイデアは、我々はこれらのビットから0を排除しているので、私たちはほとんどがある（次の操作を行うことができるようになり、あるXOR：これは、彼が上で書いていた紙のスキャンですビット/多項式の間で）すべてのビットを処理した場合よりもはるかに高速です。

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

あなたはパフォーマンスを向上させるためにこれを実装する方法を知っていますか？すべてのコード/スニペット/記事は非常に高く評価されています。

アプリケーションはJavaで記述されています。

おかげで、

モタ

更新：

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

Answer 1

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

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

Answer 2

Monomial彼が提案しているのはPolynomialになる - 複合パターンだと思う。 （加算、減算、乗算、除算）と必要と思われるその他のもの（例：差別化と統合）の両方について、通常の数学演算をすべて定義します。あなただけの二つの用語でそれをキャプチャすることができますので、

多項式は本当に、x^1000 + 1ような場合のために輝きます。

本当の質問は、あなたの上司はあなたが貯蓄していると思いますか？数ビットですか？速度？開発時間？私はziesemerに同意します - あなたはBitSetよりもはるかにうまくやることを強く求められます。あなたがアプリケーションをプロファイリングした場合に表示されないような、私にはマイクロ最適化のように思えます。

しかし、はです。議論の価値がありますか？

この詳細を抽象化して2つのプロファイルを作成できますか？

Answer 3

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

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

私はziesemerのソリューションに行きます。

Answer 4

私は、あなたが128ビット文字列にどんな利益をもたらすかは疑いありません。 128ビットは16バイトです。どんなオブジェクトでも少なくとも40を取るので、（ほとんど）サポートする構造は、保存するデータよりも高価になります。

まだ、ここには既存の方法のa good surveyと1つの斬新なものがあります。これはあなたにとって有益かもしれません。それがあなたの質問に対する答えであるかのようにではなく、ziesemerの解決策がそのような膨大な数字に最適であることに同意しますが、あなたの視野を広げたい場合は、見てください。