Я эту задачку привел из-за решения. Потому что этот подход может использоваться и в других задачах. Как минимум знаю еще два случая, когда для решения задач использовался аналогичный подход. Один случай у меня лично :-)

Ответ на »сообщение 35« (Мухтар)
___________________________

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

Ответ на »сообщение 34« (Александр Малыгин)
___________________________
На моем процессоре, все-таки, вариант

  mov  al,value
  lea  ebx,table
  xlat  [ebx]

Примерно в два раза быстрее вашего. Хотя и идет обращение к памяти... Видимо, сказывается кэш процессора

Ответ на »сообщение 33« (Geo)
___________________________

Есть еще одно решение этой задачи, "широко известное в узких кругах". Мой перевод с сишного исходника, найденного в инете:

function BitCount(V : byte) : byte; assembler;
  asm
    // v = (v & 0x55) + ((v >> 1) & 0x55);
    mov  dl, al
    and  al, $55
    shr  dl, 1
    and  dl, $55
    add  al, dl
    // v = (v & 0x33) + ((v >> 2) & 0x33);
    mov  dl, al
    and  al, $33
    shr  dl, 2
    and  dl, $33
    add  al, dl
    // return (v & 0x0f) + ((v >> 4) & 0x0f);
    mov  dl, al
    and  al, $0F
    shr  dl, 4
    and  dl, $0F
    add  al, dl
  end;

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

Пардон за введение общественности в заблуждение. Я в спешке пропустил в своем примере самый важный оператор

function CalcBits(N : Byte) : Byte;
asm
      xor  ax,ax
      or    ah,N
      jz    @quit
@next:
      adc  al,0
      shl  ah,1
      jnz  @next
      adc  al,0
@quit:
end;

Здесь один лишний вызов команды adc al,0 Зато на этом деле я сэкономил один переход. Что выгоднее наизусть не помню. А лезть в справочник лениво.

Ответ на »сообщение 30« (Мухтар)
___________________________
Понял, согласен.

У вас где-то команда сдвига потерялась :)
Но можно второй вариант еще улучшить. См. мой пост ниже.

Ответ на »сообщение 25« (CoreWars)
___________________________
У вас вызов процедуры превращается в пару лишних обращений к памяти, плюс в стек идет адрес возврата, у меня лишь одно обращение - напрямую к переменной в которой хранятся исходные данные

Ответ на »сообщение 26« (Сергей Перовский)
___________________________
Прошу прощения, я забыл, что b в квадратных скобках означает переход на болд.
Вот и получилось вместо b-го элемента массива A, переход на жирный шрифт.

В данном случае размер элемента массива байт (самое большое число единиц = 8) и умножения не требуется. Так что оптимальнее с массивом (одно сложение номера элемента массива с адресом его начала).
Далее, вариант Мухтара (неработающий) выполняет тело цикла ВСЕГДА 8 раз. Есть алгоритм, который позволяет выполнить тело цикла столько раз, сколько единиц в исходном числе.
Если кто знает, пусть пока не говорит, дадим время подумать? :))

Все правильно. Самый быстрый способ -- хранить таблицу из 256 значений, каждый элемент которой содержит количество установленных бит в его индексе. А таблицу задать в виде константы. Я специально подчеркивал, что другие критерии оптимизации (в том числе, объем занимаемой памяти) роли не играют. В общем, здесь даже ассемблер не нужен. Можно написать прямо на Паскале:

const
  Bits : array[0..255] of Byte = (0,1,1,2,1,2,..);

function CalcBits(N : Byte) : Byte;
begin
  Result:=Bits[N];
end;

А в ассемблерном варианте у меня получилось что-то вроде такого:

function CalcBits(N : Byte) : Byte;
asm
      xor  ax,ax
      or    ah,N
      jz    @quit
@next:
      adc  al,0
      jnz  @next
      adc  al,0
@quit:
end;

Кстати, задача и решеие из реальной практики фирмы, разрабатывающей OCR-системы.

