Я выполнял некоторые проблемы LeetCode, и я замечаю, что решения C в два раза быстрее, чем те же самые вещь в С++. Например:
Обновлено с помощью нескольких простых примеров:
Учитывая отсортированный массив и целевое значение, верните индекс, если цель найдена. Если нет, верните индекс, где он был бы, если бы он был вставлен по порядку. Вы не можете принимать дубликаты в массиве. (Ссылка на вопрос о LeetCode)
Мое решение в C работает в 3 ms:
int searchInsert(int A[], int n, int target) {
int left = 0;
int right = n;
int mid = 0;
while (left<right) {
mid = (left + right) / 2;
if (A[mid]<target) {
left = mid + 1;
}
else if (A[mid]>target) {
right = mid;
}
else {
return mid;
}
}
return left;
}
Мое другое решение на С++, точно такое же, но как функция-член класса Solution, запускается в 13 ms:
class Solution {
public:
int searchInsert(int A[], int n, int target) {
int left = 0;
int right = n;
int mid = 0;
while (left<right) {
mid = (left + right) / 2;
if (A[mid]<target) {
left = mid + 1;
}
else if (A[mid]>target) {
right = mid;
}
else {
return mid;
}
}
return left;
}
};
Даже более простой пример:
Обозначьте цифры целого числа. Возвращает 0, если результат будет переполняться. (Ссылка на вопрос о LeetCode)
Версия C работает в формате 6 ms:
int reverse(int x) {
long rev = x % 10;
x /= 10;
while (x != 0) {
rev *= 10L;
rev += x % 10;
x /= 10;
if (rev>(-1U >> 1) || rev < (1 << 31)) {
return 0;
}
}
return rev;
}
И версия С++ точно такая же, как и функция-член класса Solution, и работает для 19 ms:
class Solution {
public:
int reverse(int x) {
long rev = x % 10;
x /= 10;
while (x != 0) {
rev *= 10L;
rev += x % 10;
x /= 10;
if (rev>(-1U >> 1) || rev < (1 << 31)) {
return 0;
}
}
return rev;
}
};
Я вижу, как будут значительные накладные расходы от использования вектора вектора в качестве 2D-массива в исходном примере, если система тестирования LeetCode не компилирует код с включенной оптимизацией. Но более простые примеры выше не должны страдать от этой проблемы, потому что структуры данных довольно сырые, особенно во втором случае, когда все, что у вас есть, - это длинная или целая арифметика. Это еще медленнее в три раза.
Я начинаю думать, что может произойти что-то странное с тем, как LeetCode делает бенчмаркинг вообще, потому что даже в C-версии целочисленной проблемы с обращением вы получаете огромный бамп в процессе работы от просто замены строки if (rev > (- 1U → 1) || rev < (1 < 31)) { с if (rev > INT_MAX || rev < INT_MIN) {
Теперь я полагаю, что иметь значение #include<limits.h> может иметь какое-то отношение к этому, но кажется немного экстремальным, что это простое изменение приводит к сокращению времени выполнения всего от 6 ms до 19 ms.
