0

Приветствую.

Недавно наткнулся на задачу : найти все числа, делящиеся на 3, на 5 и на 3 и 5 одновременно. Но данный алгоритм необходимо ускорить. Думал в сторону bitwise операций, но не думаю что задача заключается именно в ускорении программы относительно тактов процессора (получается, кстати, сэкономить всего-лишь 10).

  for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); it++) {
    if (*it % 3 == 0) {
        std::cout << "bar" << std::endl;
    }
    if (*it % 5 == 0) {
        std::cout << "bazz" << std::endl;
    }
    if (*it % 5 == 0 && *it % 3 == 0) {
        std::cout << "barbazz" << std::endl;
    }
}

Есть ли у кого какие идеи по этому поводу? При необходимости могу привести код проверки на деление asm

5
  • В смысле не относительно тактов, а относительно чего тогда?
    – Komdosh
    3 апр 2018 в 10:39
  • @Fat-Zer а каким образом это сделать?
    – user292501
    3 апр 2018 в 10:42
  • последнюю проверку проще заменить на it % 15 == 0
    – slippyk
    3 апр 2018 в 10:43
  • Программа сейчас работает неправильно. для 15 будут напечатанны все 3 строки. Можно убрать ветвления внутри цикла и вызывать *it % 3 *it % 5 только по одному разу. 3 апр 2018 в 10:53
  • @Fat-Zer И как вы себе представляете обработку вектора без цикла? При чем тут сумма и арифметическая прогрессия? 3 апр 2018 в 11:05

4 ответа 4

2

Может, так?

const char* foo[] = { "","bar","bazz","barbazz"};

for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
{
    int idx = (*it % 3 == 0) + 2*(*it % 5 == 0);
    if (idx)
        std::cout << *it << " : " << foo[idx] << std::endl;
}
0

Тут можно сделать таблицу результатов из заменить все ветвления на взятие остатка и индексирование:

constexpr char const * const table[15]
{
   "barbazz\n" //  0
,   ""         //  1
,   ""         //  2
,   "bar\n"    //  3
,   ""         //  4
,   "bazz\n"   //  5
,   "bar\n"    //  6
,   ""         //  7
,   ""         //  8
,   "bar\n"    //  9
,   "bazz\n"   // 10
,   ""         // 11
,   "bar\n"    // 12
,   ""         // 13
,   ""         // 14
};

for(auto it{vec.begin()}; it != vec.end(); ++it)
{
    std::cout << table[*it % 15];
}
1
  • Грустно для, скажем, 2621 и 2633, при размере вектора в пару сотен значений :)
    – Harry
    3 апр 2018 в 15:48
0

Вы решаете классическую fizbazz задачу.

Ускорить конечно можно и в данном случае наверно стоит отказаться от итератора (у меня есть подозрение, что вначале Вы просто наполняете вектор множеством чисел, а потом из него извлекаете. Наполнение вектора миллионами чисел может сильно тормозить приложение).

Следующее - скорее всего в цепочке if Вы забили else и напутали порядок.

И последнее. В самое начало программы добавьте такое

ios_base::sync_with_stdio(false);

это отключит синхронизацию std-шник потоков и сишных.

То есть, я считаю, что у Вашей программы тормоза не в расчете чисел, а в выделении большого вектора и вывода на экран.

2
  • тут не в этом дело, нужно именно алгоритм сделать быстрее. на I/O можно закрыть глаза
    – user292501
    3 апр 2018 в 10:41
  • тогда показывайте весь код. и результаты бенчмарка.
    – KoVadim
    3 апр 2018 в 11:48
0

Идея старая, я об этом знал еще в школе 40 лет назад: Числа делятся на 3, если сумма всех остатков от 10 делится на 3, а на 5 делится число, если остаток от 10 равен 5 или 0

4
  • старая, хорошая, но для двоичных ЭВМ абсолютно бесполезная...
    – Fat-Zer
    3 апр 2018 в 11:16
  • бесполезная, если не знать как использовать эту логику . Зная это я могу не проверить число 134567892 делится на 3, если я уже знаю, что 1234560000 делится на 3. Просто проверю разность этих чисел... 3 апр 2018 в 11:31
  • 1
    только вот проверить разность ни чуть не быстрее, чем проверить само число... по крайней мере пока разговор не зашёл о длинной арифметике...
    – Fat-Zer
    3 апр 2018 в 11:34
  • не проверял, но должно быть быстрее 3 апр 2018 в 11:35

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки