Манипулирование очень большими двоичными строками в c #

Question

Я работаю над проектом генетического алгоритма, где я кодирую свою хромосому в виде двоичной строки, где каждый 32 бита представляет значение. Проблема в том, что функции, которые я оптимизирую, имеют более 3000 параметров, что подразумевает, что у меня более 96000 битов в моей битовой строке, и манипуляции, которые я выполняю над этим, просто замедляются ...

Я поступил следующим образом: у меня есть двоичный класс, в котором я создаю логический массив, который представляет мою большую двоичную строку. Затем я манипулирую этой двоичной строкой с помощью различных сдвигов, ходов и тому подобного.

Мой вопрос: есть ли лучший способ сделать это? Скорость просто убивает. Я уверен, что было бы хорошо, если бы я делал это только с одной битовой строкой, но я должен делать манипуляции с 25-битной строкой на протяжении более 1000 поколений.

Answer 1

Я бы сделал шаг назад. Ваш анализ, похоже, связан с деталями реализации, а именно с тем, что вы выбрали bool [] в качестве способа представления строки битов.

Очистите свой разум от логических операций и массивов и составьте полный список операций, которые вам действительно нужно выполнить, как часто они происходят и как быстро они должны выполняться. В идеале подумайте, является ли ваше требование скорости средней скоростью или наихудшей скоростью . (Существует много структур данных, которые достигают высокой средней скорости благодаря наличию одной дорогой операции на каждую тысячу дешевых операций; если использование любых дорогостоящих операций недопустимо, вам необходимо знать об этом заранее.)

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

Например, предположим, что ваш список операций:

• строит битовые последовательности порядка 32 бит
• объединяет порядка 3000 битовых последовательностей для формирования новых битовых последовательностей
• быстро вставлять новые битовые последовательности в существующие длинные битовые последовательности в определенных местах

Учитывая только этот список операций, я бы подумал, что вам нужна структура данных catenable deque . Запатентованные запросы поддерживают быструю вставку с любого конца и могут быть эффективно разбиты на два запроса. Затем легко вставить материал в середину deque: разбить deque вверх, вставить элемент в конец одной половины и снова соединить его.

Однако, если вы затем добавите к задаче еще одну операцию, скажем, «найдите конкретную битовую строку в любом месте 90000-битной последовательности, и найдите результат в сублинейном времени », тогда это просто исправимое deque не собирается этого делать. Поиск deque идет медленно. Существуют и другие структуры данных, которые поддерживают эту операцию.

Answer 2

Если я правильно понял, вы кодируете битовый массив в bool[].Первой очевидной оптимизацией было бы изменить это значение на int[] (или даже long[]) и использовать битовые операции над целым машинным словом, где это возможно.

Например, это сделает сдвиги более эффективнымив ~ 4 раза.

Answer 3

Класс BitArray не помогает?

Answer 4

Дай мне понять; В настоящее время вы используете последовательность 32-битных значений для «хромосомы». Речь идет о ДНК-хромосомах или нейроэволюционных алгоритмических хромосомах?

Если это ДНК, вы имеете дело с 4 значениями; А, С, G, Т. Это может быть закодировано в 2 бита, что позволяет байту хранить 4 значения. Ваша последовательность хромосом из 3000 элементов может быть сохранена в байтовом массиве из 750 элементов; на самом деле это ничего.

Ваши две самые дорогие операции - это сжатый битовый поток и обратно. Я бы порекомендовал перечисление с байтовым ключом:

public enum DnaMarker : byte { A, C, G, T };

Затем вы переходите от 4 к байтам за одну операцию:

public static byte ToByteCode(this DnaMarker[] markers)
{
   byte output = 0;
   for(byte i=0;i<4;i++)
      output = (output << 2) + (byte)markers[i];
}

... и разобрать их обратно примерно так:

public static DnaMarker[] ToMarkers(this byte input)
{
   var result = new byte[4];
   for(byte i=0;i<4;i++)
       result[i] = (DnaMarker)(input - (input >> (2*(i+1))));

   return result;
}

Вы можете увидеть небольшое увеличение производительности при использовании четырех параметров (вывод при необходимости) по сравнению с выделением и использованием массива в куче. Но вы теряете итерацию, которая делает код более компактным.

Теперь, поскольку вы упаковываете их в четырехбайтовые «блоки», если длина вашей последовательности не всегда точно кратна четырем, вы в конечном итоге «заполните» конец вашего блока нулевыми значениями (A ). Обойти это не очень удобно, но если у вас есть 32-разрядное целое число, в котором указано точное количество маркеров, вы можете просто отбросить все, что найдете в этом потоке.

Отсюда возможности безграничны; Вы можете преобразовать массив enum в строку, просто вызвав ToString () для каждого из них, а также вы можете передать строку и получить массив enum, выполнив итерации с помощью Enum.Parse ().

И всегда помните, что если память не стоит дорого (как правило, это не так), почти всегда быстрее работать с данными в удобном для использования формате, а не в самом компактном формате. Одним большим исключением является передача по сети; если вам пришлось отправлять 750 байт против 12 КБ через Интернет, очевидным преимуществом является меньший размер.

Answer 5

A BitArray, вероятно, будет быстрее, чем логический массив, но вы все равно не получите встроенную поддержку для сдвига 96000 бит.

Графические процессоры очень хороши в массовых битовых операциях. Может быть, Брахма , CUDA.NET или Ускоритель может быть полезным?