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

Question

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

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

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

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

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

Спасибо,

Мота

Update:

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

Answer 1

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

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

Answer 2

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

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

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

Но s/he is босс ... стоит ли рассуждать?

Возможно, вы можете абстрагировать эту деталь и профилировать ее.

Answer 3

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

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

Я бы пошел с решением ziesemer.

Answer 4

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

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