Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Проверить integer на вхождение во множество

Страницы: 1 2 >
Tinky © (2009-08-31 13:45:00)
Есть множество из 300 предопределенных констант (чисел).
Нужно написать функцию, которая будет возвращать результат типа boolean, говорящий о том, входит ли переданный параметр в это множество.
Набор чисел известный и постоянный (около 300 значений):
29001
29014
29020
...
25625
25626
29163
25666

Как это лучше всего (правильнее) сделать?

function IsInArray(value: integer): boolean;
begin
case value of
29001, 29014, ..., 29163, 25666: result := true;
else result := false;
end;
end;

Функция будет использоваться очень часто (сотни раз в минуту) и время выполнения критично.

Leonid Troyanovsky (2009-08-31 22:14:00) [1]

> Leonid Troyanovsky © (31.08.09 22:07) [28]

Млин, квотирование оказалось неточным, sorry,
но от сути я не отказываюсь.

--
Regards, LVT.

Leonid Troyanovsky (2009-08-31 22:07:00) [2]

> Sapersky (31.08.09 18:35) [23]

> По-любому будет работать ощутимо быстрее аналогичного по
> функциональности программного цикла.

Но, сравнивать, IMHO, следует лишь с

> MBo © (31.08.09 13:58) [7]

--
Regards, LVT.

Сергей М. (2009-08-31 22:04:00) [3]

> Anatoly Podgoretsky © (31.08.09 21:47) [26]

Да, я неверно истолковал "код Дельфи" - показалось, что речь идет о штатных юнитах, включаемых в проекты, таких как system, sysutils и иже с ними.

Я в курсе, что агрегаты работают несколько медленнее эквивалентным им явно организованным циклам.

Anatoly Podgoretsky (2009-08-31 21:47:00) [4]

> Навскидку не вижу причин, по которым там при необходимости
> не могли бы фигурировать и xxxsd..

Могут, только вот необходимость еще надо найти, де факто аггрегатные функции работают медленнее, чем пара dec ecx, jnz label

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

> А ты посмотри код Дельфи, нигде не генерируется код с rep и с xxxsd,

Sapersky (2009-08-31 20:07:00) [5]
(* ***** BEGIN LICENSE BLOCK ***** * * The function CompareMem is licensed under the CodeGear license terms. * * The initial developer of the original code is Fastcode * * Portions created by the initial developer are Copyright (C) 2002-2004 * the initial developer. All Rights Reserved. * * Contributor(s): Aleksandr Sharahov * * ***** END LICENSE BLOCK ***** *) function CompareMem(P1, P2: Pointer; Length: Integer): Boolean; assembler; asm add eax, ecx add edx, ecx xor ecx, -1 add eax, -8 add edx, -8 add ecx, 9 push ebx jg @Dword mov ebx, [eax+ecx] cmp ebx, [edx+ecx] jne @Ret0 lea ebx, [eax+ecx] add ecx, 4 and ebx, 3 sub ecx, ebx jg @Dword @DwordLoop: mov ebx, [eax+ecx] cmp ebx, [edx+ecx] jne @Ret0 mov ebx, [eax+ecx+4] cmp ebx, [edx+ecx+4] jne @Ret0 add ecx, 8 jg @Dword mov ebx, [eax+ecx] cmp ebx, [edx+ecx] jne @Ret0 mov ebx, [eax+ecx+4] cmp ebx, [edx+ecx+4] jne @Ret0 add ecx, 8 jle @DwordLoop @Dword: cmp ecx, 4 jg @Word mov ebx, [eax+ecx] cmp ebx, [edx+ecx] jne @Ret0 add ecx, 4 @Word: cmp ecx, 6 jg @Byte movzx ebx, word ptr [eax+ecx] cmp bx, [edx+ecx] jne @Ret0 add ecx, 2 @Byte: cmp ecx, 7 jg @Ret1 movzx ebx, byte ptr [eax+7] cmp bl, [edx+7] jne @Ret0 @Ret1: mov eax, 1 pop ebx ret @Ret0: xor eax, eax pop ebx end;

Ну и вообще: http://fastcode.sourceforge.net/

Сергей М. (2009-08-31 19:42:00) [6]

> D2006 ..CompareMem ..быстрее CMPSD/B
> в 1.8-4.5 раза, в зависимости от размера данных

Любопытно было бы глянуть на ту реализацию ..

Sapersky (2009-08-31 18:35:00) [7]
По-любому будет работать ощутимо быстрее аналогичного по функциональности программного цикла.

Необязательно, скорее даже - медленнее. В D2006 и далее старые системные функции понемногу заменяются на оптимизированные из проекта FastCode. Например, CompareMem (автор Sha, кстати) - цикл с развёрткой быстрее CMPSD/B в 1.8-4.5 раза, в зависимости от размера данных.
Хотя оптимизация не всегда оказывается удачной - новый Move (использующий в основном FPU) на больших объёмах у меня оказался чуть медленнее старого.

Сергей М. (2009-08-31 17:15:00) [8]

> нигде не генерируется код с rep и с xxxsd

repxx scas[b|w] фигурирует как минимум в system, sysutils, classes, forms.

Навскидку не вижу причин, по которым там при необходимости не могли бы фигурировать и xxxs d..

Поясни ..

Anatoly Podgoretsky (2009-08-31 17:05:00) [9]
> Сергей М. (31.08.2009 17:02:20) [20]

А ты посмотри код Дельфи, нигде не генерируется код с rep и с xxxsd, и это не зря, а кроме того я измерял со stosb, разница в разы может быть.

Сергей М. (2009-08-31 17:02:00) [10]

> Anatoly Podgoretsky © (31.08.09 16:10) [19]

По-любому будет работать ощутимо быстрее аналогичного по функциональности программного цикла.

Anatoly Podgoretsky (2009-08-31 16:10:00) [11]
> Сергей М. (31.08.2009 16:04:18) [18]

Да без разницы - это все аггрегатные функции.

Сергей М. (2009-08-31 16:04:00) [12]

> Anatoly Podgoretsky © (31.08.09 15:26) [17]

Пардон, не CMPSD, а SCASD

Anatoly Podgoretsky (2009-08-31 15:26:00) [13]
> Сергей М. (31.08.2009 14:56:16) [16]

Я бы поддержал это предложение, но

1. ассемблерная команда, значит сильная завязка.
2. поддержал бы на 386 и не выше. Командна очень медленная на Пентиумах и их потомках.

Сергей М. (2009-08-31 14:56:00) [14]

> поиск методом деления пополам, на упорядоченом множестве

Оно так, но на определенных размерах множеств с определенным выравниванием и распределением конкурентом вполне м.б. инструкция REP CMPSD

MBo (2009-08-31 14:54:00) [15]
TBits будет быстрее примерно в 10 раз на таком наборе данных.

Tinky (2009-08-31 14:53:00) [16]
Спасибо за ответы. Значит буду производить поиск делением пополам.

Anatoly Podgoretsky (2009-08-31 14:45:00) [17]
> Tinky (31.08.2009 14:33:11) [11]

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

Сергей М. (2009-08-31 14:40:00) [18]

> будет ли оптимальным использование простого case

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

Tinky (2009-08-31 14:33:00) [19]
>Что мешает его сразу записать упорядоченным, скажем. по возрастанию?

Ничего =) Вопрос в том, будет ли оптимальным использование простого case, или стоит создавать таблицу или заполнять массив, а потом каждый раз проводить поиск.

Сергей М. (2009-08-31 14:24:00) [20]

> Набор можно записать прямо в коде

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

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »