Очень простой цикл

[ilovb]

Чета тут обобщать задачу начали. info21 циклом дейкстры махает... Лично я код писал под конкретную задачу.
Если уж обобщать, то бойер-мур...   

Я не обобщал. Честно-честно!

Та не... Я про то, что начали распространять на произвольную длину шаблона (как тут)

[valexey]

только без вые..онов  - Это раз, Влад знал задачу ПОЛНОСТЬЮ - в отличии от других, это два...

Дык задача полностью была раскрыта еще на первой странице обсуждения 25го мая: http://oberspace.dyndns.org/index.php/topic,253.msg6094.html#msg6094

[DIzer]

только без вые..онов  - Это раз, Влад знал задачу ПОЛНОСТЬЮ - в отличии от других, это два...

Дык задача полностью была раскрыта еще на первой странице обсуждения 25го мая: http://oberspace.dyndns.org/index.php/topic,253.msg6094.html#msg6094

Тык это произошло только после того как я поднял "вонь", да и то, не сразу...

[ilovb]

Хм.. А я первое сообщение смотрел. 

[Peter Almazov]

В борьбе с рукосуйством и мракобесием Info21 малость обосрался.

"Рукосуи, не понимающие, с чем "едят" ЦД (это про альтернативно удаленных), не въезжают, что конъюнкция отрицаний охран сразу доказывает корректность цикла:
(i >= LEN(a)) OR (oneZero & (a[ i]=0))"

Конъюнкция отрицаний охран, дорогой товарищ, НЕ доказывает корректность цикла. Ни сразу ни потом. Корректность цикла доказывает конъюнкция отрицаний охран & инвариант цикла. Игнорирование последнего весьма характерно для любителей линейного поиска во главе с Info21. Инвариант им на хрен не нужен, я как-то писал об этом на оберонкоре. Само собой, то сообщение было удалено Темиргалеевым.

Кроме того, Info21 не мешало бы прочитать переведенную им же книгу и понять, что в случае массива можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль. О чем черным по белому было сказано здесь http://oberspace.dyndns.org/index.php/topic,253.msg6115.html#msg6115

[ilovb]

Наверно торможу но не понял что значит:

можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль

Разве на двух элементах будет профит?

Или типа как я сэкономил?
http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133

ps У меня кстати там ошибка есть. Я не учитываю, что длина массива может быть < 2.
Ну т.е. все это нужно в IF засунуть

[DIzer]

Разве на двух элементах будет профит?

Да , будет ( и уточненные условия Влада его допускают )- проблема в том, что  Петр не привел решение
и по этому out of contest (хотя ,я не уверен, что сгенерированный машинный код будет оптимален).

[ilovb]

Понятно что на таком раскладе будет экономия в 2 раза:

[01][01][01][01][10][0]

Слева направо проверяем каждый второй элемент. Если нуль то проверяем первый. И в конце если количество элементов нечетное (дешевая проверка), то проверяем последний элемент.

Но какова вероятность такого расклада?

У бойера-мура эта стратегия хорошо работает на длинных шаблонах имхо

p.s. Хотя следует признать, что в среднем будет больше экономии чем у меня

[DIzer]

единственный момент,  ilovb, здесь существенно используется техника сокращенных вычислений логических выражений, а если вы хотите получить gain прыгая через блок (2 х элементный), пофигу первый 0 вы вставляете в начало условия (ищите) или второй ...

[Губанов Сергей Юрьевич]

можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль

Кстати можно исходный двухбайтовый wchar_t* привести к четырёхбайтовому int* и всё свести к обычному линейному поиску четырёхбайтового нуля. 

[vlad]

Да ладно..."некто Vlad"     - среди приведенных здесь вариантов не требующих особых знаний,
но "с претензиями" - это одно из внятных (мне лично, оно нравится больше вашего).

Ты уверен, что при сравнении оставил за скобками мелочи типа сишного синтаксиса и адресной арифметики, которые могут не нравится сами по себе? Кроме того, мое решение учитывает конкретную задачу (не только найти нули, но и по дороге собрать нужные данные). В чистом виде (только поиск нулей) я бы написал что-то очень похожее на последний вариант Сергея. Только вложенный цикл вытащил бы в функцию. Что-то типа:

Код: [Выделить]

while ((next = find_zero(next))[1])
    next += 2;

Куда здесь воткнуть цикл Дейкстры, чтоб оно было более наглядно/доказательно - не представляю...

[vlad]

можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль

Кстати можно исходный двухбайтовый wchar_t* привести к четырёхбайтовому int* и всё свести к обычному линейному поиску четырёхбайтового нуля. 

wchar_t бывает 32-битным, причем не на самых экзотических платформах (Мак). Кроме того, даже в случае 16-битного wchar_t - два нуля могут лечь между двумя 32-битными int.

[DIzer]

да , пример [10][01] - конец поиска лежит на границе блоков, по этому если без "претензий"

Код: [Выделить]

i:=1;
WHILE !( (A[i-1]=0) & (A[i]=0)) DO
INC(i)
END;
  если мы хотим скорости , то раскрываем  условие по правилам де Моргана - в ЯП с гарантированным использованием укороченной схемы вычисления логических выражений будет и  профит (без мозго..ства).

[Губанов Сергей Юрьевич]

wchar_t бывает 32-битным, причем не на самых экзотических платформах (Мак). Кроме того, даже в случае 16-битного wchar_t - два нуля могут лечь между двумя 32-битными int.

C#:
char - 2 byte
int - 4 byte
long - 8 byte

char* p = begin;
while (*((int*)p) != 0)
{
  p++;
}

n = (long)(p - begin);

[vlad]

C#:
char - 2 byte
int - 4 byte
long - 8 byte

Да, так будет работать на платформах с указанными размерами char и int.  При условии, что доступ к невыровненным данным не вызывает исключения