Вопрос на элегантность решения
От: Shmj Ниоткуда  
Дата: 02.10.14 12:04
Оценка:
Вопрос: определить что вторая слева цифра числа делится на 3.

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

Решение должно быть понятным и быстрым.
Re: Вопрос на элегантность решения
От: ry Россия  
Дата: 02.10.14 12:25
Оценка: 3 (1)
Здравствуйте, Shmj, Вы писали:

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


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


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


Первый вариант.
— сдвигать заданное число вправо, пока оно не попадёт в диапазон [10, 99];
— полученное число разделить на 10;
— остаток от деления проверить на делимость на 3 без остатка.

Второй вариант:
начальные данные: массив А, содержащий числа 13, 16, 19,..., 93, 96, 99.
— сдвигать заданное число вправо, пока оно не попадёт в диапазон [10, 99];
— проверить, содержится ли полученное число в массиве А.

Третий вариант:
Более правильный алгоритм второго варианта.
начальные данные: массив А размером 100, в индексах 13, 16, 19,..., 93, 96, 99 записана 1, в остальных — 0.
— сдвигать заданное число вправо, пока оно не попадёт в диапазон [10, 99];
— получить значение массива по индексу, равному полученному на первом шаге числу.
Отредактировано 02.10.2014 12:37 ry . Предыдущая версия . Еще …
Отредактировано 02.10.2014 12:27 ry . Предыдущая версия .
Re[2]: Вопрос на элегантность решения
От: ry Россия  
Дата: 02.10.14 12:41
Оценка:
Здравствуйте, ry, Вы писали:

А в чём тогда был прикол, если оценил решения? Есть более быстрые решения. В лом думать над ними, если их нет.
Re: Вопрос на элегантность решения
От: mogikanin Россия  
Дата: 02.10.14 13:00
Оценка: +7
Здравствуйте, Shmj, Вы писали:

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


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


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


А в чем вопрос то? в определении второй слева цифры?
* самый простой и понятный — ToString()[1]
* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.
Re: Вопрос на элегантность решения
От: Abyx Россия  
Дата: 02.10.14 13:08
Оценка:
Здравствуйте, Shmj, Вы писали:

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


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


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


1) проверяем что у число больше 9
2) пока число больше 127, сдвигаем число на 1 бит и считаем количество бит.
получаем число в форме x + 2^n + ε, x < 128
3) по таблице находим делится цифра или нет: table[x][n]
In Zen We Trust
Отредактировано 02.10.2014 13:14 Abyx . Предыдущая версия .
Re[3]: Вопрос на элегантность решения
От: Shmj Ниоткуда  
Дата: 02.10.14 13:08
Оценка:
Здравствуйте, ry, Вы писали:

ry>А в чём тогда был прикол, если оценил решения? Есть более быстрые решения. В лом думать над ними, если их нет.


Это не этюд а простой вопрос на наиболее практичное решение.
Re[2]: Вопрос на элегантность решения
От: ry Россия  
Дата: 02.10.14 13:12
Оценка:
Здравствуйте, mogikanin, Вы писали:

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


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


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


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


M>А в чем вопрос то? в определении второй слева цифры?

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

M>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.

Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022.
Re: Вопрос на элегантность решения
От: Sni4ok  
Дата: 02.10.14 13:18
Оценка: 15 (2) :))) :))) :)))
Здравствуйте, Shmj, Вы писали:

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


uint32_t twoM(boost::uint32_t i){
    if(i <= 9999){
        if(i <= 99){
            if(i <= 9)
                throw std::runtime_error("nahuy");
            else
                return i % 10;
        }
        else
            return (i <= 999) ? (i / 10) % 10 : (i / 100) % 10;
    }
    else{
        if(i <= 999999)
            return (i <= 99999) ? (i / 1000) % 10 : (i / 10000) % 10;
        else{
            if (i <= 99999999)
                return (i <= 9999999 ) ? (i / 100000) % 10 : (i / 1000000) % 10;
            else
                return (i <= 999999999 ) ? (i / 10000000) % 10 : (i / 100000000) % 10;
        }
    }
}
bool kaka(uint32_t i)
{
    uint32_t s = twoM(i);
    return !(s % 3);
}

