Comments 147
Во-первых, забыли объявить
Во-вторых, забыли вернуть false в случае не нахождения цифры
В-третьих, в чём сакральный смысл отказа от регулярок?
В-четвёртых:
$i, потому выскакивает NoticeВо-вторых, забыли вернуть false в случае не нахождения цифры
В-третьих, в чём сакральный смысл отказа от регулярок?
В-четвёртых:
function check_for_number($str)
{
$lenght = strlen($str);
for($i=0;$i<$lenght;)
{
if ((int)$str[$i++])
{
return true;
}
}
return false;
}
var_dump(check_for_number('test-111111')); // true
var_dump(check_for_number('test-000000')); // epic fail
Точно! Спасибо за указание на ошибку. Пофиксил (добавил if ((int)$str[$i++] === 0))
Та же хрень =)
Всё =) сделал if (is_numeric($str[$i++]))
угу, теперь верно. но можно улучшить:
function check_for_number($str) {
$i = strlen($str);
while ($i--) {
if (is_numeric($str[$i])) return true;
}
return false;
}
А в чём прикол? в том, что нет лишнего сравнения $i<$lenght?
function check_for_number($str) {
for ($=0;$i++;$i<10)
if (strpos($str,$i)!==false) return true;
return false;
}
не запускал.
но работать на длинных строках должно быстрее. (хотя это только моя догадка)) )
for ($=0;$i++;$i<10)
if (strpos($str,$i)!==false) return true;
return false;
}
не запускал.
но работать на длинных строках должно быстрее. (хотя это только моя догадка)) )
На длинной строке без чисел работает за 10*n операций, в то время как предложенный — за n. (где n — длина строки).
Вы точно правильно считали? ;)
А где я считаю неправильно?
Предложенный в худшем случае делает n итераций, в каждой из которых проверяет подстроку(символ) на то, что он число, и там неизвестно, сколько операций производится. (вы смотрели ее исходники? )) )
В моем варианте всего 10 итераций(в худшем случае), но ф-я strpos имеет так же линейную сложность.
так что в терминах языка, мой вариант имеет меньшую сложность. А вот быстродействие надо проверять на практике.
В моем варианте всего 10 итераций(в худшем случае), но ф-я strpos имеет так же линейную сложность.
так что в терминах языка, мой вариант имеет меньшую сложность. А вот быстродействие надо проверять на практике.
Проверил быстродействие. Предложенный Вами способ на большинстве наборов данных на очень больших строках (десятки мегабайт) обычно показывает самые лучшие результаты по сравнению с другими способами, если цифры встречаются далеко от начала или конца строки.
Исключение составляет лишь использование strbrk, которое работает быстрее в неудачных для Вашего способа случаях (например, когда строка заканчивается на 9), но зато недостаток strbrk — копирование результирующей строки — сводит на нет преимущество strbrk в скорости за счет высокого потребления памяти.
То есть, Ваш способ имеет право на жизнь, хотя и в редких случаях.
P.S. Кстати, чтобы этот способ работал, нужно немного изменить код:
Исключение составляет лишь использование strbrk, которое работает быстрее в неудачных для Вашего способа случаях (например, когда строка заканчивается на 9), но зато недостаток strbrk — копирование результирующей строки — сводит на нет преимущество strbrk в скорости за счет высокого потребления памяти.
То есть, Ваш способ имеет право на жизнь, хотя и в редких случаях.
P.S. Кстати, чтобы этот способ работал, нужно немного изменить код:
function hasDigit($str) {
$haystack = '0123456789';
for ($i = 0; $i <= 9; ++$i) {
if (strpos($str, $haystack[$i]) !== false) {
return true;
}
}
return false;
}
Лучше бы notice убрали xD
Ваш пример, впрочем как и первый, вернет тру если хотя бы один символ будет цифрой.
Я бы использовал функцию Ord для определения принадлежности переданной строки к числу.
Я бы использовал функцию Ord для определения принадлежности переданной строки к числу.
ммм, не совсем понятна вся сложность задачи.
Простенький такой вариант на python-е:
Простенький такой вариант на python-е:
def integer_in_string(str=''):
for x in range(10):
if x in str:
return True
return False
Если я правильно понимаю, и x in str выполняется таким-же перебором по порядку от начала и пока не встретится x в str, то, скажем для строки string9 питон сначала пробежится по строке полностью в поисках единицы, потом в поисках двойки и ещё 7 раз. Поправьте меня, если я не прав.
def int_in_str(str=""):
… return filter(lambda x: x.isdigit(), str)!=""
… return filter(lambda x: x.isdigit(), str)!=""
Ну и в тему «конкурса» — решение на Javascript:
String.prototype.hasDigit = function () {
for (var i = this.length; i--;) {
if (!isNaN(this[i])) return true;
}
return false;
};
Я так понимаю, что тут тоже ошибка, если будет строка типа «hello-000-hello»
String.prototype.hasDigit = function () {
for (var i = this.length; i--;) {
if (!isNaN(this[i])) return true;
}
return false;
};
alert([
'hello-000-hello'.hasDigit() ? 1 : 0, // 1
'hello-111-hello'.hasDigit() ? 1 : 0, // 1
'hello-xxx-hello'.hasDigit() ? 1 : 0 // 0
]);
Нет, тут её нет :)
Тут проверка на isNaN — NotANumber, так что ошибки нет.
Тоже не понимаю
ps.
Этот код по вашей ссылке станет причиной ошибок в некоторых браузерах. Лучше так:
ps.
/\d/.test(this);Этот код по вашей ссылке станет причиной ошибок в некоторых браузерах. Лучше так:
!this.match(/\d/);
Видимо это последствия фразы «если вы собираетесь решить проблему с помощью рег. выражений — значит у вас уже две проблемы» :)
def has_digit(value):
return ''.join([_ for _ in value if _.isdigit()]) or False
С возвратом всех цифр, которые есть в строке
return ''.join([_ for _ in value if _.isdigit()]) or False
С возвратом всех цифр, которые есть в строке
Интересный подход. Мой ответ на js:
Или Javascript 1.8:
String.prototype.hasDigit = function () {
return this.split('').filter(isNaN).join('').length == this.length;
};
Или Javascript 1.8:
String.prototype.hasDigit = function () {
return !!this.split('').filter(function(v) !isNaN(v)).length;
};
Забыл про some. Вот так правильнее:
String.prototype.hasDigit = function () {
return this.split('').some(function(v) !isNaN(v));
};
Забыл про every))
String.prototype.hasDigit = function () {
return !this.split('').every(isNaN);
};
Красиво, хоть я ничего и не понял =)
у меня похожий результат
String.prototype.hasDigit = function(){
return !!Array.prototype.filter.call(this, function(){if(!isNaN(arguments[0])){return true}}).length
}
Кстати,
Array.prototype.filter.call можно было заменить на [].filter.callА
if(!isNaN(arguments[0])){return true} на return !isNaN(arguments[0]). Хотя лучше добавить аргумент в объявление и тогда получится такой код:String.prototype.hasDigit = function(){
return !![].filter.call(this, function(a){ return !isNaN(a) }).length
}
// Javascript 1.8:
String.prototype.hasDigit = function(){
return !![].filter.call(this, function(a) !isNaN(a) ).length
}
Красивый python way. Стало стыдновато за свое решение =)
Позволите чуть-чуть допилить, до условия в топике?
Позволите чуть-чуть допилить, до условия в топике?
def has_digit(value):
return any(''.join([_ for _ in value if _.isdigit()]))
Тогда так:
def has_digit(value):
return any([True for _ in value if _.isdigit()])
Извиняюсь за форматирование, кармы нет, а пасер лох.
def has_digit(value):
return any([True for _ in value if _.isdigit()])
Извиняюсь за форматирование, кармы нет, а пасер лох.
def has_digit(value): return value.isalpha()==value.isalnum()
или так:
def has_digit(value): return sorted(value)[0].isdigit()
или так:
def has_digit(value): return any((i in value) for i in '0123456789')
def has_digit(value): return any((i in value) for i in string.digits)
def has_digit(value): return any((i in value) for i in map(str,range(10)))
или так:
def has_digit(value): return value==value.strip(string.digits)
def has_digit(value): return len(value)==len(value.strip(string.digits))
ну и ещё много-много извращенных способов можно придумать для этой обычной (ничего ненормального) задачи.
А чего ненормального в подобной задаче?
UFO just landed and posted this here
Что в этой задаче интересного, и какой ещё может быть подход, кроме очевидного?
strpbrk() (PHP 5)
Вот, я думаю, что это самый лучший ответ. Функция быстрее будет работать, чем самописный цикл?
Что-то мои тесты (~100 MB текста с цифрой в конце) показали, что самописный цикл работает быстрее…
Может быть это потому, что эта функция возвращает не просто да/нет, а часть строки начиная с той позиции, где был найден символ.
Может быть это потому, что эта функция возвращает не просто да/нет, а часть строки начиная с той позиции, где был найден символ.
как на счет strspn() (PHP)?
Странно, на моих тестах strpbrk() работает быстрее любых других способов в PHP на больших строках 100 Mb с цифрой в конце (конечно, не считая самописного цикла, который перебирает с конца).
Да и вообще, если бы не копирование строки (и соответственно более высокое потребление памяти), этот способ можно было бы признать лучшим для большинства случаев.
Но не для всех случаев, так как с цифрой вначале, а также на очень коротких строках — уже нет, этот способ не является лучшим.
Да и вообще, если бы не копирование строки (и соответственно более высокое потребление памяти), этот способ можно было бы признать лучшим для большинства случаев.
Но не для всех случаев, так как с цифрой вначале, а также на очень коротких строках — уже нет, этот способ не является лучшим.
Оптимизированное по какому критерию? Скорость работы, потребление памяти, LOC, синтаксический сахар?
по скорости работы и потреблению памяти. Второе важнее
Если в лоб линейно от размера строки и константно по памяти.
const char *pointer; const char *source; const int current; for (pointer = source; (current = *pointer++) != 0;) if (table[current]) return true;
Без дополнительно памяти
const char *pointer; const char *source; const char current; for (pointer = source; (current = *pointer++) != 0;) if (isalpha(char)) return true;
UFO just landed and posted this here
function check_for_number($str)
{
for ($i = strlen($str) - 1; $i >= 0 && ($str[$i] < '0' || $str[$i] > '9'); --$i);
return $i >= 0;
}
Haskell:
check = any isDigit
ПоХаПэ:
Такая версия функции, на выборке из 10000 строк, работает в несколько раз быстрее вашей версии.
function check_for_number($str, $range){
return ($str != str_replace($range, '', $str));
}
$test_string = 'test-0123456';
$range = range('0', '9');
var_dump(check_for_number($test_string, $range));
$test_string = 'test';
var_dump(check_for_number($test_string, $range));
Такая версия функции, на выборке из 10000 строк, работает в несколько раз быстрее вашей версии.
Дааа, Haskell конечно крут =)
Задачка простенькая, красивая. вопрошающим почему не регулярные выражения — а вы сложность сравните) не только для этой простой задачи, а и для любой другой. ну и практикум конечно тоже)
Karde, у вас количество перебираемых символов аж 10*length(s) — это очень много.
TheShock у вас офигенная логика, правда, (напомнила [аж гуглить пришлось, уже и забыл фамилию] Погорелова) но потребление памяти наверное не маленькое (хотя зависит от того копируется ли строка при split'e) ну и перебор по объектам… Зато синтаксический сахар очевидный :) я бы даже сказал ванилин — мне понравилось)
Задачка простенькая, красивая. вопрошающим почему не регулярные выражения — а вы сложность сравните) не только для этой простой задачи, а и для любой другой. ну и практикум конечно тоже)
Karde, у вас количество перебираемых символов аж 10*length(s) — это очень много.
TheShock у вас офигенная логика, правда, (напомнила [аж гуглить пришлось, уже и забыл фамилию] Погорелова) но потребление памяти наверное не маленькое (хотя зависит от того копируется ли строка при split'e) ну и перебор по объектам… Зато синтаксический сахар очевидный :) я бы даже сказал ванилин — мне понравилось)
Даю самый красивый вариант решения:
frozenset(«1234567890») & frozenset (teststing)
Возвращает пустое множество, если цифр нет, ненулевое множество (содержащее найденные цифры) если цифры есть.
Задача на одну строчку. О чём вопрос?
frozenset(«1234567890») & frozenset (teststing)
Возвращает пустое множество, если цифр нет, ненулевое множество (содержащее найденные цифры) если цифры есть.
Задача на одну строчку. О чём вопрос?
Через коды символов
че-то не получается код вставить
dumpz.org/32884/
dumpz.org/32884/
Для Delphi:
function IsHaveDigit(str: string): Boolean;
var
StrLength: Integer;
I: Integer;
begin
StrLength := Length(str);
if StrLength > 0 then
begin
for I := 1 to StrLength do
begin
if str[I] in ['0'..'9'] then
begin
Result := True;
Exit;
end;
end;
end;
Result := False;
end;
function IsHaveDigit(str: string): Boolean;
var
StrLength: Integer;
I: Integer;
begin
StrLength := Length(str);
if StrLength > 0 then
begin
for I := 1 to StrLength do
begin
if str[I] in ['0'..'9'] then
begin
Result := True;
Exit;
end;
end;
end;
Result := False;
end;
Зачем над паскалем так издеваться? И при чем тут Delphi?
Вы зачем столько begin-end'ов натыкали?
а в чем «интересность задачи»?
и почему в «ненормальном программировании»?
и почему в «ненормальном программировании»?
на C#
bool hasDigit(string str)
{
return (str.IndexOfAny("1234567890".ToCharArray()) >= 0);
}
Это решение отработает как и одно из вышепрведенных на PHP — за 10*n операций.
habrahabr.ru/blogs/crazydev/113544/#comment_3649174 — самое правильное.
На яве (ынтерпрайз инклюдед):
class Finder {
public static boolean hasDigit(String s) {
for(char c: s.toCharArray())
if(c >= '0' && c
habrahabr.ru/blogs/crazydev/113544/#comment_3649174 — самое правильное.
На яве (ынтерпрайз инклюдед):
class Finder {
public static boolean hasDigit(String s) {
for(char c: s.toCharArray())
if(c >= '0' && c
static bool HasDigit(String input)
{
return input.Any(c => Char.IsDigit©);
}
perl:
bool hasDigit(char* str)
{
int tmp[256];
for (char* pos = str; *pos; ++pos) ++tmp[*pos];
for (char i = '0'; i <= '9'; ++i) if (tmp[i]) return true;
return false;
}
Не подумал :(
bool hasDigit(char* str)
{
int tmp[256];
for (char i = '0'; i <= '9'; ++i) tmp[i] = 0;
for (char* pos = str; *pos; ++pos) ++tmp[*pos];
for (char i = '0'; i <= '9'; ++i) if (tmp[i]) return true;
return false;
}
фууу…
мало того что вы 256 ячеек памяти (причём int а не byte ;D ) заняли, так ещё и умудрились 20 лишних итераций впихнуть.
выкиньте первый и последний цикл и напишите в теле оставшегося что то вроде if ((*pos>='0')&&(*pos<='9'))
return true;
уже будет логичнее красивее. а вы целый частотный словарь строите, а потом анализируете в нем промежуток 0..9.
мало того что вы 256 ячеек памяти (причём int а не byte ;D ) заняли, так ещё и умудрились 20 лишних итераций впихнуть.
выкиньте первый и последний цикл и напишите в теле оставшегося что то вроде if ((*pos>='0')&&(*pos<='9'))
return true;
уже будет логичнее красивее. а вы целый частотный словарь строите, а потом анализируете в нем промежуток 0..9.
borisko@vaio:~/test-num$ cat test.cpp#include <stdio.h>
#define LEN (1000 * 1000 * 100)
char line[LEN + 1];
bool hasDigit(char* str)
{
#ifdef MY_METHOD
int tmp[256];
for (char i = '0'; i <= '9'; ++i) tmp[i] = 0;
for (char *pos = str; *pos; ++pos) ++tmp[*pos];
for (char i = '0'; i <= '9'; ++i) if (tmp[i]) return true;
return false;
#else
for (char *pos = str; *pos; ++pos) if ('0' <= *pos && *pos <= '9') return true;
return false;
#endif
}
int main()
{
for(int i = 0; i < LEN; ++i) line[i] = 'a';
line[LEN] = 0;
hasDigit(line);
}borisko@vaio:~/test-num$ g++ -o test_your -O3 test.cpp
borisko@vaio:~/test-num$ g++ -o test_my -O3 -DMY_METHOD test.cpp
borisko@vaio:~/test-num$ time ./test_your
real 0m0.129s
user 0m0.083s
sys 0m0.045s
borisko@vaio:~/test-num$ time ./test_my
real 0m0.054s
user 0m0.012s
sys 0m0.040s
Зато, мой вариант работает быстрее Вашего больше, чем в 8 раз.
Вы знаете, я почти поверил в то что ваш вариант быстрее. Поскольку в моем по факту 4 вычитания и 2 сравнения в теле цикла, а у вас всего лишь 1 инкремент.
но решил проверить — результат прямо противоположный.
./maketest
puzzle@somehost:/home/puzzle/habr# time ./test_borisko3
real 0m0.401s
user 0m0.252s
sys 0m0.148s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle3
real 0m0.257s
user 0m0.108s
sys 0m0.144s
puzzle@somehost:/home/puzzle/habr#
time ./test_borisko
real 0m0.899s
user 0m0.340s
sys 0m0.556s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.746s
user 0m0.640s
sys 0m0.108s
Но обратите внимание на результаты в вариантах БЕЗ оптимизации!
cpp полностью скопирован из вашего.
решил перепроверить несколько раз и вот результаты:
borisko with -O3
real 0:00.40 user 0.25 sys 0.14
real 0:00.40 user 0.26 sys 0.13
real 0:00.41 user 0.25 sys 0.15
real 0:00.40 user 0.26 sys 0.13
real 0:00.42 user 0.28 sys 0.13
puzzle with -O3
real 0:00.26 user 0.12 sys 0.13
real 0:00.24 user 0.11 sys 0.13
real 0:00.24 user 0.11 sys 0.13
real 0:00.26 user 0.11 sys 0.14
real 0:00.25 user 0.11 sys 0.14
borisko
real 0:00.77 user 0.63 sys 0.13
real 0:00.76 user 0.62 sys 0.14
real 0:00.75 user 0.58 sys 0.17
real 0:00.76 user 0.61 sys 0.15
real 0:00.76 user 0.58 sys 0.18
puzzle
real 0:00.77 user 0.58 sys 0.18
real 0:00.76 user 0.58 sys 0.17
real 0:00.76 user 0.60 sys 0.16
real 0:00.76 user 0.62 sys 0.14
real 0:00.77 user 0.61 sys 0.15
(дергалось скриптом из под /bin/sh)
вот более детально:
borisko with -O3
real 0m0.402s
user 0m0.264s
sys 0m0.136s
real 0m0.395s
user 0m0.268s
sys 0m0.124s
real 0m0.398s
user 0m0.256s
sys 0m0.140s
real 0m0.405s
user 0m0.264s
sys 0m0.136s
real 0m0.400s
user 0m0.260s
sys 0m0.136s
puzzle with -O3
real 0m0.247s
user 0m0.108s
sys 0m0.140s
real 0m0.249s
user 0m0.108s
sys 0m0.136s
real 0m0.242s
user 0m0.100s
sys 0m0.140s
real 0m0.243s
user 0m0.116s
sys 0m0.124s
real 0m0.240s
user 0m0.104s
sys 0m0.132s
borisko
real 0m0.753s
user 0m0.596s
sys 0m0.152s
real 0m0.761s
user 0m0.628s
sys 0m0.132s
real 0m0.751s
user 0m0.580s
sys 0m0.172s
real 0m0.750s
user 0m0.592s
sys 0m0.156s
real 0m0.760s
user 0m0.604s
sys 0m0.152s
puzzle
real 0m0.762s
user 0m0.628s
sys 0m0.132s
real 0m0.761s
user 0m0.624s
sys 0m0.132s
real 0m0.760s
user 0m0.612s
sys 0m0.144s
real 0m0.762s
user 0m0.592s
sys 0m0.168s
real 0m0.762s
user 0m0.636s
sys 0m0.124s
перед отправкой ещё раз решил вызвать time вручную, смотрите:
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.774s
user 0m0.544s
sys 0m0.228s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.766s
user 0m0.604s
sys 0m0.160s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.798s
user 0m0.504s
sys 0m0.296s
puzzle@somehost:/home/puzzle/habr#
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.753s
user 0m0.588s
sys 0m0.164s
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.749s
user 0m0.508s
sys 0m0.240s
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.749s
user 0m0.592s
sys 0m0.156s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.809s
user 0m0.384s
sys 0m0.420s
Массовые результаты по крайней мере не сильно друг от друга отличаются, а вот разовое исполнение удивляет.
вот ./maketest
#!/bin/bash
rm test_*
g++ -o test_puzzle3 -O3 test.cpp
g++ -o test_borisko3 -O3 -DMY_METHOD test.cpp
g++ -o test_puzzle test.cpp
g++ -o test_borisko -DMY_METHOD test.cpp
echo borisko with -O3
time ./test_borisko3
time ./test_borisko3
time ./test_borisko3
time ./test_borisko3
time ./test_borisko3
echo puzzle with -O3
time ./test_puzzle3
time ./test_puzzle3
time ./test_puzzle3
time ./test_puzzle3
time ./test_puzzle3
echo borisko
time ./test_borisko
time ./test_borisko
time ./test_borisko
time ./test_borisko
time ./test_borisko
echo puzzle
time ./test_puzzle
time ./test_puzzle
time ./test_puzzle
time ./test_puzzle
time ./test_puzzle
(repeat не использовал потому что его нет в sh в котором работает форматирование для time)
Есть идеи? =)
но решил проверить — результат прямо противоположный.
./maketest
puzzle@somehost:/home/puzzle/habr# time ./test_borisko3
real 0m0.401s
user 0m0.252s
sys 0m0.148s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle3
real 0m0.257s
user 0m0.108s
sys 0m0.144s
puzzle@somehost:/home/puzzle/habr#
time ./test_borisko
real 0m0.899s
user 0m0.340s
sys 0m0.556s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.746s
user 0m0.640s
sys 0m0.108s
Но обратите внимание на результаты в вариантах БЕЗ оптимизации!
cpp полностью скопирован из вашего.
решил перепроверить несколько раз и вот результаты:
borisko with -O3
real 0:00.40 user 0.25 sys 0.14
real 0:00.40 user 0.26 sys 0.13
real 0:00.41 user 0.25 sys 0.15
real 0:00.40 user 0.26 sys 0.13
real 0:00.42 user 0.28 sys 0.13
puzzle with -O3
real 0:00.26 user 0.12 sys 0.13
real 0:00.24 user 0.11 sys 0.13
real 0:00.24 user 0.11 sys 0.13
real 0:00.26 user 0.11 sys 0.14
real 0:00.25 user 0.11 sys 0.14
borisko
real 0:00.77 user 0.63 sys 0.13
real 0:00.76 user 0.62 sys 0.14
real 0:00.75 user 0.58 sys 0.17
real 0:00.76 user 0.61 sys 0.15
real 0:00.76 user 0.58 sys 0.18
puzzle
real 0:00.77 user 0.58 sys 0.18
real 0:00.76 user 0.58 sys 0.17
real 0:00.76 user 0.60 sys 0.16
real 0:00.76 user 0.62 sys 0.14
real 0:00.77 user 0.61 sys 0.15
(дергалось скриптом из под /bin/sh)
вот более детально:
borisko with -O3
real 0m0.402s
user 0m0.264s
sys 0m0.136s
real 0m0.395s
user 0m0.268s
sys 0m0.124s
real 0m0.398s
user 0m0.256s
sys 0m0.140s
real 0m0.405s
user 0m0.264s
sys 0m0.136s
real 0m0.400s
user 0m0.260s
sys 0m0.136s
puzzle with -O3
real 0m0.247s
user 0m0.108s
sys 0m0.140s
real 0m0.249s
user 0m0.108s
sys 0m0.136s
real 0m0.242s
user 0m0.100s
sys 0m0.140s
real 0m0.243s
user 0m0.116s
sys 0m0.124s
real 0m0.240s
user 0m0.104s
sys 0m0.132s
borisko
real 0m0.753s
user 0m0.596s
sys 0m0.152s
real 0m0.761s
user 0m0.628s
sys 0m0.132s
real 0m0.751s
user 0m0.580s
sys 0m0.172s
real 0m0.750s
user 0m0.592s
sys 0m0.156s
real 0m0.760s
user 0m0.604s
sys 0m0.152s
puzzle
real 0m0.762s
user 0m0.628s
sys 0m0.132s
real 0m0.761s
user 0m0.624s
sys 0m0.132s
real 0m0.760s
user 0m0.612s
sys 0m0.144s
real 0m0.762s
user 0m0.592s
sys 0m0.168s
real 0m0.762s
user 0m0.636s
sys 0m0.124s
перед отправкой ещё раз решил вызвать time вручную, смотрите:
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.774s
user 0m0.544s
sys 0m0.228s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.766s
user 0m0.604s
sys 0m0.160s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.798s
user 0m0.504s
sys 0m0.296s
puzzle@somehost:/home/puzzle/habr#
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.753s
user 0m0.588s
sys 0m0.164s
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.749s
user 0m0.508s
sys 0m0.240s
puzzle@somehost:/home/puzzle/habr# time ./test_borisko
real 0m0.749s
user 0m0.592s
sys 0m0.156s
puzzle@somehost:/home/puzzle/habr# time ./test_puzzle
real 0m0.809s
user 0m0.384s
sys 0m0.420s
Массовые результаты по крайней мере не сильно друг от друга отличаются, а вот разовое исполнение удивляет.
вот ./maketest
#!/bin/bash
rm test_*
g++ -o test_puzzle3 -O3 test.cpp
g++ -o test_borisko3 -O3 -DMY_METHOD test.cpp
g++ -o test_puzzle test.cpp
g++ -o test_borisko -DMY_METHOD test.cpp
echo borisko with -O3
time ./test_borisko3
time ./test_borisko3
time ./test_borisko3
time ./test_borisko3
time ./test_borisko3
echo puzzle with -O3
time ./test_puzzle3
time ./test_puzzle3
time ./test_puzzle3
time ./test_puzzle3
time ./test_puzzle3
echo borisko
time ./test_borisko
time ./test_borisko
time ./test_borisko
time ./test_borisko
time ./test_borisko
echo puzzle
time ./test_puzzle
time ./test_puzzle
time ./test_puzzle
time ./test_puzzle
time ./test_puzzle
(repeat не использовал потому что его нет в sh в котором работает форматирование для time)
Есть идеи? =)
Кстати, претензия к int снята %)
Это уже интересный результат — кинул Вам в ПМ ssh на сервер, где я только что получил обратный — 0.00-0.01user для моего варианта и 0.07-0.08user для Вашего.
Неоптмизированные в среднем там выполняются одинаковое время (0.58-0.62).
Можете рассказать Вашу версию gcc и архитектуру?
Неоптмизированные в среднем там выполняются одинаковое время (0.58-0.62).
Можете рассказать Вашу версию gcc и архитектуру?
рассказываю
ubuntu server 10 (32 битный как я понимаю) в vmware 7.xx на w7x64@Q8400+4GbDDR2
MACHTYPE=i686-pc-linux-gnu
/home/puzzle/habr# g++ --version
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
полностью повторил вчерашний эксперимент:
вот логи maketest: pastebin.com/6sgS7H4V
второй хост: (vds 300mhz, 64 ram, freebsd)
(bash там не было, поэтому в makefile исправил на /bin/sh, по идее x86)
> g++ --version
g++ (GCC) 4.2.1 20070719 [FreeBSD]
вот результаты: pastebin.com/Z0fsJyB5
(кстати, они подтверждают Ваши!)
А вот что ещё интересно, на этом же хосте (без скрипта): pastebin.com/RjbrXmwU
В общем, у меня складывается впечатление что накладные расходы на запуск процесса едва ли не больше чем само время его выполнения.
вот результаты этого же скрипта на вашем хосте:
MACHTYPE=x86_64-redhat-linux-gnu
OSTTYPE=x86_64
g++ (GCC) 4.5.1 20100924 (Red Hat 4.5.1-4)
pastebin.com/76bhjjtH
мой вариант действительно тут медленнее.
но это ещё не всё! =) смотрите мой пост ниже.
ubuntu server 10 (32 битный как я понимаю) в vmware 7.xx на w7x64@Q8400+4GbDDR2
MACHTYPE=i686-pc-linux-gnu
/home/puzzle/habr# g++ --version
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
полностью повторил вчерашний эксперимент:
вот логи maketest: pastebin.com/6sgS7H4V
второй хост: (vds 300mhz, 64 ram, freebsd)
(bash там не было, поэтому в makefile исправил на /bin/sh, по идее x86)
> g++ --version
g++ (GCC) 4.2.1 20070719 [FreeBSD]
вот результаты: pastebin.com/Z0fsJyB5
(кстати, они подтверждают Ваши!)
А вот что ещё интересно, на этом же хосте (без скрипта): pastebin.com/RjbrXmwU
В общем, у меня складывается впечатление что накладные расходы на запуск процесса едва ли не больше чем само время его выполнения.
вот результаты этого же скрипта на вашем хосте:
MACHTYPE=x86_64-redhat-linux-gnu
OSTTYPE=x86_64
g++ (GCC) 4.5.1 20100924 (Red Hat 4.5.1-4)
pastebin.com/76bhjjtH
мой вариант действительно тут медленнее.
но это ещё не всё! =) смотрите мой пост ниже.
Я попробовал так:
Получились реультаты
Method1: 0.157560, 0
Method2: 0.100310, 0
Method3: 0.097030, 0
Так что через массив в полтора раза дольше.
Компилятор — VS 2008.
Странно, что когда я не использовал переменную res, а просто вызывал HasDigit, то первый метод потребовал нулевое время — компилятор его соптимизировал полностью :)
#include <stdio.h>
#include <time.h>
#define LEN (1000 * 1000 * 100)
char line[LEN + 1];
bool HasDigit1(char* str)
{
int tmp[256];
for (char i = '0'; i <= '9'; ++i) tmp[i] = 0;
for (char *pos = str; *pos; ++pos) ++tmp[*pos];
for (char i = '0'; i <= '9'; ++i) if (tmp[i]) return true;
return false;
}
bool HasDigit2(char *str){
for (char *pos = str; *pos; ++pos) if ('0' <= *pos && *pos <= '9') return true;
return false;
}
bool HasDigit3(char *str){
while(*str) if((unsigned int)(*str++-'0')<10) return true;
return false;
}
int main()
{
for(int i = 0; i < LEN; ++i) line[i] = 'a';
line[LEN] = 0;
int N=100;
int res=0;
long m=clock();
for(int i=0;i<N; i++) res+=HasDigit1(line) ? 1 : 0;
m=clock()-m;
printf("Method1: %lf, %d\n",(double)m/N/CLOCKS_PER_SEC,res);
m=clock(); res=0;
for(int i=0;i<N; i++) res+=HasDigit2(line) ? 1 : 0;
m=clock()-m;
printf("Method2: %lf, %d\n",(double)m/N/CLOCKS_PER_SEC,res);
m=clock(); res=0;
for(int i=0;i<N; i++) res+=HasDigit3(line) ? 1 : 0;
m=clock()-m;
printf("Method3: %lf, %d\n",(double)m/N/CLOCKS_PER_SEC,res);
scanf("%d",&N);
}
Получились реультаты
Method1: 0.157560, 0
Method2: 0.100310, 0
Method3: 0.097030, 0
Так что через массив в полтора раза дольше.
Компилятор — VS 2008.
Странно, что когда я не использовал переменную res, а просто вызывал HasDigit, то первый метод потребовал нулевое время — компилятор его соптимизировал полностью :)
Забавно :)
gcc-4.5.1, slackware64-current, core i5 m520:
C -O3
borisko@vaio:~/test-num$ ./test2
Method1: 0.003000, 0
Method2: 0.079900, 0
Method3: 0.116000, 0
C -O0
Method1: 0.730300, 0
Method2: 0.323600, 0
Method3: 0.284900, 0
gcc-4.5.1, slackware-current, в qemu-kvm виртуалке, Pentium D E5500:
С -O3
root@server:~/test0# ./test
Method1: 0.002400, 0
Method2: 0.090500, 0
Method3: 0.112700, 0
C -O0
Method1: 0.340100, 0
Method2: 0.305500, 0
Method3: 0.280500, 0
Видимо, всё зависит не только от сути, но и от конкретных особенностей оптимизатора компилятора.
Совсем не понятно, что случилось с первым методом без оптимизации на 64битном процессоре.
gcc-4.5.1, slackware64-current, core i5 m520:
C -O3
borisko@vaio:~/test-num$ ./test2
Method1: 0.003000, 0
Method2: 0.079900, 0
Method3: 0.116000, 0
C -O0
Method1: 0.730300, 0
Method2: 0.323600, 0
Method3: 0.284900, 0
gcc-4.5.1, slackware-current, в qemu-kvm виртуалке, Pentium D E5500:
С -O3
root@server:~/test0# ./test
Method1: 0.002400, 0
Method2: 0.090500, 0
Method3: 0.112700, 0
C -O0
Method1: 0.340100, 0
Method2: 0.305500, 0
Method3: 0.280500, 0
Видимо, всё зависит не только от сути, но и от конкретных особенностей оптимизатора компилятора.
Совсем не понятно, что случилось с первым методом без оптимизации на 64битном процессоре.
я решил учесть негативное влияние накладных расходов и воспользоваться вашим методом подсчёта (точнее, вашим исходником =) )
вот набор результатов полученных мною на win7x64 msvs2008:
(менял и размер строки, и количество итераций для проверки)
Method1: 0.371660, 0
Method2: 0.343120, 0
Method3: 0.316570, 0
(это по-моему почти гигабайная строка, 10^9, и 1000 итераций)
Method1: 3.719880, 0
Method2: 3.476280, 0
Method3: 3.174450, 0
с использованием 4 варианта:
Method1: 0.372020, 0
Method2: 0.350170, 0
Method3: 0.319430, 0
Method4: 0.206550, 0
но потом я решил запустить эту же версию на *nix, вот результаты:
мой первый хост с убунту:
puzzle@somehost:/home/puzzle/habr/3# ./test_3
Method1: 0.256500, 0
Method2: 0.100500, 0
Method3: 0.125500, 0
^^^^^^^^^^^^^^^^ странно?!
0
puzzle@somehost:/home/puzzle/habr/3# ./test_
Method1: 0.378600, 0
Method2: 0.339100, 0
Method3: 0.310600, 0
vds: (но пришлось уменьшить длину строки до 10 метров, иначе убивалось)
with -O3
Method1: 0.026016, 0
Method2: 0.010859, 0
Method3: 0.012344, 0 — такое ощущение что компилятор сам себе переоптимизировал
without
Method1: 0.034609, 0
Method2: 0.037656, 0
Method3: 0.027734, 0
borisko's host:
with -O3
Method1: 0.002200, 0
Method2: 0.073700, 0
Method3: 0.109700, 0
КАК???
without
Method1: 0.299400, 0
Method2: 0.299900, 0
Method3: 0.273300, 0
в общем — я не удержался, простите заранее :)
у вас стоит аж CPU0: Intel® Core(TM) i7 CPU 920 @ 2.67GHz
я покопался и нашёл в окрестностях i5 650 — пошёл проверять на нём =)))
на нём все странно (win7x64)
Method1: 0.667020, 100 — странно исходя из предположения что дело в платформе iXXX
Method2: 0.287640, 100
Method3: 0.291820, 100
Method4: 0.105980, 100
Покопался ещё и запустил бинарник (опять винда, но на этот раз 2008) на X5650
Вот результаты:
Method1: 0.209740, 100
Method2: 0.105180, 100
Method3: 0.102230, 100
Method4: 0.038360, 100
опять всё ожидаемо.
Итого…
borisko, колитесь — ЧТО у вас за система такая реактивная? :)))
Mrrl: а у вас нет идей?
PS. с одной стороны, я считаю что сравнивать «на скорость» вообще имеет смысл только алгоритмы, дабы избежать влияния оптимизаций (не будем забывать что у нас синтетический тест со статическими входными данными)
с другой же, я прекрасно понимаю что практика — критерий истины. с этой стороны — оптимизации компилятора и кода (не алгоритма! привет (unsigned int) :) ) штука необходимая.
вот набор результатов полученных мною на win7x64 msvs2008:
(менял и размер строки, и количество итераций для проверки)
Method1: 0.371660, 0
Method2: 0.343120, 0
Method3: 0.316570, 0
(это по-моему почти гигабайная строка, 10^9, и 1000 итераций)
Method1: 3.719880, 0
Method2: 3.476280, 0
Method3: 3.174450, 0
с использованием 4 варианта:
Method1: 0.372020, 0
Method2: 0.350170, 0
Method3: 0.319430, 0
Method4: 0.206550, 0
но потом я решил запустить эту же версию на *nix, вот результаты:
мой первый хост с убунту:
puzzle@somehost:/home/puzzle/habr/3# ./test_3
Method1: 0.256500, 0
Method2: 0.100500, 0
Method3: 0.125500, 0
^^^^^^^^^^^^^^^^ странно?!
0
puzzle@somehost:/home/puzzle/habr/3# ./test_
Method1: 0.378600, 0
Method2: 0.339100, 0
Method3: 0.310600, 0
vds: (но пришлось уменьшить длину строки до 10 метров, иначе убивалось)
with -O3
Method1: 0.026016, 0
Method2: 0.010859, 0
Method3: 0.012344, 0 — такое ощущение что компилятор сам себе переоптимизировал
without
Method1: 0.034609, 0
Method2: 0.037656, 0
Method3: 0.027734, 0
borisko's host:
with -O3
Method1: 0.002200, 0
Method2: 0.073700, 0
Method3: 0.109700, 0
КАК???
without
Method1: 0.299400, 0
Method2: 0.299900, 0
Method3: 0.273300, 0
в общем — я не удержался, простите заранее :)
у вас стоит аж CPU0: Intel® Core(TM) i7 CPU 920 @ 2.67GHz
я покопался и нашёл в окрестностях i5 650 — пошёл проверять на нём =)))
на нём все странно (win7x64)
Method1: 0.667020, 100 — странно исходя из предположения что дело в платформе iXXX
Method2: 0.287640, 100
Method3: 0.291820, 100
Method4: 0.105980, 100
Покопался ещё и запустил бинарник (опять винда, но на этот раз 2008) на X5650
Вот результаты:
Method1: 0.209740, 100
Method2: 0.105180, 100
Method3: 0.102230, 100
Method4: 0.038360, 100
опять всё ожидаемо.
Итого…
borisko, колитесь — ЧТО у вас за система такая реактивная? :)))
Mrrl: а у вас нет идей?
PS. с одной стороны, я считаю что сравнивать «на скорость» вообще имеет смысл только алгоритмы, дабы избежать влияния оптимизаций (не будем забывать что у нас синтетический тест со статическими входными данными)
с другой же, я прекрасно понимаю что практика — критерий истины. с этой стороны — оптимизации компилятора и кода (не алгоритма! привет (unsigned int) :) ) штука необходимая.
Предлагаю поэкспериментировать с другим состоянием строки. Например, так:
Такая строка должна сбить с толку все предсказания переходов с CPU. У меня результаты такие:
Method1: 0.158280
Method2: 0.126480
Method3: 0.099860
Method4: 0.050060
Method5: 0.043820
(метод 5 — работа через unsigned int*, там основной цикл такой:
Из странных вещей — с утра у меня время метода 4 увеличилось с 0.041 сек до 0.05. Возможно, из-за температуры в комнате.
Процессор — AMD Phenom II X4 965, 3.4 GHz
for(int i = 0; i < LEN; ++i){
char s=(char)i;
s^=(s>>7)&1;
if(s==0 || (s>='0' && s<='9')) s='a';
line[i] = s;
}
Такая строка должна сбить с толку все предсказания переходов с CPU. У меня результаты такие:
Method1: 0.158280
Method2: 0.126480
Method3: 0.099860
Method4: 0.050060
Method5: 0.043820
(метод 5 — работа через unsigned int*, там основной цикл такой:
unsigned int *a=(unsigned int *)str;
char m=0;
while(m==0){
unsigned int k=*a++;
m=Tbl[(unsigned short)k];
if(m!=0) break;
m=Tbl[k>>16];
}
return (m&1)!=0;
Из странных вещей — с утра у меня время метода 4 увеличилось с 0.041 сек до 0.05. Возможно, из-за температуры в комнате.
Процессор — AMD Phenom II X4 965, 3.4 GHz
P.S. Интересно, почему у топика такой низкий рейтинг?
Такая строка всё равно соптимизировалась в gcc-4.5 и отработала так:
Method1: 0.003300, 0
Method2: 0.233900, 0
Method1: 0.003300, 0
Method2: 0.233900, 0
Можно еще перед каждым вызовом «пострелять» внутрь строки, как-нибудь так:
for(int i=0;i<N; i++){
for(int j=0;j<LEN;j+=LEN/1000) line[j]=(char)(i+1);
res+=HasDigit1(line)? 1: 0;
}
Если компилятор и тогда его соптимизирует, будет очень интересно.
for(int i=0;i<N; i++){
for(int j=0;j<LEN;j+=LEN/1000) line[j]=(char)(i+1);
res+=HasDigit1(line)? 1: 0;
}
Если компилятор и тогда его соптимизирует, будет очень интересно.
Заменил i+1 на i+'9', в противном случае попадались цифры и методы, делающие return в середине выигрывали.
Но и так Вы уже подловили оптимизатор:
Method1: 0.298900, 1
Method2: 0.077400, 1
Method3: 0.117500, 1
Хотя, clone всё равно остался и вызывается.
Но и так Вы уже подловили оптимизатор:
Method1: 0.298900, 1
Method2: 0.077400, 1
Method3: 0.117500, 1
Хотя, clone всё равно остался и вызывается.
Вообще, данная оптимизация похожа на идею «если str не изменился, то и tmp не изменится, значит. пересчитывать его оставшиеся 99 раз не надо». Но не понятно, почему эта оптимизация не работает на уровне целых функий.
вообще-то она как раз и должна бы работать…
Всем спасибо!
borisko, извините что развенчали ваш способ, он тоже очень хорош, если задача сложнее чем проверка просто наличия какого-либо символа ;)
доступ у меня не забудьте забрать к вашему волшебному компилятору)
Mrrl: огромное спасибо за правильный пример, у меня rand() его так и не подловил, до динамического изменения строки я б ещё думал )
Автору топика, apollonin: спасибо за возвращение меня во времена программирования!) тема хорошая, поднимайте ещё такие ;)
Всем спасибо!
borisko, извините что развенчали ваш способ, он тоже очень хорош, если задача сложнее чем проверка просто наличия какого-либо символа ;)
доступ у меня не забудьте забрать к вашему волшебному компилятору)
Mrrl: огромное спасибо за правильный пример, у меня rand() его так и не подловил, до динамического изменения строки я б ещё думал )
Автору топика, apollonin: спасибо за возвращение меня во времена программирования!) тема хорошая, поднимайте ещё такие ;)
Где же еще такие задачи взять? «Сдвинуть массив на k ячеек циклически, не пользуясь дополнительными массивами»? Из-за второго условия половина шарма пропадает. «Найти фрагмент с максимальной суммой»? Выиграет тот, кто использует double или int64, а на BF задача вообще неподъемна. «Преобразование hex->dec и наоборот»? Хм…
АГАААА!!! попался %)
with -O3
Method1: 0.001500, 0
Method1+: 0.146800, 10 стреляный вариант
Method2: 0.073800, 0
Method3: 0.109000, 0
with -O3
Method1: 0.001500, 0
Method1+: 0.146800, 10 стреляный вариант
Method2: 0.073800, 0
Method3: 0.109000, 0
вот и посидел, только не отладчиком — кукушками и логикой)
обычные результаты на хосте borisko можно посмотреть выше или вот.
попытался рандомизировать строку, вот так:
for(int i = 0; i < LEN; ++i)
//line[i]='a';
{fill='a'; fill+=(char)((rand()%(10-1+1)+10)); line[i]=fill;} //printf("%d\t",(int)line[i]);}
// line[i]=+(int)(10.0*rand());}
// line[LEN/2]='7';
line[LEN] = 0;
ФИГУШКИ!!! 8)
$ ./maketest (хост borisko)
with -O3
Method1: 0.001500, 0
Method2: 0.073600, 0
Method3: 0.109500, 0
Mrrl: проверил ваш вариант с заполнением строки, вот результат:
with -O3
Method1: 0.001500, 0
Method2: 0.073300, 0
Method3: 0.108900, 0
может действительно gcc тут такой агрессивный? :)
могу дать доступ к виртуалке, но у меня на ней не получилось его обновить
gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
/home/puzzle/habr/3# apt-get install gcc
Reading package lists… Done
Building dependency tree
Reading state information… Done
gcc is already the newest version.
gcc set to manually installed.
0 upgraded, 0 newly installed, 0 to remove and 78 not upgraded.
обычные результаты на хосте borisko можно посмотреть выше или вот.
попытался рандомизировать строку, вот так:
for(int i = 0; i < LEN; ++i)
//line[i]='a';
{fill='a'; fill+=(char)((rand()%(10-1+1)+10)); line[i]=fill;} //printf("%d\t",(int)line[i]);}
// line[i]=+(int)(10.0*rand());}
// line[LEN/2]='7';
line[LEN] = 0;
ФИГУШКИ!!! 8)
$ ./maketest (хост borisko)
with -O3
Method1: 0.001500, 0
Method2: 0.073600, 0
Method3: 0.109500, 0
Mrrl: проверил ваш вариант с заполнением строки, вот результат:
with -O3
Method1: 0.001500, 0
Method2: 0.073300, 0
Method3: 0.108900, 0
может действительно gcc тут такой агрессивный? :)
могу дать доступ к виртуалке, но у меня на ней не получилось его обновить
gcc (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
/home/puzzle/habr/3# apt-get install gcc
Reading package lists… Done
Building dependency tree
Reading state information… Done
gcc is already the newest version.
gcc set to manually installed.
0 upgraded, 0 newly installed, 0 to remove and 78 not upgraded.
Я совсем ничего не понимаю :-(
Нашел самое слабое, что только было:
root@server:~# ./test
Method1: 0.003400, 0
Method2: 0.205300, 0
Method3: 0.245900, 0
Конфигурация — та же, что была в виртуалке на Pentium D, но AMD Sempron(tm) Processor 2800+, работающий на 1607.941 мгц.
Сдаётся мне, что дело всё-таки в gcc-4.5. Сделал objdump (предварительно обернув всё в extern «C»), на выходе — что-то совсем странное: pastebin.com/TMphA6cs
При этом вызывается — клон функции. Видимо, он как-то учёл, что строка состоит целиком из ашек. Увы, у меня сейчас нет возможности протестировать с более старым gcc. Можно попробовать включить volatile для основной строки, но это фактически будет равно варианту без оптимизации,
Если это действительно оказалось фичей компилятора, а не идейной, то прошу прощения за поднятый шум :-)
Кстати, больше ни одну функцию оптимизатор не стал оптимизировать «клонированием».
Нашел самое слабое, что только было:
root@server:~# ./test
Method1: 0.003400, 0
Method2: 0.205300, 0
Method3: 0.245900, 0
Конфигурация — та же, что была в виртуалке на Pentium D, но AMD Sempron(tm) Processor 2800+, работающий на 1607.941 мгц.
Сдаётся мне, что дело всё-таки в gcc-4.5. Сделал objdump (предварительно обернув всё в extern «C»), на выходе — что-то совсем странное: pastebin.com/TMphA6cs
При этом вызывается — клон функции. Видимо, он как-то учёл, что строка состоит целиком из ашек. Увы, у меня сейчас нет возможности протестировать с более старым gcc. Можно попробовать включить volatile для основной строки, но это фактически будет равно варианту без оптимизации,
Если это действительно оказалось фичей компилятора, а не идейной, то прошу прощения за поднятый шум :-)
Кстати, больше ни одну функцию оптимизатор не стал оптимизировать «клонированием».
Еще есть такой вариант:
Выигрыш больше 2 раз — 0.0415 сек против 0.1 сек!
static char *Tbl=0;
bool HasDigit4(char *str){
if(Tbl==0){
Tbl=new char[65536];
for(int i=0;i<65536;i++){
int a1=i&255,a2=i>>8;
if(a1==0) Tbl[i]=2;
else Tbl[i]=(a2==0 ? 2 : 0)+(((unsigned int)(a1-48)<10 || (unsigned int)(a2-48)<10) ? 1 : 0);
}
}
char m=0;
if(((int)str&1)!=0) m=Tbl[*(unsigned short *)(str++)];
unsigned short *a=(unsigned short *)str;
while(m==0) m|=Tbl[*a++];
return (m&1)!=0;
}
Выигрыш больше 2 раз — 0.0415 сек против 0.1 сек!
Не понял, что такого необычного в топике. Помню, как такую задачу на паскале писал в седьмом классе.
А если так:
bool HasDigit(char *s){
int v=0;
while(*s) v|=1<<((unsigned char)(*s++-48));
return (v&1023)!=0;
}
И еще проще:
Или так:
bool HasDigit(char *s){
int v=0;
while(*s) v|=((*s++-48)&255)-10;
return v<0;
}
Или так:
HASDIG:: 1$: TSTB (R0) BEQ 2$ MOVB (R0)+,R1 SUB #60,R1 CMP R1,#12 BNC 1$ 2$: BIC R0,R0 ADC R0 RTS PC
о, супер! подтянулись люди с асмом)
помню задачки про самый короткий на асме hex2dec/dec2hex/etc… :)
помню задачки про самый короткий на асме hex2dec/dec2hex/etc… :)
О, да…
ADD A,90
DAA
ADC A,40
DAA
— конверсия числа от 0 до 15 в код ascii на Z80 :)
В моем коде выше есть опечатка — команда перехода пишется не BNC, а BCC. И, как выяснилось, я не очень помню, какие команды меняют бит С, а в сети таких подробностей не нашел :) У меня предполагалось, что TST его очищает, а BIC сохраняет.
ADD A,90
DAA
ADC A,40
DAA
— конверсия числа от 0 до 15 в код ascii на Z80 :)
В моем коде выше есть опечатка — команда перехода пишется не BNC, а BCC. И, как выяснилось, я не очень помню, какие команды меняют бит С, а в сети таких подробностей не нашел :) У меня предполагалось, что TST его очищает, а BIC сохраняет.
В неделю брейнфака эта задача была бы веселее
90 байт — но это без ввода-вывода. В начале головка стоит на самом левом символе строки.
[<++++++[->--------<]<<<++++++++++[>>+>>[-<+<[-]>>]<[->+<]<[-<[-]+>]<<-]>[->+<]>>>[-]>]<<<
Если делать ввод, то вопрос — чем терминировать строку? Символом \n (код 10)? И проблема в том, что тогда захочется посчитать результат сразу, не сохраняя символы на ленте.
[<++++++[->--------<]<<<++++++++++[>>+>>[-<+<[-]>>]<[->+<]<[-<[-]+>]<<-]>[->+<]>>>[-]>]<<<
Если делать ввод, то вопрос — чем терминировать строку? Символом \n (код 10)? И проблема в том, что тогда захочется посчитать результат сразу, не сохраняя символы на ленте.
Вот решение за 13 байт (ассемблер Z80):
hasdigit:
ld a,(hl)
inc hl
or a
ret z
sub 48
cp 10
jnc hasdigit
ld a,1
ret
На 8086 получается длиннее — там почти нет однобайтовых команд.
hasdigit:
ld a,(hl)
inc hl
or a
ret z
sub 48
cp 10
jnc hasdigit
ld a,1
ret
На 8086 получается длиннее — там почти нет однобайтовых команд.
Вообще за фразу «столкнулся с интересной задачей проверить есть ли в строке цифры» топик следовало бы заплюсовать, а не наоборот. Но увы, аудитория Хабра это не романтики программирования, а что-то другое.
То есть я бы сначала написал очевидное
bool has_digit(const char* s) {
while (*s) if (*s >= '0' && *s <= '9') return true; else ++s;
return false;
}
Потом бы поправил бы на почти тоже самое:
bool has_digit(const char* s) {
while (*s) if (*s < '0' || *s > '9') ++s; else return true;
return false;
}
Потом бы долго радовался, тому что
будет работать быстрее.
if (*s > '9' || *s < '0')
будет работать быстрее.
Потом бы сообразил, что да быстрее, но написать это надо тогда так:
if ((unsigned char)*s > '9' || *s < '0')
Потом бы наконец вспомнил, что ASCII не дураки придумывали:
bool has_digit(const char* s) {
for (;*s;++s) if ((*s & 0x30) == 0x30 && *s < ':') return true;
return false;
}
Ну тут бы мне надоело, я бы расстроился, что жизнь на какую-то фигню трачу, и заминусовал бы топик. Ну, потом бы еще полез посмотреть в ответ, т.е. как isdigit в libc сделан.
Sign up to leave a comment.
Проверить наличие цифр в строке