Мозгоштурм или нужна идея :)

@Molotoff · Регистрация: 21.07.2009

Author24 — интернет-сервис помощи студентам

Друзья, нужна идея по одной программульке.
Задача состоит в следующем:
Работаю с булевыми функциями 5-ти, 6-ти, 7-ми и т.д. переменных, т.е. представляет собой двоичный набор длины 32, 64, 128 и т.д. соответственно.
Например, функция 5-ти переменных может быть представлена набором из 32 бит
(0101 1110 0001 0110 0100 0000 1000 1111)
Над этими наборами выполняются различные функции и проще всего их хранить как бинарный массив.
Все было бы хорошо, если б не нужно было вычислять так называемую сложность этих самых функций. По сути сводится к вычислению сложности функции 5-ти переменных, т.е. 32 бита, но для вычисления этой сложности нужно обращаться к специальной библиотеке (читай - массиву) и передавать функции уже не двоичный этот вектор, а значение формата unsigned int.

Теперь кратко и по пунктам:
1) необходимо хранить булевые (двоичные) наборы длины 32, 64, 128 и т.д. бит, мне проще всего работать с каждым как с массивом
2) набор длины 32 нужно каким-то образом быстро переводить в unsigned int

В связи с вышесказанным вопрос - как лучше хранить эти двоичные вектора и перегонять их в unsigned int?

@CheshireCat · 21.07.2009, 13:13

std::bitset, boost::dynamic_bitset смотрел?

@odip · 21.07.2009, 13:24

Покажи свой код, где ты ты определяешь набор длины 32-бита, набор 64-бита.
Как именно он хранится ?

А что именно ты хочешь - чтобы быстро работало ? Тогда покажи какие именно операции ты делаешь со своими наборами. Может можно работать с битами не переводя 32-битное число в массив.

Я бы хранил набор как указатель, если нет противопоказаний.

C

1	uint32 *pset;

@Monte-Cristo · 21.07.2009, 13:36

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

пишется не сложная функция по переводу. я бы перегонял двоичный массив в дестичное число (unsigned int)

@Molotoff · 21.07.2009, 15:04 **[ТС]**

Сообщение от odip

Покажи свой код, где ты ты определяешь набор длины 32-бита, набор 64-бита.
Как именно он хранится ?

А что именно ты хочешь - чтобы быстро работало ? Тогда покажи какие именно операции ты делаешь со своими наборами. Может можно работать с битами не переводя 32-битное число в массив.

Я бы хранил набор как указатель, если нет противопоказаний.

C

1	uint32 *pset;

Я реализую генетический алгоритм. Здесь кратко про этот алгоритм.
Так вот по условию задачи особи у меня кодируются 32, 64, 128 и т.д. битными векторами.
Сначала я реализовывал для вектора длины 32 как unsigned int.
При использовании генетических операторов - скрещивания, мутации и т.д., я переводил из unsigned int в булевый массив (с помощью побитовых операций), производил необходимые действия и обратно переводил в int, после чего вновь полученную особь проверя по специальной библиотеке (читай массиву) ее уровень приспособленности.
В дальнейшем при работе с 64, 128 битными особями, надо выполнять очень много итераций и этот метод не очень эффективен.
Вот меня и интересует вопрос, можно ли, имея 32-х элементный массив или вектор или битсет, быстро перегнать его в unsigned int. В литературе такого не нашел.

@odip · 21.07.2009, 15:14

Знаю что такое генетический алгоритм.
Разделим задачу на две части.
(1) Как быстро перегнать массив в unsigned int.
(2) Попробовать сделать все операции (скрещивание,мутации) прямо с uint32 *pset;
Я не очень понял как именно ты считаешь уровень приспособленности ?

Насчет (1).
Например так:

C

unsigned char arr[32]; // arr[i] равен строго 0 или 1
uint32 val;
 
val= .. (((arr[31]<<1)|arr[30])<<1)| .... arr[1])<<1)|arr[0];

@Molotoff · 21.07.2009, 15:16 **[ТС]**

Сообщение от odip

