В задаче больше математики (но притом полезной с точки зрения ежедневного практического программирования) но и машинной оптимизации в ней есть место. Допустим у нас есть массив длин единичных и нулевых строк полученный из задачи 11. Нам нужно создать массив представляющий множество которому принадлежат значения из ряда длин (на случай если кому то неизвестна разница - в множестве нет повторяющихся элементов т.е. для ряда 1,22,1,13,13 множество будет {1,22,13}) До того как мы будем множество это создавать нам нужно выделить память, а она драгоценна, её нужно выделить не меньше чем может понадобится, но и не явно больше (динамическое выделение по принципу - добавим если не хватит - откидывается как неприемлимое по скорости) Т.е. нам нужно определить размер памяти больше которой нам явно не понадобится (пусть на размер одного элемента множества выделяется двойное слово). Определить это нам нужно исходя из следующих данных (которые у нас есть) 1. Размер бинарного массива (который дан нам показателем степени двойки например x=27 будет означать что массив в котором считались длины был равен 2^27 или 128и мегабит) 2. Размер массива с длинами нулевых и единичных строк полученных и массива 1. Понятно что мощность множества не может быть больше (2.) но оно может быть явно меньше что можно вычислить из (1.) Хинт нулевых длин быть не может, любая длина - натуральное число, наибольшее количество значений будет при распределении 1+2+3+... а размер массива из которого считали длины - степерь двойки
вычисление размера массива: Код (Text): in: ecx=x (x<32) out: eax-максимальное число элементов calcsize: xor eax,eax lea edx,[eax+1] shl edx,cl .l0: inc eax sub edx,eax jnc .l0 dec eax ret само множество может потом построю.
Алгоритм компактный, но он резко проигрывает в скорости так же компактному но сделаному после анализа с точки зрения математики. В задачке был хинт. Видно что рассмотреть нужно с точки зрения арифметической прогрессии с единицы с шагом 1. Т.е. 1+2+3+...+n Нам нужно будет найти такое максимально возможное n, которое <= 2<sup>x</sup> Далее вспомним что пусть а >=1+2+3+..+n значит а >= (n(n+1)):2 вместо а подставим 2<sup>x</sup> и попробуем сделать преобразования... ...ну дальше я удовольствие портить нехочу Да, давайте уточним действительно что x <= 31 и данная задачка не на построение множества а на нахождение максимальной его мощности для выделения памяти а на элемент требуется 4 байта - нужно выдать уже число в байтах а это можно сделать (учёт размера) немного по разному что тоже скажется на эффективности и по скорости и по размеру. Опять прошу - не подходите к задачам с точки зрения тупого сканирования, когда уделяется больше времени лишь на подбор оптимальных инструкций, всё же дискретная математика служит для того чтоб прогрызать дырки в пространстве тупых переборов.
The Svin Зато резко выигрывает в скорости выборка ответа одной командой из таблицы на 32 слова. Ну а формула по которой заполняется таблица у меня получилась такая: n=(sqrt(1+2<sup>x+3</sup>)-1)/2 (округляем вверх)
Хех Гиганты валятся на мелочах А если у тебя количество строк меньше (2. в исходной задаче). Кстати существует компроммисный вариант пара-тройка дополнительных тактов к скорости выборки по индексу и таблички создавать не нужно.
The Svin Нормально работает при x=0..60 Код (Text): csz:;(x +4, len +8)->eax mov ecx,[esp+4] ;x mov eax,$80000000 mov ebx,eax mov edx,eax add ecx,3 shr ecx,1 jnc .l0 mov edx,$5A827999 lea eax,[edx*2+1] .l0: shr ebx,cl sub eax,ebx shr edx,cl shr edx,cl add eax,edx not ecx shr eax,cl shr eax,1 ;я правильно понял замечание про количество строк? cmp eax,[esp+8] ;len(в словах) jb .l1 mov eax,[esp+8] .l1: ret
