Вопрос на элегантность решения - О работе

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

vsb>Я нолик упустил. Рассуждения такие. Все эти цифры делят всю числовую прямую на отрезки. Если у нас числа от 0 до 999 999 999, то будет 8 * 27 * 2 = 432 точек, разбивающих числовую прямую на отрезки (для 13, 16, 19 это "вырожденный" отрезок, там надо будет проверять на равенство, но сути не меняет). Каждый отрезок это или "попадание", т.е. выдаём true, или непопадание, т.е. выдаём "false". Каждое сравнение отсекает половину точек, так что будет по идее не более 9 сравнений.

А, да, верно.

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

M>>>* самый простой и понятный — ToString()[1]
ry>>Ну как бы это — не комильфо. Сначала преобразуешь к строке, потом надо будет найденный символ преобразовывать обратно в число.

N>Лучшее решение — преобразование к строке. Тоже самое что и второе, так как мы все равно по числу бегаем, но пишется в одну строчку и понятно с первого взгляда.
То, что оно просто, понятно. А по скорости как?

function f(x){
var mod = x%10;
var div = x/10;
return div==0 ? false : (div>9 ? f(div) : (mod % 3 == 0));

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

N>Менее 10 не подходит по условию задачи.

поэтому сразу и false

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

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

S>>Вопрос: определить что вторая слева цифра числа делится на 3.

S>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).

S>>Решение должно быть понятным и быстрым.

M>А в чем вопрос то? в определении второй слева цифры?
M>* самый простой и понятный — ToString()[1]
M>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.

в первом варианте много лишних преобразований и по сути внутри мы будем иметь реализацию второго решения

char *itoa(i) int i;
{
/* Room for INT_DIGITS digits, — and '\0' */
static char buf[INT_DIGITS + 2];
char *p = buf + INT_DIGITS + 1; /* points to terminating '\0' */
if (i >= 0) {
do {
*--p = '0' + (i % 10);
i /= 10;
} while (i != 0);
return p;
}
else { /* i < 0 */
do {
*--p = '0' — (i % 10);
i /= 10;
} while (i != 0);
*--p = '-';
}
return p;
}

Здравствуйте, ry, Вы писали:
ry>То, что оно просто, понятно. А по скорости как?
Да говорю же тоже самое. Можно посмотреть примерный вариант в K&R.
Точно так же идем по числу(делим/сдвигаем) и получаем строку.
Ну у нас еще нужно будет char перевести в число, так это дело одной операции.
Так что скорость в норме.

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

ry>>То, что оно просто, понятно. А по скорости как?
N>Да говорю же тоже самое. Можно посмотреть примерный вариант в K&R.
N>Точно так же идем по числу(делим/сдвигаем) и получаем строку.
N>Ну у нас еще нужно будет char перевести в число, так это дело одной операции.
N>Так что скорость в норме.
Не очень понятно, почему скорость в норме.
Сдвиги производятся в регистрах процессора, а преобразования к строке в ОЗУ. Скорость доступа к этой памяти несопоставима. Или я опять ошибаюсь?

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

ry>Не очень понятно, почему скорость в норме.
ry>Сдвиги производятся в регистрах процессора, а преобразования к строке в ОЗУ. Скорость доступа к этой памяти несопоставима. Или я опять ошибаюсь?
Ошибаетесь, строка из числа получается при операции деления(K&R) такие операции проводятся в регистрах процессора тоже.

S>Вопрос: определить что вторая слева цифра числа делится на 3.
S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).

S>Решение должно быть понятным и быстрым.

bool check(const char *s)
{
    if (!*s) return false;
    ++s;
    return (*s=='0' || *s=='3' || *s=='6' || *s=='9');
}

хинди руси пхай пхай!

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

S>>Вопрос: определить что вторая слева цифра числа делится на 3.
S>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).

S>>Решение должно быть понятным и быстрым.
O>

O>bool check(const char *s)
O>{
O>    if (!*s) return false;
O>    ++s;
O>    return (*s=='0' || *s=='3' || *s=='6' || *s=='9');
O>}
O>

O>хинди руси пхай пхай!

