проверка, имеет ли std :: vector нулевой размер

Question

в vs2010 std :: vector.size ():

return (this->_Mylast - this->_Myfirst);

и std :: vector.empty ():

return (this->_Myfirst == this->_Mylast);

Мой вопрос: есть ли скорость?отличается между этими двумя функциями, если вы собираетесь проверить, если вектор имеет нулевые элементы.Минус и равно - это почти одинаковые бинарные операции, так что скорость для обеих этих функций одинакова?

Answer 1

Если вы не делаете это и миллионы раз в секунду (и серьезно, почему будет вас?), Это не будет иметь никакого значения.

Если вам действительно интересно, проверьте это. Установите цикл в несколько миллионов раз и посмотрите, сколько времени займет каждый.

Я думаю, вы обнаружите, что разница незначительна.

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

И, в любом случае, оптимизация для удобочитаемости является допустимым подходом, и я обычно использую его, если нет серьезных узких мест в производительности. Другими словами, используйте empty() или !empty(), если вы делаете что-то, основываясь на том, пусто оно или нет. Любая другая проверка размера (например, если в ней хотя бы двенадцать элементов) должна использовать size() (очевидно).

В качестве примера того, насколько бесполезными могут быть некоторые микрооптимизации, рассмотрим код на C:

#include <stdio.h>

int main(void) {
    int i, j, k, diff;
    for (i = 0; i < 1000; i++)
        for (j = 0; j < 1000000; j++)
            //diff = (i == j);
            diff = (i - j);
    return 0;
}

Когда я компилирую это с оптимизацией по умолчанию ^(a) и запускаю его с помощью команды time, я получаю время ЦП (более пяти запусков) с одной из этих строк без комментариев:

diff = (i - j)     diff = (i == j)
==============     ===============
         2.488              2.216
         2.424              2.220
         2.452              2.224
         2.484              2.152
         2.464              2.152
         =====              =====
Avrgs:   2.463              2.193

Теперь этот первый вариант медленнее на 12%, но есть одна вещь, которую вам нужно понять. Несмотря на то, что он медленнее, это заняло всего две секунды, миллиардов раз. Если вы делаете это один раз, разница между 0,000000002463 секундами и 0,000000002193 секундами, не стоит усилий по оптимизации.

Выбирай свои сражения, нацеливайся на оптимизацию. Вы можете получить значительное улучшение скорости с помощью стратегий макро-оптимизации.

---

^(a) При gcc "безумном" уровне оптимизации -O3 они оба занимают 0,000 секунд (иногда 0,004, но редко - насколько я понимаю, есть ограничение на разрешение time команда), делая разницу еще более неактуальной: -)

Answer 2

Существует две причины использования empty() сверх size() для проверки пустоты вектора:

• std::vector.empty() может быть быстрее , чем std::vector.size(), в зависимости от реализаций.

• Использование empty() для проверки пустоты вектора более интуитивно понятно и читабельно, чем использование size().

---

Справка:
Николая М. Иосутиля:
Стандартная библиотека C ++: учебное пособие и справочник

который гласит:

size()
Возвращает фактическое количество элементов контейнера.

empty()
Это ярлык для проверки, равно ли число элементов нулю (size()==0). Тем не менее, empty() может быть реализовано более эффективно, поэтому вы должны использовать его, если возможно.

---

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

Answer 3

Для вектора производительность, вероятно, такая же.Даже если это не то же самое, оно имеет ту же сложность Big O, и разница в скорости незначительна.Так что, вероятно, удобнее использовать empty, если вы хотите проверить, что вектор пуст.Он более точно описывает, что вы действительно хотите сделать.

Другая причина использования empty заключается в том, что при последующем изменении контейнера на list он может иметь большую сложность Big O.Потому что есть некоторые реализации std::list, в которых size имеет линейную сложность, а пустое всегда равно O (1).

Answer 4

Скотт Мейерс из "Effective STL" рекомендует звонить empty() вместо проверки размера для всех контейнеров.Причина, которую он приводит, состоит в том, что empty является постоянным временем для всех стандартных контейнеров, тогда как size требует линейного времени в некоторых реализациях списка.

Если вы используете размер и вам случится сменить контейнер позже, может возникнуть проблема с производительностью.

Таким образом, если проверка на отсутствие элементов в контейнере не является реальным узким местом (сначала измерьте, оптимизируйте)если есть проблема), используйте empty.

Answer 5

Давайте остановим фабуляции здесь:

bool empty_by_difference(int* b, int* e) {
  return (e - b) == 0;
}

bool empty_by_equality(int* b, int* e) {
  return e == b;
}

Скомпилировано Clang 3.0 в следующий IR:

define zeroext i1 @_Z19empty_by_differencePiS_(i32* %b, i32* %e) nounwind uwtable readnone {
  %1 = icmp eq i32* %e, %b
  ret i1 %1
}

define zeroext i1 @_Z17empty_by_equalityPiS_(i32* %b, i32* %e) nounwind uwtable readnone {
  %1 = icmp eq i32* %e, %b
  ret i1 %1
}

Возможно, вы не знаете представление IR, но все же я думаю, что это ударит по дому.

Итак, позвольте мне предположить, что эталон - это просто потеря моего и вашего времени.

---

Теперь, с семантической точки зренияВообще-то, мне лично удобнее читать if (x.empty()), чем читать if (x.size() == 0).

В последнем случае:

• мои глаза должны работать больше: различать ==с != или <= или >=, ...
• мой мозг должен работать больше: запоминание чем 0 является своего рода дозорным значением, очень отличающимся от любого другого значения, такого как 1 и т.д ...

Answer 6

Если есть разница между пустым и размером, он настолько мал, что даже эталон не увидит его. Так как размер для списка, начинающегося с C ++ 11, равен O (1), я думаю, что его удобнее записывать, а не пустой. Но это только мое мнение:)

Answer 7

Не должно быть разницы в скорости. На самом деле вы должны увидеть один и тот же код, сгенерированный для обоих случаев. Компилятор должен иметь возможность выполнять следующие преобразования:

if (vec.size() == 0)
// After inlining:
if (_Mylast - _Myfirst == 0)
// Equivalent to:
if (_Mylast == _Myfirst) // Which is the same as empty() after it is inlined

Answer 8

Минус и равно почти одинаковые двоичные операции справа

Действительно, почти то же самое. Но логические операторы AFAIK работают быстрее, чем другие операторы.