int main()
{
    uint32_t i;
    std::cin >> i;
    if(i < 10)
        return 1;
    std::cout << kaka(i) << std::endl;
    return 0;
}
Re: Вопрос на элегантность решения
От: AlexRK  
Дата: 02.10.14 13:22
Оценка: +2 -1
Здравствуйте, Shmj, Вы писали:

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


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


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


bool Foo(int num)
{
    if (num > 9)
        return (new[] { '3', '6', '9'}).Contains(num.ToString[1]);
    else
        return false;
}
Re[2]: тру решение
От: Няшка Россия  
Дата: 02.10.14 13:26
Оценка:
Здравствуйте, mogikanin, Вы писали:

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


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


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


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


M>А в чем вопрос то? в определении второй слева цифры?

M>* самый простой и понятный — ToString()[1]
много преобразований

M>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.

самое верное, только делить долго
надо от y = 100 проверять, не больше ли число чем y
да — умножаем y*10
нет — берем x = число % 10, а потом bool res = !(x % 3);
80% людей оценивают свое мастерство выше среднего...
Re[3]: тру решение
От: Няшка Россия  
Дата: 02.10.14 13:27
Оценка:
M>>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.
Н>самое верное, только делить долго
Н>надо от y = 100 проверять, не больше ли число чем y
Н>да — умножаем y*10
Н>нет — берем x = число % 10, а потом bool res = !(x % 3);

+ для менее 10 — сразу false
80% людей оценивают свое мастерство выше среднего...
Re[3]: Вопрос на элегантность решения
От: mogikanin Россия  
Дата: 02.10.14 13:28
Оценка: +3
Здравствуйте, ry, Вы писали:

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


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


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


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


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


M>>А в чем вопрос то? в определении второй слева цифры?

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

M>>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.

ry>Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022.
сам возьми и проверь, молодой человек.
если нужно такие очевидные вещи объяснять, то я не знаю, как вы вообще в программистах оказались
89022 / 10 -> 8902
8902 / 10 -> 890
и т.д. пока не получится 8, остаток будет 9
Re[4]: Вопрос на элегантность решения
От: ry Россия  
Дата: 02.10.14 13:32
Оценка:
Здравствуйте, mogikanin, Вы писали:

ry>>Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022.

M>сам возьми и проверь, молодой человек.
M>если нужно такие очевидные вещи объяснять, то я не знаю, как вы вообще в программистах оказались
M>89022 / 10 -> 8902
M>8902 / 10 -> 890
M>и т.д. пока не получится 8, остаток будет 9
В таком случае остаток у тебя будет 0, а не 9.
Re[4]: Вопрос на элегантность решения
От: ry Россия  
Дата: 02.10.14 13:35
Оценка: +1
Здравствуйте, mogikanin, Вы писали:

M>>>* чуть быстрее — делить на 10 пока число не станет меньше 10. остаток от последнего деления — искомая цифра.

ry>>Возьми любое из приведённых чисел, кроме 13, и проверь. Например, остаток от деления числа 89022 по твоему алгоритму будет 9022.
M>сам возьми и проверь, молодой человек.
M>если нужно такие очевидные вещи объяснять, то я не знаю, как вы вообще в программистах оказались
M>89022 / 10 -> 8902
M>8902 / 10 -> 890
M>и т.д. пока не получится 8, остаток будет 9
Признаю, был неправ.
Re: Вопрос на элегантность решения
От: vsb Казахстан  
Дата: 02.10.14 14:05
Оценка: 4 (2)
Это следующие числа:
Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99.
Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999.
И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...

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

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

Самое элегантное — toString[1] in ('3', '6', '9').
Отредактировано 02.10.2014 14:15 vsb . Предыдущая версия . Еще …
Отредактировано 02.10.2014 14:06 vsb . Предыдущая версия .
Re[2]: Вопрос на элегантность решения
От: AlexRK  
Дата: 02.10.14 14:43
Оценка:
Здравствуйте, vsb, Вы писали:

