Oberon space
General Category => Общий раздел => Тема начата: vlad от Май 25, 2012, 03:02:45 pm
-
Раз уж речь пошла про циклы... :) Дана последовательность. Найти позицию первого из двух последовательно идущих нулевых элементов. Кто какой цикл считает самым правильным?
1 0 1 1 0 1 0 1 0 0 ...
---------------^
P.S. 2Илья: твой вариант интересен как референсный от школы научного составления циклов.
-
Раз уж речь пошла про циклы... :) Дана последовательность. Найти позицию первого из двух последовательно идущих нулевых элементов. Кто какой цикл считает самым правильным?
1 0 1 1 0 1 0 1 0 0 ...
---------------^
P.S. 2Илья: твой вариант интересен как референсный от школы научного составления циклов.
Корявое задание... но лично я за самый простой и наглядный... пусть 2 нуля являются терминальными членами, и получение осуществляется с помощью функции getel() и минимальное число элементов в последовательности >=2, тогда (конечные автоматы не трогаем)
st1:=getel(); st2:=getel(); ind:=0;
WHILE ~((st1=0) & (st2=0)) DO
INC(ind); st1:=st2; st2:=getel();
END;
где то так....
-
Условия слишком нечеткие. Одно дело массив, когда можно заглядывать вперед, другое дело, скажем, ленивая последовательность.
Что значит "правильным". Лишнее сравнение в случае массива - это правильно?
-
Условия слишком нечеткие. Одно дело массив, когда можно заглядывать вперед, другое дело, скажем, ленивая последовательность.
Что значит "правильным". Лишнее сравнение в случае массива - это правильно?
Заглядывать вперед можно (но не за второй 0). "Правильным" - с поправкой на ваши личные пристрастия. Для кого-то это будет максимально формальная запись (классический конечный автомат в пределе), для кого-то максимально короткая и т.д.
-
Действительно, может быть много вариантов... Но если начинать с самого простого, с массивом, без выборки во вспом. переменные, я бы строил так:
i := 1;
WHILE (i < n) & ~((mas[i-1] = 0) & (mas[i] = 0)) DO
INC(i)
END;
IF i < n THEN
i-1 - искомый
ELSE
не найден
END
Цикл работает с последовательностью любой длины.
Если не массив, а поток, то вариант Dizera...
--- кстати, про КА я тоже сразу подумал, если бы задачка была чуть сложнее, уже стоило бы строить КА...
-
Действительно, может быть много вариантов... Но если начинать с самого простого, с массивом, без выборки во вспом. переменные, я бы строил так:
Ага. Т.е., в принципе тебя и Дизера не коробит "двойная проверка" одних и тех же элементов? И постройки КА такая задачка не достойна?
-
да , можно и так... но меня смутили пробельные символы между цифрами.. и я не стал напрягаться...
-
Действительно, может быть много вариантов... Но если начинать с самого простого, с массивом, без выборки во вспом. переменные, я бы строил так:
Ага. Т.е., в принципе тебя и Дизера не коробит "двойная проверка" одних и тех же элементов? И постройки КА такая задачка не достойна?
НЕТ - я же сказал, что за наглядность.... а КА не стал строить (а так же заниматься "выкрутасами") по причине темы -"Очень простой цикл".и кроме того если автор, темы коряво ее подает не фиг вообще напрягаться..
-
и кроме того если автор, темы коряво ее подает не фиг вообще напрягаться..
Вот оригинальные данные: http://msdn.microsoft.com/en-us/library/windows/desktop/ms683187(v=vs.85).aspx
Оригинальная задача: сложить полученные строки в массив.
Сначала у меня была идея, собственно, найти два нуля (конец), а потом воспользоваться библиотечной tokenize (указав нули как разделители). Да, и я тоже думал о примерно таких циклах как вы с Ильей привели. Но мне такой цикл показался слишком страшным только для того, чтобы найти конец. Поэтому я в итоге написал так:
wchar_t* env = ::GetEnvironmentStringsW();
...
wchar_t* next;
while ((next = ::wcschr(env, '\x0')) > env)
{
result.push_back(std::wstring(env, next));
env = next + 1;
}
-
Понял.. 2 Vlad- мне не нравится ваше решение... просто по тому, что оно
1. Не является наглядным
2. Низкоуровневое
ИМХО
1. мое нагляднее (отражает 1 в 1 высокоуровневый алгоритм)
2. легко РЕАЛИЗУЕТСЯ на ЛЮБОМ императивном ЯП
3. знаний собственно ЯП (и подлежащих моделей) - не требуется.
Но разумеется если ТРЕБУЕТСЯ производительность, то его нужно модифицировать в соответствии с вашими замечаниями...
-
В этой задаче, при решении на Обероне, я предпочту раскрутить одну итерацию, как-то так
входные данные
n # 0, result = -1 (индексы начинаются с 0), i = - 1
WHILE ( r < 0 ) & ( i < n ) DO
INC (i);
IF Arr[i] = 0 THEN
INC(i);
IF Arr[i] = 0 THEN r := i; DEC(r) END;
END;
END;
-
В этой задаче, при решении на Обероне, я предпочту раскрутить одну итерацию, как-то так
входные данные
n # 0, result = -1 (индексы начинаются с 0), i = - 1
WHILE ( r < 0 ) & ( i < n ) DO
INC (i);
IF Arr[i] = 0 THEN
INC(i);
IF Arr[i] = 0 THEN r := i; DEC(r) END;
END;
END;
Что будет, если второй ноль окажется вне строки?
-
Что будет, если второй ноль окажется вне строки?
Жадность фраера сгубила )))
Изначально у меня было 2 условных INC, я одним пожадничал, свернул условия и удалил один инкремент, а второй вынес в начало итерации, а условие цикла не поправил, в результате получилась лишняя итерация
WHILE ( r < 0 ) & ( i < n-1 ) DO
INC (i);
IF Arr[i] = 0 THEN
INC(i);
IF Arr[i] = 0 THEN r := i; DEC(r) END;
END;
END;
-
2 Kemet Ну и как стоит ваша "развертка" ошибок? ;)
-
2 Kemet Ну и как стоит ваша "развертка" ошибок? ;)
Да, в принципе, ошибка дурацкая, из-за спешки и расслабухи.
Но раскрутка цикла в данном примере дает существенный профит
-
Что будет, если второй ноль окажется вне строки?
Жадность фраера сгубила )))
К сожалению, на таких ошибках ловят... Если второй проверяемый символ окажется "за границей", то возникает исключение, которое уже перехвачено... в стеке... исключений. Но такой код не пишется первоклашками, а теми, кем пишется, не решаются частные задачи...
-
Что будет, если второй ноль окажется вне строки?
Жадность фраера сгубила )))
К сожалению, на таких ошибках ловят... Если второй проверяемый символ окажется "за границей", то возникает исключение, которое уже перехвачено... в стеке... исключений. Но такой код не пишется первоклашками, а теми, кем пишется, не решаются частные задачи...
:( беда в том, что пишется- по крайней мере делаются попытки... - а некоторые умудряются писать нечто подобное и на контрольных работах... да что там, я страдал на первом курсе такой болезнью... все хотел "оптимальности" - толком не понимая даже что это такое...
-
Поиск подпоследовательности из 2 символов:
public static int Search (int[] a, int N, int firstSymbol, int secondSymbol)
{
int result = -1;
if (N >= 2)
{
int n = 0;
do
{
while ((n < N - 1) && !(a[n] == firstSymbol))
{
n++;
}
n++;
}
while ((n < N) && !(a[n] == secondSymbol));
if (n < N)
{
result = n - 1;
}
}
return result;
}
Поиск подпоследовательности из 3 символов:
public static int Search (int[] a, int N, int firstSymbol, int secondSymbol, int thirdSymbol)
{
int result = -1;
if (N >= 3)
{
int n = 0;
do
{
do
{
while ((n < N - 2) && !(a[n] == firstSymbol))
{
n++;
}
n++;
}
while ((n < N - 1) && !(a[n] == secondSymbol));
n++;
}
while ((n < N) && !(a[n] == thirdSymbol));
if (n < N)
{
result = n - 2;
}
}
return result;
}
Аналогично для 4, 5 и т. д. символов.
-
Плохо.
В случае поиска в массиве надо начинать проверку со второго символа (с конца). Если он не 0, то можно продвинуться сразу на 2. (поиск 00)
-
К сожалению, на таких ошибках ловят... Если второй проверяемый символ окажется "за границей", то возникает исключение, которое уже перехвачено... в стеке... исключений. Но такой код не пишется первоклашками, а теми, кем пишется, не решаются частные задачи...
Так я первоклашка-двоечник )
Это же просто цикл, зачем в него проверку предусловий, очевидно, что такие действия производятся до входа в цикл, на то они и предусловия, и если мы до него дошли, значит там есть что искать.
-
К сожалению, на таких ошибках ловят... Если второй проверяемый символ окажется "за границей", то возникает исключение, которое уже перехвачено... в стеке... исключений. Но такой код не пишется первоклашками, а теми, кем пишется, не решаются частные задачи...
Так я первоклашка-двоечник )
Нет, нет... речь не о Вас, а о том, что на таком уровне (перехват PAGE_FAULT и т.п.) работают профи, труд которых оплачивается из специальных фондов... не менее специальных служб...
В своё время попадалась интересная работа израильтян, где описывались некоторые принципы/методы... например, там говорилось о том, что не надо трогать основной код, но надо фильтровать все исключения... Метод прост и эффективен и не требует внедрения внутрь нулевого кольца...
-
Так я первоклашка-двоечник )
Это же просто цикл, зачем в него проверку предусловий, очевидно, что такие действия производятся до входа в цикл, на то они и предусловия, и если мы до него дошли, значит там есть что искать.
Хорошо составленный цикл с условием, как правило, расчитан на выполнение [0..+inf) раз.
Если мы смотрим на программу и видим, что цикл в ней выполняется не менее 1 раза, а сверху навешано условие, чтобы "отсечь" ситуацию 0 раз, то, как правило, можно и нужно преобразовать цикл так, чтобы он был "сам себе условие" на все случаи.
-
Хорошо составленный цикл с условием, как правило, расчитан на выполнение [0..+inf) раз.
Если мы смотрим на программу и видим, что цикл в ней выполняется не менее 1 раза, а сверху навешано условие, чтобы "отсечь" ситуацию 0 раз, то, как правило, можно и нужно преобразовать цикл так, чтобы он был "сам себе условие" на все случаи.
Илья, с методической стороны это, несомненно, верно, и об этом, тоже несомненно, нужно всегда помнить и переходить к следующему шагу оптимизации цикла только после исчерпания возможности преобразования условий вхождения.
С практической - ситуации могут быть разные. Если перед каждой итерацией для проверки истинности условия мы делаем скрытый паразитический декремент ([i-1]), потому, что вошли в цикл не с 0-го а с 1-го индекса, и поэтому вынуждены откатываться назад для проверки, то, по крайней мере для меня, лучше проверить перед циклом, чтобы не накапливать паразитические инструкции.
-
Я бы тогда просто завёл две переменных, i0, i1...
i0 := 0; i1 := 1
-
Если мы смотрим на программу и видим, что цикл в ней выполняется не менее 1 раза, а сверху навешано условие, чтобы "отсечь" ситуацию 0 раз, то, как правило, можно и нужно преобразовать цикл так, чтобы он был "сам себе условие" на все случаи.
Ты предлагаешь отказаться от цикла REPEAT-UNTIL. Зачем?
-
Нет, нет... речь не о Вас,
Как раз обо мне, видимо пора в детский сад или на пенсию, я позволил сбить себя с толку, потому что правильным (для меня) являлся первый вариант, так как на очередном шаге оптимизации я вынес выражение n-1 из цикла, вычислив его один раз.
-
Если мы смотрим на программу и видим, что цикл в ней выполняется не менее 1 раза, а сверху навешано условие, чтобы "отсечь" ситуацию 0 раз, то, как правило, можно и нужно преобразовать цикл так, чтобы он был "сам себе условие" на все случаи.
Ты предлагаешь отказаться от цикла REPEAT-UNTIL. Зачем?
Во-первых, у меня "а сверху навешано условие...".
Т.е. если ситуация объективно позволяет REPEAT-UNTIL, то почему нет. А если уже после постановки охраны в IF стало возможным - то нафиг нужно IF + REPEAT вместо WHILE.
По поводу REPEAT - реально только в единственных случаях с ним сталкиваюсь - где идут попытки чего-то сделать до тех пор, пока работа не исчерпается. Пытаться послать в неблокирующий поток, пока длина оставшихся не будет 0, и т.п.
-
cur := findNext();
prev := cur;
WHILE (cur < len) & (cur - prev # 1) DO
prev := cur;
cur := findNext()
END;
IF cur < len THEN use(prev) END
-
на хацкеле что ли привести вариант:
xs = [1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1]
find_zeroes [] = error "Empty list!"
find_zeroes (y:ys) = find y ys 0
where
find 0 (0:zs) n = n
find _ (z:zs) n = find z zs (n+1)
find _ [] _ = error "Not found!"Ваще наверное правильнее было бы оформить в виде связки map-fold-zip, но лень...
-
1С (если нигде не накололся)
Процедура КнопкаВыполнитьНажатие(Кнопка)
Массив = Новый Массив;
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(1);
Массив.Добавить(0);
Массив.Добавить(0);
Граница = Массив.ВГраница();
ТекущийИндекс = 0;
Пока ТекущийИндекс < Граница Цикл
СледующийИндекс = ТекущийИндекс + 1;
Если Массив[ТекущийИндекс] = 0 Тогда
Если Массив[СледующийИндекс] = 0 Тогда
Граница = 0; // нашли
Иначе
ТекущийИндекс = СледующийИндекс + 1;
КонецЕсли;
Иначе
ТекущийИндекс = СледующийИндекс;
КонецЕсли;
КонецЦикла;
Если Граница = 0 Тогда
Сообщить(ТекущийИндекс);
Иначе
Сообщить("Хрен");
КонецЕсли;
КонецПроцедуры
-
Переменная СледующийИндекс конечно не нужна если компилер оптимизирующий
-
для разнообразия :) однострочная функция на мампсе
00(x) new p set p=$find(x,$char(0,0)) set:p p=p-2 quit p
возвращает номер позиции (отсчёт с 1) первого из двух подряд нулевых байтов в входной строке x или 0, если таковых нет
-
А что значит "00(x)"? :)
Я так понимаю это библиотечный поиск паттерна в массиве как в строке?
-
для разнообразия :) однострочная функция на мампсе
00(x) new p set p=$find(x,$char(0,0)) set:p p=p-2 quit p
возвращает номер позиции (отсчёт с 1) первого из двух подряд нулевых байтов в входной строке x или 0, если таковых нет
не ну ежели на то пошло, то я тоже могу передлать свой вариант в однострочник:
find_zeroes (y:ys) = find y ys 0 where find 0 (0:_) n = n; find _ (z:zs) n = find z zs (n+1)
Только понятность резко упала, имхо... )))
-
А что значит "00(x)"? :)
Я так понимаю это библиотечный поиск паттерна в массиве как в строке?
00 - это я такое имя дал функции.
это просто поиск в строке ( в мампсе строки могут содержать любые байты от 0 до 255)
Боюсь, что многое в мампсе будет вызывать вопросы :)
-
Только понятность резко упала, имхо... )))
Вот многострочный вариант :)
00(x)
new p
set p=$find(x,$char(0,0))
set:p p=p-2
quit p
-
00 - это я такое имя дал функции.
Имя из цифр! Круто ;D
-
Имя из цифр! Круто ;D
Ну, если бы были допустимы русские буковки в идентификаторах, то можно было бы назвать так :)
ИГдеТутУНасНуликиСпрятались(x)
-
Я однажды написал процедуру "НажатиеНаЯйца(Кнопка)".
В интерфейсе кассира была кнопка "Яйца" ну и ... :)
А эту процедуру я бы назвал "НайтиЯйца(Ячейки)" ;D
-
MODULE ms;
IMPORT StdLog, seq;
(*
MODULE seq;
VAR
oes*, open: BOOLEAN;
len, pos: LONGINT;
(* ~undefined(open) & ~undefined(len) & (0 <= len) & (len < MAX(LONGINT)) *)
(* open <= ~undefined(oes) & ~undefined(pos) & (1 <= pos) & (pos <= len + 1) & (oes = (pos = len + 1)) *)
(* ~open <= undefined(oes) & undefined(pos) *)
(* open' & (0 <= i') & (i' <= len') *)
PROCEDURE element (i: LONGINT): BYTE;
(* (len = len') & open & (pos = pos') & (Result = (element number i')) *)
(* ~open' *)
PROCEDURE reset*;
(* (len = len') & open & (pos = 1) *)
(* open' *)
PROCEDURE close*;
(* (len = len') & ~open *)
(* open' & ~oes' *)
PROCEDURE read* (OUT a: BYTE);
(* (len = len') & open & (pos = pos' + 1) & ~undefined(a) & (a = element(pos')) & ((a = 0) OR (a = 1)) *)
BEGIN
END seq.
*)
VAR
a: BYTE;
i: INTEGER;
(* seq.open' & ~undefined(i') & (i' = seq.pos' - 2) & (def: element(0) = 1) & ~undefined(a') & (a' = element(i' + 1)) *)
PROCEDURE p* (VAR a, i: INTEGER);
VAR b: BOOLEAN;
BEGIN
b := FALSE;
WHILE ((a # 0) OR ~b) & ~seq.oes & (i < MAX(INTEGER)) DO
b := (a = 0);
seq.read(a);
INC(i)
END;
IF (a = 0) & b THEN
StdLog.Int(i);
StdLog.Ln
ELSIF seq.oes THEN
StdLog.Bool(FALSE);
StdLog.Ln
ELSE
StdLog.String('limit length');
StdLog.Ln
END
END
(* (seq.len = seq.len') & seq.open & (def: element(0) = 1) & ~undefined(i) *)
(* i = min({j | j IN {i' .. MIN(seq.len, MAX(INTEGER)) - 1}: (element(j) = 0) & (element(j + 1) = 0)} + {MIN(seq.len, MAX(INTEGER))}) *)
(* (seq.pos = i + 2) & ~(a) & (a = element(i + 1)) *)
BEGIN
seq.reset; (* seq.open *)
a := 1; (* a = element(0) *)
i := -1; (* i = seq.pos - 2 *)
p(a, i); (* p(a, i); p(a, i); p(a, i); ... *)
seq.close (* ~seq.open *)
END ms.Сам алгоритм:
a := 1;
b := FALSE;
i := -1;
WHILE ((a # 0) OR ~b) & ~seq.oes & (i < MAX(INTEGER)) DO
b := (a = 0);
seq.read(a);
INC(i)
END;
IF (a = 0) & b THEN
StdLog.Int(i);
StdLog.Ln
ELSIF seq.oes THEN
StdLog.Bool(FALSE);
StdLog.Ln
ELSE
StdLog.String('limit length');
StdLog.Ln
END
-
Последовательность нумеруется с 1, последовательный доступ как в файле.
А в чем сложность: в удалении мелких повторных вычислений, поиск новых форм цикла, или это чисто вопрос педагогики?
-
А в чем сложность: в удалении мелких повторных вычислений, поиск новых форм цикла, или это чисто вопрос педагогики?
Нет никакой сложности. Просто этот цикл не вписывался ни в одни из библиотечных шаблонов. Поэтому пришлось его сочинять. Наивное решение казалось не совсем првильным (что коробило, потому что если уж дело дошло до "ручного" цикла, то хотелось составить его максимально правильно). Решение через КА - черезчур громоздким. Поэтому было интересно кто как такое решает.
-
А тем временем появлися вариант с ЦД. Причем от самого info21!
http://forum.oberoncore.ru/viewtopic.php?p=72954#p72954
i := 0;
oneZero := FALSE;
LOOP IF (i < LEN(a)) & ~oneZero THEN
oneZero := a[i] = 0;
INC(i);
ELSIF (i < LEN(a)) & (a[i] # 0) THEN
oneZero := FALSE;
INC(i);
ELSE EXIT END END;
IF (i < LEN(a)) & oneZero THEN
Log.String("нашли: "); Log.Int( i-1 ); Log.Ln;
ELSE
Log.String("не нашли"); Log.Ln;
END;
ИМХО, самый нечитабельный вариант из всех. Хотя я верю, что этот код легко пишется "автоматом по постусловию".
-
NumZeroes := 0;
Success := FALSE;
i := 0;
WHILE (i < LEN(a)) & ~Success DO
IF a[i] = 0 THEN
INC(NumZeroes);
Success := NumZeroes = 2;
ELSE
NumZeroes := 0;
END;
INC(i);
END;
-
CONST
CHAIN_LEN = 7;
CHAIN_BYTE = 0;
ChainLen := 0;
i := 0;
WHILE (i < LEN(a)) & (ChainLen < CHAIN_LEN) DO
IF a[i] = CHAIN_BYTE THEN
INC(ChainLen);
ELSE
ChainLen := 0;
END;
INC(i);
END;
Обновление.
-
Нет никакой сложности. Просто этот цикл не вписывался ни в одни из библиотечных шаблонов. Поэтому пришлось его сочинять. Наивное решение казалось не совсем првильным (что коробило, потому что если уж дело дошло до "ручного" цикла, то хотелось составить его максимально правильно). Решение через КА - черезчур громоздким. Поэтому было интересно кто как такое решает.
Ну вот и я добрался до этой темы :-)
По моему мнению, в данном случае явное использование цикла это явный оверкилл. Ведь задача отлично ложится на один из стандартных библиотечных алгоритмов, а именно - std::search:
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
template<typename Iterator>
Iterator search_00(Iterator begin, Iterator end) {
auto tmp = *begin;
std::array<decltype(tmp),2> what = {0,0};
return std::search(begin, end, what.begin(), what.end());
}
int main() {
auto where = {0,1,2,3,4,0,0,1,2,3,4};
auto place = search_00(where.begin(), where.end());
std::cout << "place number: " << place - where.begin() << std::endl;
}
Собственно "ищущих" строк кода тут ровно две, остальное - подготовка данных и вывод.:
std::array<decltype(tmp),2> what = {0,0};
auto place = std::search(begin, end, what.begin(), what.end());
Как побочный профит - получаем независимость от используемых контейнеров (если они вообще используются - итеротор может быть для stdin - потока ввода) и от типов.
PS. В коде использовал C++11, но std::search есть и в C++98, просто с C++11 чуть покороче обвязка вышла (но не сам поиск).
-
Вообще, идеальный цикл, это тот которого нет :-) Также как и идеальный SQL-запрос, идеальный полигон и идеальное преобразование Фурье :-)
-
Ну вот и я добрался до этой темы :-)
По моему мнению, в данном случае явное использование цикла это явный оверкилл. Ведь задача отлично ложится на один из стандартных библиотечных алгоритмов, а именно - std::search:
Хитрый какой :) std::search использовать нельзя - потому что конец последовательности неизвестен, блин! Чтобы найти конец последовательности и отдать его в std::search - надо сначала найти два нуля ;)
-
Ну вот и я добрался до этой темы :-)
По моему мнению, в данном случае явное использование цикла это явный оверкилл. Ведь задача отлично ложится на один из стандартных библиотечных алгоритмов, а именно - std::search:
Хитрый какой :) std::search использовать нельзя - потому что конец последовательности неизвестен, блин! Чтобы найти конец последовательности и отдать его в std::search - надо сначала найти два нуля ;)
Не понял. Конец - это, в частном случае, просто барьер для контейнера. Все остальные примеры решений радостно используют какой-нибудь LEN(a), а чем я хуже? Дискриминация по алгоритмическому признаку шоле?!
:-)
search будет искать пока либо не найдейт что дадено, либо не упрется в end.
-
Вообще, контрпример давай, где это не будет работать. Показывай твои входные данные, а я попробую на них натянуть std::search. Может тебе из stdin читать что-нибудь? :-) stdin вполне себе "бесконечный".
-
Вообще, контрпример давай, где это не будет работать. Показывай твои входные данные, а я попробую на них натянуть std::search. Может тебе из stdin читать что-нибудь? :-) stdin вполне себе "бесконечный".
Я там когда свое решение приводил - говорил откуда данные. Голый wchar_t* там, без длины. Избаловался ты на всяких разных ЯВУ... :)
В случае stdin как раз проблем нет, у него есть eof :)
-
Вообще, контрпример давай, где это не будет работать. Показывай твои входные данные, а я попробую на них натянуть std::search. Может тебе из stdin читать что-нибудь? :-) stdin вполне себе "бесконечный".
Я там когда свое решение приводил - говорил откуда данные. Голый wchar_t* там, без длины. Избаловался ты на всяких разных ЯВУ... :)
В случае stdin как раз проблем нет, у него есть eof :)
Эмм... Ну нет длины и даже нет eof, и какие от этого тут могут быть проблемы?
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
template<typename Iterator>
Iterator search_00(Iterator begin, Iterator end) {
auto tmp = *begin;
std::array<decltype(tmp),2> what = {0,0};
return std::search(begin, end, what.begin(), what.end());
}
int main() {
char where[] = "hello\0world\0\0here";
auto place = search_00(where, (char*)nullptr);
std::cout << "place number: " << (int)(place-where) << std::endl;
}
Все прекрасно работает. Код собственно поиска менять не пришлось, как и обещалось мною ранее :-)
-
Ответ на сообщение: http://forum.oberoncore.ru/viewtopic.php?p=72961#p72961
Чтобы не казалось, что мой вариант сложнее, перепишу на Обероне-07, где ЦД есть явно:
i := 0;
oneZero := FALSE; (*oneZero = перед i стоит нуль*)
WHILE (i < LEN(a)) & ~oneZero DO
oneZero := a[i] = 0;
INC(i);
ELSIF (i < LEN(a)) & (a[i] # 0) DO
oneZero := FALSE;
INC(i);
END;
Все равно write-only код. Даже на языке с непосредственной поддержкой ЦД. Что еще раз показывает ненужность данного конструкта в ЯП общего назначения. И нечего пенять на необразованность авторов "более другмх" ЯП.
Рукосуи, не понимающие, с чем "едят" ЦД (это про альтернативно удаленных), не въезжают, что конъюнкция отрицаний охран сразу доказывает корректность цикла:
(i >= LEN(a)) OR (oneZero & (a=0))
Люди, которые не читают код, а только пишут, не понимают, что "конъюнкция отрицаний охран" даже в таком тривиальном примере неочевидна и неявна. Люди, которые читают код, хотят все видеть в явном виде и сразу. А не заниматься коньюнкциями в уме с человеческим правом ошибиться.
И даже не понимают, что это ("сразу дает ...") важно.
Ничего это не дает, кроме ощущения собственной элитарности от того, что зашифровал такую простую вещь в трех разных логических выражениях.
У меня нет проблем с идеей автоматического и правильного построением цикла по постусловию. У меня даже нет проблем вот с этим кодом, если это выход с некого генератора, который будет читать только компилятор. Но если подразумевается, что "это" будет читать человек - то такой говнокод автоматически отправляется на помойку, а писателя заставляют посидеть и нормально декомпозировать цикл.
-
Все прекрасно работает. Код собственно поиска менять не пришлось, как и обещалось мною ранее :-)
Мда... Признаюсь, о таком хаке как передача заведомо невалидного итератора в качестве конца я не подумал. Подозреваю, что оно будет валится в отладочном режиме любой приличной реализации STL ;) Спасибо за "нестандартное" решение, но в свой в код я такое не вставлю ;)
P.S. Еще можно представить какую-нибудь мультипроцессорную реализацию, которая будет бить последовательность на отрезки по количеству процессоров и искать а параллель. Такая реализация тоже обломается ;)
-
Рукосуи, не понимающие, с чем "едят" ЦД (это про альтернативно удаленных), не въезжают, что конъюнкция отрицаний охран сразу доказывает корректность цикла:
(i >= LEN(a)) OR (oneZero & (a[i]=0))
Люди, которые не читают код, а только пишут, не понимают, что "конъюнкция отрицаний охран" даже в таком тривиальном примере неочевидна и неявна. Люди, которые читают код, хотят все видеть в явном виде и сразу. А не заниматься коньюнкциями в уме с человеческим правом ошибиться.
Кстати, да. Результат конъюнкции отрицания охран хочется видеть сразу, в не бегать по коду глазами вычисляя его в уме.
Кстати в именно данном случае " конъюнкция отрицаний охран" сразу ничего не доказывает (даже если привести её в явном виде) хотя бы потому, что в выражении (i >= LEN(a)) OR (oneZero & (a[i]=0)) присутствует вычисляемое в теле (точнее в телах) ЦД переменная oneZero, таким образом чтобы удостевериться в правильности результирующего выражения нужно прочитать ВЕСЬ цикл целиком, со всем императивным фаршем внутри, прокрутить в голове по шагам этот цикл. Одних охранных выражений с последующим их отрицанием и конъюнкцией не достаточно.
-
Все прекрасно работает. Код собственно поиска менять не пришлось, как и обещалось мною ранее :-)
Мда... Признаюсь, о таком хаке как передача заведомо невалидного итератора в качестве конца я не подумал. Подозреваю, что оно будет валится в отладочном режиме любой приличной реализации STL ;) Спасибо за "нестандартное" решение, но в свой в код я такое не вставлю ;)
P.S. Еще можно представить какую-нибудь мультипроцессорную реализацию, которая будет бить последовательность на отрезки по количеству процессоров и искать а параллель. Такая реализация тоже обломается ;)
В обоих случаях не обломается. Просто потому, что в std::search аргументами идут ForwardIterator, а не RandomIterator. Алгоритм std::search не имеет права бить последовательность на куски, не имеет права идти от конца к началу (в любом месте). Я все это постарался учесть перед тем как постить сюда решение :-) nullptr абсолютно валидный в данном случае "конец" последовательности. Вообще ты же знаешь, что end() это итератор "указывающий" на элемент ПОСЛЕ последнего, то есть его разименовывать тоже нельзя.
-
В обоих случаях не обломается.
Проверил. Падает. И это правильно. VC10.
-
В обоих случаях не обломается.
По поводу forward итертаоров. Ты уверен, что запрещается специализировать std::search для более специализированных итераторов (random)?
-
В обоих случаях не обломается.
Проверил. Падает. И это правильно. VC10.
Это очень странно. Я не вижу противоречий стандарту в таком использовании.
-
Все равно write-only код. Даже на языке с непосредственной поддержкой ЦД. Что еще раз показывает ненужность данного конструкта в ЯП общего назначения. И нечего пенять на необразованность авторов "более другмх" ЯП.
;D ;D ;D Да ладно..."некто Vlad" :D ;) - среди приведенных здесь вариантов не требующих особых знаний,
но "с претензиями" - это одно из внятных (мне лично, оно нравится больше вашего).
-
В обоих случаях не обломается.
По поводу forward итертаоров. Ты уверен, что запрещается специализировать std::search для более специализированных итераторов (random)?
Залез в стандарт. Там все специализации прописаны явно (например для vector<bool> и всякие алгоритмы специализированные для разных типов данных), так вот, специализаций search для более конкретных итераторов (bidirectional, random) там нет. А все что не разрешено, то, запрещено. В данной области.
По факту ведь просто шаблонный класс и специализация его (того же vector'a) это два РАЗНЫХ класса, никак друг с другом не связанных. Аналогично и для функций. Поэтому в стандарте все они приводятся явным образом. Поэтому в реализации стандартной библиотеки нельзя рядом с template<typename ForwardIterator1, typename ForwardIterator2>search(...) дописать template<> char* search<char*, char*>(...) не нарушив при этом стандарт.
-
Да Алексей, ирония судьбы.. припоминаю с пол года назад вы (и я) издевались над ритуалом коровцев , по которому, они по случаю всякой фигни лезли в толмуды... Сравнивая ваши действия сейчас...ммм в голову лезут весьма злобные и жестокие слова.. Но замечу ИМХО если уж заниматься идолопоклонничеством, то религия коровят попроще будет...
-
Да Алексей, ирония судьбы.. припоминаю с пол года назад вы (и я) издевались над ритуалом коровцев , по которому, они по случаю всякой фигни лезли в толмуды... Сравнивая ваши действия сейчас...ммм в голову лезут весьма злобные и жестокие слова.. Но замечу ИМХО если уж заниматься идолопоклонничеством, то религия коровят попроще будет...
Да не, я без идолопоклонничества, я просто читаю доку инструмента который использую. В случае Оберона это будет Oberon report by NW, в случае Go это будет вот это (http://golang.org/ref/spec) + это (http://golang.org/pkg/), в случае С++ естественно будет стандарт (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3242.pdf), как и в случае с Адой например. Если поведение инструмента отличается от того, что должно быть по спеке, я завожу багрепорт (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39045) и эти баги таки фиксятся, как видим.
Все абсолютно формально и без эмоций :-)
У "коровят" пунктик обратный - там живут не по закону (спеке на язык) а по понятиям (как они привыкли, как им кажется правильным - например откуда то у них внезапно появилась проверка выхода за границу массива в Обероне).
-
Решение через КА - черезчур громоздким. Поэтому было интересно кто как такое решает.
ну на хацкеле фактически КА получился -- и всё простенько и чотко -- никакой громоздкости!
-
Да не, я без идолопоклонничества, я просто читаю доку инструмента который использую. ....
;) Ну ну, что за язык такой, что для решения подобных задач требуется залезть в толмуды... а залезши
использовать принцип "что не запрещено, то разрешено". Вообщем, предлагаю сие действо назвать "STL- ритуалом". :)
-
.. а людей занимающихся этим по малейшему поводу ( и в особенности , без оного) - STL- культистами.
-
Да не, я без идолопоклонничества, я просто читаю доку инструмента который использую. ....
;) Ну ну, что за язык такой, что для решения подобных задач требуется залезть в толмуды... а залезши
использовать принцип "что не запрещено, то разрешено". Вообщем, предлагаю сие действо назвать "STL- ритуалом". :)
В данном случае не язык, а стандартная библиотека. Любая библиотека на любом языке как только становится больше одного вендора (больше одной независимой реализации) требует залезать в доки. Причем как в спеки стандартные, так и в доки конкретных реализаций, а потом еще, до кучи, в исходники этих реализаций (а потом еще смотреть специфику поведения всего этого на конкретной железке с конкретной осью).
Повторюсь - это не специфично для C++, это у подобной библиотеки на любом языке так. Например это так у той же Java.
-
это "ежу понятно"... я говорю вам про то, что прилагаемые усилия неадекватны рассматриваемой задаче..
-
Я там когда свое решение приводил - говорил откуда данные. Голый wchar_t* там, без длины. Избаловался ты на всяких разных ЯВУ... :)
В случае stdin как раз проблем нет, у него есть eof :)
Ух ты! Без длины! Ну тогда это ещё проще, вот:
int n = 0;
do
{
while (a[n] != 0)
{
n++;
}
n++;
}
while (a[n] != 0);
искомая позиция равна n - 1;
Идея цикла та же что и в прошлый раз: сверхмоментально линейным поиском отыскиваем первый ноль
while (a[n] != 0)
{
n++;
}
затем проверяем нужно ли это дело повторить ещё разок. Пожалуй это самый быстрейший поиск.
-
это "ежу понятно"... я говорю вам про то, что прилагаемые усилия неадекватны рассматриваемой задаче..
Да какие там усилия - с утра под чаёк полчасика поковырялся, заодно C++ вспомнил (давненько на нем не писал).
-
Чета тут обобщать задачу начали. ??? info21 циклом дейкстры махает... Лично я код писал под конкретную задачу.
Если уж обобщать, то бойер-мур... :P ;)
-
.....
затем проверяем нужно ли это дело повторить ещё разок. Пожалуй это самый быстрейший поиск.
Да, ИМХО пожалуй самое ясное из частных решений "с претензиями", поздравляю.
-
Чета тут обобщать задачу начали. ??? info21 циклом дейкстры махает... Лично я код писал под конкретную задачу.
Если уж обобщать, то бойер-мур... :P ;)
Я не обобщал. Честно-честно! На плюсах (то есть не Си) я бы ровно так и написал бы. Просто потому что лениво циклы писать а потом их еще и читать :-)
На других языках (Go, C, возможно даже Java) скорее всего пришлось бы таки написать какой-то цикл.
-
Я там когда свое решение приводил - говорил откуда данные. Голый wchar_t* там, без длины. Избаловался ты на всяких разных ЯВУ... :)
В случае stdin как раз проблем нет, у него есть eof :)
Ух ты! Без длины! Ну тогда это ещё проще, вот:
int n = 0;
do
{
while (a[n] != 0)
{
n++;
}
n++;
}
while (a[n] != 0);
искомая позиция равна n - 1;
Это 1 в 1 решеие Влада.
-
только без вые..онов ;) - Это раз, Влад знал задачу ПОЛНОСТЬЮ - в отличии от других, это два...
-
Чета тут обобщать задачу начали. ??? info21 циклом дейкстры махает... Лично я код писал под конкретную задачу.
Если уж обобщать, то бойер-мур... :P ;)
Я не обобщал. Честно-честно!
Та не... Я про то, что начали распространять на произвольную длину шаблона (как тут (http://oberspace.dyndns.org/index.php/topic,253.msg6173.html#msg6173))
-
только без вые..онов ;) - Это раз, Влад знал задачу ПОЛНОСТЬЮ - в отличии от других, это два...
Дык задача полностью была раскрыта еще на первой странице обсуждения 25го мая: http://oberspace.dyndns.org/index.php/topic,253.msg6094.html#msg6094
-
только без вые..онов ;) - Это раз, Влад знал задачу ПОЛНОСТЬЮ - в отличии от других, это два...
Дык задача полностью была раскрыта еще на первой странице обсуждения 25го мая: http://oberspace.dyndns.org/index.php/topic,253.msg6094.html#msg6094
Тык это произошло только после того как я поднял "вонь", да и то, не сразу...
-
Хм.. А я первое сообщение смотрел. :)
-
В борьбе с рукосуйством и мракобесием Info21 малость обосрался.
"Рукосуи, не понимающие, с чем "едят" ЦД (это про альтернативно удаленных), не въезжают, что конъюнкция отрицаний охран сразу доказывает корректность цикла:
(i >= LEN(a)) OR (oneZero & (a[ i]=0))"
Конъюнкция отрицаний охран, дорогой товарищ, НЕ доказывает корректность цикла. Ни сразу ни потом. Корректность цикла доказывает конъюнкция отрицаний охран & инвариант цикла. Игнорирование последнего весьма характерно для любителей линейного поиска во главе с Info21. Инвариант им на хрен не нужен, я как-то писал об этом на оберонкоре. Само собой, то сообщение было удалено Темиргалеевым.
Кроме того, Info21 не мешало бы прочитать переведенную им же книгу и понять, что в случае массива можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль. О чем черным по белому было сказано здесь http://oberspace.dyndns.org/index.php/topic,253.msg6115.html#msg6115
-
Наверно торможу но не понял что значит:
можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль
Разве на двух элементах будет профит?
Или типа как я сэкономил?
http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133 (http://oberspace.dyndns.org/index.php/topic,253.msg6133.html#msg6133)
ps У меня кстати там ошибка есть. Я не учитываю, что длина массива может быть < 2.
Ну т.е. все это нужно в IF засунуть
-
Разве на двух элементах будет профит?
Да , будет ( и уточненные условия Влада его допускают )- проблема в том, что Петр не привел решение
и по этому out of contest (хотя ,я не уверен, что сгенерированный машинный код будет оптимален).
-
Понятно что на таком раскладе будет экономия в 2 раза:
[01][01][01][01][10][0]
Слева направо проверяем каждый второй элемент. Если нуль то проверяем первый. И в конце если количество элементов нечетное (дешевая проверка), то проверяем последний элемент.
Но какова вероятность такого расклада?
У бойера-мура эта стратегия хорошо работает на длинных шаблонах имхо
p.s. Хотя следует признать, что в среднем будет больше экономии чем у меня
-
единственный момент, ilovb, здесь существенно используется техника сокращенных вычислений логических выражений, а если вы хотите получить gain прыгая через блок (2 х элементный), пофигу первый 0 вы вставляете в начало условия (ищите) или второй ...
-
можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль
Кстати можно исходный двухбайтовый wchar_t* привести к четырёхбайтовому int* и всё свести к обычному линейному поиску четырёхбайтового нуля. :) :) :)
-
;D ;D ;D Да ладно..."некто Vlad" :D ;) - среди приведенных здесь вариантов не требующих особых знаний,
но "с претензиями" - это одно из внятных (мне лично, оно нравится больше вашего).
Ты уверен, что при сравнении оставил за скобками мелочи типа сишного синтаксиса и адресной арифметики, которые могут не нравится сами по себе? Кроме того, мое решение учитывает конкретную задачу (не только найти нули, но и по дороге собрать нужные данные). В чистом виде (только поиск нулей) я бы написал что-то очень похожее на последний вариант Сергея. Только вложенный цикл вытащил бы в функцию. Что-то типа:
while ((next = find_zero(next))[1])
next += 2;
Куда здесь воткнуть цикл Дейкстры, чтоб оно было более наглядно/доказательно - не представляю...
-
можно в 2 раза сэкономить на сравнениях, если начинать искать второй нуль
Кстати можно исходный двухбайтовый wchar_t* привести к четырёхбайтовому int* и всё свести к обычному линейному поиску четырёхбайтового нуля. :) :) :)
wchar_t бывает 32-битным, причем не на самых экзотических платформах (Мак). Кроме того, даже в случае 16-битного wchar_t - два нуля могут лечь между двумя 32-битными int.
-
да , пример [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);
-
C#:
char - 2 byte
int - 4 byte
long - 8 byte
Да, так будет работать на платформах с указанными размерами char и int. При условии, что доступ к невыровненным данным не вызывает исключения ;)
-
wchar_t бывает 32-битным, причем не на самых экзотических платформах (Мак). Кроме того, даже в случае 16-битного wchar_t - два нуля могут лечь между двумя 32-битными int.
C#:
char - 2 byte
Кстати, а как в винде и шарпе живут с таким недоюникодом? Это же получается UCS-16, который не покрывает весь диапазон юникодовых символов. В нормальных системах и языках обычно для обработки хранят в UCS-32, он же UTF-32, который включает в себя весь юникоддиапазон при фиксированном размере кодирования одного символа.
-
Пардон, ucs-2 и ucs-4 конечно. Вечно путаю где там биты а где байты.
-
Ты уверен, что при сравнении оставил за скобками мелочи типа сишного синтаксиса и адресной арифметики, которые могут не нравится сами по себе? Кроме того, мое решение учитывает конкретную задачу (не только найти нули, но и по дороге собрать нужные данные). В чистом виде (только поиск нулей) я бы написал что-то очень похожее на последний вариант Сергея. Только вложенный цикл вытащил бы в функцию. Что-то типа:
1. ДА
2. Вот ИМЕННО по этому я и "развонялся" -в исходной постановке задача , бесполезная трата времени... судить вы же ВСЕ РАВНО будете относительно своей задачи.
3. Я вам ответил- код чуть выше адаптация моего исходного (с учетом ваших уточнений). Скорость -раскрытие условия -drawback - потеря наглядности (но замечу, что это делается без вые... онов аля Сергей и доступно начинающему)
4. Насчет инфо21 - тут несколько проблем проистекающих из идолопоклонничества... как Доцент натягивал, глаз на жопу Николе Питерскому, так и культисты натягивают на все ЦД (или наоборот?) - глумиться над этим я устал(временно)...
Но решение Инфо21 ИМХО гораздо понятнее чем ваше..
-
:D :D :D господа, не удержался , глянул в коровник по Владовской ссылке... и что могу сказать... нафиг Прометей, да long live cowshed! заряд "одреналина" хоть и не в 3d но бесплатно, господа "мракобесы" :)
-
В борьбе с рукосуйством и мракобесием Info21 малость обосрался.
"Рукосуи, не понимающие, с чем "едят" ЦД (это про альтернативно удаленных), не въезжают, что конъюнкция отрицаний охран сразу доказывает корректность цикла:
(i >= LEN(a)) OR (oneZero & (a[ i]=0))"
Конъюнкция отрицаний охран, дорогой товарищ, НЕ доказывает корректность цикла. Ни сразу ни потом. Корректность цикла доказывает конъюнкция отрицаний охран & инвариант цикла. Игнорирование последнего весьма характерно для любителей линейного поиска во главе с Info21. Инвариант им на хрен не нужен, я как-то писал об этом на оберонкоре. Само собой, то сообщение было удалено Темиргалеевым.
Я конечно неграмытное быдло, но разве в данном случае
(i >= LEN(a)) OR (oneZero & (a[ i]=0))не есть инвариант цикла?
-
Я конечно неграмытное быдло, но разве в данном случае
(i >= LEN(a)) OR (oneZero & (a[ i]=0))не есть инвариант цикла?
Нет :)
Формулировать и подсказывать инвариант цикла я не буду. Предлагаю это сделать участникам соревнований. Уже 3 года как.
-
Я конечно неграмытное быдло, но разве в данном случае
(i >= LEN(a)) OR (oneZero & (a[ i]=0))не есть инвариант цикла?
Гм. Реально неграмотное быдло. Впрочем, как обычно с утра (хоть зарекайся не писать ничего и к коду себя не подпускать до пяти-шести часов дня).
Естественно хотел сказать, что это отрицание инварианта. Инваринт конечно вот:
~(i >= LEN(a)) OR (oneZero & (a[ i]=0))
Как-то так.
Но конечно могу быть где-то еще не прав, ибо все еще утро :-)
-
Нет :)
Формулировать и подсказывать инвариант цикла я не буду. Предлагаю это сделать участникам соревнований. Уже 3 года как.
Злой ты... :-)
А вообще, соревнования эти уже начинают напоминать специальную олимпиаду.
-
Кстати, должен присоединиться к DIzer'у и поставить vlad'у жирный минус за безобразность начальной формулировки задачи. У меня оно сразу же отбило желание что-либо делать.
При том, что реальная задача, озвученная позже, вполне хороша. И поиска двух нулей там вообще нет - к массиву добавляются строки, оканчивающиеся 0, до тех пор, пока не встретится строка нулевой длины.
-
Кстати, а как в винде и шарпе живут с таким недоюникодом?
Библиотечная процедура читающая текстовый юникодный файл возвращает 4-байтовый int
namespace System.IO
{
public class StreamReader: TextReader
{
//
// Summary:
// Reads the next character from the input stream and advances the character
// position by one character.
//
// Returns:
// The next character from the input stream represented as an System.Int32 object,
// or -1 if no more characters are available.
//
// Exceptions:
// System.IO.IOException:
// An I/O error occurs.
public override int Read ();
Хочешь сужай полученный int в 2-байтовый char, а не хочешь - не сужай (работай врукопашную с массивами int), дело-то хозяйское.
А вообще конечно ни для кого не секрет, что 2-байтовый char (при > 50'000 одном лишь Японском алфавите) это англосаксонские империалистические происки, это даже у Таненбаума в "Архитектура компьютера" написано.
-
Кстати, а как в винде и шарпе живут с таким недоюникодом?
Библиотечная процедура читающая текстовый юникодный файл возвращает 4-байтовый int
namespace System.IO
{
public class StreamReader: TextReader
{
//
// Summary:
// Reads the next character from the input stream and advances the character
// position by one character.
//
// Returns:
// The next character from the input stream represented as an System.Int32 object,
// or -1 if no more characters are available.
//
// Exceptions:
// System.IO.IOException:
// An I/O error occurs.
public override int Read ();
Хочешь сужай полученный int в 2-байтовый char, а не хочешь - не сужай (работай врукопашную с массивами int), дело-то хозяйское.
Ага. То есть можно, но врукопашную. Ну, хоть это радует.
А вообще конечно ни для кого не секрет, что 2-байтовый char (при > 50'000 одном лишь Японском алфавите) это англосаксонские империалистические происки, это даже у Таненбаума в "Архитектура компьютера" написано.
Угу. Это при том, что во всех юниксах и недоюниксах (linux) и совсем не юниксах, а просто нормальных системах, (Haiku/BeOS) 4 байта либо utf8 в качестве альтернативного кактуса. Ну и в других языках этой проблемы тоже нет (по моему, только в жабе есть, хотя там вроде бы перешли на UTF-16 с UCS-2, что с одной стороны черевато, но с другой дает полный охват юникода).
Кстати, заметь - англосаксы уже идут на уступки, раньше то был вообще жестко однобайтовый ASCII. :-)
-
Кстати, должен присоединиться к DIzer'у и поставить vlad'у жирный минус за безобразность начальной формулировки задачи. У меня оно сразу же отбило желание что-либо делать.
ОК. только напомню что ваша относительно недавно инициированная тема(про сортировку) обладала ровно такими же "достоинствами" как и Влада.
-
Капец, пока меня не было уже успели подраться )))
А что там с ЦД и инвариантами? Я правильно понимаю, что в случае с ЦД однородность не постулируется? Тогда что есть инвариант в ЦД?
-
А что там с ЦД и инвариантами? Я правильно понимаю, что в случае с ЦД однородность не постулируется? Тогда что есть инвариант в ЦД?
:) А этот вопрос не к нам = это в коровник, либо к Петру только он ничего не скажет. :) тихарит инфу, короче...
-
Померил скорость работы 4 разных алгоритмов.
Поиск 4-байтового нуля:
static long A1 (char* begin)
{
char* p = begin;
while (*((int*)p) != 0)
{
p++;
}
return (long)(p - begin);
}
Два вложенных цикла:
static long A2 (char* begin)
{
char* p = begin;
do
{
while (*p != 0)
{
p++;
}
p++;
}
while (*p != 0);
return (long)(p - begin) - 1;
}
Двойная проверка:
static long A3 (char* begin)
{
char* p = begin;
while (!((*p == 0) && (*(p+1) == 0)))
{
p++;
}
return (long)(p - begin);
}
Поиск а-ля чокнутый доктор, но оптимизированный по самые помидоры (авторская чокнутая вспомогательная переменная oneZero оставлена):
static long A4 (char* begin)
{
char* p = begin;
bool oneZero = false;
while (true)
{
if (!oneZero)
{
oneZero = (*p == 0);
p++;
}
else if (*p != 0)
{
oneZero = false;
p++;
}
else
{
break;
}
}
return (long)(p - begin) - 1;
}
Измерял десять раз прокручивая по массиву из миллиарда чаров циклически заполненных значениями 0..char.MaxValue
char[] buffer = new char[1000000000];
for (int i = 0; i < buffer.Length; i++)
{
buffer[ i ] = (char)i;
}
buffer[buffer.Length - 1] = (char)0;
buffer[buffer.Length - 2] = (char)0;
Каждый тест прогнал 3 раза. Из трёх взял лучший результат.
Итого:
A1 3.04 seconds
A2 5.60 seconds
A3 5.60 seconds
A4 6.79 seconds
Win 7, 64 bit, .Net 4.0, i7 2600K.
Прикреплённый архив содержит бинарник плюс исходник (проект на C# для 2010-студии).
-
A1 3.04 seconds
A2 5.60 seconds
A3 5.60 seconds
A4 6.79 seconds
A1 либо не будет работать на самой популярной процессорной архитектуре, либо будет работать медленно (если jit-компилятор достаточно умен, чтобы сделать дополнительное побайтовое копирование во временную переменную).
Про A4… Предвижу контраргумент от info21, точнее даже два:
1) Зато оно пишется автоматом и гарантированно корректно.
2) Оптимизации зло! Все зло от оптимизаций!
-
(авторская чокнутая вспомогательная переменная oneZero оставлена)
А почему чокнутая?
-
Формулировать и подсказывать инвариант цикла я не буду. Предлагаю это сделать участникам соревнований. Уже 3 года как.
Чтобы потом не было упреков выложил здесь запароленные инварианты.
Надо отметить, что простота вопроса просто смехотворная, и он не заслуживает таких извратов.
Но раз пошла такая пьянка...
-
A1 либо не будет работать на самой популярной процессорной архитектуре, либо будет работать медленно (если jit-компилятор достаточно умен, чтобы сделать дополнительное побайтовое копирование во временную переменную).
На x64 работает. И быстрее всех. Ты о какой архитектуре?
А почему чокнутая?
Потому что костыль.
-
Итого:
A1 3.04 seconds
A2 5.60 seconds
A3 5.60 seconds
A4 6.79 seconds
То есть, получается, что второй и третий варианты с точки зрения производительности одинаковы? Тогда однозначно стоит выбрать более наглядный - третий.
-
На x64 работает. И быстрее всех. Ты о какой архитектуре?
На самой популярной. И это не .NET : )
-
Померил скорость работы 4 разных алгоритмов.
Сергей - не затруднит, в варианте с "двойной проверкой" раскрыть условие по правилу де Моргана? (что бы гарантированно сработало укороченное вычисление логических выражений)?
-
А2 и А3 оказались равными на суперскалярном i7 2600 в 64 разрядной программе. Возможно на каком-то древнем процессоре выполняющем 1 инструкцию за такт А2 окажется быстрее чем А3.
А3 конечно лидер по понятности.
-
Просто, сделайте а? считайте что личная просьба, ПОЖАЛУЙСТА. :)
-
Имхо, вариант А2 вполне понятен и прост...
-
Сергей - не затруднит, в варианте с "двойной проверкой" раскрыть условие по правилу де Моргана? (что бы гарантированно сработало укороченное вычисление логических выражений)?
Оператор && в C# как раз и обозначает укороченное вычисление (второй операнд не вычисляется при ложности первого).
Название "двойная проверка" относится к тому, что теоретически можно делать шаг +2 вместо +1 если вторая буква не ноль. Но как это сделать практически мне не очевидно, а напрягаться и думать мне лень :)
-
Имхо, вариант А2 вполне понятен и прост...
По мне так A3 (правда свои "какашки" ближе к "телу") :D
-
Но как это сделать практически мне не очевидно, а напрягаться и думать мне лень :)
убрать отрицание(! знак) по правилу де Моргана(мне интересен уровень оптимизации C#)
-
Если в А3 заменить укороченное логическое && в побитовое & то вместо 5.60 секунд будет 8.28 секунд.
-
убрать отрицание(! знак) по правилу де Моргана(мне интересен уровень оптимизации C#)
Я про переход на 2 позиции вместо 1 при ненулевой второй букве.
-
убрать отрицание(! знак) по правилу де Моргана(мне интересен уровень оптимизации C#)
А, дошло. Ты имел ввиду, что вместо вот этого:
while (!((*p == 0) && (*(p+1) == 0)))
{
p++;
}
написать вот это:
while ((*p != 0) || (*(p+1) != 0))
{
p++;
}
Да?
Попробовал. Разницы по времени выполнения нет.
-
НЕ я говорю про !((*p == 0) && (*(p+1) == 0)) = !(*p ==0) || !(*(p+1)==0) = (*p!=0) || (*(p+1)!=0) вроде так...
-
да - спасибо. (вывод, в случае хорошего компилятора жертвовать наглядностью смысла нет - во общем то это подтверждает мою "выстраданную" точку зрения).
-
A1 либо не будет работать на самой популярной процессорной архитектуре, либо будет работать медленно (если jit-компилятор достаточно умен, чтобы сделать дополнительное побайтовое копирование во временную переменную).
На x64 работает. И быстрее всех. Ты о какой архитектуре?
ARM конечно же :-) Хотя, я не уверен, вполне возможно msp430 таки популярнее. С другой стороны, софта под арм (в строчках кода в и разнообразии проявлений) больше чем под msp430.
-
Напряг извилины и родил алгоритм A0 который прыгает на 2 позиции если вторая буква не ноль
static long A0 (char* begin)
{
char* p = begin + 1;
do
{
while (*p != 0)
{
p += 2;
}
p--;
}
while (*p != 0);
return (long)(p - begin);
}
A0 2.99 seconds
A1 3.04 seconds
A2 5.60 seconds
A3 5.60 seconds
A4 6.79 seconds
-
Понятно что на таком раскладе будет экономия в 2 раза:
[01][01][01][01][10][0]
Слева направо проверяем каждый второй элемент. Если нуль то проверяем первый. И в конце если количество элементов нечетное (дешевая проверка), то проверяем последний элемент.
Примерно так наверно:
MODULE TestFind;
IMPORT Log;
PROCEDURE Do*(a: ARRAY OF CHAR);
VAR
i, next, len: INTEGER;
BEGIN
len := LEN(a) - 1;
IF len > 1 THEN
i := 0;
next := 1;
WHILE (next < len) DO
IF a[next] = "0" THEN
IF a = "0" THEN
len := -1; (* FIND!!! *)
ELSE
INC(next, 1);
END;
ELSE
INC(next, 2)
END;
i := next - 1;
END;
IF len = -1 THEN
Log.Int(i);
ELSIF ODD(len) & (a = "0") & (a[i - 1] = "0") THEN
Log.Int(i - 1);
ELSE
Log.Int(-1);
END;
END;
END Do;
END TestFind.
ps Не уверен, что нет ошибок
-
а алгоритм который порождает идея Петра - здорово! Только gain ИМХО не стоит неочевидности.
-
Блин там в IF a = "0" THEN обращение по индексу к i
Надо j писать в следующий раз ;D
add: и тут тоже ELSIF ODD(len) & (a = "0") & (a[i - 1] = "0") THEN
-
а алгоритм который порождает идея Петра - здорово! Только gain ИМХО не стоит неочевидности.
но он подтверждает второй тезис (выстраданный) - хороший алгоритм перебивает танцульки вокруг железа...
-
Блин там в IF a = "0" THEN обращение по индексу к i
Надо j писать в следующий раз ;D
add: и тут тоже ELSIF ODD(len) & (a = "0") & (a[i - 1] = "0") THEN
DEC (len) опустить под IF len
-
Напряг извилины и родил алгоритм A0 который прыгает на 2 позиции если вторая буква не ноль
A0 2.99 seconds
A1 3.04 seconds
Разница в 50 мс похожа на погрешность измерения...
-
2 Kemet
Зачем?
Кстати, если кто не знает, в ЧЯ можно так тестить этот код:
^Q "TestFind.Do('110110111101100')"
-
Разница в 50 мс похожа на погрешность измерения...
В данном случае принципиально другое - один алгоритм использует низкоуровневые преобразования (область и использования потенциально ограничена) - второй без проблем реализуем на произвольном императивном ЯВУ
-
Разница в 50 мс похожа на погрешность измерения...
Да нет. Колеблется третий десятичный знак после десятичной точки. Вот прогнал по 3 раза:
A0:
2.9870269 seconds
2.9838307 seconds
2.981162 seconds
A1:
3.0446316 seconds
3.0322871 seconds
3.0352119 seconds
A2:
5.6005083 seconds
5.5965022 seconds
5.5998833 seconds
A3:
5.595559 seconds
5.5904891 seconds
5.5997908 seconds
A4:
6.7877969 seconds
6.7981043 seconds
6.7933201 seconds
-
Сергей, есть возможность мой говнокод прогнать тоже? ::)
-
2 Kemet
Зачем?
Ну или условие изменить
-
Так зачем? Там ошибка?
-
Напряг извилины и родил алгоритм A0 который прыгает на 2 позиции
А если попробовать прыгать на три позиции?
WHILE (a[i] # 0) OR ((a[i - 1] # 0) & (a[i + 1] # 0)) DO
i := i + 3
END;
Правда, тогда размер массива должен быть кратен и двум, и трём...
-
А если попробовать прыгать на три позиции?
Следующие улучшения алгоритма буду сильно зависеть от характера входных данных. Придумать что-то более эффективное для "общего" случая трудно. Причем даже "прыгающий" алгоритм может оказаться хуже самого простого на конкретной железке/компиляторе.
P.S. Вообще изначально вопрос ставился не о самом эффективном по скорости, а о самом правильном (по сумме критериев) цикле :)
-
Прыжки туда-сюда могут привести к увеличению промахов кэша. Ну и ветвления вообще неплохо тормозят систему (сбивается предсказывалка переходов). Но это все конечно действительно СИЛЬНО от железяки зависит. Скажем если мы пишем под процессор msp430, то нам на это пофиг, ибо там нет ни кэша ни предсказаний переходов :-) Зато есть табличка где четко указана стоимость каждой из инструкций в тактах.
-
P.S. Вообще изначально вопрос ставился не о самом эффективном по скорости, а о самом правильном (по сумме критериев) цикле :)
Я понял задачу буквально - простой цикл и один единственный, т.е. решить задачу используя один цикл, без вспомогательных механизмов и библиотечных методов, разруливая состояния условиями вхождения и IF'ами внутри цикла.
-
Сергей, есть возможность мой говнокод прогнать тоже? ::)
Я затрудняюсь адекватно перевести его на ансэйфный C# в варианте без заранее известной длины массива (чтобы адекватно сравнить с предыдущими). В результате творческого пересказа у меня получается что-то вроде такого:
static long A5 (char* begin)
{
char* next = begin + 1;
bool BREAK = false;
while (!BREAK)
{
if (*next == 0)
{
if (*(next-1) == 0)
{
BREAK = true;
}
else
{
next++;
}
}
else
{
next += 2;
}
}
return (long)(next - begin) - 1;
}
Время его выполнения такое же как и у A0
A5:
2.9989265 seconds
2.9958975 seconds
2.9939577 seconds
A0:
2.9941996 seconds
2.9946799 seconds
2.9830016 seconds
Если рукопашный костыль BREAK заменить на встроенный в C# костыль break, то скорость выполнения не меняется.
----------
Занимательное наблюдение: если в главном if-е инвертировать условие:
if (*next != 0)
{
next += 2;
}
else if (*(next-1) == 0)
{
BREAK = true;
}
else
{
next++;
}
то скорость работы существенно замедляется (до 4.26 секунды). Видимо в тройном if-else_if-else ошибается процессорный блок отвечающий за спекулятивное выполнение обеих веток if-else.
-
Напряг извилины ....
Круто! Значительно проще чем у меня :)
-
Прыжки туда-сюда могут привести к увеличению промахов кэша. Ну и ветвления вообще неплохо тормозят систему (сбивается предсказывалка переходов). Но это все конечно действительно СИЛЬНО от железяки зависит. Скажем если мы пишем под процессор msp430, то нам на это пофиг, ибо там нет ни кэша ни предсказаний переходов :-) Зато есть табличка где четко указана стоимость каждой из инструкций в тактах.
Так не в коде прыгать. В данных. Тогда получится, что условие цикла будет меньшее количество раз проверяться (в полтора раза).
-
Прыжки туда-сюда могут привести к увеличению промахов кэша. Ну и ветвления вообще неплохо тормозят систему (сбивается предсказывалка переходов). Но это все конечно действительно СИЛЬНО от железяки зависит. Скажем если мы пишем под процессор msp430, то нам на это пофиг, ибо там нет ни кэша ни предсказаний переходов :-) Зато есть табличка где четко указана стоимость каждой из инструкций в тактах.
Так не в коде прыгать. В данных. Тогда получится, что условие цикла будет меньшее количество раз проверяться (в полтора раза).
Именно прыжки в данных и могут приводить к увеличению промахов кэша.
-
А разве в данном случае не без разницы?
-
Кстати: "инвариант цикла не является единственным".
-
Кстати: "инвариант цикла не является единственным".
:D ;)
-
Кстати: "инвариант цикла не является единственным".
:D ;)
С этого на самом деле можно долго кормиться требуя выдать единственно верный инвариант данного конкретного цикла.
-
Новый рекорд поставлен алгоритмом A6 (взял алгоритм A0 и немножко раскрыл цикл вручную).
static long A6 (char* begin)
{
char* p = begin + 1;
do
{
while (*p != 0)
{
if (*(p+2) == 0)
{
p += 2;
}
else if (*(p+4) == 0)
{
p += 4;
}
else if (*(p+6) == 0)
{
p += 6;
}
else if (*(p+8) == 0)
{
p += 8;
}
else
{
p += 10;
}
}
p--;
}
while (*p != 0);
return (long)(p - begin);
}
Добавление следующей ветки с прыжком на +12 позиций перестало давать улучшение и даже наоборот сильно ухудшило результат, поэтому остановился на прыжке в +10 позиций.
Итого (делалось по три прогона):
A6:
1.9233069 seconds
1.9081622 seconds
1.9067381 seconds
A0:
2.9498565 seconds
2.9519935 seconds
2.95218 seconds
A5:
2.9516315 seconds
2.9512815 seconds
2.9507045 seconds
A1:
3.0003191 seconds
3.0015618 seconds
3.002155 seconds
A2:
5.5711093 seconds
5.5719351 seconds
5.571565 seconds
A3:
5.5734382 seconds
5.5723023 seconds
5.572676 seconds
A4:
6.7624739 seconds
6.7605317 seconds
6.7603002 seconds
-
Интересно, тут экономия только на арифметике или еще на предсказаниях переходов?
-
Интересно, тут экономия только на арифметике или еще на предсказаниях переходов?
Я думаю это 100% за счёт спекулятивных вычислений процессора Sandy Bridge. Алгоритм А6 указывает на их глубину в этом процессоре.
Начиная кажется с Pentium 4 процессоры спекулятивно вычисляют обе ветки if-else параллельно с вычислением условия.