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

← →
Tinky (2009-08-31 13:45) [0]

Есть множество из 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;

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

← →
Медвежонок Пятачок © (2009-08-31 13:46) [1]

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

← →
Медвежонок Пятачок © (2009-08-31 13:47) [2]

хотя множество отпадает сразу

← →
Tinky (2009-08-31 13:49) [3]

У меня постоянный предопределенный неупорядоченный набор чисел, поэтому скорее подходит название "множество" (необходимо реализовать логическую функцию "вхождение во множество"). Как записать этот набор в коде - роли не играет. Главное, чтобы работало быстро.

← →
MBo © (2009-08-31 13:50) [4]

Хэш-таблица.

← →
Tinky (2009-08-31 13:50) [5]

И конечно не хотелось бы писать:
result := (value = 29001) or (value = 29014) or ...;

← →
Медвежонок Пятачок © (2009-08-31 13:52) [6]

не хотелось бы, но придется

← →
MBo © (2009-08-31 13:58) [7]

Да, кстати, если диапазон чисел невелик, то TBits будет лучше, чем хэш-таблица.

← →
Tinky (2009-08-31 14:10) [8]

>Да, кстати, если диапазон чисел невелик, то TBits будет лучше, чем хэш-таблица.
От 10 до 30 тысяч.

Набор можно записать прямо в коде, список не подразумевает модифицирования...

← →
Сергей М. © (2009-08-31 14:22) [9]

Чтобы

> работало быстро

надо из

> неупорядоченный набор чисел

сделать

> упорядоченный набор чисел

Впрочем на множестве из 300 чисел это ловля блох

← →
Сергей М. © (2009-08-31 14:24) [10]

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

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

← →
Tinky (2009-08-31 14:33) [11]

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

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

← →
Сергей М. © (2009-08-31 14:40) [12]

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

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

← →
Anatoly Podgoretsky © (2009-08-31 14:45) [13]

> Tinky (31.08.2009 14:33:11) [11]

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

← →
Tinky (2009-08-31 14:53) [14]

Спасибо за ответы. Значит буду производить поиск делением пополам.

← →
MBo © (2009-08-31 14:54) [15]

TBits будет быстрее примерно в 10 раз на таком наборе данных.

← →
Сергей М. © (2009-08-31 14:56) [16]

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

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

← →
Anatoly Podgoretsky © (2009-08-31 15:26) [17]

> Сергей М. (31.08.2009 14:56:16) [16]

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

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

← →
Сергей М. © (2009-08-31 16:04) [18]

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

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

← →
Anatoly Podgoretsky © (2009-08-31 16:10) [19]

> Сергей М. (31.08.2009 16:04:18) [18]

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

← →
Сергей М. © (2009-08-31 17:02) [20]

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

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

> Сергей М. (31.08.2009 17:02:20) [20]

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

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

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

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

Поясни ..

← →
Sapersky (2009-08-31 18:35) [23]

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

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

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

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

← →
Sapersky (2009-08-31 20:07) [25]

(* ***** 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/

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

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

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

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

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

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

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

> Sapersky (31.08.09 18:35) [23]

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

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

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

--
Regards, LVT.

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

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

--
Regards, LVT.

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