Как использовать полиномы вместо битов для улучшения производительности?

Question

У меня есть 128-битная строка, и мой супервизор попросил меня представить эти 128-битные как полином. Это отсканированная бумага, на которой он писал:

Его идея заключается в том, что, поскольку мы исключаем 0 из этих битов, мы сможем выполнять следующие операции (большинство из которых XOR между битами / полиномами) намного быстрее, чем если бы мы работали со всеми битами.

Я понимаю, что требование, и я могу сделать это на бумаге, а также в приложении. Но мой путь не достигнет его цели, которая заключается в улучшении производительности. Он фактически сказал, что уже есть библиотеки, которые делают это, но, к сожалению, я не смог найти ни одной. Единственной вещью, которую я нашел, был класс Polynomial, который оценивает полиномы, а это не то, что я хочу.

Так вы, ребята, знаете, как я могу реализовать это для улучшения производительности? Любой код / ​​фрагменты / статьи очень ценятся.

Приложение написано на Java, если это имеет какое-либо значение.

Спасибо

Mota

Обновление:

Мой руководитель говорит, что эта C библиотека выполнит задачу. Я не мог понять, как это работает и как он это сделает.

Answer 1

Ваш руководитель знаком с BitSet?128 бит - это 16 байтов, которые могут быть сохранены как 2 longs.Однако, используя BitSet, вам не нужно беспокоиться о работе с комбинацией 2 longs.BitSet также предоставляет методы для всех распространенных битовых операций.Я думаю, что вам будет довольно трудно найти лучшее решение, чем это.

Полиномиальный подход - довольно крутая идея, но я думаю, что он скорее теоретический, чем практический.

Answer 2

То, что он предлагает, - это Monomial, который вы можете составить в Polynomial - подумайте Composite pattern. Определите все обычные математические операции как для сложения, вычитания, умножения, деления, так и для любых других операций, которые вам могут понадобиться (например, дифференцирование и интеграция).

Полином действительно будет сиять в таких случаях, как x^1000 + 1, потому что вы можете захватить его всего двумя терминами.

Реальный вопрос: что, по мнению вашего босса, вы экономите? Несколько бит? Скорость? Время разработки? Я согласен с ziesemer - вам будет трудно сделать намного лучше, чем BitSet. Экономия, о которой он / она думает, кажется мне микрооптимизацией, такого рода вещи не появятся, если вы профилируете свое приложение.

Но он / она является боссом ... стоит ли спорить?

Может быть, вы можете абстрагироваться от этой детали и профилировать их.

Answer 3

Я очень сомневаюсь, что вы получите какую-либо выгоду от 128-битных строк. 128 бит - это 16 байтов; любой объект займет не менее 40, поэтому (почти) любая вспомогательная структура будет дороже, чем хранящиеся в ней данные.

Тем не менее, вот хороший обзор существующих методов - и один новый, который может (или не может) быть полезным для вас. Не так, как если бы это был ответ на ваш вопрос, и согласитесь, что решение ziesemer лучше всего подходит для такого огромного числа, но если вы хотите расширить свой кругозор, взгляните.

Answer 4

Если у вас есть несколько строк, требующих XOR, это фактически приведет к снижению производительности. Это потому, что вам нужно соответствовать весам.

Все зависит от того, с чем вы выполняете XOR, и сколько раз вам придется делать это, чтобы рассчитать преимущество для использования этого подхода.

Я бы пошел с решением Циземера.