Здравствуйте, Анатолий Широков, Вы писали:

АШ>>>Только не одновременно. Либо set + set::find, либо vector + sort + binary_search.

А>>А почему не одновременно? Вот мне совсем не очевидно, что лучше с set: его find или binary_search...

АШ>Почему не очевидно, set::iterator не является итератором произвольного доступа. Этого достаточно?

Недостаточно. При чем тут итераторы произвольного доступа?

А>Недостаточно. При чем тут итераторы произвольного доступа?

А при том, что binary_search реализует поиск методом половинного деления.

Здравствуйте, dar veter, Вы писали:

DV>Здравствуйте, Анатолий Широков, Вы писали:

АШ>>unsigned int bitset = 1;
АШ>>unsigned int element = 0;

АШ>>bool exist = (1 << element) & bitset);

DV> Брр .... сорри не понял, как это применить... например:
DV> Необходимо определить, является WORD w членом вот этого массива
DV> {0x7E7E, 0x3F3F, 0x9F9F, 0xCFCF, 0xE7E7, 0xF3F3, 0xF9F9, 0xFCFC} ?

Битовая арифметика пригодна для чисел в диапазоне 0..31.

// пустое множество и универсум
#define ZSET (0L)
#define USET (~ZSET)
#define ELEM_LBOUND (0)
#define ELEM_UBOUND (CHAR_BIT * sizeof(long)) // общая формула.
// элемент должен быть в пределах [ELEM_LBOUND .. ELEM_UBOUND-1]

// одноэлементное множество
#define ESET(e) (1 << (e)) // 0 <= e < ELEM_LBOUND

// теоретико-множественные операции
#define COMBINE(a,b)   ((a)|(b))  // a U b
#define INTERSECT(a,b) ((a)&(b))  // a ^ b
#define SUBTRACT(a,b)  ((a)&~(b)) // a \ b

// предикаты
#define SUBSET(a,b)  (SUBTRACT(a,b) != ZSET) // a <= b
#define BELONGS(e,s) SUBSET(ESET(e),s) // e in s

Если хочешь — делай это макросами, если не хочешь — инлайнами

Для небольшого диапазона чисел (скажем, до 256) можно пользоваться std::bitset'ом.
Для бОльших и сильно разреженных множеств — std::set.
(В bitset'е на один элемент тратится 1 бит, а в set — порядка 20 байт).

Здравствуйте, Анатолий Широков, Вы писали:

А>>Недостаточно. При чем тут итераторы произвольного доступа?

АШ>А при том, что binary_search реализует поиск методом половинного деления.

И что?

Здравствуйте, Кодт, Вы писали:

К>#define ELEM_UBOUND (CHAR_BIT * sizeof(long)) // общая формула.

Значащих разрядов может быть меньше.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Анатолий Широков, Вы писали:

А>>>Недостаточно. При чем тут итераторы произвольного доступа?

АШ>>А при том, что binary_search реализует поиск методом половинного деления.

А>И что?

А то, что поиск расстояния (std::distance) для контейнеров не поддерживающих итераторы произвольного доступа равна O(N). Тогда как для контейнеров с итераторами произвольного доступа это O(1).

Здравствуйте, dar veter, Вы писали:

А>>Набор значений именно таков?
DV> Да ... именно таков ... это комбинации сигнальной единицы одного прибора, для которого пишется это программа... точнее переписывается с Delphi

Это очень специфичный набор. Прежде всего, бросается в глаза то, что в зацикленных двоичных представлениях чисел шестерки едениц разделены двойками нулей. Но для написания эффективного по времени кода это вряд ли будет полезно (хотя, с другой стороны, для манипуляции с битами не нужно обращаться к памяти, и это может очень выручить).

Тут можно либо просто switch устроить, либо...

Обратим внимание, что в "годных" значениях старший байт точно равен младшему:

WORD x = ...;
int y = x & 0xFF;
if (x >> 8 != y)
return false;

Дальше получаем байт y.

Наиболее эффективный способ, пожалуй, будет таков: завести таблицу из 256 значений:

static const bool good[256] = {0, 0, 0, ..., 0, 1, 0, 0, ..., 0 };

Единицы в ней поместить в позициях 0x7E, 0x3F, 0x9F, 0xCF...

А затем:

return good[y];

В общем, для получения шустрого кода нужно поэкспериментировать.

Здравствуйте, Анатолий Широков, Вы писали:

АШ>>>А при том, что binary_search реализует поиск методом половинного деления.

А>>И что?

АШ>А то, что поиск расстояния (std::distance) для контейнеров не поддерживающих итераторы произвольного доступа равна O(N). Тогда как для контейнеров с итераторами произвольного доступа это O(1).

Прекрасно. Теперь вернемся к теме: почему предпочтительней set::find?

А>Прекрасно. Теперь вернемся к теме: почему предпочтительней set::find?

Потому что set::find осуществляет поиск в бинарном дереве, то есть движение он начинает с корня (середины) и этот корень set::find знает, тогда как binary_search должен на каждом шаге отыскать корень (середину).

Здравствуйте, achp, Вы писали:

A>Наиболее эффективный способ, пожалуй, будет таков: завести таблицу из 256 значений:

A>static const bool good[256] = {0, 0, 0, ..., 0, 1, 0, 0, ..., 0 };

A>Единицы в ней поместить в позициях 0x7E, 0x3F, 0x9F, 0xCF...

A>А затем:

A>return good[y];

A>В общем, для получения шустрого кода нужно поэкспериментировать.
По моему самый шустрый вариант, будет этот... только вот две операции взятия из памяти...
вообщем поэксперементирую со switch ... с этим вариантом... там видно будет :о)

Здравствуйте, Анатолий Широков, Вы писали:

А>>Прекрасно. Теперь вернемся к теме: почему предпочтительней set::find?

АШ>Потому что set::find осуществляет поиск в бинарном дереве, то есть движение он начинает с корня (середины) и этот корень set::find знает, тогда как binary_search должен на каждом шаге отыскать корень (середину).

Да, Вы правы, конечно. Такое количество инкрементов итератора безусловно перевесит выигрыш от возможного уменьшения количества сравнений.

Спасибо.

Здравствуйте, dar veter, Вы писали:

A>>В общем, для получения шустрого кода нужно поэкспериментировать.
DV> По моему самый шустрый вариант, будет этот... только вот две операции взятия из памяти...
DV> вообщем поэксперементирую со switch ... с этим вариантом... там видно будет :о)

Побаловаться с битами тоже очень советую. Даже довольно длинный алгоритм (5-7 инструкций) может оказаться быстрей, чем доступ к памяти, если потребуется подгрузка кэш-линеек. Впрочем, это заметно зависит от процессора.

Какой используете компилятор? Обычно свитч сводится к тривиальному преобразованию для получения индекса, условию граничной проверки и переходу по адресу, выбираемому как индекс из массива, что, очевидно, (почти всегда) быстрее, чем дельфевский <value> in <set>.
Опять же, можно как обычно сделать все это "вручную", получая индекс по своему алгоритму, особенно если числа специфичные.
В данном случае (0x7E7E, 0x3F3F, 0x9F9F, 0xCFCF, 0xE7E7, 0xF3F3, 0xF9F9, 0xFCFC), очевидно, что значимым является только один байт. Далее рассмотрим все значения в двоичном виде — замечаем, что _каждом_ все биты установлены, кроме 2-х рядом стоящих (для 0x7E мы имеем 01111110,что при циклическом сдвиге даст желаемый результат).
Итак, задача сводится к проверке, что в числе 6 бит установлено, а 2 — сброшено, причем эти 2 находятся в циклически соседних позициях.
Представим, что нам надо поподробнее.
1. Получить индекс первого сброшенного бита справа (ну, или, проинвертировав число, установленого — без разницы).
2. Проверить следующий бит (т.к. число состояит из 2-х одинаковых байт, то выход за границы байта в этом случае нам не страшен — 8-й бит будет равен 0-му). Если этот бит также сброшен (установлен) — тогда это искомое число.

Алгоритм _быстрого_ нахождения первого установленного (или сброшенного) бита смотреть здесь или использовать BSF/BSR, но тут мы теряем переносимость.

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


DV>Тогда как быть .... писать на ассме ? ... Почему-то использование switch генерит нерациональный код ?

Здравствуйте, dar veter, Вы писали:

DV>Прошу сильно меня не пинать, но ответе пожалуйста на такой вопрос....
DV>В Delphi есть такой оператор in и выполняет он операцию For an ordinal O and a set S, O in S is True just in case O is a member of S.
DV>В С++ есть что нибудь подобное ??? А то я найти не могу

Наболее близким аналогом паскалевских set-ов является шаблон класса 'std::bitset' из стандартной библиотеки C++.

Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>Наболее близким аналогом паскалевских set-ов является шаблон класса 'std::bitset' из стандартной библиотеки C++.

Но, как выяснилось, исходный вопрос не имел ко всему этому никакого отношения...

Здравствуйте, achp, Вы писали:

A>Здравствуйте, Андрей Тарасевич, Вы писали:

АТ>>Наболее близким аналогом паскалевских set-ов является шаблон класса 'std::bitset' из стандартной библиотеки C++.

A>Но, как выяснилось, исходный вопрос не имел ко всему этому никакого отношения...
Не совсем то, просто исходный вопрос плавно перерос во второй вопрос ...
Вообщем то всем ОГРОМНОЕ СПАСИБО

Здравствуйте, Andrew S, Вы писали:

AS>Итак, в результате мы получаем в минимуме 3 сдвига, 3 сравнения и 3 сложения. Достаточно оптимально, не правда ли?

Вообщем различные эксперементы и показания профилировщика, показали что самый быстрый метод в моей задаче оказался этот:

bool IsSignalOne(WORD w)
{
__asm {
        movzx eax,w;
        cmp ax,0x7e7e;
        jz go_true;
        movzx ecx,al;
        not cl;
        bsr ecx,cl;
        ror ax,cl;
        cmp ax,0x7e7e;
        jnz go_false;
go_true:
        mov eax,1;
        jmp go_end;
go_false:
        xor eax,eax;
go_end:
    }
}

На Пенке 700Mgz данный код выполняется ~50 наносек, сгенерированый код компилятором для switch выполняется ~120 наносек.