Знаю что такое генетический алгоритм.
Разделим задачу на две части.
(1) Как быстро перегнать массив в unsigned int.
(2) Попробовать сделать все операции (скрещивание,мутации) прямо с uint32 *pset;
Я не очень понял как именно ты считаешь уровень приспособленности ?

Насчет (1).
Например так:

C

unsigned char arr[32]; // arr[i] равен строго 0 или 1
uint32 val;
 
val= .. (((arr[31]<<1)|arr[30])<<1)| .... arr[1])<<1)|arr[0];

Уровень приспособленности смотрю по заранее созданному массиву, т.е. сама особь есть число в unsigned int, это же по сути номер порядковый, по которому уже и лезу в массив за функцией приспособленности этой особи

@odip · 21.07.2009, 15:21

Насчет (2).
Например мутация одного элемента - это просто инвентирование бита в массиве.

C

uint32 val;
int rand_num; // от 0 до 31
 
val^= (1<<rand_num);

Добавлено через 1 минуту 37 секунд

т.е. сама особь есть число в unsigned int, это же по сути номер порядковый, по которому уже и лезу в массив за функцией приспособленности этой особи

Тогда зачем тебе генетический алгоритм ?

Найди максимум в этом массиве приспособленности - вот тебе оптимальная особь.

@Molotoff · 21.07.2009, 15:27 **[ТС]**

Сообщение от odip

Насчет (2).
Например мутация одного элемента - это просто инвентирование бита в массиве.

C

uint32 val;
int rand_num; // от 0 до 31
 
val^= (1<<rand_num);

Добавлено через 1 минуту 37 секунд

Тогда зачем тебе генетический алгоритм ?

Найди максимум в этом массиве приспособленности - вот тебе оптимальная особь.

нет, тут немного сложнее ситуация

)))))
я реализовывал этот алгоритм для булевых функций 6-ти переменных, т.е. длинной 64 бита, они в свою очередь разбиваются на 2 по 5, и нужно найти с помощью генетического алгоритма такую функцию 5-ти переменных, которая бы минимизировала этот показатель, учитывая заранее заданные эти 2 части и самую себя

То, что ты описал выше - это все замечательно, но тот же кроссовер мне кажется не так просто уже будет реализовывать при векторах длины 64 или 128

@odip · 21.07.2009, 15:31

То, что ты описал выше - это все замечательно, но тот же кроссовер мне кажется не так просто уже будет реализовывать при векторах длины 64 или 128

Просто.
Еще и работать будет быстрее, чем на массиве - так как за одну операцию можно перенести до 32-ух элементов.
Если избавиться от конвертирования из массива в uint32 *pset - это тоже даст прирост.

Кстати может стандартные библиотеки для этого уже есть: std::bitset, boost::dynamic_bitset.
Тогда и писать ничего не придется

@Molotoff · 21.07.2009, 16:46 **[ТС]**

Вот так выглядит одноточечный кроссовер. Если у меня особь занимает например 128 бит, значит она представляет собой массив 4-х переменных по 32 бита, соответственно надо каким-то образом разрывать эти особи и получать новые.
Далее, оператор инверсии - например, имеется вектор 110010100011 инвертируем выделенную часть, должно получиться 110010001011, если разбито на 4 переменные, то реализовать такие функции сложнее, чем с массивом

@odip · 22.07.2009, 01:13

Положу пока сюда кусок кода

C

#include <stdio.h>
#include <stdlib.h>
 
int main( void ) {
 
unsigned int p0[4]= { 0x1ABC0132, 0x1CD12121, 0x1DE73834, 0x37856348 };
unsigned int p1[4]= { 0x284BE89A, 0xAEF8467D, 0x84746555, 0x9DAEF8AB };
unsigned int p2[4];
 
int fence= 17; /* from 0 to 128 */
 
if ( fence<0 ) {
    exit( 1 );
} else if ( fence == 0 ) {
    p2[0]= p1[0]; p2[1]= p1[1]; p2[2]= p1[2]; p2[3]= p1[3];
} else if ( fence < 32 ) {
} else if ( fence == 32 ) {
    p2[0]= p0[0]; p2[1]= p1[1]; p2[2]= p1[2]; p2[3]= p1[3];
} else if ( fence < 64 ) {
} else if ( fence == 64 ) {
    p2[0]= p0[0]; p2[1]= p0[1]; p2[2]= p1[2]; p2[3]= p1[3];
} else if ( fence < 96 ) {
} else if ( fence == 96 ) {
    p2[0]= p0[0]; p2[1]= p0[1]; p2[2]= p0[2]; p2[3]= p1[3];
} else if ( fence < 128 ) {
} else if ( fence == 128 ) {
    p2[0]= p0[0]; p2[1]= p0[1]; p2[2]= p0[2]; p2[3]= p0[3];
} else {
    exit( 1 );
}
 
return 0;
 
}

Добавлено через 3 минуты 27 секунд
Вообще из биологии я думал что кроссовер немного более сложный процесс, твой вариант проще.
Как ты догадался это для 128-битных чисел.
Осталось 4 однотипных куска дописать

@Molotoff · 22.07.2009, 06:22 **[ТС]**

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

@Patch · 22.07.2009, 07:16

Сообщение от Molotoff

Как быстро получить такую маску?

например так:

C

int i = 1;
count=3;
while(--count>0){
i++<<=1;
}

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

@odip · 22.07.2009, 10:30

2Molotoff: Да понял я, я просто не дописал

Добавлено через 3 минуты 4 секунды
Маску быстро получить двумя способами - по заранее заданном массиву или с помощью только одной операции '<<'.
Какой из этих двух способов будет быстрее - это нужно тестировать программу.
Способ предложенный Patch плохой, так как там цикл, а это уже будет медленнее.

@Patch · 22.07.2009, 10:36

Сообщение от odip

Способ предложенный Patch плохой, так как там цикл, а это уже будет медленнее.

а другого для битного поля нет.
либо делать так, либо ассемблерной вставкой.
а вот по одному биту - можно и одной операцией.
но маски-массивы, кстати, все равно делать нужно, иначе медленно будет.

@odip · 22.07.2009, 14:38

Где ты увидел битовые поля ?

А - ты наверное unsigned int обозвал битовым полем

Операция сдвига на N в коде выполняется одной командой за один такт.

C

1	b= (a<<n);

Добавлено через 3 часа 56 минут 44 секунды
Получилось даже проще чем ожидал.

C

#include <stdio.h>
#include <stdlib.h>
 
static unsigned int mask[]= {
    0x00000000, 0x00000001, 0x00000003, 0x00000007,     /* 0,1,2,3,     */
    0x0000000F, 0x0000001F, 0x0000003F, 0x0000007F,     /* 4,5,6,7,     */
    0x000000FF, 0x000001FF, 0x000003FF, 0x000007FF,     /* 8,9,10,11,   */
    0x00000FFF, 0x00001FFF, 0x00003FFF, 0x00007FFF,     /* 12,13,14,15, */
    0x0000FFFF, 0x0001FFFF, 0x0003FFFF, 0x0007FFFF,     /* 16,17,18,19, */
    0x000FFFFF, 0x001FFFFF, 0x003FFFFF, 0x007FFFFF,     /* 20,21,22,23, */
    0x00FFFFFF, 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF,     /* 24,25,26,27, */
    0x0FFFFFFF, 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF,     /* 28,29,30,31, */
    0x0FFFFFFF                                                                  /* 32                 */
};
 
static unsigned int rmask[]= {
    0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFC, 0xFFFFFFF8, /* 0,1,2,3,     */
    0xFFFFFFF0, 0xFFFFFFE0, 0xFFFFFFC0, 0xFFFFFF80, /* 4,5,6,7,     */
    0xFFFFFF00, 0xFFFFFE00, 0xFFFFFC00, 0xFFFFF800, /* 8,9,10,11,   */
    0xFFFFF000, 0xFFFFE000, 0xFFFFC000, 0xFFFF8000, /* 12,13,14,15, */
    0xFFFF0000, 0xFFFE0000, 0xFFFC0000, 0xFFF80000, /* 16,17,18,19, */
    0xFFF00000, 0xFFE00000, 0xFFC00000, 0xFF800000, /* 20,21,22,23, */
    0xFF000000, 0xFE000000, 0xFC000000, 0xF8000000, /* 24,25,26,27, */
    0xF0000000, 0xE0000000, 0xC0000000, 0x80000000, /* 28,29,30,31, */
    0x00000000                                                                  /* 32                 */
};
 
/* ================================================================ */
int main( void ) {
 
unsigned int p0[4]= { 0x1ABC0132, 0x1CD12121, 0x1DE73834, 0x37856348 };
unsigned int p1[4]= { 0x284BE89A, 0xAEF8467D, 0x84746555, 0x9DAEF8AB };
unsigned int p2[4];
 
int fence; /* from 0 to 128 */
 
int i;
 
 
fence= 17;
 
if ( fence < 0 ) {
    exit( 1 );
} else if ( fence < 32 ) {
    p2[0]= (p0[0]&mask[fence-0]) | (p1[0]&rmask[fence-0]);
    p2[1]= p1[1]; p2[2]= p1[2]; p2[3]= p1[3];
} else if ( fence < 64 ) {
    p2[1]= (p0[1]&mask[fence-32]) | (p1[1]&rmask[fence-32]);
    p2[0]= p0[0];
    p2[2]= p1[2]; p2[3]= p1[3];
} else if ( fence < 96 ) {
    p2[2]= (p0[2]&mask[fence-64]) | (p1[2]&rmask[fence-64]);
    p2[0]= p0[0]; p2[1]= p0[1];
    p2[3]= p1[3];
} else if ( fence <= 128 ) {
    p2[3]= (p0[3]&mask[fence-96]) | (p1[3]&rmask[fence-96]);
    p2[0]= p0[0]; p2[1]= p0[1]; p2[2]= p0[2];
} else {
    exit( 1 );
}
 
for ( i= 0; i<4; i++ ) {
    printf( " %08X", p2[i] );
}
printf( "\n" );
 
return 0;
 
}

@resource · 22.07.2009, 15:23

Сообщение от odip

Операция сдвига на N в коде выполняется одной командой за один такт.

ну вообщето сдвиг регистра выполняется за 1 такт, а сдвиг переменной на пентиуме2 (конкретно помню) выполнялся за 4, и это при условии что операнды выровнены по границе двойного слова и находятся в кэше и шина данных не заблокирована. А в твоем сдвиге, кроме всего прочего, n нужно сначала загрузить в регистр, а всё это вместе уже совсем не 1 такт.

@odip · 22.07.2009, 15:25

Ну да - конечно Pentium II, ты еще 486-ые вспомни

Ты прав конечно, но суть в том, что для сдвига на 31 бит не нужно крутить цикл 31 раз. И цикл будет во много раз медленнее.

И потом я уже все сделал через массивы.

@resource · 22.07.2009, 15:26

В этом плане я и не пытался с тобой спорить

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50
		1
	Мозгоштурм или нужна идея :) 21.07.2009, 12:46. Показов 3631. Ответов 39 Метки нет (Все метки) Друзья, нужна идея по одной программульке. Задача состоит в следующем: Работаю с булевыми функциями 5-ти, 6-ти, 7-ми и т.д. переменных, т.е. представляет собой двоичный набор длины 32, 64, 128 и т.д. соответственно. Например, функция 5-ти переменных может быть представлена набором из 32 бит (0101 1110 0001 0110 0100 0000 1000 1111) Над этими наборами выполняются различные функции и проще всего их хранить как бинарный массив. Все было бы хорошо, если б не нужно было вычислять так называемую сложность этих самых функций. По сути сводится к вычислению сложности функции 5-ти переменных, т.е. 32 бита, но для вычисления этой сложности нужно обращаться к специальной библиотеке (читай - массиву) и передавать функции уже не двоичный этот вектор, а значение формата unsigned int. Теперь кратко и по пунктам: 1) необходимо хранить булевые (двоичные) наборы длины 32, 64, 128 и т.д. бит, мне проще всего работать с каждым как с массивом 2) набор длины 32 нужно каким-то образом быстро переводить в unsigned int В связи с вышесказанным вопрос - как лучше хранить эти двоичные вектора и перегонять их в unsigned int? 0