vsb>Это следующие числа:

vsb>Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99.
vsb>Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999.
vsb>И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...

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


Наверное худший случай все же не 5, а что-то в районе 16? 10 на неудачные сравнения длины, и внутри еще 6 — проверки начала и конца 3-х диапазонов.
Отредактировано 02.10.2014 14:44 AlexRK . Предыдущая версия .
Re: Вопрос на элегантность решения
От: -n1l-  
Дата: 02.10.14 16:28
Оценка:
Превратить число в строку, взять вторую цифру и проверить.
Все современные языки это умеют.
Re[4]: тру решение
От: -n1l-  
Дата: 02.10.14 16:35
Оценка:
Менее 10 не подходит по условию задачи.
Re[3]: Вопрос на элегантность решения
От: -n1l-  
Дата: 02.10.14 16:38
Оценка:
Здравствуйте, ry, Вы писали:
M>>А в чем вопрос то? в определении второй слева цифры?
M>>* самый простой и понятный — ToString()[1]
ry>Ну как бы это — не комильфо. Сначала преобразуешь к строке, потом надо будет найденный символ преобразовывать обратно в число.

Лучшее решение — преобразование к строке. Тоже самое что и второе, так как мы все равно по числу бегаем, но пишется в одну строчку и понятно с первого взгляда.
Re[3]: Вопрос на элегантность решения
От: vsb Казахстан  
Дата: 02.10.14 16:46
Оценка:
Здравствуйте, AlexRK, Вы писали:

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


vsb>>Это следующие числа:

vsb>>Двузначные: 13, 16, 19, 23, 26, 29, ..., 93, 96, 99.
vsb>>Трёхзначные: 130-139, 160-169, ..., 960-969, 990-999.
vsb>>И так далее. Если входное число до одного миллиарда, то максимальная длина числа будет 130 000 000 — 139 999 999, ...

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


ARK>Наверное худший случай все же не 5, а что-то в районе 16? 10 на неудачные сравнения длины, и внутри еще 6 — проверки начала и конца 3-х диапазонов.


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

Если будет понятней — то суть алгоритма такая. Все числа выписываем в массив. nums = [130, 139, 160, 169, 190, 199, ..., 990, 999, 1300, 1399, 1600, 1699, ..., 9600, 9699, 9900, 9999, 13000, 13999, ..., 130_000_000, 139_999_999, 160_000_000, 169_999_99, ..., 990_000_000, 999_999_999]. В этом массиве будет 378 элементов. Мы ищем позицию в этом массиве nums[i] <= x <= nums[i + 1]. Собственно по этой позиции и определяется ответ. Ищем методом деления пополам, должно найтись за не более 9 сравнений. Можно написать как я сказал, с массивом и т.д., а можно "развернуть" этот поиск в виде кода, будет такая большая (естественно автоматически генерируемая) лапша из нескольких сотен if-ов.

Как отнесётся современный процессор к такому коду, с его branch predictions, я не совсем понимаю и было бы интересно услышать. Вполне может быть, что поиск второй цифры делениями на 10 будет быстрей.
Отредактировано 02.10.2014 16:53 vsb . Предыдущая версия . Еще …
Отредактировано 02.10.2014 16:50 vsb . Предыдущая версия .
Re[4]: Вопрос на элегантность решения
От: AlexRK  
Дата: 02.10.14 16:54
Оценка:
Здравствуйте, vsb, Вы писали:

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


А, да, верно.
Re[4]: Вопрос на элегантность решения
От: ry Россия  
Дата: 02.10.14 18:41
Оценка:
Здравствуйте, -n1l-, Вы писали:

M>>>* самый простой и понятный — ToString()[1]

ry>>Ну как бы это — не комильфо. Сначала преобразуешь к строке, потом надо будет найденный символ преобразовывать обратно в число.

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

То, что оно просто, понятно. А по скорости как?
Re: Вопрос на элегантность решения
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 02.10.14 18:53
Оценка: +1 :)
Здравствуйте, Shmj, Вы писали:

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


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


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


