Коли оптимізувати для пам'яті або швидкості продуктивності для методу?

Нещодавно я взяв інтерв'ю в Amazon. Під час сеансу кодування інтерв'юер запитав, чому я визначив змінну в методі. Я пояснив свій процес, і він закликав мене вирішити ту ж проблему з меншою кількістю змінних. Наприклад (це не з інтерв'ю), я почав з Методу A , потім покращив його до Методу B , видаливши int s . Він був задоволений і сказав, що це зменшить використання пам'яті цим методом.

Я розумію логіку, але моє запитання:

Коли доцільно використовувати метод A проти методу B, і навпаки?

Ви можете бачити, що Метод A буде мати більш високе використання пам'яті, оскільки int s оголошено, але він повинен виконати тільки один розрахунок, тобто a + b . З іншого боку, Метод B має менше використання пам'яті, але він повинен виконати два обчислення, тобто a + b двічі. Коли я використовую одну техніку над іншою? Або, чи одна з методів завжди краща за іншу? Що потрібно враховувати при оцінці цих двох методів?

Метод A:

private bool IsSumInRange(int a, int b)
{
    int s = a + b;

    if (s > 1000 || s < -1000) return false;
    else return true;
}

Метод B:

private bool IsSumInRange(int a, int b)
{
    if (a + b > 1000 || a + b < -1000) return false;
    else return true;
}
106
Ця частина вашого інтерв'ю пояснює багато чого про те, чому інженери Amazon не можуть створити гідний API, щоб врятувати їх життя. Пам'ятайте, що інтерв'ю є двосторонніми вулицями: Ви вирішуєте, чи хочете ви працювати з ними так само, як вони вирішують, чи хочуть вони працювати з вами. Передчасні оптимізаційні вправи, як це, безглузді і повинні бути червоним прапором. Хотілося б бачити, щоб хтось перевертав таблиці інтерв'ю одного дня, і замість того, щоб інтерв'юер написав код.
додано Автор Roland Bengtsson, джерело
@Andy якщо ви працюєте для Amazon, ви повинні бути в змозі оптимізувати швидкість. Ваш код може бути розгорнутий на тисячах серверів. Якщо він працює повільно, це може коштувати компанії багато грошей і впливати на багатьох клієнтів. Ви можете тримати його читаним одночасно, але це не дитячий сад.
додано Автор Alexander, джерело
Різниця між оголошенням і не декларуванням змінної повинна бути незначною, якщо навіть є різниця - якщо питання про це конкретно, досить справедливо, але ви, здається, задаєте більш загальне питання. Крім того, це компроміс - потрібно зрозуміти, скільки пам'яті та часу використовують різні підходи, і скільки з них у вас є. Я не впевнений, що тут є загальна відповідь (крім "не оптимізуйте передчасно").
додано Автор Arjan, джерело
@philipxy Звичайно, це може переповнюватися, але, тим не менш, це правильно, як є. Ви не можете перевірити на переповнення всюди, так що в цілому, ви просто повинні ігнорувати цю проблему.
додано Автор David Nehme, джерело
@philipxy Я написав "у загальному , ви просто повинні ігнорувати проблему". Це не означає, що ви не можете виявити переповнення в окремих випадках.
додано Автор David Nehme, джерело
До речі, ніколи не пишіть if (умова), а потім повертайте false false return
додано Автор miguel.de.icaza, джерело
@ T.Sar Ось чому технічні інтерв'ю кодування, як правило, нісенітниця. Вони навіть не копіюють фактичне робоче середовище ... просто нерви можуть потрапити до вас і в кінцевому підсумку "не вдасться" щось інакше ви зможете зробити.
додано Автор Vineel Adusumilli, джерело
Я повернув питання до початкового стану, оскільки ваша редакція скасувала мою відповідь - будь ласка, не робіть цього! Якщо ви задаєте питання, як покращити код, не змінюйте питання, покращуючи код у показаному вигляді - це робить відповіді незначними.
додано Автор Peter LeFanu Lumsdaine, джерело
Запам'ятайте: профіль перед оптимізацією. У сучасних компіляторах метод A і метод B можуть бути оптимізовані до одного і того ж коду (використовуючи більш високі рівні оптимізації). Крім того, за допомогою сучасних процесорів вони можуть мати інструкції, які виконують більше, ніж додавання в одній операції.
додано Автор Lost in Alabama, джерело
Ні; оптимізувати для читання.
додано Автор Andy, джерело
@rghome Я впевнений, що вони також профайлюють свій код, щоб побачити, чи можуть бути поліпшення, і не намагайтеся оптимізувати кожну лінію. Непрочитана лінія, яка містить помилку, також може коштувати мільйонам Amazon.
додано Автор Andy, джерело
@ T.Sar Дійсно вражаючий кандидат би вказав це у той час. Хоча це звучить як інтерв'юер щиро не тестував таким чином, що є ганьбою
додано Автор Lightness Races in Orbit, джерело
@code_dredd Я згоден, що кодування інтерв'ю є звичайно безглуздим і більш-менш марним. Зазвичай, кілька платних тижнів тест-драйву є набагато кращими, ніж хороші від поганих кандидатів, ніж ті типи питань. Я пробував чимало інтерв'ю, тому що я панікував себе ...
додано Автор T. Sar, джерело
Я готовий посперечатися, що сучасний компілятор буде генерувати одну і ту ж збірку для обох цих випадків.
додано Автор Minihawk, джерело
На якій мові це? Мова може впливати на метод, використовуючи менше пам'яті
додано Автор Ferrybig, джерело
Метод А має менший обсяг пам'яті, оскільки тільки 2 змінні повинні бути завантажені в один момент, компілятор може замінити значення a на s і зробити те ж саме з коли він порівнює тепер званий a з цільовим значенням. З іншим кодом, він потребує ще 1 значення в області, щоб зберегти значення результату обчислення, перш ніж він зможе порівняти його
додано Автор Ferrybig, джерело
Крім того, int abs (int) може бути реалізований без типових схем на типових архітектурах, тому я б вивів повернення abs (a + b) <= 1000 у кільце ...
додано Автор bubbleking, джерело
Зачекайте секунди, вони попросили позбутися від int s , будучи абсолютно добре з тими магічними числами для верхньої та нижньої меж?
додано Автор Orient, джерело
@ 17of26: Тільки якщо ввімкнути оптимізацію. Крім того, не просто робите ставку, дивіться її на explorer explorer
додано Автор Samuel Littley, джерело
Всі сукупні відповіді в даний час страждають від переповнення. (Не особливо стосується вашої відповіді, окрім того, щоб отримати її безпосередньо, перш ніж подумати про "оптимізацію".)
додано Автор philipxy, джерело
@maaartinus Незрозуміло, що ви намагаєтеся сказати. IsSumInRange легко писати, так що це тотальна, так що це не так, що "ви просто повинні ігнорувати проблему". (Чи є A на даний момент правильним залежить від його специфікації. Оскільки B має розрахувати, що A робить, це, мабуть, добре.)
додано Автор philipxy, джерело
Мені цікаво, може, екзаменатор хотів визнати, що змінна s , оголошена у вашій першій відповіді, не призведе до більшого використання пам'яті ...
додано Автор Nuzzolilo, джерело
Метод B виконуватиме обчислення двічі, коли сума становить <-1000. Є часи, щоб оптимізувати для пам'яті (IO операцій), інші 99% буде про продуктивність.
додано Автор user143241, джерело
Просто для будь-яких майбутніх відповідей, спробуйте ігнорувати "формат" коду і спробуйте зосередитися на загальному запиті. Я не запитую, як очистити мій код, метод A і B - це лише приклади.
додано Автор user1476849, джерело
Це багато в чому залежить від мети коду. Скільки людей, швидше за все, стануть відповідальними за перегляд і підтримку коду? Напевно, нам доведеться розширити її пізніше? Якщо це ваш власний код, ви можете робити те, що хочете, але якщо ви є частиною якоїсь команди, було б доцільно подумати про такі речі.
додано Автор Vilvas, джерело
Не кажучи вже про те, що було б набагато простіше сказати return! (Condition) .
додано Автор Marc-André Lafortune, джерело
C ++ еквівалентний код , скомпільований g ++, створює той самий код. Для інших мов вони мають JIT, тому я не впевнений.
додано Автор user314625, джерело

14 Відповіді

Замість того, щоб спекулювати про те, що може або не може статися, давайте просто подивимося, чи не так? Я буду використовувати C ++, так як я не маю C# компілятор зручний (хоча див. приклад C# від VisualMelon ), але я впевнений, що ці принципи застосовуються незалежно.

Ми включимо дві альтернативи, з якими ви зіткнулися в інтерв'ю. Ми також включимо версію, яка використовує abs , як це передбачено деякими відповідями.

#include 

bool IsSumInRangeWithVar(int a, int b)
{
    int s = a + b;

    if (s > 1000 || s < -1000) return false;
    else return true;
}

bool IsSumInRangeWithoutVar(int a, int b)
{
    if (a + b > 1000 || a + b < -1000) return false;
    else return true;
}

bool IsSumInRangeSuperOptimized(int a, int b) {
    return (abs(a + b) < 1000);
}

Now compile it with no optimization whatsoever: g++ -c -o test.o test.cpp

Now we can see precisely what this generates: objdump -d test.o

0000000000000000 <_Z19IsSumInRangeWithVarii>:
   0:   55                      push   %rbp              # begin a call frame
   1:   48 89 e5                mov    %rsp,%rbp
   4:   89 7d ec                mov    %edi,-0x14(%rbp)  # save first argument (a) on stack
   7:   89 75 e8                mov    %esi,-0x18(%rbp)  # save b on stack
   a:   8b 55 ec                mov    -0x14(%rbp),%edx  # load a and b into edx
   d:   8b 45 e8                mov    -0x18(%rbp),%eax  # load b into eax
  10:   01 d0                   add    %edx,%eax         # add a and b
  12:   89 45 fc                mov    %eax,-0x4(%rbp)   # save result as s on stack
  15:   81 7d fc e8 03 00 00    cmpl   $0x3e8,-0x4(%rbp) # compare s to 1000
  1c:   7f 09                   jg     27                # jump to 27 if it's greater
  1e:   81 7d fc 18 fc ff ff    cmpl   $0xfffffc18,-0x4(%rbp) # compare s to -1000
  25:   7d 07                   jge    2e                # jump to 2e if it's greater or equal
  27:   b8 00 00 00 00          mov    $0x0,%eax         # put 0 (false) in eax, which will be the return value
  2c:   eb 05                   jmp    33 <_Z19IsSumInRangeWithVarii+0x33>
  2e:   b8 01 00 00 00          mov    $0x1,%eax         # put 1 (true) in eax
  33:   5d                      pop    %rbp
  34:   c3                      retq

0000000000000035 <_Z22IsSumInRangeWithoutVarii>:
  35:   55                      push   %rbp
  36:   48 89 e5                mov    %rsp,%rbp
  39:   89 7d fc                mov    %edi,-0x4(%rbp)
  3c:   89 75 f8                mov    %esi,-0x8(%rbp)
  3f:   8b 55 fc                mov    -0x4(%rbp),%edx
  42:   8b 45 f8                mov    -0x8(%rbp),%eax  # same as before
  45:   01 d0                   add    %edx,%eax
  # note: unlike other implementation, result is not saved
  47:   3d e8 03 00 00          cmp    $0x3e8,%eax      # compare to 1000
  4c:   7f 0f                   jg     5d <_Z22IsSumInRangeWithoutVarii+0x28>
  4e:   8b 55 fc                mov    -0x4(%rbp),%edx  # since s wasn't saved, load a and b from the stack again
  51:   8b 45 f8                mov    -0x8(%rbp),%eax
  54:   01 d0                   add    %edx,%eax
  56:   3d 18 fc ff ff          cmp    $0xfffffc18,%eax # compare to -1000
  5b:   7d 07                   jge    64 <_Z22IsSumInRangeWithoutVarii+0x2f>
  5d:   b8 00 00 00 00          mov    $0x0,%eax
  62:   eb 05                   jmp    69 <_Z22IsSumInRangeWithoutVarii+0x34>
  64:   b8 01 00 00 00          mov    $0x1,%eax
  69:   5d                      pop    %rbp
  6a:   c3                      retq

000000000000006b <_Z26IsSumInRangeSuperOptimizedii>:
  6b:   55                      push   %rbp
  6c:   48 89 e5                mov    %rsp,%rbp
  6f:   89 7d fc                mov    %edi,-0x4(%rbp)
  72:   89 75 f8                mov    %esi,-0x8(%rbp)
  75:   8b 55 fc                mov    -0x4(%rbp),%edx
  78:   8b 45 f8                mov    -0x8(%rbp),%eax
  7b:   01 d0                   add    %edx,%eax
  7d:   3d 18 fc ff ff          cmp    $0xfffffc18,%eax
  82:   7c 16                   jl     9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
  84:   8b 55 fc                mov    -0x4(%rbp),%edx
  87:   8b 45 f8                mov    -0x8(%rbp),%eax
  8a:   01 d0                   add    %edx,%eax
  8c:   3d e8 03 00 00          cmp    $0x3e8,%eax
  91:   7f 07                   jg     9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
  93:   b8 01 00 00 00          mov    $0x1,%eax
  98:   eb 05                   jmp    9f <_Z26IsSumInRangeSuperOptimizedii+0x34>
  9a:   b8 00 00 00 00          mov    $0x0,%eax
  9f:   5d                      pop    %rbp
  a0:   c3                      retq

Ми бачимо з адрес стека (наприклад, -0x4 у mov% edi, -0x4 (% rbp) у порівнянні з -0x14 у mov% edi, -0x14 (% rbp) ), що IsSumInRangeWithVar() використовує 16 додаткових байтів у стеку.

Оскільки IsSumInRangeWithoutVar() не виділяє місця на стеку, щоб зберігати проміжне значення s , воно має перерахувати його, внаслідок чого ця реалізація триватиме довше.

Забавно, IsSumInRangeSuperOptimized() дуже схожий на IsSumInRangeWithoutVar() , за винятком того, що він порівнюється з -1000 спочатку і 1000 секунд.

Тепер скомпілюймо лише найпростіші оптимізації: g ++ -O1 -c -o test.o test.cpp . Результат:

0000000000000000 <_Z19IsSumInRangeWithVarii>:
   0:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
   7:   3d d0 07 00 00          cmp    $0x7d0,%eax
   c:   0f 96 c0                setbe  %al
   f:   c3                      retq

0000000000000010 <_Z22IsSumInRangeWithoutVarii>:
  10:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
  17:   3d d0 07 00 00          cmp    $0x7d0,%eax
  1c:   0f 96 c0                setbe  %al
  1f:   c3                      retq

0000000000000020 <_Z26IsSumInRangeSuperOptimizedii>:
  20:   8d 84 37 e8 03 00 00    lea    0x3e8(%rdi,%rsi,1),%eax
  27:   3d d0 07 00 00          cmp    $0x7d0,%eax
  2c:   0f 96 c0                setbe  %al
  2f:   c3                      retq

Would you look at that: each variant is identical. The compiler is able to do something quite clever: abs(a + b) <= 1000 is equivalent to a + b + 1000 <= 2000 considering setbe does an unsigned comparison, so a negative number becomes a very large positive number. The lea instruction can actually perform all these additions in one instruction, and eliminate all the conditional branches.

Щоб відповісти на ваше запитання, майже завжди для оптимізації - це не пам'ять або швидкість, а читаність . Читання коду набагато важче, ніж його написання, і читання коду, який було зіпсовано, щоб "оптимізувати" це набагато важче, ніж читання коду, який було написано, щоб бути ясним. Найчастіше ці "оптимізації" мають незначний або, як у цьому випадку, точно нульовий вплив на продуктивність.


Виникає питання, які зміни, коли цей код знаходиться в інтерпретованій мові, а не компілюється? Тоді чи має значення оптимізація, чи має той самий результат?

Давайте виміряти! Я переписав приклади до Python:

def IsSumInRangeWithVar(a, b):
    s = a + b
    if s > 1000 or s < -1000:
        return False
    else:
        return True

def IsSumInRangeWithoutVar(a, b):
    if a + b > 1000 or a + b < -1000:
        return False
    else:
        return True

def IsSumInRangeSuperOptimized(a, b):
    return abs(a + b) <= 1000

from dis import dis
print('IsSumInRangeWithVar')
dis(IsSumInRangeWithVar)

print('\nIsSumInRangeWithoutVar')
dis(IsSumInRangeWithoutVar)

print('\nIsSumInRangeSuperOptimized')
dis(IsSumInRangeSuperOptimized)

print('\nBenchmarking')
import timeit
print('IsSumInRangeWithVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeWithoutVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithoutVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeSuperOptimized: %fs' % (min(timeit.repeat(lambda: IsSumInRangeSuperOptimized(42, 42), repeat=50, number=100000)),))

Запускати з Python 3.5.2, це виробляє вихід:

IsSumInRangeWithVar
  2           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (b)
              6 BINARY_ADD
              7 STORE_FAST               2 (s)

  3          10 LOAD_FAST                2 (s)
             13 LOAD_CONST               1 (1000)
             16 COMPARE_OP               4 (>)
             19 POP_JUMP_IF_TRUE        34
             22 LOAD_FAST                2 (s)
             25 LOAD_CONST               4 (-1000)
             28 COMPARE_OP               0 (<)
             31 POP_JUMP_IF_FALSE       38

  4     >>   34 LOAD_CONST               2 (False)
             37 RETURN_VALUE

  6     >>   38 LOAD_CONST               3 (True)
             41 RETURN_VALUE
             42 LOAD_CONST               0 (None)
             45 RETURN_VALUE

IsSumInRangeWithoutVar
  9           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (b)
              6 BINARY_ADD
              7 LOAD_CONST               1 (1000)
             10 COMPARE_OP               4 (>)
             13 POP_JUMP_IF_TRUE        32
             16 LOAD_FAST                0 (a)
             19 LOAD_FAST                1 (b)
             22 BINARY_ADD
             23 LOAD_CONST               4 (-1000)
             26 COMPARE_OP               0 (<)
             29 POP_JUMP_IF_FALSE       36

 10     >>   32 LOAD_CONST               2 (False)
             35 RETURN_VALUE

 12     >>   36 LOAD_CONST               3 (True)
             39 RETURN_VALUE
             40 LOAD_CONST               0 (None)
             43 RETURN_VALUE

IsSumInRangeSuperOptimized
 15           0 LOAD_GLOBAL              0 (abs)
              3 LOAD_FAST                0 (a)
              6 LOAD_FAST                1 (b)
              9 BINARY_ADD
             10 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             13 LOAD_CONST               1 (1000)
             16 COMPARE_OP               1 (<=)
             19 RETURN_VALUE

Benchmarking
IsSumInRangeWithVar: 0.019361s
IsSumInRangeWithoutVar: 0.020917s
IsSumInRangeSuperOptimized: 0.020171s

Розбирання в Python не дуже цікаве, оскільки "компілятор" байт-коду не робить багато чого на шляху оптимізації.

Продуктивність трьох функцій майже однакова. Ми можемо спокуситися йти з IsSumInRangeWithVar() через його граничне збільшення швидкості. Хоча я додаю, оскільки я пробував різні параметри, щоб timeit , іноді IsSumInRangeSuperOptimized() вийшов найшвидшим, тому я підозрюю, що це можуть бути зовнішні фактори, які відповідають за різницю ніж будь-яка внутрішня перевага будь-якої реалізації.

Якщо це дійсно критичний код, то інтерпретований мова просто дуже поганий вибір. Запускаючи ту саму програму з pypy, я отримую:

IsSumInRangeWithVar: 0.000180s
IsSumInRangeWithoutVar: 0.001175s
IsSumInRangeSuperOptimized: 0.001306s

Просто використання pypy, яке використовує компіляцію JIT для усунення великої кількості накладних витрат на інтерпретатор, дало змогу поліпшити продуктивність на 1 або 2 порядки. Я був дуже вражений тим, що IsSumInRangeWithVar() на порядок швидше, ніж інші. Тому я змінив порядок тестів і знову запустив:

IsSumInRangeSuperOptimized: 0.000191s
IsSumInRangeWithoutVar: 0.001174s
IsSumInRangeWithVar: 0.001265s

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

Я хотів би глибше заглибитися в це, тому що, чесно кажучи, я не знаю, чому це відбувається. Але я вважаю, що справа була зроблена: мікро-оптимізація, наприклад, чи потрібно оголошувати проміжне значення як змінну чи не є рідко актуальними. З інтерпретованою мовою або високо оптимізованим компілятором, першою метою все ще є написання чіткого коду.

Якщо може знадобитися подальша оптимізація, benchmark . Пам'ятайте, що найкращі оптимізації виходять не з дрібних деталей, а з більшою алгоритмічною картиною: pypy буде на порядок швидше для повторної оцінки тієї ж функції, що й cpython, оскільки він використовує більш швидкі алгоритми (JIT compiler vs interpret) програми. І тут є кодований алгоритм: пошук через B-дерево буде швидше, ніж пов'язаний список.

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

146
додано
Про те, чому для PyPy важливий порядок: чи ви спалили період прогріву JIT?
додано Автор Piers C, джерело
@VisualMelon досить погано позитивна перевірка: "return (((a + b)> = -1000) && ((a + b) <= 1000));" дає інший результат. : sharplab.io/…
додано Автор xirt, джерело
Ці Pypy загальні часи здаються дуже короткими для мови, яка зупиняється, і JIT-компіляції. Крім того, недостатньо, щоб частота процесорних частот від простою до максимального турбо може бути фактором, особливо якщо ви не використовуєте Skylake (з апаратними P-станами). Бенчмаркінг в секундах замість тактових циклів ядра вимагає контролю частоти процесора. Як перевірка розумності, чи лінійно масштабується час з повтором? Якщо ні, ви вимірюєте накладні витрати. Крім того, чи не JIT зможе вбудувати і підняти розрахунок з циклу? Якщо ви не використовуєте вихід одного як вхідний для наступного, вимірювання затримки не tput.
додано Автор Mathieu Ravaux, джерело
Так, ефект розгону зазвичай робив більш ранні речі повільніше. Час не настільки короткий, що ~ 8us паузи, коли процесор перемикає частоту і напругу ( втрачені цикли на Intel? Невідповідність між rdtsc і CPU_CLK_UNHALTED .REF_TSC ) не повинні робити нічого повільніше. Я просто згадав це як ще одну причину, через яку ваш інтервал у лавці занадто короткий. Можливо, він спочатку інтерпретує, а потім зупиняється на JIT, як JVM HotSpot? Якщо він вирішив зупинитися і JIT-компіляції безпосередньо перед останньою ітерацією, що б смоктати.
додано Автор Mathieu Ravaux, джерело
У будь-якому випадку, якщо ви просто розкрутите повтори повторного підрахунку, то вони займуть приблизно від 0,5 до 1,0 секунди, чи результати залишаться подібними? Ваші результати PyPy безперечно дивують. (Але я зазвичай не дивлюся на Python, тому IDK, який тип gotchas може існувати для timeit на такій короткій функції.) О, я просто спробував. Ці часи є середніми для кожного виклику, а не фактичним загальним інтервалом вимірювання. Так IDK.
додано Автор Mathieu Ravaux, джерело
Перший запускається після import timeit , тоді як інші виконуються відразу після повернення print . Можливо, існує деякий ефект розминки, або вплив на те, що робить JIT? Що робити, якщо ви збираєте всі 3 результати, перш ніж друкувати що-небудь?
додано Автор Mathieu Ravaux, джерело
Так, timeit все ще намагається окремо визначати час кожного виклику? Ця функція є занадто короткою для цього. Щоб реально дозволити JIT зробити що-небудь, потрібно викликати його в циклі над масивом, або з вхідним виходом подачі, або щось, і час весь цикл.
додано Автор Mathieu Ravaux, джерело
Моя думка полягала в тому, що документ PyPy говорить, що він друкує середнє і стандартне відхилення , тому внутрішньо timeit має все-таки записувати тимчасові мітки навколо цієї майже тривіальної речі. Це не пояснює цей божевільний ефект "охолодження", але це означає, що є величезні накладні витрати. (Див. clflush, щоб скасувати рядок кешу за допомогою функції C , і відповідь на Розуміння впливу lfence на петлю з двома довгими ланцюгами залежностей, для збільшення довжини для того, наскільки важко час дуже коротких інтервалів, навіть з непереносним < код> rdtsc
додано Автор Mathieu Ravaux, джерело
@chux: gcc також має скасувати abs і повернути його назад у діапазон перевірки (як я прокоментував на іншу відповідь, що запропонував abs() " оптимізацію ", після чого застосуйте непідписаний трюк: (без знака) (a + b + 999) <= 1998U . (Я не можу повторити a + b + 1000 <2000) виводить на Godbolt з -O1 або -O3 з декількома версіями gcc. godbolt.org/z/d0isuc Інші компілятори (наприклад, clang) не спроможні скасувати його.
додано Автор Mathieu Ravaux, джерело
@Corey: ця відповідь насправді говорить вам, що я написав у своїй відповіді: немає ніякої різниці, коли ви використовуєте гідний компілятор, і замість цього зосередьтеся на readibilty. Звичайно, це виглядає краще заснованою - можливо, ви повірите мені зараз.
додано Автор Peter LeFanu Lumsdaine, джерело
Я підозрюю причину, чому порядок вашого бенчмаркінгу, мабуть, має значення, можливо, пов'язано з прогнозом гілок в CPU. stackoverflow.com/questions/11227809/…
додано Автор maple_shaft, джерело
Здатність читатись може також полегшити оптимізацію програми. Компілятор може легко переписати, щоб використовувати еквівалентну логіку, як це було вище, тільки якщо вона дійсно може з'ясувати, що ви намагаєтеся зробити. Якщо ви використовуєте багато старої школи і покажчиків, повторне використання змінюваних зберігання і т.д. може бути набагато складніше для компілятора довести, що перетворення еквівалентно, і це просто залишить те, що ви написали, які можуть бути неоптимальними.
додано Автор Leushenko, джерело
@Corey див. Редагування.
додано Автор Darhuuk, джерело
@PeterCordes Чи не означає це, що перший запуск відбувається повільніше, а не швидше? Не впевнений, наскільки оптимізація pypy jit здатна - є модуль, який може перевірити згенерований машинний код, але я не мав часу грати з ним.
додано Автор Darhuuk, джерело
@PeterCordes Так, збільшення ітерацій на 100x, незалежно від того, що тестується спочатку все ще на порядок швидше. Як не дивно, якщо я перевіряю всі три реалізації один раз, то знову, то третій раз, на кожній ітерації одна й та ж реалізація є більш повільною, ніж це було вперше. Мені цікаво, якщо timeit якось відрізняється під pypy. doc.pypy.org/en/latest/cpython_differences.html говорить: " Модуль timeit веде себе по-різному в PyPy: він друкує середній час і стандартне відхилення, а не мінімум, оскільки мінімум часто вводить в оману. "
додано Автор Darhuuk, джерело
Ні, параметри number , що викликають передану функцію багато разів, у моїх останніх тестах, 100000000 разів. Я розігріваю JIT, і все це, це те, що в першу чергу - це те, що для того, щоб отримати бенчмаркінг, є найшвидшим. Це не розминка, це охолодження.
додано Автор Darhuuk, джерело
@maple_shaft Я серйозно сумніваюся. Код і вхід є кожен раз один і той же, і все ж, якщо я запускаю його кілька мільйонів разів, то якимось чином стає на три порядки повільніше.
додано Автор Darhuuk, джерело
@PeterCordes timeit , що виконує виклик number , а потім повторює тест повторити раз, і я друкую найшвидші з цих повторів припущення, що це найшвидший час, - це внутрішня швидкість функції без будь-яких накладних витрат JIT, переривання інших процесів на хості, пропуски в кеші тощо. не говори, чому. Можливо, він періодично перекомпілює функцію, навіть якщо нічого не змінилося. Можливо, це помилка. Я не знаю.
додано Автор Darhuuk, джерело
@ Кевін JIT розігріву вже обговорювалися довго в коментарях.
додано Автор Darhuuk, джерело
! (a + b> 1000 або a + b <-1000) і abs (a + b) <= 1000 можуть створювати різні функції, коли a + b == INT_MIN із звичайною проблемою з abs (INT_MIN) . Цей компілятор випустив потрібний код, але не зобов'язав abs (a + b) <= 1000 .
додано Автор chux, джерело
Для того, щоб привести приклад в C #: SharpLab виробляє ідентичний асемблер для обох методів (настільний CLR v4.7.3130.00 (clr.dll) на x86)
додано Автор tommycatpr, джерело
@PhilFrost Це була неймовірна відповідь і саме те, що я шукав. Подальше питання, які зміни, коли цей код знаходиться в інтерпретованій мові, а не компілюється? Тоді, чи має значення оптимізація, чи має той самий результат?
додано Автор user1476849, джерело

Відповісти на поставлене запитання:

Коли оптимізувати пам'ять у порівнянні зі швидкістю продуктивності для методу?

Ви повинні встановити дві речі:

  • Що обмежує вашу програму?
  • Де можна повернути більшу частину цього ресурсу?

Для того, щоб відповісти на перше запитання, потрібно знати, які вимоги до продуктивності для вашої програми. Якщо немає вимог до продуктивності, то немає жодних причин для оптимізації так чи інакше. Вимоги до ефективності допоможуть вам дістатися до місця "досить хорошого".

Метод, який ви самі надавали, сам по собі не викликав би проблем з продуктивністю, але, можливо, в межах циклу та обробки великої кількості даних, ви повинні трохи по-іншому подумати про те, як ви підходите до проблеми.

Виявлення обмеження програми

Почніть дивитися на поведінку вашої програми за допомогою монітора продуктивності. Слідкуйте за використанням процесора, диска, мережі та пам'яті під час роботи. Один або кілька пунктів буде вичерпано, а все інше буде помірно використане - якщо ви не досягнете ідеального балансу, але це майже ніколи не відбувається).

Коли вам потрібно виглядати глибше, зазвичай ви використовуєте profiler . Є профайлери пам'яті і профілі процесів , які вимірюють різні речі. Акт профілювання має значний вплив на продуктивність, але ви інструментуєте свій код, щоб дізнатися, що не так.

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

Якщо ви не можете знайти будь-які гарячі точки, ви почнете дивитися на пам'ять. Можливо, ви створюєте більше об'єктів, ніж потрібно, і ваш збір сміття працює понаднормово.

Відновлення продуктивності

Думайте критично. Наведений нижче перелік змінюється відповідно до того, скільки прибутку ви отримаєте:

  • Архітектура: шукайте точки комунікації
  • Алгоритм: спосіб обробки даних може потребувати зміни
  • Гарячі точки: мінімізація частоти виклику гарячої точки може принести великий бонус
  • Мікрооптимізація: це не поширене явище, але іноді потрібно подумати про незначні зміни (наприклад, наданий приклад), особливо якщо це гаряча точка в коді.

У таких ситуаціях потрібно застосовувати науковий метод. Придумайте гіпотезу, внесіть зміни і перевірте її. Якщо ви досягаєте цілей ефективності, все готово. Якщо ні, перейдіть до наступної речі у списку.


Відповідаючи на запит жирним шрифтом:

Коли доцільно використовувати метод A проти методу B, і навпаки?

Чесно кажучи, це останній крок у спробі вирішити проблеми з продуктивністю або пам'яттю. Вплив методу A на метод B буде дійсно різним залежно від платформи та (у деяких випадках).

Майже будь-який скомпільований мова з напівприйнятним оптимізатором буде генерувати подібний код з будь-якою з цих структур. Однак ці припущення не обов'язково залишаються вірними в патентованих і іграшкових мовах, які не мають оптимізатора.

Саме те, що матиме кращий вплив, залежить від того, чи є sum змінною стека або змінною купи. Це вибір мови. Наприклад, у C, C ++ і Java число примітивів, як int , є змінними стека за замовчуванням. Ваш код більше не впливає на пам'ять, призначаючи змінну стека, ніж це було б із повністю вбудованим кодом.

Інші оптимізації, які ви могли б знайти в бібліотеках C (особливо старших), де ви можете вирішити між копіюванням 2-х мірного масиву вниз першим або першим, є залежною від платформи оптимізацією. Це вимагає певних знань про те, як найкраще оптимізує доступ до пам'яті, яку ви націлюєте. Існують тонкі відмінності між архітектурами.

Суть у тому, що оптимізація - це поєднання мистецтва і науки. Це вимагає критичного мислення, а також певної гнучкості в тому, як ви підходите до проблеми. Шукайте великі речі, перш ніж звинувачувати маленькі речі.

67
додано
@Eric, як я вже згадував, остання категорія поліпшення продуктивності буде вашою мікро-оптимізацією. Єдиний спосіб мати гарне припущення, якщо він буде мати будь-який вплив, це вимірювання продуктивності/пам'яті у профілі. Це рідко, що ці типи поліпшень мають виграш, але в проблеми чутливості часу чутливості у вас є в тренажерах пара добре розміщені зміни, як це може бути різниця між ударом вашої мети часу, а не. Я думаю, що я з одного боку можу розраховувати на кількість разів, що виправдалися за 20 років роботи над програмним забезпеченням, але це не дорівнює нулю.
додано Автор tim_yates, джерело
@DocBrown, я виправив це. Що стосується другого питання, я з вами дуже згоден.
додано Автор tim_yates, джерело
Це вимагає певних знань про те, як найкраще оптимізує доступ до пам'яті, який ви націлюєте на набір мікросхем. або як організована структура даних). Всі апаратні засоби значно краще з послідовним безперервним доступом до всіх байтів у рядку кешу, ніж до кроків.
додано Автор Mathieu Ravaux, джерело
Ваша відповідь говорить лише про використання пам'яті в контексті загального розподілу пам'яті всієї програми. Іншим типом споживання пам'яті, що має відношення до продуктивності, є кеш відбитка/робочий набір через внутрішній цикл або над зовнішнім циклом. Пам'ять дешева, але кеш немає. Таблиця 1MiB, що замінює короткі обчислення, може добре виглядати в мікросенсорі і мати незначний вплив на ваш загальний обсяг пам'яті, але в реальному використанні (коли ви індексуєте її лише між іншими операціями пам'яті) може призвести до тонн пропусків кешу, принаймні, в кеш L2.
додано Автор Mathieu Ravaux, джерело
@Corey: таким чином, ви могли б профілі з лічильниками продуктивності для пропусків кешу, щоб переконатися, що дотик до меншого простору стека та інших даних може допомогти, якщо у вас був фактичний випадок, коли це був компроміс між обчисленням та простором (на відміну від нерозумного прикладу у вашому запитанні ). напр. perf stat -d ./my_program на Linux, щоб отримати відліки по всій програмі або записати профіль пропусків кешу останнього рівня. Linux C ++: як профайлувати час, витрачений за рахунок пропусків кешу? .
додано Автор Mathieu Ravaux, джерело
Я відчуваю, що це загальна відповідь на "Як ви вирішуєте вузькі місця в продуктивності", але вам буде важко визначити відносну пам'ять від конкретної функції на основі того, чи має він 4 або 5 змінних з використанням цього методу. Я також сумніваюся, наскільки релевантним є цей рівень оптимізації, коли компілятор (або інтерпретатор) може або не може оптимізувати це.
додано Автор joshmcode, джерело
@BerinLoritsch Знову ж таки, взагалі я з вами згоден, але в цьому конкретному випадку я цього не роблю. Я дав свою відповідь, але я особисто не бачив жодних інструментів, які б позначали або навіть давали вам способи потенційно виявити проблеми з продуктивністю, пов'язані з розміром пам'яті стека функції.
додано Автор joshmcode, джерело
Ця відповідь зосереджується найбільше на моєму питанні і не потрапляє на мої приклади кодування, тобто метод А і метод Б.
додано Автор user1476849, джерело

"Це зменшить пам'ять" - ем, ні. Навіть якщо це було б вірно (що для будь-якого гідного компілятора немає), різниця, швидше за все, була б незначною для будь-якої реальної ситуації в світі.

Однак я рекомендую використовувати метод A * (метод A з невеликою зміною):

private bool IsSumInRange(int a, int b)
{
    int sum = a + b;

    if (sum > 1000 || sum < -1000) return false;
    else return true;
   //(yes, the former statement could be cleaned up to
   //return abs(sum)<=1000;
   //but let's ignore this for a moment)
}

але з двох абсолютно різних причин:

  • надавши змінній s пояснювальному назві, код стає більш ясним

  • це дозволяє уникнути того, щоб двічі в коді була однакова логіка підсумовування, тому код стає більше DRY, що означає менше помилок, схильних до змін.

45
додано
@Corey: якщо це " трохи більш складний", він, ймовірно, не стане "помітним використанням пам'яті". Можливо, якщо ви побудуєте дійсно більш складний приклад, але це робить інше питання. Зауважте також, що лише тому, що ви не створюєте конкретну змінну для виразу, для складних проміжних результатів, середовище часу виконання може все ще створювати тимчасові об'єкти, тому повністю залежить від деталей мови, середовища, рівня оптимізації та все, що ви називаєте "помітним".
додано Автор Peter LeFanu Lumsdaine, джерело
Я змінював би порядок if (-1000 <�сума || сума <1000) повертає true; else return false; , оскільки впорядкування умовних умов таким чином робить більш зрозумілим, що ви робите перевірку діапазону.
додано Автор Eloy, джерело
@TobySpeight кожен. Знову вражає код для редагування 30-х років.
додано Автор Eloy, джерело
Будьте обережні @Dan - це не той самий тест. (Навіть якщо ви зміните || на && , ви також отримали неправильне порівняння: розгляньте sum == 1000 , наприклад).
додано Автор Toby Speight, джерело
@Corey будь-який гідний оптимізатор буде використовувати регістр ЦП для змінної sum , що призведе до нульового використання пам'яті. І навіть якщо ні, це єдине слово пам'яті в методі «листа». Враховуючи, наскільки неймовірно марнотратні пам'ять Java або C# можуть бути інакше пов'язані з їхньою GC і об'єктною моделлю, локальна змінна int буквально не використовує ніякої помітної пам'яті. Це безглузда мікрооптимізація.
додано Автор amon, джерело
Я хотів би очистити його ще далі і піти з "повернути суму> -1000 && сума <1000;".
додано Автор Minihawk, джерело
На додаток до наведених вище пунктів, я впевнений, що C #/Java вибирає для зберігання sum деталі реалізації , і я сумніваюся, що хтось може зробити переконливий випадок чи буде нерозумний трюк, як уникнення одного локального int , призведе до того чи іншого обсягу використання пам'яті в довгостроковій перспективі. Чим легше читати ІМО. Читання може бути суб'єктивним, але FWIW, особисто я б краще ніколи не робити те ж обчислення в два рази, а не для використання процесора, а тому, що я повинен тільки перевірити ваше додаток один раз, коли я шукаю помилку.
додано Автор jrh, джерело
... також зауважте, що мови зібрані зі сміття взагалі є непередбачуваним, "збиваючи морем пам'яті", що (для C# у будь-якому випадку) може бути очищено тільки при необхідності , я пам'ятаю, що я зробив програму, яка виділяла гігабайти оперативної пам'яті і вона тільки почала "прибирати" після себе, коли пам'ять стала маловалою. Якщо GC не потрібно запускати, це може зайняти його солодкий час і зберегти ваш процесор для більш нагальних питань.
додано Автор jrh, джерело
Чому б це не зменшило використання пам'яті? Припустимо, мій приклад коду був відмінно відформатований на будь-який смак, то чи A або B буде краще?
додано Автор user1476849, джерело
@amon, спасибі за роз'яснення. Отже, припустимо, що це не int , а, можливо, щось трохи складніше, що має помітне використання пам'яті. Як же я розгляну свої варіанти?
додано Автор user1476849, джерело

Ви можете зробити краще, ніж обидва з

return (abs(a + b) > 1000);

Більшість процесорів (і, отже, компілятори) можуть робити abs() за одну операцію. У вас є не тільки менші суми, але й менше порівнянь, які, як правило, є більш дорогими для обчислень. Вона також видаляє розгалуження, що набагато гірше на більшості процесорів, тому що припиняє можливість конвеєризації.

Інтерв'юер, як кажуть інші відповіді, є життям рослин і не має справи на технічне інтерв'ю.

Тим не менш, його питання є дійсним. Відповідь, коли ви оптимізуєте та яким чином, це , коли ви довели, що це необхідно, і ви профілізували його, щоб довести, які саме деталі потрібні . Кнут знаменито сказав, що передчасна оптимізація є корінь всього зла, тому що це занадто легко спробувати золоті пластини неважливі розділи, або вносити зміни (наприклад, ваш інтерв'юер), які не мають ефекту, в той час як відсутні місця, які дійсно потрібні. Доки у вас немає жорстких доказів, це дійсно необхідно, чіткість коду є більш важливою метою.

Edit FabioTurati correctly points out that this is the opposite logic sense to the original, (my mistake!), and that this illustrates a further impact from Knuth's quote where we risk breaking the code while we're trying to optimise it.

35
додано
"Покращений" код у цій відповіді все ще помилковий, оскільки він видає іншу відповідь для IsSumInRange (INT_MIN, 0) . Початковий код повертає false тому, що INT_MIN + 0> 1000 || INT_MIN + 0 <-1000 ; але "новий і покращений" код повертає true тому, що abs (INT_MIN + 0) <1000 . (Або на деяких мовах він викине виняток або не визначено поведінку. Перевірте місцеві списки.)
додано Автор sstock, джерело
Більшість процесорів (і, отже, компілятори) можуть виконувати abs() за одну операцію. На жаль, це не стосується цілих чисел. ARM64 має умовне заперечення, яке він може використовувати, якщо прапорці вже встановлені з adds , а ARM передбачає зворотне підпорядкування ( rsblt = reverse-sub, якщо менше-tha), але все інше вимагає декількох додаткових інструкцій для реалізації abs (a + b) або abs (a) . godbolt.org/z/Ok_Con показує x86, ARM, AArch64, PowerPC, MIPS і RISC-V вихід asm. Це лише шляхом перетворення порівняння в код (без знака) (a + b + 999) <= 1998U , що gcc може оптимізувати його, як у відповіді Філа.
додано Автор Mathieu Ravaux, джерело
Плаваючою точкою відрізняється: abs просто маскує верхній біт, тому що IEEE FP використовує представлення знаку/величини, і більшість ISA мають або команду SIMD І або інструкцію fabs . Найшвидший спосіб обчислення абсолютного значення за допомогою SSE . Ціле число abs() є швидким і невід'ємним: хоча кілька інструкцій, так що він все ще в основному дешевий, а gcc досить розумний, щоб скасувати його і повернути його в діапазон перевірки, що дозволяє непідписаному - сумісний трюк. abs (a + b) <1000 легко зрозуміти для людей, тому це не погано. Але кланяється ще гірше.
додано Автор Mathieu Ravaux, джерело
Хороша відповідь, але було б поліпшено, якщо 1000 було замінено на добре названу константу.
додано Автор MrG, джерело
Так, a та b можуть бути корисно перейменовані. Насправді я не фанат звичайних "конструктивних" аргументів функції, оскільки додає багатослівність і шум майже до нуля. YMMV.
додано Автор MrG, джерело
@Corey, я цілком впевнений, що Грем запитує "він закликав мене вирішити ту ж саму проблему з меншою кількістю змінних" , як і очікувалося. Якби я був інтерв'юером, я б очікував, що відповідь не буде переносити a + b у if і робити це двічі. Ви розумієте це неправильно "Він був задоволений і сказав, що це зменшить використання пам'яті цим методом" - він був приємний до вас, приховуючи своє розчарування цим безглуздим поясненням про пам'ять. Не варто серйозно ставити питання тут. Ви отримали роботу? Я думаю, ви не зробили :-(
додано Автор Sinatr, джерело
@ user949300 Погоджені, за винятком того, що я не знаю, що постійна представляє, тому я не можу допомогти. :) Все-таки моя думка була більше про оптимізацію, ніж про стандарти кодування. Якщо ми додаємо назву константи, я також хотів би кращі імена змінних, ніж "a" і "b", обидва параметри оголошені const, і Doxygen коментарі для оголошення функції.
додано Автор soho19941018, джерело
@ FabioTurati Добре помітили - спасибі! Я оновлю відповідь. І це хороший момент щодо рефакторингу та оптимізації, що робить цитату Кнута ще більш актуальною. Ми повинні довести, що нам потрібна оптимізація, перш ніж ми ризикуємо.
додано Автор soho19941018, джерело
Ви одночасно застосовуєте 2 перетворення: ви перетворили 2 умови на 1, використовуючи abs() , і у вас також є один return , замість одного коли умова є істинним ("if branch"), а інша, коли вона є помилковою ("else branch"). Коли ви змінюєте код, подібний до цього, будьте обережні: є ризик ненавмисно написати функцію, яка повертає true, коли вона повинна повернути false, і навпаки. Це саме те, що сталося тут. Я знаю, що ви зосередилися на іншій справі, і ви зробили хорошу роботу. Тим не менш, це могло легко коштувати вам роботу ...
додано Автор Marie Simm, джерело
Код був просто продемонструвати моє питання. Див. Мою записку.
додано Автор user1476849, джерело

Коли доцільно використовувати метод A проти методу B, і навпаки?

Hardware is cheap; programmers are expensive. So the cost of the time you two wasted on this question is probably far worse than either answer.

Незважаючи на це, більшість сучасних компіляторів знайдуть спосіб оптимізації локальної змінної в регістрі (замість виділення простору стека), тому методи, ймовірно, ідентичні з точки зору виконуваного коду. З цієї причини більшість розробників вибирають варіант, який найістотніше повідомляє про намір (див. Написання дійсно ясного коду (ROC) ). На мій погляд, це був би метод A.

З іншого боку, якщо це чисто академічна вправа, ви можете мати найкраще з обох світів за допомогою методу С:

private bool IsSumInRange(int a, int b)
{
    a += b;
    return (a >= -1000 && a <= 1000);
}
16
додано
"Апаратне забезпечення дешеве; програмісти дорогі". У світі споживчої електроніки це твердження є помилковим. Якщо ви продаєте мільйони одиниць, то це дуже гарна інвестиція, щоб витратити $ 500.000 на додаткові витрати на розробку, щоб заощадити $ 0,10 на апаратні витрати на одиницю.
додано Автор Dee, джерело
@JohnWu, моя точка зору була, що це не універсальна істина. Для компаній, таких як Amazon, це, безумовно, може бути правдою.
додано Автор Dee, джерело
Я згоден @jrh. Я - сильний пропагандист РПЦ, і такі речі нічого немає.
додано Автор John Wu, джерело
@BartvanIngenSchenau Я не впевнений, що Amazon будує побутову електроніку. Я думаю, що вони в основному будують серверне програмне забезпечення, а серверне обладнання дешеве в порівнянні з командами, які підтримують програмне забезпечення, яке працює на ньому.
додано Автор John Wu, джерело
Завдяки @ ShadowRanger. Прості логічні помилки є ще однією причиною написання ROC.
додано Автор John Wu, джерело
Це абсолютно правильна відповідь. Я багато років працював з 1K оперативної пам'яті або навіть менше у випадку мікроконтролерів. Тепер з появою 4GL і масштабованих екземплярів EC2. Цей вид ретельної деталі не є економічним. Є випадки, коли кодування для швидкості виконання все ще необхідне .. але використання пам'яті в даний час майже безглузде.
додано Автор Richard, джерело
a + = b - це акуратний трюк, але я маю згадати (про всяк випадок, що не передбачається з решти відповіді), з мого досвіду методи, які зв'язані з параметрами можуть бути дуже важко налагоджувати і підтримувати.
додано Автор jrh, джерело
@Richard Правильно в дусі (відповідно до деяких аспектів стилю коду ви не з'ясуєте, прямолінійність, я думаю), але він може переповнюватися (як код інших відповідей).
додано Автор philipxy, джерело
(До речі, я впевнений, що у поточній версії цієї відповіді return (a> = -1000 || a <= 1000); завжди буде оцінюватися як true .) @ShadowRanger
додано Автор Jermal Smith, джерело
@JohnWu: Ви спростили перевірку if , але забули змінити результат порівняння; Ваша функція повертає true , якщо a + b не у діапазоні. Або додайте ! назовні умови ( return! (A> 1000 || a <-1000) ), або поширюйте ! , інвертуючи тести, щоб отримати повернути <= 1000 && a> = -1000; Або зробити перевірку діапазону добре, повернути -1000 <= a && a <= 1000;
додано Автор Matt, джерело
@JohnWu: все ще трохи вимкнений на крайніх випадках, розподілена логіка вимагає <= /> = , а не </> (за допомогою </> , 1000 і -1000 розглядаються як поза межами діапазону, оригінальний код розглядається як такий, що знаходиться в діапазоні).
додано Автор Matt, джерело
@mathmandan: Так. Серйозно, просто скопіюйте та вставте: return a <= 1000 && a> = -1000; або return -1000 <= a && a <= 1000; , або правильно , це просто питання особистого стилю. Тут немає привілеїв для редагування, або я б це зробив сам.
додано Автор Matt, джерело

Я б оптимізував для читання. Метод X:

private bool IsSumInRange(int number1, int number2)
{
    return IsValueInRange(number1+number2, -1000, 1000);
}

private bool IsValueInRange(int Value, int Lowerbound, int Upperbound)
{
    return  (Value >= Lowerbound && Value <= Upperbound);
}

Невеликі методи, які роблять тільки одну річ, але легко розсуджувати.

(Це особисті уподобання. Мені подобається позитивне тестування, а не негативне, оригінальний код фактично перевіряє, чи це значення НЕ знаходиться поза діапазоном.)

11
додано
@ivanivan Коли ми працювали з набагато слабшими машинами і, таким чином, мали набагато слабшу оптимізацію, потрібно було більше трюків, щоб отримати прийнятну продуктивність. Тепер, багато хто з цих трюків взагалі не мають ніякої різниці, і більшість решти рідко є достатньо важливими, якщо вони взагалі перешкоджають читаності.
додано Автор Shizam, джерело
Тепер ви повинні простежити через 2 функції, щоб побачити, що відбувається. Ви не можете взяти його за номінальною вартістю, тому що ви не можете сказати від імені, чи є вони включними чи виключними межами. І якщо ви додасте цю інформацію, то назва функції буде довше, ніж код для його вираження.
додано Автор Maurice, джерело
Оптимізуйте читабельність і зробіть невеликі, прості для розумних функцій - звичайно, згодні. Але я не згоден з тим, що перейменування a та b на number1 та number2 допомагає читатись будь-яким чином. Також іменування функцій є несумісним: чому IsSumInRange жорстко кодує діапазон, якщо IsValueInRange приймає його як аргументи?
додано Автор zarose, джерело
@ivanivan: Я не думаю, що "проблема y2k" була дійсно про пам'ять. З точки зору введення даних, введення двох цифр є більш ефективним, ніж введення чотирьох, і утримання речей, як введено, легше, ніж перетворення їх у іншу форму.
додано Автор supercat, джерело
@leftaround я хотів зберегти оригінальну функцію. Особисто я хотів би використовувати функцію "IsValueInRange" над "IsSumInRange". Про перейменування a та b на number1 та number2 це тому, що "a" не говорить вам що-небудь про те, що це ціле число.
додано Автор xirt, джерело
@philipxy і тому ви ніколи не повинні копіювати код з stackexchange. Це - доказ концепції. Насправді я не можу згадати, що коли-небудь бачив код на стеку, який можна використовувати у виробництві. Перевірка діапазону, захист від переповнення, правильна обробка виключень, ніколи не існує. І це переможе мету відповіді на запитання.
додано Автор xirt, джерело
Перша функція може переповнюватися. (Як і код інших відповідей.) Хоча складність коду без переповнення є аргументом для введення його у функцію.
додано Автор philipxy, джерело
Це. (Вищезазначені коментарі вище, що були подібні до читань). 30 років тому, коли ми працювали з машинами, які мали менше 1 Мб оперативної пам'яті, потрібна була стискаюча продуктивність - так само, як і проблема y2k, отримайте кілька сотень тисяч записів, кожен з яких має декілька байтів пам'яті, що втрачаються через невикористані вари і посилання, і т.д., і це додає швидко, коли у вас є тільки 256k оперативної пам'яті. Тепер, коли ми маємо справу з машинами, які мають декілька гігабайт оперативної пам'яті, економія навіть декількох МБ використання оперативної пам'яті чи читабельність і доступність коду не є гарною торгівлею.
додано Автор dreadiscool, джерело

Коротше кажучи, я не думаю, що це питання має велике значення в поточних обчислень, але з історичної точки зору це цікава думка.

Ваш інтерв'юер, швидше за все, є прихильником Міфічного місяця людини. У книзі Фред Брукс вважає, що програмістам, як правило, потрібні дві версії ключових функцій у своїй панелі інструментів: оптимізована пам'ять і версія, оптимізована для процесора. Фред базував це на своєму досвіді, що веде розробку операційної системи IBM System/360, де машини можуть мати лише 8 кілобайт оперативної пам'яті. У таких машинах, пам'ять, необхідна для локальних змінних у функціях, потенційно може бути важливою, особливо якщо компілятор не ефективно оптимізував їх (або якщо код був написаний безпосередньо на асемблері).

У нинішній епосі, я думаю, вам буде важко знайти систему, де наявність або відсутність локальної змінної в методі зробить помітну різницю. Для змінної значення має бути рекурсивний з очікуваною глибокою рекурсією. Навіть тоді, ймовірно, що глибина стека буде перевищена, викликаючи виключення переповнення стека, перш ніж сама змінна викликала проблему. Єдиним реальним сценарієм, де це може бути проблема, є дуже великі масиви, виділені на стеку в рекурсивному методі. Але це також малоймовірно, оскільки я думаю, що більшість розробників двічі подумають про непотрібні копії великих масивів.

6
додано

Після призначення s = a + b; змінні a та b більше не використовуються. Таким чином, пам'ять не використовується для s, якщо ви не використовуєте компілятор, повністю пошкоджений мозок; пам'ять, яка використовувалася в будь-якому випадку для a і b, повторно використовувалася.

Але оптимізація цієї функції є повною нісенітницею. Якщо ви могли б заощадити простір, то воно може бути 8 байт, поки функція буде запущена (яка відновлюється, коли функція повертається), тому абсолютно безглуздо. Якщо б ви могли заощадити час, це були б окремі числа наносекунд. Оптимізація цього є повним витрачанням часу.

4
додано

Локальні змінні типу значення виділяються на стеку або (більш ймовірно для таких невеликих частин коду) використовуються регістри в процесорі і ніколи не можуть бачити будь-яку оперативну пам'ять. У будь-якому випадку вони недовговічні і нічого не турбують. Ви починаєте розглядати використання пам'яті, коли вам потрібно буферизувати або зберігати елементи даних в колекціях, які є потенційно великими і довгоживучими.

Тоді це залежить від того, що ви найбільше дбаєте про свою програму. Швидкість обробки? Час реакції? Слід пам'яті? Технічна придатність? Консистенція в дизайні? Все залежить від вас.

3
додано
@jrh Локальні змінні на стеку або купі можуть бути деталізацією реалізації, але якщо хтось дійсно хотів змінну в стеку, є stackalloc і тепер Span. Можливо корисний в гарячій точці, після профілювання. Крім того, деякі документи, що стосуються структур, означають, що типи значень можуть бути в стеку, тоді як типи посилання не будуть . У всякому разі, у кращому випадку ви можете уникнути трохи GC.
додано Автор Wesley, джерело
Nitpicking:. NET принаймні (мова повідомлення не вказано) не дає ніяких гарантій про локальні змінні, що виділяються "на стеку". Див. "стек є деталізацією реалізації" Еріка Ліпперта.
додано Автор jrh, джерело

Як кажуть інші відповіді, потрібно подумати, для чого ви оптимізуєте.

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

Вона впливає на читабельність коду. (Кодекс для людей, щоб читати, а не тільки комп'ютери.) Існує не дуже велика різниця між цими двома прикладами; коли всі інші речі рівні, я вважаю, що короткочасність - це чеснота, тому я, напевно, вибираю метод B. Але всі інші речі рідко рівні, і в більш складному випадку в реальному світі це може мати великий ефект.

Речі, які слід враховувати:

  • Чи має проміжний вираз будь-які побічні ефекти? Якщо він викликає будь-які нечисті функції або оновлює будь-які змінні, то, звичайно, дублювання буде справою правильності, а не просто стилю.
  • Наскільки складним є проміжний вираз? Якщо він робить багато обчислень і/або функцій викликів, то компілятор може не бути в змозі оптимізувати його, і це вплине на продуктивність. (Хоча, як сказав Кнут : "Ми повинні забудьте про малу ефективність, скажімо, про 97% часу ».)
  • Чи має проміжна змінна значення ? Чи можна назвати ім'я, яке допомагає пояснити, що відбувається? Коротке, але інформативне ім'я може краще пояснити код, а безглуздий - лише візуальний шум.
  • Як довго існує проміжний вираз? Якщо довго, то дублювання може зробити код довшим і важче прочитати (особливо якщо він змушує перерву рядка); якщо ні, то копіювання може бути коротшим.
2
додано

Як зазначалося у багатьох відповідях, спроба налаштувати цю функцію з сучасними компіляторами не матиме ніякого значення. Оптимізатор, швидше за все, зможе розібратися з найкращим рішенням (голос до відповіді, що показав ассемблерний код, щоб довести це!). Ви заявили, що код в інтерв'ю не був точно кодом, який вам було запропоновано порівняти, так що, можливо, фактичний приклад трохи більше сенсу.

Але давайте ще раз подивимося на це питання: це питання інтерв'ю. Отже, справжня проблема полягає в тому, як ви повинні відповісти на це питання, вважаючи, що ви хочете спробувати отримати роботу?

Давайте також припустимо, що інтерв'юер знає, про що вони говорять, і вони просто намагаються побачити, що ви знаєте.

Я хотів би зазначити, що, не звертаючи уваги на оптимізатор, перший може створити тимчасову змінну на стеку, тоді як другий не буде, але буде виконувати обчислення двічі. Тому перше використовує більше пам'яті, але швидше.

Можна згадати, що розрахунок може вимагати тимчасової змінної для збереження результату (так, щоб він порівнювався), так чи можна назвати цю змінну чи ні, це не має ніякого значення.

Я б тоді згадав, що насправді код буде оптимізований і, швидше за все, еквівалентний машинний код буде створений, оскільки всі змінні локальні. Однак, це залежить від того, який компілятор ви використовуєте (це було не так давно, що я міг би отримати корисне підвищення продуктивності, оголосивши локальну змінну як "final" на Java).

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

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

Все це свідчить про те, що ви знаєте, про що ви говорите.

Я б залишив це до кінця, щоб сказати, що краще зосередитися на читабельності. Хоча в даному випадку це правда, в контексті інтерв'ю це може бути витлумачено як "Я не знаю про продуктивність, але мій код читається як історія Джанет і Джона .

Те, що ви не повинні робити, - це те, що звичайні висловлювання про те, як оптимізація коду не потрібна, не оптимізувати, поки ви не профiлювали код (це просто вказує на те, що ви не бачите поганого коду для себе), а апаратна частина коштує менше, ніж програмісти і, будь ласка, не процитуйте Кнута "передчасна бла-бла ...".

Продуктивність коду є справжньою проблемою в багатьох організаціях, і багатьом організаціям потрібні програмісти, які її розуміють.

Зокрема, з такими організаціями, як Amazon, деякі коди мають величезні важелі. Фрагмент коду може бути розгорнутий на тисячах серверів або мільйонах пристроїв і може називатися мільярдами разів на день кожен день року. Можуть бути тисячі подібних фрагментів. Різниця між поганим алгоритмом і хорошим алгоритмом може бути легким у тисячу разів. Зробіть цифри і множини все це: це робить різницю. Потенційні витрати на організацію непрацездатного коду можуть бути дуже значними або навіть смертельними, якщо система втрачає потенціал.

Більше того, багато хто з цих організацій працюють у конкурентному середовищі. Таким чином, ви не можете просто сказати вашим клієнтам, щоб купити більший комп'ютер, якщо програмне забезпечення вашого конкурента вже працює добре на апаратному забезпеченні, яке вони мають, або якщо програмне забезпечення працює на мобільному телефоні і не може бути оновлено. Деякі програми є особливо критичними (ігри та мобільні програми приходять на розум) і можуть жити або вмирати відповідно до їхньої швидкості або швидкості.

Я особисто протягом двох десятиліть працював над багатьма проектами, де системи не вийшли з ладу або були непридатні через проблеми з продуктивністю. вплив того, що вони писали. Більше того, він ніколи не є одним кодом, він завжди скрізь. Коли я з'являюся, це пізно, щоб почати думати про продуктивність: шкода була зроблена.

Розуміння продуктивності коду - це хороша уміння мати такий самий спосіб, як розуміння правильності коду та стилю коду. Це виходить з практики. Порушення продуктивності можуть бути настільки ж поганими, як і функціональні збої. Якщо система не працює, вона не працює. Неважливо, чому. Аналогічно, продуктивність та функції, які ніколи не використовуються, є поганими.

Отже, якщо інтерв'юер запитає вас про продуктивність, я рекомендую спробувати і продемонструвати якомога більше знань. Якщо це питання здається поганим, ввічливо вкажіть, чому ви вважаєте, що в цьому випадку це не буде проблемою. Не цитуйте Кнута.

1
додано

Спочатку потрібно оптимізувати правильність.

Ваша функція виходить з ладу для вхідних значень, близьких до Int.MaxValue:

int a = int.MaxValue - 200;
int b = int.MaxValue - 200;
bool inRange = test.IsSumInRangeA(a, b);

Це повертає true, оскільки сума переповнюється до -400. Функція також не працює для a = int.MinValue + 200. (неправильно додає до "400")

Ми не будемо знати, що шукав інтерв'юер, якщо він або вона не втрутиться, але «переповнення реальне» .

В ситуації інтерв'ю задайте питання, щоб з'ясувати обсяг проблеми: що таке допустиме максимальне та мінімальне значення вхідного сигналу? Після того, як ви їх отримаєте, ви можете кинути виняток, якщо абонент подає значення за межами діапазону. Або (у C #), ви можете використовувати перевірений {} розділ, який викине виключення на переповнення. Так, це більше роботи і складні, але іноді це те, що потрібно.

0
додано
Я думаю, що питання інтерв'ю спрямоване на продуктивність, тому вам потрібно відповісти на наміри питання. Інтерв'юер не питає про поведінку на межі. Але цікава сторона в будь-якому випадку.
додано Автор Alexander, джерело
@Corey Хороші інтерв'юери, як питання до 1) оцінюють здатність кандидата щодо питання, як це запропонував rghome тут ще 2) як відкриття до більших питань (наприклад, невисловленої функціональної коректності) і глибини відповідних знань - це тим більше в подальших кар'єрних інтерв'ю - удачі.
додано Автор chux, джерело
Методи були лише прикладами. Вони не були написані, щоб бути правильними, але щоб проілюструвати фактичне питання. Дякуємо за вхід, хоча!
додано Автор user1476849, джерело

Коли оптимізувати пам'ять у порівнянні зі швидкістю продуктивності для методу?

Після отримання функціональних можливостей спочатку спочатку . Потім вибірковість стосується мікро оптимізації.


Як питання інтерв'ю щодо оптимізації, код спровокує звичайну дискусію, але пропускає мету вищого рівня Чи правильно код кодний?

І C ++, і C, і інші вважають переповнення int проблемою від a + b . Це не дуже добре визначено, і C викликає його невизначене поведінка . Вона не вказується на "обтікання" - навіть якщо це поширена поведінка.

bool IsSumInRange(int a, int b) {
    int s = a + b; //Overflow possible
    if (s > 1000 || s < -1000) return false;
    else return true;
}

Таку функцію, яка називається IsSumInRange() , слід очікувати, що вона буде добре визначена і правильно виконуватиме всі значення int a, b . Сировина a + b не є такою. Рішення C можна використовувати:

#define N 1000
bool IsSumInRange_FullRange(int a, int b) {
  if (a >= 0) {
    if (b > INT_MAX - a) return false;
  } else {
    if (b < INT_MIN - a) return false;
  }
  int sum = a + b;
  if (sum > N || sum < -N) return false;
  else return true;
}

The above code could be optimized by using a wider integer type than int, if available, as below or distributing the sum > N, sum < -N tests within the if (a >= 0) logic. Yet such optimizations may not truly lead to "faster" emitted code given a smart compiler nor be worth the extra maintenance of being clever.

  long long sum a;
  sum += b;

Навіть за допомогою abs (sum) схильні до проблем, коли sum == INT_MIN .

0
додано

Ваше запитання повинно було бути: "Чи потрібно взагалі оптимізувати це?".

Версії A і B відрізняються однією важливою деталлю, що робить A кращим, але не пов'язаний з оптимізацією: Ви не повторюєте код.

Фактична "оптимізація" називається загальним усуненням підекспресії, що робить кожен компілятор. Деякі виконують цю основну оптимізацію, навіть коли оптимізацію вимкнено. Так що це не дійсно оптимізація (згенерований код майже напевно буде точно таким же в кожному випадку).

Але якщо це не є оптимізацією, то чому воно краще? Добре, ви не повторюєте коду, кого це хвилює!

Перш за все, ви не маєте ризику випадково отримати половину умовного пункту неправильно. Але що більш важливо, хтось читає цей код може grok негайно , що ви намагаєтеся зробити, а не if ((((wtf || це || ) . Те, що читач бачить, є if (один | інший) , що добре. Не рідко, я буваю, що ви це інша людина, що читає ваш власний код через три роки, і думаючи, що "WTF це означає?". У цьому випадку завжди корисно, якщо ваш код негайно повідомляє, яким був намір. З належною назвою назви спільної експресії Крім того, якщо в майбутньому ви вирішите, що, наприклад, потрібно змінити a + b на a-b , потрібно змінити одне місце розташування, а не два. І немає ніякого ризику, що (знову) випадково вийде другий.

Що стосується вашого фактичного питання, для чого ви повинні оптимізувати, перш за все, ваш код має бути правильним . Це абсолютно головне. Код, який не є правильним, є поганим кодом, навіть якщо він, незважаючи на неправильність, працює нормально, або, принаймні, виглядає , він працює нормально. Після цього код повинен бути читабельний (читати його може хтось незнайомий).
Що стосується оптимізації, то, звичайно, не варто навмисно писати антиоптимізований код, і, звичайно, я не кажу, що ви не повинні витрачати думки про дизайн перед початком роботи (наприклад, вибір правильного алгоритму для проблеми, не найменш ефективний).

Але для більшості додатків, більшість часу продуктивність, яку ви отримуєте після запуску правильного, читаного коду з використанням розумного алгоритму через оптимізуючий компілятор, просто прекрасна, немає ніякої реальної необхідності хвилюватися.

Якщо це не так, наприклад, якщо продуктивність програми дійсно не відповідає вимогам, і лише потім , ви повинні турбуватися про виконання таких локальних оптимізацій, як це було зроблено. Але бажано переглядати алгоритм верхнього рівня. Якщо ви називаєте функцію 500 разів замість 50 000 разів через кращий алгоритм, це має більший вплив, ніж збереження трьох тактових циклів на мікрооптимізацію. Якщо ви не затягуєтеся на кілька сотень циклів у випадковому доступі до пам'яті весь час, це має більший вплив, ніж робити кілька дешевих розрахунків додатково, і т.д.

Оптимізація є складною справою (про це можна писати цілі книги і не закінчуватися), а витрачати час на сліпому оптимізації певного місця (навіть не знаючи, чи це вузьке місце взагалі!) Зазвичай витрачається час. Без профілювання, оптимізація дуже важко отримати правильно.

Але, як правило, коли ви летите сліпим і вам просто потрібно/хочете щось зробити чи чи загальну стратегію за замовчуванням, я пропоную оптимізувати для "пам'яті".
Оптимізація для "пам'яті" (зокрема, просторової локалізації та шаблонів доступу) зазвичай дає користь, тому що на відміну від колись, коли все було "те ж саме", в даний час доступ до оперативної пам'яті є одним з найдорожчих речей (за винятком читання з диска!) що ви можете в принципі зробити. В той час, як ALU, з іншого боку, є дешевий та отримуючий більш швидкий кожний тиждень. Пропускна здатність пам'яті та затримка не покращуються майже так само швидко. Хороша локалізація та хороші шаблони доступу можуть легко зробити 5x різницю (20x в екстремальних, спотворених прикладах) у середовищі виконання в порівнянні з поганими моделями доступу у важких додатках даних. Будьте ласкаві до своїх кешей, і ви будете щасливою людиною.

Щоб поставити попередній абзац у перспективу, подумайте, які різні речі, які ви можете зробити, коштують вам. Виконання щось подібне a + b приймає (якщо не оптимізовано) один або два цикли, але процесор зазвичай може запускати кілька інструкцій за цикл, і може конвеєрацію незалежних інструкцій так реально коштувати щось близько половини циклу або менше. В ідеалі, якщо компілятор хороший у плануванні, і в залежності від ситуації, він може коштувати нуль.
Вибірка даних ("пам'ять") коштує вам 4-5 циклів, якщо вам пощастить, і це в L1, і близько 15 циклів, якщо вам не пощастило (L2 хіт). Якщо дані взагалі не знаходяться в кеші, потрібно кілька сотень циклів. Якщо ваш хаотичний шаблон доступу перевищує можливості TLB (легко зробити лише з ~ 50 записів), додайте ще кілька сотень циклів. Якщо ваш випадковий зразок доступу насправді призводить до помилки сторінки, то це в кращому випадку обійдеться вам у десять тисяч циклів, а найгірше - кілька мільйонів. Тепер подумайте про те, що саме ви хочете уникнути?

0
додано