@CheshireCat 2924 / 1274 / 114 Регистрация: 27.05.2008 Сообщений: 3,465
	21.07.2009, 13:13	2
	std::bitset, boost::dynamic_bitset смотрел? 0

@Monte-Cristo 2816 / 1407 / 107 Регистрация: 07.03.2009 Сообщений: 4,446
	21.07.2009, 13:36	4
	Molotoff, вот так вот и хранить. Перегонять либо из двоичного массива в десятичную систему) либо из десятичного числа перегонять в двоичный массив. пишется не сложная функция по переводу. я бы перегонял двоичный массив в дестичное число (unsigned int) 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	21.07.2009, 15:31	10
	То, что ты описал выше - это все замечательно, но тот же кроссовер мне кажется не так просто уже будет реализовывать при векторах длины 64 или 128 Просто. Еще и работать будет быстрее, чем на массиве - так как за одну операцию можно перенести до 32-ух элементов. Если избавиться от конвертирования из массива в uint32 *pset - это тоже даст прирост. Кстати может стандартные библиотеки для этого уже есть: std::bitset, boost::dynamic_bitset. Тогда и писать ничего не придется 0

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50
	21.07.2009, 16:46 [ТС]	11
	Вот так выглядит одноточечный кроссовер. Если у меня особь занимает например 128 бит, значит она представляет собой массив 4-х переменных по 32 бита, соответственно надо каким-то образом разрывать эти особи и получать новые. Далее, оператор инверсии - например, имеется вектор 110010100011 инвертируем выделенную часть, должно получиться 110010001011, если разбито на 4 переменные, то реализовать такие функции сложнее, чем с массивом Миниатюры 0

@Molotoff 1 / 1 / 0 Регистрация: 21.07.2009 Сообщений: 50
	22.07.2009, 06:22 [ТС]	13
	твою идею понял, но там несколько сложнее - разрыв по хромосомам может произойти не только по элементам как у тебя, но и где-нибудь посередине одного из элементов массива. Тут уже надо генерировать маски и рвать по маскам. Как быстро получить такую маску? А по поводу кроссовера - это простой или одноточечный кроссовер, их есть еще несколько вариантов. 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	22.07.2009, 10:30	15
	2Molotoff: Да понял я, я просто не дописал Добавлено через 3 минуты 4 секунды Маску быстро получить двумя способами - по заранее заданном массиву или с помощью только одной операции '<<'. Какой из этих двух способов будет быстрее - это нужно тестировать программу. Способ предложенный Patch плохой, так как там цикл, а это уже будет медленнее. 0

@Patch 2343 / 499 / 22 Регистрация: 01.04.2009 Сообщений: 2,200
	22.07.2009, 10:36	16
	Сообщение от odip Способ предложенный Patch плохой, так как там цикл, а это уже будет медленнее. а другого для битного поля нет. либо делать так, либо ассемблерной вставкой. а вот по одному биту - можно и одной операцией. но маски-массивы, кстати, все равно делать нужно, иначе медленно будет. 0

@resource 7 / 7 / 1 Регистрация: 22.07.2009 Сообщений: 104
	22.07.2009, 15:23	18
	Сообщение от odip Операция сдвига на N в коде выполняется одной командой за один такт. ну вообщето сдвиг регистра выполняется за 1 такт, а сдвиг переменной на пентиуме2 (конкретно помню) выполнялся за 4, и это при условии что операнды выровнены по границе двойного слова и находятся в кэше и шина данных не заблокирована. А в твоем сдвиге, кроме всего прочего, n нужно сначала загрузить в регистр, а всё это вместе уже совсем не 1 такт. 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	22.07.2009, 15:25	19
	Ну да - конечно Pentium II, ты еще 486-ые вспомни Ты прав конечно, но суть в том, что для сдвига на 31 бит не нужно крутить цикл 31 раз. И цикл будет во много раз медленнее. И потом я уже все сделал через массивы. 0

@resource 7 / 7 / 1 Регистрация: 22.07.2009 Сообщений: 104
	22.07.2009, 15:26	20
	В этом плане я и не пытался с тобой спорить 0