function f(x){
var mod = x%10;
var div = x/10;
return div==0 ? false : (div>9 ? f(div) : (mod % 3 == 0));
Re[5]: тру решение
От: Няшка Россия  
Дата: 03.10.14 09:12
Оценка:
Здравствуйте, -n1l-, Вы писали:

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


поэтому сразу и false
80% людей оценивают свое мастерство выше среднего...
Re[2]: Почему работа со строкой плохо
От: Няшка Россия  
Дата: 03.10.14 09:18
Оценка:
Здравствуйте, 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;
}
80% людей оценивают свое мастерство выше среднего...
Re[5]: Вопрос на элегантность решения
От: -n1l-  
Дата: 03.10.14 13:40
Оценка:
Здравствуйте, ry, Вы писали:
ry>То, что оно просто, понятно. А по скорости как?
Да говорю же тоже самое. Можно посмотреть примерный вариант в K&R.
Точно так же идем по числу(делим/сдвигаем) и получаем строку.
Ну у нас еще нужно будет char перевести в число, так это дело одной операции.
Так что скорость в норме.
Re[6]: Вопрос на элегантность решения
От: ry Россия  
Дата: 03.10.14 18:00
Оценка:
Здравствуйте, -n1l-, Вы писали:

ry>>То, что оно просто, понятно. А по скорости как?

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

ry>Не очень понятно, почему скорость в норме.

ry>Сдвиги производятся в регистрах процессора, а преобразования к строке в ОЗУ. Скорость доступа к этой памяти несопоставима. Или я опять ошибаюсь?
Ошибаетесь, строка из числа получается при операции деления(K&R) такие операции проводятся в регистрах процессора тоже.
Re: ответ на элегантность условия
От: ononim  
Дата: 03.10.14 19:21
Оценка:
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');
}

хинди руси пхай пхай!
Как много веселых ребят, и все делают велосипед...
Re[2]: ответ на элегантность условия
От: AlexRK  
Дата: 03.10.14 19:30
Оценка:
Здравствуйте, 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>хинди руси пхай пхай!

На входе число, а не строка.
Re[3]: ответ на элегантность условия
От: ononim  
Дата: 03.10.14 20:49
Оценка:
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 — ответ был бы другой, или третий. Я это к тому что если просишь элегантное решение — элегантно формулируй задание.
Как много веселых ребят, и все делают велосипед...
Re: Вопрос на элегантность решения
От: vpchelko  
Дата: 03.10.14 20:55
Оценка: +2
Здравствуйте, 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 парой сточек кода.
Сало Украине, Героям Сала
Отредактировано 03.10.2014 21:07 vpchelko . Предыдущая версия . Еще …
Отредактировано 03.10.2014 21:03 vpchelko . Предыдущая версия .
Отредактировано 03.10.2014 21:01 vpchelko . Предыдущая версия .
Re[2]: Вопрос на элегантность решения
От: AlexRK  
Дата: 03.10.14 21:15
Оценка:
Здравствуйте, vpchelko, Вы писали:

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



Это самое лучшее решение. Из всего ада, который тут предлагали.
Re[2]: Вопрос на элегантность решения
От: BulatZiganshin  
Дата: 13.10.14 01:19
Оценка:
Здравствуйте, vsb, Вы писали:

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


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


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


будешь смеяться, но выгодней сделать последовательный поиск, а не двочный. каждый неверно предсказанный переход — ~15 тактов, предсказанный верно — меньше одного такта
Люди, я люблю вас! Будьте бдительны!!!
Re[4]: Вопрос на элегантность решения
От: BulatZiganshin  
Дата: 13.10.14 01:26
Оценка: 8 (1)
Здравствуйте, vsb, Вы писали:

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


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

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

а для того чтобы "совсем понимать" — читай агнера фога: http://www.agner.org/optimize/
Люди, я люблю вас! Будьте бдительны!!!
Отредактировано 13.10.2014 1:38 BulatZiganshin . Предыдущая версия .
Re[7]: Вопрос на элегантность решения
От: BulatZiganshin  
Дата: 13.10.14 01:31
Оценка:
Здравствуйте, ry, Вы писали:

N>>Точно так же идем по числу(делим/сдвигаем) и получаем строку.

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

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

ry>Не очень понятно, почему скорость в норме.

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

данные кешируются, обращение к L1$ — 4 такта, но часто эта задержка скрывается за общей конвейеризацией операций (ядро буферизует примерно 100 последних операций и выполняет их по мере готовности операндов)
Люди, я люблю вас! Будьте бдительны!!!
Re[2]: Вопрос на элегантность решения
От: BulatZiganshin  
Дата: 13.10.14 01:35
Оценка:
Здравствуйте, vpchelko, Вы писали:

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


1. неясно на каком проце тестировали
2. данные генерятся равномерно-распределёнными. дальше сами сообразите, как сделать код, который будет ещё быстрее на этих данных
Люди, я люблю вас! Будьте бдительны!!!
Re[2]: Вопрос на элегантность решения
От: Muxa  
Дата: 13.10.14 07:01
Оценка:
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
}
Отредактировано 13.10.2014 7:09 Muxa . Предыдущая версия . Еще …
Отредактировано 13.10.2014 7:08 Muxa . Предыдущая версия .
Re[3]: Вопрос на элегантность решения
От: BulatZiganshin  
Дата: 13.10.14 11:23
Оценка:
Здравствуйте, 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 умножений
Люди, я люблю вас! Будьте бдительны!!!
Re: Вопрос на элегантность решения
От: Tilir Россия http://tilir.livejournal.com
Дата: 13.10.14 11:38
Оценка:
Здравствуйте, 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 строк и плюс две полезные функции в библиотеку
Re[4]: Вопрос на элегантность решения
От: Muxa  
Дата: 13.10.14 12:56
Оценка:
BZ>тут две ошибки. во-первых, для поиска делением диапазона пополам надо пересчитывать i после каждого сравнения. иначе для числа больше 100000000 у тебя сработают все if
Согласен, я затупил.

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

В интах-то?
Насколько я знал такое может быть только при делении на float константу, а вот сейчас смотрю ассемблер — так оно и есть: деление на константу реализовано через умножение-сдвиг и какие-то таблицы.
Re[5]: Вопрос на элегантность решения
От: watchmaker  
Дата: 13.10.14 17:57
Оценка: 14 (2)
Здравствуйте, Muxa, Вы писали:

M>В интах-то?

M>Насколько я знал такое может быть только при делении на float константу
Забавно, но вот как раз с float так не всегда получается — если вместо деления на d делать умножение на (1.0/d), то результат, как правило, отличается от результата простого деления и обладает худшей точностью. Это связано с тем, что происходит лишнее округление при вычислении константы (1.0/d), ведь, как правило, это число не представимо точно. Так что обычно компиляторы вычисляют выражения с плавающей запятой практически ровно как они записаны, ведь даже внешне незначительные преобразования, вроде изменения порядка слагаемых в сумме, порой приводят к значительному изменению результата. И у компилятора недостаточно знаний о том, действительно-ли в данной формуле нужно строго соблюдать порядок операций или можно её преобразовать ради увеличения скорости. Собственно, тут всё решает программист и только он может сообщить компилятору, что (a/b) == a*(1/b) (например, путём указания соответствующих опций вроде ключа -ffast-math в gcc).
А вот с делением целого на целочисленную константу такого выбора не стоит — там всегда достигается истинный результат.
Отредактировано 13.10.2014 17:59 watchmaker . Предыдущая версия .
Re: Вопрос на элегантность решения
От: goto Россия  
Дата: 14.12.18 13:02
Оценка:
Здравствуйте, Shmj, Вы писали:

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


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


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


Можно найти вторую цифру без строк через log10() и pow(). Плавающая математика у Интел очень быстрая.

int SecondDigit( int v ) // v - наше число
{
    if ( v < 0 ) v = -v;
    if ( v < 10 ) return -1; // второй цифры нет - вернуть -1 для примера
    
    int n = (int)log10((double) v); //число цифр -1 

    return  v / (int)pow(10.0, n - 1) % 10; 
}
Отредактировано 14.12.2018 13:05 goto . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.