1 Востаннє редагувалося koala (15.03.2020 07:08:10)

Тема: Кривий код чи оптимізація?

Наштовхнувся в мережі на ось таку творчість:

Прихований текст

https://replace.org.ua/uploads/images/931/fee17a29a4333883873f98c5b064bce6.jpg

Автор картинки, вочевидь, вважає цей код поганим. Серед претензій в коментарях я побачив таке:
- код довгий;
- код надмірний (немає циклу, зайві умови, немає else);
- код не використовує стандартні функції, якими тут можна було б скористатися.

Ну що ж, розберімося. Для початку: довжина коду (в межах розумного, звісно) не має особливого значення, значення має читаність, і тут вона непогана: мета чітко зрозуміла, як вносити зміни (наприклад, якщо знадобиться від'ємні числа враховувати) - теж видно. Єдине, що можна було б краще код вирівняти, щоб другий стовпчик чисел був по одній вертикалі, це допомагає краще бачити помилки; порівняння в таких випадках краще розташовувати у вигляді

(1000 <= num && num <10000)

це робить очевидним, що перевіряється належність числа інтервалу; і return краще виносити на наступний рядок, але в цьому коді, гадаю, краще саме так. Ну добре, але ж можна було зробити й коротший код читаним? Так, звісно. Читаність — не перевага цього коду, але й не недолік.
Відсутність else? Ні, тут це не має значення: якщо якась умова виконається, то відбудеться return, і подальший код не буде виконуватися в будь-якому разі.
Зайві умови? Так, є трохи. Справді, після перевірки на num<10 немає сенсу перевіряти, чи виконується n>=10 (виконується), тому перші половини всіх умов можна просто викинути. Сучасні компілятори часто бувають достатньо просунутими, щоб зрозуміти можливість цієї оптимізації, а перевірка - дуже швидка операція, тому в результаті швидкість виконання від цього майже не страждає; але нащо ж змушувати компілятор з процесором перепрацьовувати?
Але ж це все можна було загнати в цикл чи скористатися стандартними функціями? Так. Але цей код має несподівану перевагу: він в біса швидкий. Я зібрав десяток інших способів пошуку довжини числа; цей код посідає 3-є місце серед них за швидкістю, а з оптимізацією - ділить 2-е з ним же без зайвих умов. Використовувався clang 7.0.0 з -o3.

Код
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <cmath>
#include <random>
#include <limits>
#include <array>
#include <chrono>

/*****************************************************************
 * number length
 * naive optimization
******************************************************************/
long long num_len1(long long num)
{
  if(                       0<=num && num<                       10 ) return 1;
  if(                      10<=num && num<                      100 ) return 2;
  if(                     100<=num && num<                    1'000 ) return 3;
  if(                   1'000<=num && num<                   10'000 ) return 4;
  if(                  10'000<=num && num<                  100'000 ) return 5;
  if(                 100'000<=num && num<                1'000'000 ) return 6;
  if(               1'000'000<=num && num<               10'000'000 ) return 7;
  if(              10'000'000<=num && num<              100'000'000 ) return 8;
  if(             100'000'000<=num && num<            1'000'000'000 ) return 9;
  if(           1'000'000'000<=num && num<           10'000'000'000 ) return 10;
  if(          10'000'000'000<=num && num<          100'000'000'000 ) return 11;
  if(         100'000'000'000<=num && num<        1'000'000'000'000 ) return 12;
  if(       1'000'000'000'000<=num && num<       10'000'000'000'000 ) return 13;
  if(      10'000'000'000'000<=num && num<      100'000'000'000'000 ) return 14;
  if(     100'000'000'000'000<=num && num<    1'000'000'000'000'000 ) return 15;
  if(   1'000'000'000'000'000<=num && num<   10'000'000'000'000'000 ) return 16;
  if(  10'000'000'000'000'000<=num && num<  100'000'000'000'000'000 ) return 17;
  if( 100'000'000'000'000'000<=num && num<1'000'000'000'000'000'000 ) return 18;
  return 0;
}

/*****************************************************************
 * number length
 * to string c-style
******************************************************************/
long long num_len2(long long num)
{
  char s[21];
  std::sprintf(s,"%lld",num);
  return strlen(s);
}

/*****************************************************************
 * number length
 * to string c++-style
******************************************************************/
long long num_len3(long long num)
{
  std::stringstream s;
  s<<num;
  return s.str().length();
}

/*****************************************************************
 * number length
 * loop - division
******************************************************************/
long long num_len4(long long num)
{
  if(num==0)
    return 1;
  long long length = 0;
  while(num>0) {
    ++length;
    num/=10;
  }
  return length;
}

/*****************************************************************
 * number length
 * no lower checks
******************************************************************/
long long num_len5(long long num)
{
  if( num<                       10 ) return 1;
  if( num<                      100 ) return 2;
  if( num<                    1'000 ) return 3;
  if( num<                   10'000 ) return 4;
  if( num<                  100'000 ) return 5;
  if( num<                1'000'000 ) return 6;
  if( num<               10'000'000 ) return 7;
  if( num<              100'000'000 ) return 8;
  if( num<            1'000'000'000 ) return 9;
  if( num<           10'000'000'000 ) return 10;
  if( num<          100'000'000'000 ) return 11;
  if( num<        1'000'000'000'000 ) return 12;
  if( num<       10'000'000'000'000 ) return 13;
  if( num<      100'000'000'000'000 ) return 14;
  if( num<    1'000'000'000'000'000 ) return 15;
  if( num<   10'000'000'000'000'000 ) return 16;
  if( num<  100'000'000'000'000'000 ) return 17;
  if( num<1'000'000'000'000'000'000 ) return 18;
  return 0;
}

/*****************************************************************
 * number length
 * loop - multiplication
******************************************************************/
long long num_len6(long long num)
{
  if(num==0)
    return 0;
  long long power = 10;
  for(long long length=1; length<19; ++length) {
    if( num<power ) return length;
    power *= 10;
  }
  return 0;
}

/*****************************************************************
 * number length
 * loop - power
******************************************************************/
long long num_len7(long long num)
{
  if(num==0)
    return 0;
  for(long long length=1; length<19; ++length)
    if( num<pow(10,length) ) return length;
  return 0;
}

/*****************************************************************
 * number length
 * logarithm
******************************************************************/
long long num_len8(long long num)
{
  if(num==0)
    return 1;
  return log10(static_cast<long double>(num))+1;
}

/*****************************************************************
 * number length
 * recursion - division
******************************************************************/
long long num_len9(long long num)
{
  if(num<10)
    return 1;
  return num_len9(num/10)+1;
}

/*****************************************************************
 * number length
 * tail recursion - multiplication
******************************************************************/
long long num_len10(long long num, long long length=0, long long power = 10)
{
  if(length>18)
    return 18;
  if(num<power)
    return length+1;
  return num_len10(num, length+1, power*10);
}

/*****************************************************************
 * number length
 * dichotomy
******************************************************************/
long long num_len11(long long num)
{
  if(num<1000000000) {
    if(num<100000)
    {
      if(num<1000){
        if(num<100)
        {
          if(num<10)
            return 1;
          else
            return 2;
        } else { //>=1e2
          return 3;
        }
      } else { //>=1e3
        if(num<10000)
          return 4;
        else
          return 5;
      }
    } else { //>=1e5
      if(num<10000000){
        if(num<1000000)
          return 6;
        else
          return 7;
      } else { //>=1e7
        if(num<100000000)
          return 8;
        else
          return 9;
      }
    }
  } else { //>=1e9
    if(num<100000000000000){
      if(num<1000000000000){
        if(num<100000000000) {
          if(num<10000000000)
            return 10;
          else
            return 11;
        } else { //>=1e11
          return 12;
        }
      }else{ //>=1e2
        if(num<10000000000000)
          return 13;
        else
          return 14;
      }
    } else { //>>1e14
      if(num<10000000000000000)
      {
        if(num<1000000000000000)
          return 15;
        else
          return 16;
      } else { //>=1e16
        if(num<100000000000000000)
          return 17;
        else
          return 18;
      }
    }
  }
}

void test_eq(long long a,long long b, const char *msg, long long data)
{
  if(a!=b){
    std::cout<<a<<" should equal "<<b<<"! "<<msg<<" of "<<data<<"\n";
    abort();
  }
}

int main() {
  std::default_random_engine generator;
  std::uniform_int_distribution<long long> distribution(0,100000000000000000);
  for(int i=0; i<1000; ++i)
  {
    long long rnd = distribution(generator);
    long long v1 = num_len1(rnd);
    long long v2 = num_len2(rnd);
    long long v3 = num_len3(rnd);
    long long v4 = num_len4(rnd);
    long long v5 = num_len5(rnd);
    long long v6 = num_len6(rnd);
    long long v7 = num_len7(rnd);
    long long v8 = num_len8(rnd);
    long long v9 = num_len9(rnd);
    long long v10 = num_len10(rnd);
    long long v11 = num_len11(rnd);
    test_eq(v1, v2, "v2", rnd);
    test_eq(v1, v3, "v3", rnd);
    test_eq(v1, v4, "v4", rnd);
    test_eq(v1, v5, "v5", rnd);
    test_eq(v1, v6, "v6", rnd);
    test_eq(v1, v7, "v7", rnd);
    test_eq(v1, v8, "v8", rnd);
    test_eq(v1, v9, "v9", rnd);
    test_eq(v1, v10, "v10", rnd);
    test_eq(v1, v11, "v11", rnd);
  }
  std::cout<<"Test done!\n";

  std::array<long long, 1000000> data;
  for(auto &x:data)
    x = distribution(generator);

#define BENCHMARK(function)  \
  {                          \
    long long s = 0;         \
    auto start = std::chrono::high_resolution_clock::now(); \
    for(auto x:data)    \
      s += function(x); \
    auto end = std::chrono::high_resolution_clock::now(); \
    double time_lapse=std::chrono::duration_cast<std::chrono::duration<double>>(end - start).count();    \
    std::cout<<#function<<": "<<s<<" in "<<time_lapse<< " seconds\n"; \
  }

  BENCHMARK(num_len1)
  BENCHMARK(num_len2)
  BENCHMARK(num_len3)
  BENCHMARK(num_len4)
  BENCHMARK(num_len5)
  BENCHMARK(num_len6)
  BENCHMARK(num_len7)
  BENCHMARK(num_len8)
  BENCHMARK(num_len9)
  BENCHMARK(num_len10)
  BENCHMARK(num_len11)
}

Місця з кінця, час на мільйон операцій на сервері repl.it. Час я трохи округлив.
11. 3.6с. №7. Наївний цикл, з обчисленням 10**i в кожній ітерації. Піднесення до степеня - дуже повільна операція.
10. 2.8с. №3. Перетворюємо число в стрічку за допомогою об'єктів. Це - приблизний аналог Python-івського len(str(num)). Дуже повільно, бо всі тимчасові об'єкти виділяться-знищуються.
8-9. 0.8с. №4, №9. Цикл і рекурсія з діленням. Ділення - повільна операція.
6-7. 0.4с. №2. Перетворення в стрічку за допомогою sprintf.
№10. Хвостова рекурсія з множенням; загалом мала б бути швидшою, можливо, clang чомусь не тягне, треба розбиратися.
5. 0.16с. №6. Цикл з множенням.
4. 0.14с. №8. Логарифм. Логарифм - теж не швидка операція, але поза циклом не так вже й погано.
2-3. 0.03с. №1. Очікувано наша функція.
№5. Вона ж, але без зайвих умов. Оптимізація зрівнює ці дві функції за швидкістю.
1. 0.02с. №11. Приблизно те саме, але тепер порівняння відсортовані так, щоб кількість порівнянь була приблизно однаковою, за принципом бісекції.

Таким чином, ми бачимо, що позірно надмірний код може бути, насправді, просто оптимізованим. Не поспішайте робити висновки, коли бачите незрозумілий код - спробуйте уявити собі, що думав програміст, коли писав це. Особливо якщо код явно дбайливо вирівняний.

Подякували: Q-bart, ostap34PHP, P.Y., pluszz, leofun01, 221VOLT6

2

Re: Кривий код чи оптимізація?

Чи справді оптимально починати послідовну перевірку з діапазонів, у які потрапляє найменше чисел?
Звісно, залежить від контексту, але якщо можливі значення num рівномірно розподіляються по всьому діапазону від 0 до 1010, то чисел з n десяткових цифр (де n≥2) буде гарантовано в 9 разів більше, ніж чисел з менш ніж n десяткових цифр — логічніше було б починати з більших чисел, а не з менших.

Подякували: koala, ostap34PHP2

3

Re: Кривий код чи оптимізація?

Ну якщо створити бінарне дерево таких порівнянь, то воно ще швидше буде, але читати і модифікувати його треба буде за методом патріка з картинки.

4

Re: Кривий код чи оптимізація?

так логарифм вдвічі швидший, чи я чогось не розумію?

5

Re: Кривий код чи оптимізація?

Vo_Vik написав:

Ну якщо створити бінарне дерево таких порівнянь, то воно ще швидше буде, але читати і модифікувати його треба буде за методом патріка з картинки.

Бінарне скоротить максимальну тривалість пошуку, але див. вище: якщо 9/10 чисел потрапляють у 10-цифрові, з решти чисел 9/10 потрапляють у 9-цифрові, і т.д., то середня тривалість пошуку скоротиться, якщо робити не бінарне галуження, а починати з найімовірніших варіантів.

6

Re: Кривий код чи оптимізація?

P.Y. написав:
Vo_Vik написав:

Ну якщо створити бінарне дерево таких порівнянь, то воно ще швидше буде, але читати і модифікувати його треба буде за методом патріка з картинки.

Бінарне скоротить максимальну тривалість пошуку, але див. вище: якщо 9/10 чисел потрапляють у 10-цифрові, з решти чисел 9/10 потрапляють у 9-цифрові, і т.д., то середня тривалість пошуку скоротиться, якщо робити не бінарне галуження, а починати з найімовірніших варіантів.

Так якщо числа розподілені рівномірно в діапазоні  0_10^10, то цілком з вами згоден.

7 Востаннє редагувалося koala (11.03.2020 17:48:05)

Re: Кривий код чи оптимізація?

ur_naz, дякую, виправив.
Vo_Vik, додав код - num_len11

8

Re: Кривий код чи оптимізація?

Ще є один в принципі швидкий спосіб по ідеї.
Перетворити 10^n в бінарний вигляд і порівнювати біти починаючи зі старших

9

Re: Кривий код чи оптимізація?

Vo_Vik написав:

Ще є один в принципі швидкий спосіб по ідеї.
Перетворити 10^n в бінарний вигляд і порівнювати біти починаючи зі старших

І що це дасть? Хіба що заготувати табличку степенів 10...

10

Re: Кривий код чи оптимізація?

koala написав:
Vo_Vik написав:

Ще є один в принципі швидкий спосіб по ідеї.
Перетворити 10^n в бінарний вигляд і порівнювати біти починаючи зі старших

І що це дасть? Хіба що заготувати табличку степенів 10...

Ну я про це і кажу.

11

Re: Кривий код чи оптимізація?

Ще варіант: порівнювати число з наперед підготованим масивом чисел 10n (який можна згенерувати програмно чи зробити руками як константу) — на швидкодію впливатиме, в якому порядку порівнювати елементи масиву з числом.

12

Re: Кривий код чи оптимізація?

Додав ще два методи

Прихований текст
/*****************************************************************
 * number length
 * reverse checks
******************************************************************/
long long num_len12(long long num)
{
  if( num>=100000000000000000 ) return 18;
  if( num>=10000000000000000  ) return 17;
  if( num>=1000000000000000   ) return 16;
  if( num>=100000000000000    ) return 15;
  if( num>=10000000000000     ) return 14;
  if( num>=1000000000000      ) return 13;
  if( num>=100000000000       ) return 12;
  if( num>=10000000000        ) return 11;
  if( num>=1000000000         ) return 10;
  if( num>=100000000          ) return 9;
  if( num>=10000000           ) return 8;
  if( num>=1000000            ) return 7;
  if( num>=100000             ) return 6;
  if( num>=10000              ) return 5;
  if( num>=1000               ) return 4;
  if( num>=100                ) return 3;
  if( num>=10                 ) return 2;
  if( num>=0                  ) return 1;
  return 0;
}

/*****************************************************************
 * number length
 * binary search
******************************************************************/
long long num_len13(long long num)
{
  static long long TABLE[] = {0,10,100,1000,10000,100000,1000000,
  10000000,100000000,1000000000,10000000000,100000000000,
  1000000000000,10000000000000,100000000000000,1000000000000000,
  10000000000000000,100000000000000000,1000000000000000000};
  return 1+(std::upper_bound(std::begin(TABLE), std::end(TABLE), num)-TABLE)-1;
}

№12 - те саме, що №5 (ряд перевірок) у зворотному порядку; це новий чемпіон, бо він оптимізований під рівномірно розподілені числа, десь удвічі швидший за №11.
№13 - бінарний пошук у масиві стандартним std::upper_bound. Швидкість десь як у множення. Можливо, варто власний бінарний пошук написати.
Точний час не наводжу, бо це суттєво залежить від сервера. Треба буде ще якось це все вдома поганяти.

Подякували: 221VOLT1

13 Востаннє редагувалося 221VOLT (14.03.2020 22:36:28)

Re: Кривий код чи оптимізація?

за статтю дякую, нехай вона і однобока

на мою думку, назвою цієї статті може/повинно бути
"clang vs gcc, або ж про оптимізації компіляторів"

для того, щоб внести ясність :)

бо з першого, та і другого погляду --
здається, що мова йде про код, читабельність та форматування

а по факту -- "хвалебна ода clang",
навіть без згадки gcc та порівняння швидкодії зі згаданим вище clang *SCRATCH*



моя думка про код -- за таке по рукам різками треба))

по-перше, замість

if( 1000000<=num && num<10000000 ) return 7;

варто писати

if( num >= 1000000 && num < 10000000 ) return 7;

так читабельніше!
зверніть увагу, як ви читаєте код вголос --
"якщо ікс більше сто, та менше тисячі"...
невже хтось читає чи думає "якщо сотня менше ікса та ікс менше тисячі.." ?  :o


по-друге, дивлячись на

if( num>=100000000000000000 ) return 18;

особисто мені хочеться дати підсрачника тому, хто це писав,
за те, що він вирішив не жаліти очі тих, хто його лайнокод читатиме!

навіть у відносно мало-популярні haskell та erlang завезли underscores in numeric;

невже в таких популярних сішко-плюсах (якими я не користуюсь) цієї фічі немає?
не вірю!

пишіть код для людей! читабельним)

if( num >= 100_000_000_000_000_000 ) return 18;

14 Востаннє редагувалося koala (15.03.2020 09:42:44)

Re: Кривий код чи оптимізація?

Мова саме про читаність та оптимізації. Якби там було про два компілятори, то це було б порівняння компіляторів. До речі, clang і gcc - не єдині два компілятори C++, що існують.

221VOLT написав:

зверніть увагу, як ви читаєте код вголос --
"якщо ікс більше сто, та менше тисячі"...

Так у цьому ж і халепа! Зверніть увагу, як навіть ви читаєте вголос - "якщо ікс більше сто, та менше тисячі"...

Heil Spellcheck!

"якщо ікс більший за сто і менший за тисячу"

Не "та ікс менше за тисячу", а пропустивши змінну. "num>=100 && <1000" - компілятор так не вміє. Утім, будь-яка притомна людина прочитає це "якщо нум між сотнею і тисячею"; у математиці запишуть 100≤num<100; Python навіть уміє таке читати: "100<=num<1000". Мій запис - найближче з того, що C++ дозволяє для імітації такого математичного запису, і я вважаю його оптимальним для подібних ситуацій.

221VOLT написав:

невже в таких популярних сішко-плюсах (якими я не користуюсь) цієї фічі немає?
не вірю!

Ваша правда - в останніх версіях C++ з'явилося.

if( num>=100'000'000'000'000'000 ) return 18;

Виправив. Щоправда, підсвітка коду на Replace тепер не може впоратися.

Подякували: wander, leofun012