Ответ на »сообщение 14« (Geo)
___________________________
Считается, что самым быстрым будет вариант с хранением заранее подсчитанных результатов в массиве.
Действительно, очень красиво - Result:=A и все.
Но что такое обращение к элементу массива?
Это прежде всего вычисление смещения относительно начала массива. Транслятор превратит это в умножение индекса на длину элемента массива. А умножение - операция медленная. Решение от Мухтара может оказаться быстрее.
Чтобы гарантировать выигрыш от хранения результатов, нужно избавиться от индекса:
Result:=Byte(pointer(inc(Longint(@A),b))^);
Эффективно, но очень заумно.

Ох, ну давайте сравнивать: у меня 18 байт у вас - 20. Т.к. для 32х битных процессоров 16и битные команды длиннее. Или вы имели в виду скорость выполнения?
Про стек не понял: это вы про lea? В данном случае это же сложение не затрагивающее флаги!

Ответ на »сообщение 20« (CoreWars)
___________________________
Со стеком, плюс вес инструкций больше

Кстати, задача: можно ли отсортировать массив за один проход? Иначе говоря каждый элемент должен считываться только один раз (и записываться соответсвенно тоже). Дополнительный массив не предлагать.

Ответ на »сообщение 20« (CoreWars)
___________________________
У вас слишком много обращений к памяти

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

Если брать ваш вариант (жутко неоптимальный, кстати), то получится что-то подобное:

function Bits(value: byte): int;
asm
        xor    ecx, ecx
        test    al, al
        jz      @quit
@noinc:
        shl    al, 1
        jnc    @noinc
        lea    ecx, [ecx + 1]
        jnz    @noinc
@quit:
        mov    eax, ecx
end;

Ответ на »сообщение 18« (CoreWars)
___________________________

Да, лажа. Но смысл понятен...

Да, в памяти. Оптимизация по скорости потому что.
У вас, кстати, ошибка. Считает неправильно. В 5 нашел 3 единицы, в 3 - 1.

Ответ на »сообщение 16« (CoreWars)
___________________________

Самое быстрое брать ответ из таблицы (256 значений). Если нельзя использовать заранее вычисленные данные, то вычитанием и AND'ом.

Ага, а таблица в памяти хранится...

Самое быстрое брать ответ из таблицы (256 значений). Если нельзя использовать заранее вычисленные данные, то вычитанием и AND'ом.

Ответ на »сообщение 14« (Geo)
___________________________
На оптимальность не претендую. Итак, вариант №1:

inline unsigned short BitsCounter(unsigned char value)
{
  _asm {
    mov al,value
    xor cx,cx
noinc:
    shl al,1
    jz quit
    jno noinc
    inc cx
    jmp noinc
quit:
    mov ax,cx
  }
}

Ответ на »сообщение 13« (Сергей Перовский)
___________________________
Самое смешное, что наилучшее решение не зависит от процессора и является наилучшим независимо ни от чего. Честно говоря, я (когда мне эту задачу задали) до самого карсивого решения не догадался. Я тоже думал о сдвгах через CF и сложеннии с CF.

В принципе, я могу решение привести, если никто не хочет поизвращаться. Так что, как скажете.

Подсказка: "Требуется максимальная оптимизация по быстродействию. Остальные критерии несущественны".

Ответ на »сообщение 12« (Geo)
___________________________
Задача отличная. Забавно, что и тут однозначного ответа нет - на разных процессорах оптимальными по быстродействию окажутся принципиально разные алгоритмы. Дело в соотношении длительности умножения и простых операций - сложений, сдвигов и т.д.

Кстати, поситал вот сообщения и вспомнил прикольную задачку на оптимизацию.

Нужно написать функцию, которая бы получала на вход байт, а возвращала бы количество битов в этом байте, установленных в 1. Требуется максимальная оптимизация по быстродействию. Остальные критерии несущественны.

