Допустим, вам нужно выяснить, делится ли положительное целое число K на число от 100 000 до 150 000, и это настолько редкая операция, что выполнение предварительных вычислений просто не стоит процессорного времени или памяти б.
Если K <100 000, то оно не может быть кратно числу от 100 000 до 150 000. </p>
Если 100 000 ≤ K ≤ 150 000, оно делится само по себе. Вам решать, будет ли это иметь значение.
Чтобы K > 150 000 делилось на M , при 100 000 ≤ M ≤ 150 000, K также должно делиться L = K / M . Это потому, что K = L × M , и все три являются натуральными числами. Таким образом, вам нужно только проверить делимость K на набор L , где ⌊ K / 150000 ⌋ ≤ L ≤ 10 K / 100 000 ⌋.
Однако этот набор L с становится больше, чем набор возможных M с, когда K> = 15 000 000 000. Тогда опять же меньше работы, чтобы просто проверить K на делимость на каждый M , так же, как сейчас код OP.
При реализации этого в качестве программы самое важное на практике, к удивлению, это добавляемые вами комментарии. Не пишите комментарии, которые описывают, что делает код; напишите комментарии, которые объясняют модель или алгоритм, который вы пытаетесь реализовать (скажем, на уровне функций), и ваше намерение того, что должен выполнить каждый небольшой блок кода.
В этом конкретном случае вам, вероятно, следует добавить комментарий к каждому предложению if, поясняющий ваши рассуждения, так же, как я это делал выше.
Начинающие программисты часто опускают комментарии полностью. К сожалению, потому что писать хорошие комментарии - сложная привычка. Это определенно хорошая идея, чтобы научиться комментировать свой код (как я описал выше - комментарии, которые описывают то, что делает код, менее чем полезны; больше шума, чем помогать), и продолжать оттачивать свое мастерство на этом.
Программист, чей код обслуживаем, стоит десяти гениев, которые создают код только для записи. Это потому, что во всем коде есть ошибки, потому что люди делают ошибки. Чтобы быть эффективным разработчиком, ваш код должен быть поддерживаемым. В противном случае вы будете вынуждены переписывать каждую ошибочную часть с нуля, тратя впустую много времени. И, как вы можете видеть выше, «оптимизация» на алгоритмическом уровне, то есть размышление о о том, как избежать необходимости выполнять работу , дает гораздо лучшие результаты, чем попытка оптимизировать ваши циклы или что-то в этом роде. (В реальной жизни вы обнаружите, что на удивление часто, правильно оптимизируя цикл, он полностью удаляется.)
Даже в упражнениях правильные комментарии могут быть разницей между "нет баллов, это не работает" и "хорошо, я частично дам вам кредит, потому что вы в строке N была опечатка, ошибка, но в противном случае ваше решение сработало бы ".
Поскольку bolov не понимает, как вышеприведенное приводит к функции "naive_with_checks", я покажу, как она реализована здесь.
Для удобства тестирования я покажу полную программу тестирования. В качестве параметров программы укажите диапазон целых чисел и диапазон принятых делителей (т. Е. thisprogram 1 500000 100000 150000 для дублирования тестов Болова).
#include <stdlib.h>
#include <inttypes.h>
#include <limits.h>
#include <locale.h>
#include <ctype.h>
#include <stdio.h>
#include <errno.h>
int is_divisible(const uint64_t number,
const uint64_t minimum_divisor,
const uint64_t maximum_divisor)
{
uint64_t divisor, minimum_result, maximum_result, result;
if (number < minimum_divisor) {
return 0;
}
if (number <= maximum_divisor) {
/* Number itself is a valid divisor. */
return 1;
}
minimum_result = number / maximum_divisor;
if (minimum_result < 2) {
minimum_result = 2;
}
maximum_result = number / minimum_divisor;
if (maximum_result < minimum_result) {
maximum_result = minimum_result;
}
if (maximum_result - minimum_result > maximum_divisor - minimum_divisor) {
/* The number is so large that it is the least amount of work
to check each possible divisor. */
for (divisor = minimum_divisor; divisor <= maximum_divisor; divisor++) {
if (number % divisor == 0) {
return 1;
}
}
return 0;
} else {
/* There are fewer possible results than divisors,
so we check the results instead. */
for (result = minimum_result; result <= maximum_result; result++) {
if (number % result == 0) {
divisor = number / result;
if (divisor >= minimum_divisor && divisor <= maximum_divisor) {
return 1;
}
}
}
return 0;
}
}
int parse_u64(const char *s, uint64_t *to)
{
unsigned long long value;
const char *end;
/* Empty strings are not valid. */
if (s == NULL || *s == '\0')
return -1;
/* Parse as unsigned long long. */
end = s;
errno = 0;
value = strtoull(s, (char **)(&end), 0);
if (errno == ERANGE)
return -1;
if (end == s)
return -1;
/* Overflow? */
if (value > UINT64_MAX)
return -1;
/* Skip trailing whitespace. */
while (isspace((unsigned char)(*end)))
end++;
/* If the string does not end here, it has garbage in it. */
if (*end != '\0')
return -1;
if (to)
*to = (uint64_t)value;
return 0;
}
int main(int argc, char *argv[])
{
uint64_t kmin, kmax, dmin, dmax, k, count;
if (argc != 5) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help | help ]\n", argv[0]);
fprintf(stderr, " %s MIN MAX MIN_DIVISOR MAX_DIVISOR\n", argv[0]);
fprintf(stderr, "\n");
fprintf(stderr, "This program counts which positive integers between MIN and MAX,\n");
fprintf(stderr, "inclusive, are divisible by MIN_DIVISOR to MAX_DIVISOR, inclusive.\n");
fprintf(stderr, "\n");
return EXIT_SUCCESS;
}
/* Use current locale. This may change which codes isspace() considers whitespace. */
if (setlocale(LC_ALL, "") == NULL)
fprintf(stderr, "Warning: Your C library does not support your current locale.\n");
if (parse_u64(argv[1], &kmin) || kmin < 1) {
fprintf(stderr, "%s: Invalid minimum positive integer to test.\n", argv[1]);
return EXIT_FAILURE;
}
if (parse_u64(argv[2], &kmax) || kmax < kmin || kmax >= UINT64_MAX) {
fprintf(stderr, "%s: Invalid maximum positive integer to test.\n", argv[2]);
return EXIT_FAILURE;
}
if (parse_u64(argv[3], &dmin) || dmin < 2) {
fprintf(stderr, "%s: Invalid minimum divisor to test for.\n", argv[3]);
return EXIT_FAILURE;
}
if (parse_u64(argv[4], &dmax) || dmax < dmin) {
fprintf(stderr, "%s: Invalid maximum divisor to test for.\n", argv[4]);
return EXIT_FAILURE;
}
count = 0;
for (k = kmin; k <= kmax; k++)
count += is_divisible(k, dmin, dmax);
printf("%" PRIu64 "\n", count);
return EXIT_SUCCESS;
}
Полезно отметить, что вышеприведенный тест Болова, т. Е. thisprogram 1 500000 100000 150000, занимает всего около 15 мс времени настенных часов (13 мс времени процессора), в среднем, на более медленном процессоре Core i5-7200U. Для действительно больших чисел, например от 280 000 000 000 до 280 000 010 000, тест выполняет максимальный объем работы и занимает около 3,5 секунд на 10 000 номеров на этом компьютере.
Другими словами, я бы не поверил, что числа Болова имеют какое-либо отношение к временам для правильно написанных тестовых случаев.
важноотметить, что для любого K от 1 до 500 000, того же теста, который Болов говорит, что их код измеряет, приведенный выше код выполняет не более двух тестов делимости, чтобы найти, если K делится на целое число от 100 000 до 150 000.
Следовательно, это решение весьма эффективно. Это определенно приемлемо и почти оптимально, когда проверенные значения K относительно малы (скажем, 32-разрядные целые числа без знака или меньше) или когда нельзя использовать предварительно вычисленные таблицы.
Даже если можно использовать предварительно вычисленные таблицы, неясно, станет ли / когда простое разложение быстрее, чем прямые проверки. Несомненно, существует компромисс в размере и содержании предварительно вычисленных таблиц. Болов утверждает, что он явно превосходит другие методы, но не реализовал надлежащий «наивный» тест делимости, как показано выше, и основывает свое мнение на экспериментах с довольно маленькими целыми числами (от 1 до 500 000), которые имеют простые простые разложения.
Например, таблица целых чисел от 1 до 500 000, предварительно проверенная на делимость, занимает всего 62500 байт (43750 байт для 150 000 - 500 000). С этой таблицей каждый тест занимает небольшое почти постоянное время (которое зависит только от эффектов памяти и кэша). Расширение его на все 32-разрядные целые числа без знака потребовало бы 512 ГиБ (536 870 912 байт); таблица может храниться в отображаемом в памяти файле, доступном только для чтения, чтобы позволить ядру ОС в любое время управлять тем, сколько из него отображается в ОЗУ.
Сама первичная декомпозиция, особенно с использованием пробного деления, становится дороже, чем наивный подход, когда число пробных делений превышает диапазон возможных делителей (50 000 делителей в данном конкретном случае). Поскольку между 1 и 150 000 имеется 13848 простых чисел (если считать 1 и 2 простыми числами), число пробных делений может легко приблизиться к числу делителей для достаточно больших входных значений.
Для чисел со многими простыми факторами комбинаторная фаза, нахождение того, умножается ли любое подмножество простых факторов на число между 100 000 и 150 000, еще более проблематично. Количество возможных комбинаций растет быстрее, чем в геометрической прогрессии. Без тщательных проверок одна только эта фаза может выполнить намного больше работы на большое количество входных данных, чем просто пробное деление с каждым возможным делителем.
(Например, если у вас есть 16 различных простых факторов, у вас уже есть 65 535 различных комбинаций; это больше, чем количество прямых пробных делений. Однако все такие числа больше, чем 64-битные; наименьшее - 2 · 3 · 5 · 7 · 11 · 13 · 17 · 19 · 23 · 29 · 31 · 37 · 41 · 43 · 47 · 53 = 32 589 158 477 190 044 730, что является 65-разрядным числом.)
Существует также проблема сложности кода. Чем сложнее код, тем сложнее его отладить и поддерживать.