LINUX.ORG.RU
Форум — Development  

общий вопрос по программированию — расчитать индекс массива


0

1

есть некоторый массив, состоящий из субмассивов, в которых хранится некоторое количество векторов, несущих информацию и много мусора. ( http://ompldr.org/vYW9sZg/newfile1.png)

процессе работы программы на каждом глобальном шаге итераций несущие информацию вектора будут меняться:

а)переходить, между соседними субмассивами. б)уничтожаться в)рождаться

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

1)номер первой свободной ячейки в соседнем массиве

2)номера всех ячеек, несущих информацию

как это лучше сделать? самый дубовый вариант — это завести или внутри этого массива или внутри дополнительного булевую ячейку, но тогда придётся лишний раз бегать по нему, а это затратно.

по идее, всю информацию о том, в каких ячейках информация, а в каких мусор можно представить ввиде двоичного числа (111100011111...N1), где 0 — пустая ячейка, а 1 — информативная. можно ли из этого числа как то быстро узнать номер первого нуля, номера единиц?

★★★★★

Последнее исправление: thunar (всего исправлений: 3)

>по идее, всю информацию о том, в каких ячейках информация, а в каких мусор можно представить ввиде двоичного числа (111100011111...N1)

А какой размер массива? Число не переполнится?

anonymous
()

Э... так делать не надо. При каждом переносе R надо делать дефрагментацию A_i. Т.е. для каждого A_i мы храним число актуальных элементов N_i, если из A_i нужно убрать элемент и этот элемент не последний, пишем на его место последний элемент и декрементируем N_i. Новый элемент добавляется в конец, N_i инкрементируется. Тогда все актуальные элементы всегда лежат вначале A_i и никаких проблем;-)

AIv ★★★★★
()

«свободных, не несущих информациюб, ячеек заведомо больше, чем значащих» Тогда есть надежда что такой фрагмент кода 

	if( b == 0 )
		cout<<"all zeroes"<<endl;
	else if( b == -1 )
		cout<<"all ones"<<endl;
	else if( (b & (b-1) ) == 0)
		cout<<"sigle one on "<<__builtin_clz(b)<<endl;
	else while( b ){
		int pos= __builtin_clz(b);
		cout<<pos<<endl;
		b ^= 1<<(31-pos); 
		}
будет достаточно эфективен, даже если __builtin_clz на самом деле окажется не вызовом одной ассемблерной инструкции а функцией содержащей цикл.

cool-e-bin
()
Ответ на: комментарий от AIv

эээ.. а если подохли не один, а несколько элементов?

что то похоже надо снова к вам подъехать, проконсультироваться.

thunar ★★★★★
() автор топика
Ответ на: комментарий от thunar

Они ж не сразу, а по одному дохнут (типа в цикле). Кто сдох - на его место последнего.

Хотите - приезжайте, у нас как обычно по средам в 17.00 семинар;-)

AIv ★★★★★
()

ты сам пишешь программу, формат массива и прочего можно менять, или он жестко задан?

Если можно менять, то лучше всего хранить битовую карту как массив int, как ты и написал, и при каждом удалении/добавлении очищать/поднимать соответствующий бит. Быстрее этого ты вряд ли что-нибудь придумаешь, потому что в остальных случаях придется обходить массив.

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

gaga ★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
Development