Оптимизация предусматривает наличие критерия.
Привычными для программистов являются оптимизация по памяти и по скорости. А какие еще встречаются критерии?
Мне приходит в голову оптимизация по простоте использования, по надежности, по скорости разработки, по простоте модификации.Дополнения принимаются.
Таким образом мы имеем дело с многокритериальной оптимизацией. Для нее существует понятие множества Паретто. Это множество решений, для которых для любой пары решений не существует предпочтения по всем критериям одновременно. Если по каким-то критериям лучше A то по другим B.
Не вошедшие в множество Паретто варианты не являются лучшими ни в каком смысле.
К сожалению в случае программ множество Паретто очень велико т.к. критерии сильно противоречат друг другу.
Попробуем с этой точки зрения рассмотреть применение СУБД для небольших объемов данных.
По быстродействию и (редкий случай совпадения) по используемой памяти впереди списки объектов. По скорости разработки и легкости модификации впереди "карманные" СУБД.
Выбирай, но осторожно, но выбирай: или вчера большие но по пять, или сегодня по три но маленькие (с).

Ответ на »сообщение 8« (sega-zero)
___________________________

А что? В Longhorn вроде обещали нечто подобное - файловая система на основе БД. Правда, скорее всего именно так писАться и не будет, опять тот же апи...

WinFS уже вывели из состава Longhorn

"В споре рождается истина."
Истина в споре не рождается. В споре рождаются синяки. А если серьезно, то это выражение звучит примерно так: "В споре рождается сомнение, а сомнение - первый шаг на пути к истине".

А что? В Longhorn вроде обещали нечто подобное - файловая система на основе БД. Правда, скорее всего именно так писАться и не будет, опять тот же апи...

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

Я не понимаю, почему вообще SQL-сервер не является частью операционной системы. Чтобы было можно писать

select * from 'C\windows\*.txt' where charindex('бла-бла') <> 0

Наверное, опять коммерческие штучки, без SQL можно работать, а вот без Explorer и MediaPalyer ну никак, не может kernel без музыки :)

Ответ на »сообщение 5« (bantik)
___________________________
Если все данные можно целиком загрузить в оперативную память, то возражений нет. Только непонятно, зачем это называть "База данных". Ведь этот термин уже закреплен за определенным понятием. Если же при обработке требуется подкачка с диска, то никакая CSV база данных по скорости не сравнится с нормальной реляционной базой данных.

Ты будешь смеяться, но CSV базы данных еще очень даже востребованы. Большинство систем реального времени - DSS или какие-нибудь процессинги до сих пор не работают на SQL , а используют базу попроще - вплоть до текстовых файлов. ЗА счет этого получается потрясающая скорость работы..
А надежность можно обеспечить и аппаратными средствами.

Ответ на »сообщение 3« (raic)
___________________________

Можна использовать готовое решение - заменить большие
масиви и списки (TList) на TTable. Решается 2 проблеми - нехватка памяти и бистродействие.
Проблема быстродействия не решается, так как работа с таблицей медленнее, чем работа со списком. Так что решение касается только нехватки памяти.

Кстати, если уж на то пошло, то изначально ьазы данных возникли именно для оптимизации по времени дисковых операций в случае, когда объемы данных большие и не помещаются целиком в оперативную память. Именно на таком пониманиии баз данных я и вырос. Посему сейчас просто зверею, когда к базам данных относят Access (в котором оптимизацией быстродействия и не пахнет). Или еще более крутой пример: база данных в формате CSV! Это ж надо!!! В свое время ушли от произвольных файлов данных к структурированным, чтобы оптимизировать поиск в файле. И назвали это базами данных. Сейчас понятие базы данных расширеям на файлы произвольной структуры (да еще и с записью чисел в виде строк текста). От чего ушли, к тому и вернулись. Зачем же были эти 10-15 базданческих лет. Можно было не дергаться со всякими DBase, подождать лет 10 и потребность в нем сама бы отпала :-)

Можна использовать готовое решение - заменить большие
масиви и списки (TList) на TTable. Решается 2 проблеми - нехватка памяти и бистродействие.

Ответ на »сообщение 1« (Green)
___________________________

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

Предлагаю оптимизировать код через меню "Проект-Опции", на закладке "Компилятор" включить чекбокс "Оптимизация".