На входе число, а не строка.

S>>>Вопрос: определить что вторая слева цифра числа делится на 3.
S>>>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).
S>>>Решение должно быть понятным и быстрым.
O>>

O>>bool check(const char *s)
O>>{
O>>    if (!*s) return false;
O>>    ++s;
O>>    return (*s=='0' || *s=='3' || *s=='6' || *s=='9');
O>>}
O>>

O>>хинди руси пхай пхай!

ARK>На входе число, а не строка.

В
естественной форме
(или в форме с фиксированной точкой) число представляется последовательностью десятичных цифр со знаком плюс или минус. Знак плюс можно опускать. Для отделения целой части числа от дробной используется не запятая, а точка. Ноль целых можно опускат

А вот если бы было сказано на входе int, или long, или binary-coded decimal — ответ был бы другой, или третий. Я это к тому что если просишь элегантное решение — элегантно формулируй задание.

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

S>Вопрос: определить что вторая слева цифра числа делится на 3.

S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).

S>Решение должно быть понятным и быстрым.

Как бэ тут обглодали аналогичную тему:

http://stackoverflow.com/questions/701322/how-can-you-get-the-first-digit-in-an-int-c

Самое быстрое и в принципе понятное будет:

if (i >= 100000000) i /= 100000000;
if (i >= 10000) i /= 10000;
if (i >= 100) i /= 100;
if (i >= 10) i /= 10; // тут имеем число из 2 левых цифр
i = i % 10; // тут вторая слева цифра
if (i % 3 == 0) {
  // вторая слева цифра числа делится на 3
} else {
  // вторая слева цифра числа НЕ делится на 3
}

Решение можно приспособить к int64 и int128 парой сточек кода.

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

V>Самое быстрое и в принципе понятное будет:

Это самое лучшее решение. Из всего ада, который тут предлагали.

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

vsb>И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...

vsb>Собственно решение — дерево сравнений. Будет максимум 5 сравнений.

vsb>Это на мой взгляд будет самое быстрое решение.

будешь смеяться, но выгодней сделать последовательный поиск, а не двочный. каждый неверно предсказанный переход — ~15 тактов, предсказанный верно — меньше одного такта

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

vsb>Как отнесётся современный процессор к такому коду, с его branch predictions, я не совсем понимаю и было бы интересно услышать. Вполне может быть, что поиск второй цифры делениями на 10 будет быстрей.

деление ещё хуже (10-100 тактов), умножения будут лучше. Edit: на самом деле деление на константу реализуется умнодением на обратное число, так что будет однофигственно. но задержка умножения — 3 такта, что явно не сравнить с поиском по степеням 10 или 100

но лучше использовать твой подход, только с линейным поиском. тогда у нас будет всего один ошибочно предсказанный переход (выход из цикла), и 5-10 удлачно предсказанных, которые обойдутся в 0.5-1 такта на переход

а для того чтобы "совсем понимать" — читай агнера фога: http://www.agner.org/optimize/

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

N>>Точно так же идем по числу(делим/сдвигаем) и получаем строку.
N>>Ну у нас еще нужно будет char перевести в число, так это дело одной операции.

какой char? он как раз и получается из числа. ты сначала будешь добавлять '0', а затем вычитать его?

ry>Не очень понятно, почему скорость в норме.
ry>Сдвиги производятся в регистрах процессора, а преобразования к строке в ОЗУ. Скорость доступа к этой памяти несопоставима. Или я опять ошибаюсь?

данные кешируются, обращение к L1$ — 4 такта, но часто эта задержка скрывается за общей конвейеризацией операций (ядро буферизует примерно 100 последних операций и выполняет их по мере готовности операндов)

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

V>Самое быстрое и в принципе понятное будет:

1. неясно на каком проце тестировали
2. данные генерятся равномерно-распределёнными. дальше сами сообразите, как сделать код, который будет ещё быстрее на этих данных

V>Самое быстрое и в принципе понятное будет:
V>

V>if (i >= 100000000) i /= 100000000;
V>if (i >= 10000) i /= 10000;
V>if (i >= 100) i /= 100;
V>if (i >= 10) i /= 10; // тут имеем число из 2 левых цифр
V>i = i % 10; // тут вторая слева цифра
V>if (i % 3 == 0) {
V>  // вторая слева цифра числа делится на 3
V>} else {
V>  // вторая слева цифра числа НЕ делится на 3
V>}
V>

Делений многовато для самого быстрого решения.
Я бы сделал что-то вроде:

int64_t divisor[1<<4] = { 1, 10, 100, 10*100, 10000, 10*10000, 100*10000, 10*100*10000, 100000000, 10*100000000, 100*100000000, 10*100*100000000, 10000*100000000, 10*10000*100000000, 100*10000*100000000, 10*100*10000*100000000, };
size_t mask = 0;
if (i >= 100000000) mask |= (1<<3);
if (i >= 10000)     mask |= (1<<2);
if (i >= 100)       mask |= (1<<1);
if (i >= 10)        mask |= (1<<0);
i = i/divisor[mask];
int32_t divisible_by_3[100] = {1,0,0,1,0,0,1,0,0,1,...........};
if (divisible_by_3[i]) {
  // вторая слева цифра числа делится на 3
} else {
  // вторая слева цифра числа НЕ делится на 3
}

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

M>Делений многовато для самого быстрого решения.

M>Я бы сделал что-то вроде:
M>if (i >= 100000000) mask |= (1<<3);
M>if (i >= 10000) mask |= (1<<2);
M>if (i >= 100) mask |= (1<<1);
M>if (i >= 10) mask |= (1<<0);

тут две ошибки. во-первых, для поиска делением диапазона пополам надо пересчитывать i после каждого сравнения. иначе для числа больше 100000000 у тебя сработают все if

M>i = i/divisor[mask];

во-вторых исходный код на самом деле вместо деления на константу компилируется в умножение на обратное число. а у тебя таки будет одно деление, и оно будет медленней даже 4 умножений

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

S>Вопрос: определить что вторая слева цифра числа делится на 3.

S>Примеры: 13, 89022 -- делится (3 и 9), 725933 -- не делится (2).

S>Решение должно быть понятным и быстрым.

Мне кажется многие утонули в деталях. Давайте сверху вниз:

1) Вычленить вторую сверху цифру это

unsigned
second_digit (unsigned x)
{
  unsigned divisor;

  if (x < 10)
    return 0;

  divisor = upow (10, ulen(x) - 2);

  return (x / divisor) % 10;
}

2) Теперь нам нужны быстрые реализации для ulen и upow. Это полезные повторно используемые абстракции, с ними уже можно развернуться:

unsigned
upow(unsigned base, unsigned exp)
{
  unsigned result = 1;
  while (exp)
    {
      if (exp & 1)
        result *= base;
      exp >>= 1;
      base *= base;
    }

  return result;
}

и соответственно:

unsigned
ulen (unsigned x)
{
  if (x < 10) return 1;
  if (x < 100) return 2;
  if (x < 1000) return 3;
  if (x < 10000) return 4;
  if (x < 100000) return 5;
  if (x < 1000000) return 6;
  return 7;
}

3) Поскольку ответ я набивал прямо тут и даже не компилировал теперь нужны тесты на всякие граничные случаи: скажем когда верхняя децимальная граница перекрывает UINT_MAX и т.п. Всё это долго пишется и отлаживается и делает код чуть более уродливым.

4) Зато на выходе мы получаем искомую second_digit в меньше 10 строк и плюс две полезные функции в библиотеку

	От:	AlexRK
	Дата:	02.10.14 16:54
	Оценка:

	От:	ry
	Дата:	02.10.14 18:41
	Оценка:

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	02.10.14 18:53
Оценка:	+1

	От:	Няшка
	Дата:	03.10.14 09:12
	Оценка:

	От:	Няшка
	Дата:	03.10.14 09:18
	Оценка:

	От:	BulatZiganshin
	Дата:	13.10.14 01:26
	Оценка:	8 (1)

От:	Tilir	http://tilir.livejournal.com
Дата:	13.10.14 11:38
Оценка: