如何使用多项式代替比特来提高性能？
我有一个 128 位字符串，我的主管要求我将这 128 位表示为多项式。这是他所写论文的扫描：
他的想法是，因为我们正在消除如果从这些位中删除 0，我们将能够比处理所有位更快地执行接下来的操作（其中大部分是位/多项式之间的异或）。
我了解要求是什么，我可以在纸上完成，也可以在申请中完成。但我的方式并不能达到他提高性能的目的。他实际上说已经有图书馆可以做到这一点，但不幸的是我找不到任何图书馆。我发现的唯一的东西是一个计算多项式的 Polynomial 类，这不是我想要的。
那么你们知道我该如何实现这个来提高性能吗？非常感谢任何代码/片段/文章。
如果这有什么区别的话，应用程序是用 Java 编写的。
谢谢，
Mota
更新：
我的主管说这个 C 库 就可以了任务。但我无法弄清楚它是如何工作的以及它将如何做到这一点。
I have a 128-bit string, and my supervisor has asked me to represent those 128 bits as a polynomial. This is a scan of the paper he was writing on:
His idea is, since we are eliminating the 0s from these bits, we will be able to perform the next operations (most of which are XOR between the bits/polynomials) much faster than if we worked on all bits.
I understand what the requirement is, and I can do it on paper, and also in the application. But my way will not achieve his goal, which is improving the performance. He actually said that there are libraries already that do this, but unfortunately I couldn't find any. The only thing I found was a Polynomial class that evaluates polynomials, which is not what I want.
So do you guys know how can I implement this to improve the performance? Any code/snippets/articles is very much appreciated.
The application is written in Java, if that makes any difference.
Thanks,
Mota
Update:
My supervisor says that this C library will do the task. I couldn't though figure out how it works and how it will do this.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您的主管是否熟悉
BitSet？ 128 位是 16 个字节，可以存储为 2 个long。但是，使用 BitSet，您无需担心处理 2 个long的组合。 BitSet 还提供了所有常见位操作的方法。我认为您很难找到比这更好的解决方案。多项式方法是一个非常酷的想法，但我认为它的理论意义大于实践意义。
Is your supervisor familiar with a
BitSet? 128 bits is 16 bytes, which could be stored as 2longs. However, using a BitSet, you won't need to worry about dealing with the combination of 2longs. BitSet also provides methods for all the common bit operations. I think you'd be pretty hard-pressed to find a better solution than this.The polynomial approach is a pretty cool idea, but I think it's more theoretical than practical.
他提出的是一个
单项式，您可以将其组合成多项式- 想想复合模式。定义所有常用的数学运算（加法、减法、乘法、除法）以及您认为可能需要的任何其他数学运算（例如微分和积分）。对于像
x^1000 + 1这样的情况，多项式确实会大放异彩，因为您只需两项即可捕获它。真正的问题是：你的老板认为你在节省什么？几位？速度？开发时间？我同意 ziesemer 的观点 - 你很难做得比
BitSet更好。对我来说，他/她所考虑的节省似乎是一种微观优化，如果您分析您的应用程序，这种事情就不会出现。但他/她是老板……值得争论吗？
也许您可以抽象出这个细节并分析两者。
What he's proposing is a
Monomialthat you can compose intoPolynomial- think Composite pattern. Define all the usual math operations for both (addition, subtraction, multiplication, division) and any others you think you might need (e.g. differentiation and integration).Polynomial will really shine for cases like
x^1000 + 1, because you can capture it with just two terms.The real question is: What does your boss imagine you're saving? A few bits? Speed? Development time? I agree with ziesemer - you'll be hard pressed to do much better than a
BitSet. The savings s/he's thinking of seems like a micro-optimization to me, the kind of thing that wouldn't show up if you profiled your application.But s/he is the boss...is it worth the argument?
Maybe you can abstract this detail away and profile the two.
如果您有多个需要 XOR 的字符串，它实际上会导致性能开销。这是因为您需要匹配权重。
这完全取决于您要与什么进行异或，以及您需要执行多少次才能计算出采用这种方法的优势。
我会选择齐泽默的解决方案。
If you have multiple strings that need XOR ing it will actually cause performance overhead. This is because you need to match the weights.
It all depends on what you are XOR ing it with and how many times you have to do this to calculate the advantage to take this approach.
I would go with ziesemer's solution.
我非常怀疑您能否从 128 位字符串中获得任何好处。 128位为16字节；任何对象都至少需要 40，因此（几乎）任何支撑结构都会比它存储的数据更昂贵。
尽管如此，这里还是对现有方法的一项很好的调查，而且是一种新颖的方法，这可能（或可能没有）对您有利。并不是说这就是你问题的答案，并同意齐泽默的解决方案对于如此庞大的数字来说是最好的，但如果你想拓宽你的视野，请看一下。
I doubt very much you are going to get any benefit on 128-bit strings. 128 bits are 16 bytes; any object will take at least 40, so (almost) any supporting structure will be more expensive than the data it stores.
Still, here's a good survey of existing methods—and one novel one, which may (or may not) be beneficial for you. Not as if it was an answer to your question, and agree that but ziesemer's solution is the best for such a huge numbers, but if you want to broad your horizons, take a look.