Я раздумываю тут над тем, как наиболее удобно можно хранить группу в комьюторе для работы с ней. Хотелось бы услышать комментарии по тому, что я уже пробовал, а так же предложения чего-то нового.
Наиболее очевидный метод (что называется "в лоб") — это представление в виде таблицы умножения. С одной стороны очень удобно: сразу известен порядок группы, каждый элемент нумеруется от нуля до порядка не включая, групповая операция над элементами выполняется элементарно просто и в одну примитивную операцию: взятие элемента по двум индексам из двумерного массива. Недостаток тоже очевиден: представление занимает много памяти. Даже у группы порядка 2500 при использовании типа
shot в два байта таблица умножения займёт
Это за пределами не только кэша 1-го и 2-го уровня, но и 3-го тоже (для современных процессоров, у меня старенький, только первые два есть: 64 КБ / 1 МБ). Это значит, что программа будет работать с оперативной памятью, которая, как известно, очень медленная.
Этой медленностью, а так же ограниченностью её размера, мотивируется мой поиск альтернатив. В виде текстовых соотношений способ отпадает сразу. Он компактный, да, но он удобен лишь для красивого хранения или указания какая группа имеется в виду. Развернуть соотношения в таблицу умножения группы или ещё во что-то удобное для работы — задача весьма нетривиальна.
Некоторые группы можно задать формулами, например циклические группы. Операция будет просто сумма по модулю. Причём последнюю, чтобы избавиться от медленной операции деления можно превратить в операцию индексирования в массиве двойной (от порядка группы) длины. Аналогично можно реализовать прямое или даже некоторые полупрямые произведения двух групп: входные индексы элементов разбираются на компоненты для каждой из двух групп в произведении, находятся значения групповой операции в каждой из двух групп, а затем эти значения собираются в конечный индекс. Здесь тоже есть деление с остатком, и оно тоже оптимизируется заранее подсчитанными массивами. Это работает и экономит память, но недостатки тоже очевидны. Во-первых, далеко не все группы представимы в виде произведения двух или более других легко считаемых. Просто потому, что существуют простые группы со сложной структурой. Так что у метода отсутствует универсальность. Во-вторых, даже одно скалярное произведение считается уже медленнее, чем индексация таблицы умножения на всю память (на моём компе, во всяком случае, хотя я может криво накодил).
public class CyclicGroup implements Group {
private int order;
private int [] productFunc, inverseFunc;
public CyclicGroup (int argOrder) {
int k, l;
if (1 > argOrder) {
throw new IllegalArgumentException ("\n\nIllegal group order.\n");
}
order = argOrder;
l = argOrder * 2 - 1;
productFunc = new int [l];
inverseFunc = new int [order];
for (k = 1; order > k; ++k) {
productFunc [k] = k;
inverseFunc [k] = order - k;
}
for (++k; l > k; ++k) {
productFunc [k] = k - order;
}
}
@Override
public int order () {
return order;
}
@Override
public int product (int argLeft, int argRight) {
if (0 > argLeft || 0 > argRight || order <= argLeft || order <= argRight) {
throw new IllegalArgumentException ("\n\nIllegal element index.\n");
}
//return order > argLeft + argRight ? argLeft + argRight : argLeft + argRight - order;
return productFunc [argLeft + argRight];
}
@Override
public int inverse (int arg) {
if (0 > arg || order <= arg) {
throw new IllegalArgumentException ("\n\nIllegal element index.\n");
}
//return 0 == arg ? 0 : order - arg;
return inverseFunc [arg];
}
@Override
public int [] generators () {
return new int [] {1};
}
}
import java.util.Arrays;
public class CartesianGroupProduct implements Group {
private int order, subOrder;
private int [] gens, inverseFunc, subFunc1, subFunc2;
private Group group1, group2;
public CartesianGroupProduct (Group argGroup1, Group argGroup2) {
int k, l, m;
int [] gens1, gens2;
Group .checkIntegrity (argGroup1);
Group .checkIntegrity (argGroup2);
order = argGroup1 .order () * argGroup2 .order ();
subOrder = argGroup2 .order ();
group1 = argGroup1;
group2 = argGroup2;
gens1 = argGroup1 .generators ();
gens2 = argGroup2 .generators ();
gens = new int [gens1 .length + gens2 .length];
k = 0;
for (l = 0; gens1 .length > l; ++k, ++l) {
gens [k] = gens1 [l] * subOrder;
}
for (l = 0; gens2 .length > l; ++k, ++l) {
gens [k] = gens2 [l];
}
Arrays .sort (gens);
subFunc1 = new int [order];
subFunc2 = new int [order];
inverseFunc = new int [order];
for (k = 1; order > k; ++k) {
subFunc1 [k] = k / subOrder;
subFunc2 [k] = k % subOrder;
}
for (k = 1; order > k; ++k) {
l = 0;
while (true) {
m = product (k, l);
if (0 == m) {
break;
}
l = m;
}
inverseFunc [k] = l;
}
}
@Override
public int order () {
return order;
}
@Override
public int product (int argLeft, int argRight) {
if (0 > argLeft || 0 > argRight || order <= argLeft || order <= argRight) {
throw new IllegalArgumentException ("\n\nIllegal element index.\n");
}
return group1 .product (subFunc1 [argLeft], subFunc1 [argRight]) * subOrder +
group2 .product (subFunc2 [argLeft], subFunc2 [argRight]);
//return group1 .product (argLeft / subOrder, argRight / subOrder) * subOrder +
// group2 .product (argLeft % subOrder, argRight % subOrder);
}
@Override
public int inverse (int arg) {
if (0 > arg || order <= arg) {
throw new IllegalArgumentException ("\n\nIllegal element index.\n");
}
return inverseFunc [arg];
}
@Override
public int [] generators () {
return Arrays .copyOf (gens, gens .length);
}
}
Третий (или четвёртый?) метод заключается в представлении элементов группы в виде перестановок. Групповая операция тогда будет их композицией. (Этот способ является одним из первых, рассматриваемых в любой книжке по теории групп, начинающей с азов). Ну, таблица умножения уже является в прямом смысле таким представлением, надо лишь присмотреться. Однако, я имею в виду такие перестановки, которые значительно короче порядка группы. Здесь сразу возникают большая проблема и тележка вопросов. А как найти для заданной группы набор перестановок с минимальной длиной? Возможно ли это алгоритмизировать в общем случае? Может получится, если искать не минимальной длины, а просто достаточно короткие перестановки? Всегда ли можно найти перестановку более короткую, чем порядок группы? (ОК, нет, контрпример: симметрические группы). Если нет, то когда можно, и насколько эффективно? Ну и практический вопрос (когда задачи выше решены): быстрый поиск результата композиции двух перестановок в списке перестановок, чтобы вернуть индекс результирующего элемента. Ничего более эффективного, чем бинарный поиск массива в сортированном массиве массивов (перестановок), мне не видится.
Пока единственный способ (который я знаю) получения групп в таком представлении — это случай, когда они естественным образом вычисляются сразу в этом виде. Я имею в виду группы автоморфизмов других групп. Не уверен, что группа автоморфизмов порядка 98784 от группы порядка 147 на много лучше случая выше (в плане расхода памяти), но хотя бы в теории с ней можно будет хоть как-то работать, потому что таблица умножения для неё займёт 18 ГБ! (С моими 3-мя явно запредельная величина). И тут можно пытаться делать всякие оптимизации, например, сгруппировать элементы по величине порядка, сделать списки перестановок внутри каждого порядка, а полную перестановку задавать как комбинацию перестановок для каждого из порядков. Тогда память будет ещё больше экономиться, правда производительность пострадает.
Я ничего не забыл? Буду рад любым интересным и необычным предложениям.