Просматривая недавно соцсети, я наткнулся на этот скриншот. Разумеется, его сопровождало множество злобных комментариев, критикующих попытку этого новичка в программировании решить классическую задачу computer science: операцию деления с остатком.
В современном мире, где ИИ постепенно заменяет программистов, отнимая у них работу и совершая переворот в том, как мы подходим к рассуждениям о коде, нам, возможно, следует быть более открытыми к мыслям людей, недавно пришедших в нашу отрасль? На самом деле, показанный выше код — идеальный пример компромисса между временем и задействованной памятью. Мы жертвуем временем и в то же время памятью и временем компьютера! Поистине чудесный алгоритм!
Поэтому я решил изучить эту идею проверки чётности числа при помощи одних сравнений, чтобы понять, насколько хорошо она работает в реальных ситуациях. Я сторонник высокопроизводительного кода, поэтому решил реализовать это на языке программирования C, потому что он и сегодня остаётся самым быстрым языком в мире с большим отрывом от других (благодаря гению Денниса Ричи).
Итак, я приступил к кодингу.
/* Copyright 2023. Любое неавторизованное распространение этого исходного кода
будет преследоваться по всей строгости закона */
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main(int argc, char* argv[])
{
uint8_t number = atoi(argv[1]); // Здесь никаких проблем
if (number == 0)
printf("even\n");
if (number == 1)
printf("odd\n");
if (number == 2)
printf("even\n");
if (number == 3)
printf("odd\n");
if (number == 4)
printf("even\n");
if (number == 5)
printf("odd\n");
if (number == 6)
printf("even\n");
if (number == 7)
printf("odd\n");
if (number == 8)
printf("even\n");
if (number == 9)
printf("odd\n");
if (number == 10)
printf("even\n");
}Красота! Давайте скомпилируем код, отключив оптимизации при помощи /Od, чтобы надоедливый компилятор не вмешивался в наш алгоритм. После компиляции мы можем выполнить быстрый тест программы и получить положительные результаты:
PS > cl.exe /Od program.c
PS > .\program.exe 0
even
PS > .\program.exe 4
even
PS > .\program.exe 3
odd
PS > .\program.exe 7
oddОднако при дальнейшем тестировании я обнаружил некоторые проблемы:
PS > .\program.exe 50
PS > .\program.exe 11
PS > .\program.exe 99Программа ничего не выводит! Похоже, она работает только с числами меньше 11! Вернувшись к коду, мы можем найти проблему прямо за последним оператором if — нам нужно больше if!
Конечно, это компромисс между временем и используемой памятью, но моё время в этом мире ограничено, поэтому я решил воспользоваться мета-программированием операторов if при помощи программы-программатора на другом языке программирования. Чтобы компенсировать это жульничество, я решил использовать самый медленный (благодаря гению Росса ван дер Гуссома) язык в мире — Python.
print("/* Copyright 2023. Любое неавторизованное распространение этого исходного кода
print(" будет преследоваться по всей строгости закона */")
print("#include <stdio.h>")
print("#include <stdint.h>")
print("#include <stdlib.h>")
print("int main(int argc, char* argv[])")
print("{")
print(" uint8_t number = atoi(argv[1]); // Здесь никаких проблем")
for i in range(2**8):
print(" if (number == "+str(i)+")")
if i % 2 == 0:
print(" printf(\"even\\n\");")
else:
print(" printf(\"odd\\n\");")
print("}")Отлично! Теперь мы можем сгенерировать программу, решающую задачу чётности для всех 8-битных целых чисел!
PS > python programmer.py > program.c
PS > cl.exe /Od program.c
PS > .\program.exe 99
odd
PS > .\program.exe 50
even
PS > .\program.exe 240
even
PS > .\program.exe 241
oddПосмотрите-ка на это! Работает идеально! Теперь давайте увеличим масштабы до 16 битов!
print(" uint16_t number = atoi(argv[1]); // Здесь никаких проблем")
…
for i in range(2**16):Мы получаем красивый жирный файл .c примерно из 130 тысяч строк. На самом деле, это ничто по сравнению с некоторыми кодовыми базами, с которыми я сталкивался за годы работы. Давайте его скомпилируем!
PS > python programmer.py > program.c
PS > cl.exe /Od program.c
PS > .\program.exe 21000
even
PS > .\program.exe 3475
odd
PS > .\program.exe 3
odd
PS > .\program.exe 65001
odd
PS > .\program.exe 65532
evenКрасота! Похоже, наш алгоритм масштабируется вместе с данными! Исполняемый файл имеет размер примерно 2 МБ, но это ерунда для моей мощной игровой машины с 31,8 ГБ памяти.
Ну, 16 битов — это очень прекрасная битовая ширина, но, как мы знаем, Святой Грааль вычислений — это 32 бита, и это последняя битовая ширина, которой достаточно для решения всех практических инженерных и научных задач. В конце концов, IPv4 чувствует себя как никогда хорошо, хотя его уже шестьдесят лет назад признали устаревшим из-за так называемого «исчерпания адресов».
Так что давайте без лишних церемоний увеличим масштаб до нашего последнего размера. В 32 битах всего в 65536 раз больше чисел, чем в 16 битах, что может пойти не так?
print(" uint32_t number = atoi(argv[1]); // Здесь никаких проблем")
…
for i in range(2**32):Позволим могучей змее выполнить свою работу: выпив кофе и вернувшись к программе спустя 48 часов, я обнаружил красивый файл .c размером почти 330 ГБ! Я практически уверен, что это самый большой файл .c в истории. Когда я вводил следующую команду, мои пальцы дрожали: MSVC наверняка раньше никогда не сталкивался с таким мощным исходным кодом. После активных получасовых издевательств над файлом подкачки моего бедного мощного компьютера я получил следующее:
PS > cl /Od program.c
Microsoft (R) C/C++ Optimizing Compiler Version 19.32.31329 for x64
Copyright (C) Microsoft Corporation. All rights reserved.
program.c
program.c(134397076): warning C4049: compiler limit: terminating line number emission
program.c(134397076): note: Compiler limit for line number is 16777215
program.c(41133672): fatal error C1060: compiler is out of heap spaceЖалкое зрелище!
И нас подвёл не только компилятор: изучив ограничения формата Portable Executable (.exe) для Windows, я обнаружил, что он не может обрабатывать больше, чем жалкие 4 ГБ! Учитывая, что в исполняемом файле должно быть закодировано 4 миллиарда сравнений, это серьёзное препятствие для реализации нашего алгоритма. Даже если каждое сравнение будет использовать меньше одного байта, файл всё равно будет слишком тяжёлым.
Однако плохие компиляторы и форматы файлов не должны мешать нам в стремлении к нашей мечте. В конце концов, компилятор всего лишь записывает машинный код в файл, а формат файлов — это всего лишь некая структура, сообщающая операционной системе, как помещать двоичный код в память. На самом деле, мы и сами можем с этим справиться.
Начнём с написания функции IsEven на языке ассемблера x86-64, потому что это нативный язык моей машины с процессором Intel. Функция выглядит примерно так:
; Аргумент хранится в ECX, возвращаемое значение в EAX
XOR EAX, EAX ; Присваивам eax значение 0 (возвращаемое значение для нечётного числа)
CMP ECX, 0h ; Сравниваем аргумент с 0
JNE 3h ; Пропускаем следующие две команды в случае неравенства
INC EAX ; Если число чётное, задаём возвращаемое значение чётного числа (1)
RET ; Возврат
CMP ECX, 1h ; Сравниваем аргумент с 1
JNE 2 ; Пропускаем следующую команду в случае неравенства
RET ; Возвращаемое значение нечётного числа уже находится в EAX, просто делаем RET
; сюда вставляем следующие 2...2^32-1 сравнений
RET ; Аварийный возвратНе совсем корректный ассемблерный код, но это не особо важно, потому что мы собираемся компилировать его в машинный код вручную.
Как я это сделал? Я вышел в Интернет с таким вопросом. Воспользовался своим опытом написания эмуляторов и хакинга, изучил руководства по архитектуре x86(-64), чтобы найти нужные опкоды и форматы для каждой команды.
… Да нет, шучу, это было бы ужасно. Я просто спросил у ChatGPT правильный опкод для каждой команды; к счастью для нас, она не сгаллюцинировала новые расширения для x86-64.
Теперь нам просто достаточно написать «компилятор» для вывода этого кода. Нужно учесть, что мы будем писать опкоды, которые получили от ИИ непосредственно для команд. Вот, как это выглядит на нашем любимом Python:
import struct
with open('isEven.bin', 'wb') as file:
file.write(b"\x31\xC0") # XOR EAX, EAX
for i in range(2**32):
ib = struct.pack("<I", i) # Кодируем i как 32-битное целое в little endian
file.write(b"\x81\xF9" + ib) # CMP ECX, i
if i%2 == 0:
file.write(b"\x75\x03") # JNE +3
file.write(b"\xFF\xC0") # INC EAX
file.write(b"\xC3") # RET
else:
file.write(b"\x75\x01") # JNE +1
file.write(b"\xC3") # RET
file.write(b"\xC3") # Аварийный RET Хотя мы отошли от изначального поста в TikTok, суть остаётся той же. Мы создали о-о-очень длинный список операторов if для определения чётности любого числа, игнорируя любые арифметические операции, которые могли бы нам помочь.
Мы получаем милый файл на 40 ГБ, содержащий все 4,2 миллиарда сравнений, необходимых для определения чётности любого 32-битного числа! Теперь нам просто нужно написать хост-программу, которая сможет загружать и использовать эти команды. Для повышения производительности (в нашем случае это очень важно) я решил отобразить файл в адресное пространство, а не читать его целиком. Сделав так, мы притворимся, что весь файл уже находится в памяти, и позволим бедной операционной системе разбираться с размещением блоба на 40 ГБ в виртуальной памяти. Отобразив файл с разрешениями READ и EXECUTE, мы можем вызывать код при помощи указателя функции. Это выглядит так:
#include <stdio.h>
#include <Windows.h>
#include <stdint.h>
int main(int argc, char* argv[])
{
uint32_t number = atoi(argv[1]); // Здесь никаких проблем
// Открываем файл с кодом
HANDLE binFile = CreateFileA(
"isEven.bin",
GENERIC_READ | GENERIC_EXECUTE, FILE_SHARE_READ,
NULL,
OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL,
NULL);
// Получаем 64-битный размер файла
LARGE_INTEGER codeSize;
GetFileSizeEx(binFile, &codeSize);
// Создаём отображение файла в памяти
HANDLE mapping = CreateFileMapping(
binFile,
NULL,
PAGE_EXECUTE_READ,
0,
0,
NULL);
// Получаем указатель на код
LPVOID code = MapViewOfFile(
mapping,FILE_MAP_EXECUTE | FILE_MAP_READ,
0,
0,
codeSize.QuadPart);
// Создаём функцию, указывающую на код
int (*isEven)(int) = (int(*)(int))code;
if (isEven(number))
printf("even\n");
else
printf("odd\n");
CloseHandle(binFile);
}Вот и всё! Теперь у нас есть всё необходимое для проверки чётности любого 32-битного числа. Давайте проверим:
PS >.\program.exe 300
even
PS >.\program.exe 0
even
PS >.\program.exe 1000000
even
PS >.\program.exe 100000007
odd
PS >.\program.exe 400000000
even
PS >.\program.exe 400000001
odd
PS >.\program.exe 400000006
even
PS >.\program.exe 4200000000
odd <---- ОШИБКА!Почти! Похоже, у алгоритма есть какие-то проблемы со знаками: любое значение более 2^31 выдаёт произвольные результаты. Печально!
Давайте устраним последний баг.
Оказалось, функция atoi не может работать с чистой беззнаковостью, поэтому ей не удаётся распарсить наши крупные числа. Всё это можно исправить заменой её на strtoul.
uint32_t number = strtoul(argv[1], NULL, 10);// Здесь никаких проблемPS >.\program.exe 4200000000
even
PS >.\program.exe 4200000001
oddСтоит также отметить, что программа на удивление производительна. Для небольших чисел результат возвращается мгновенно, а для больших чисел, близких к 2^32, результат всё равно возвращается примерно за 10 секунд. Учитывая, что компьютеру приходится считывать 40 ГБ с диска, отображать их на физическую память, а затем обрабатывать их CPU без особых шансов на кэширование, это потрясающий результат. Для справки — в моём компьютере установлен Core i5 12600K с 32 ГБ памяти, а файлы хранятся на SSD-диске M.2. При вычислениях я наблюдал пиковую скорость чтения с SSD примерно в 800 МБ/с (что совершенно нелогично, ведь при этом скорость исполнения была бы больше сорока секунд, но компьютеры — это магия, так что кто знает, что там происходит).
И на этом мы закончили! Мы снова доказали, что в Интернете кто-то не прав — не только можно написать полнофункциональную и высокопроизводительную программу в стиле поста в TikTok, но это ещё и очень захватывающе.
Комментарии (140)
red75prim
28.12.2023 09:57+18И ещё это демонстрация того, как легко получить undefined behavior в программе на C. Если запустить программу без параметров, то значение
argv[1]- NULL, а поведениеatoic параметром NULL не определено в стандарте. Если argc равно 0 (впрочем, под Windows этого случится не может), то значениеargv[1]не определено.
MinimumLaw
28.12.2023 09:57+1Даешь повторение эксперимента на Rust! Я бы посмотрел... на итоговую разницу. И результа запуска без параметров.
red75prim
28.12.2023 09:57+7Потенциальные ошибки придётся обрабатывать каким-то образом. Что-то вроде
let number: u32 = args().nth(1) .expect("The program needs an argument") .parse() .expect("The first argument should be a positive number");Ну, а дальше работа с загрузкой и исполнением недоверенного кода, которая не может быть безопасной по определению, так что придётся использовать unsafe.
Большая часть работы тут возложена на OS, так что измеримой разницы в производительности скорее всего не будет.
MinimumLaw
28.12.2023 09:57+1Не пойдет, ибо
if (argc < 2) { printf("Need argument!\n"); return -1; }Но это уже дополнительный код. А интересно именно без него... Особенно если вернуться к вашему верхнему комментарию.
red75prim
28.12.2023 09:57+4Чудес не бывает. Undefined behavior нужно как-то определить, иначе он останется undefined. Раст доопределяет работу с аргументами программы как: "
args().nth(n)возвращаетNone, если аргумента n не существует". Что с этим делать дальше зависит от программиста. Можно даже вернуть UB, используяunreachable_unchecked()в ветке обрабатывающей отсутствие аргумента.MinimumLaw
28.12.2023 09:57Т.е. вопрос в целом не к atoi(), а к программисту, который не проверил ввод от пользователя и в целом это не зависит от языка? Я правильно понял?
А что произойдет с вашим кодом, если мы запустим
$ ./prog fortytwoВводим дополнительную проверку? Или все же "мусор на входе - мусор на выходе"?
Cerberuser
28.12.2023 09:57+6Дополнительная проверка в комментарии выше уже есть - parse вернёт ошибку, если входная строка не будет представлять значение требуемого типа (здесь -
u32). Для этого, собственно, и нужен второй expect.MinimumLaw
28.12.2023 09:57Т.е. .pase() ведет себя не как atoi(), а как scanf(). Впрочем, при использовании scanf() в C можно было и argv[1] на NULL не проверять...
В целом очень странные чувства от анализа совершенно простого кода. С одной стороны да - при нештатном использовании (запуск без аргумента или с неподобающим аргументом) - и даже откровенно некрасиво написанная программа падает в корку. Чем явно и недвухсмысленно говорит программисту - ты не прав, надо исправляться. С другой стороны... Падение программы, вызывающее DoS - несколько не то поведение, которого ожидает заказчик. Тем более, что для такого поведения надо "нарушить правила" - т.е. создать специально условия, приводящие к ошибке. А война меча и щита - она вечная.
Да, пожалуй, DoS в большинстве случаев лучше, чем RCE. Но нужно быть гурманом...
CodeRush
28.12.2023 09:57+3В результате запуска без параметров там будет что-нибудь вроде thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', т.е. ничего интересного.
Если же повторять эксперимент на Rust, то лучше засунуть все в здоровенный блок match и посмотреть, прожует компилятор 4 миллиарда записей в нем, или тоже решит, что это не для него.
aamonster
28.12.2023 09:57Match не годится, он может быть соптимизирован и вместо полного перебора получите O(log(N)).
Shura_m
28.12.2023 09:57+36По моему, автор доказал только одну вещь:
-можно реализовать любую фигню, любым образом, особенно если ты не ограничен ресурсами.
NickyX3
28.12.2023 09:57+68ru_perl 90-х
– Парни, а можно на Perl зачитать тектовый файл в 30 миллионов строк?
– А че за железо?
– Sun StarFire, 32 CPU, 196 GB RAM.
– ТЕБЕ - МОЖНО!
Didimus
28.12.2023 09:57-17Советским программистам платили за количество строк кода.
a-cherepanov
28.12.2023 09:57Ложь
Да нет, "Клади"
Ты что, в русской школе учился?
Советским программистам платили оклад.
falcon4fun
28.12.2023 09:57+1Именно так подумали про оптимизацию в иммортал оф авеум и прочих проектах этого года (:
panzerfaust
28.12.2023 09:57+44Если ваша лайвкодинг-сессия на интервью не похожа на это, то даже не зовите меня.
WFF
28.12.2023 09:57+43Все равно надо писать на Питоне: из полученного в качестве параметра числа он должен сделать программу на C, скомпилировать ее, запустить и вернуть результат.
Но глобально хотелось бы то же самое, но на микросервисах..
antonguzun
28.12.2023 09:57+5Не забыть про слоеную архитектуру
TEMN1J
28.12.2023 09:57Было бы интересно посмотреть сравнение производительности. ИМХО куча операторов сравнения медленнее чем операция остатка от деления. Однако, если сделать некую таблицу (число-чётное или нет) и маппинг оффсета на каждое число, и хранить этот файл в RAM, то уже возможно, что будет быстрее. Но опять же, это все надо проверять.
navferty
28.12.2023 09:57+38Я слабо представляю, как что-то может быть быстрее, чем получение крайнего бита из бинарного представления в памяти целого числа.
Alexey2005
28.12.2023 09:57-3Так нам ведь нужно не просто получить бит. Нам нужно:
Прочитать аргумент, представленный в виде строки.
Зачем-то сконвертить эту строку в число.
Получить бит от этого числа
В зависимости от бита осуществить переход.
Но ведь можно же никуда строку не конвертировать, а просто взять из неё последнюю цифру и проверять только её символьный код. Там и if'ов будет меньше, и переход можно вообще таблицей переходов (или switch) сделать.
code07734
28.12.2023 09:57+34А можно таки взять младший бит последней цифры) Расположение символов цифр в ascii соответствует четности самих чисел
edogs
28.12.2023 09:57+16Вы на полном серьезе рассуждаете как можно оптимизировать код из статьи?:)
aamonster
28.12.2023 09:57+9Ну да, а что? Я считаю, что нужна пачка функций типа isEqualTo0, isEqualTo1, isEqualTo2 и так далее, которые проверяют (тоже перебором) равенство конкретному числу, а уже потом проверять пачкой вызовов типа if(isEqualTo3(number)) printf("odd\n"), так хотя бы O(N^2) будет, а не жалкое O(N).
yokotoka
28.12.2023 09:57+3Перебором неспортивно. Нужна рекурсия
aamonster
28.12.2023 09:57Ну можно. Каждый из вызовов isEqualToX вызывает все остальные isEqualToY, чтобы убедиться, что каждый из них вернёт false. А чтобы избежать зацикливания – для каждого храним флаг, что он уже вызван. Правда, это будет не thread-safe, но, сдаётся мне, это наименьшая из проблем.
Boilerplate
28.12.2023 09:57isEqual(num) {
if(num ==0)return "odd"
if (num == 1)
return "even";return isEqual(num - 1);
}
mrqak
28.12.2023 09:57Ответом всегда будет even, если num > 0
fix:
return isEqual(num - 2);А еще odd и even местами перепутаны)
Boilerplate
28.12.2023 09:57Ну тестировщиков тоже нельзя без работы оставлять. А если в исходном варианте с ифами добиваться 100% покрытия, это же сколько тестов-то будет!
edogs
28.12.2023 09:57+6if (number == 5)printf("odd\n");4 миллиарда сравнений (каждое на 2 строчках), вот что бывает когда за код платят построчно:)
LF69ssop
28.12.2023 09:57-3На самом деле, показанный выше код — идеальный пример компромисса между временем и задействованной памятью.
Хорошая попытка, но нет. Автор кода просто не понимает что он делает.
bear11
28.12.2023 09:57+5а gcc -O3 это во сколько раз сожмет?
Fil
28.12.2023 09:57+65Куча if-ов - это уровень мидла, не выше. Сеньерское же решение будет таким:
bool is_even(int n) { return n == 0 ? true : is_odd(n - 1); } bool is_odd(int n) { return n == 0 ? false : is_even(n - 1); }
Mayurifag
28.12.2023 09:57+16Стало быть, в техлидском решении ещё и n == 0 в отдельную функцию вынесется, чтобы соблюдался DRY? :)
zzzzzzzzzzzz
28.12.2023 09:57+3изучив ограничения формата Portable Executable (.exe) для Windows, я обнаружил, что он не может обрабатывать больше, чем жалкие 4 ГБ
Мне кажется, что подход с автоматизированно-ручным написанием опкодов избыточно сложен для такой простой задачи.
Я бы на вашем месте воспользовался паттерном "разделяй и властвуй" и поэкспериментировал бы с созданием нескольких DLL-файлов, каждый из которых отвечает за свой диапазон чисел.
При таком подходе первичный работающий прототип можно получить довольно быстро. И далее уже смотреть в сторону оптимизации по скорости работы: чем меньше по размеру DLL-файл, тем быстрее он будет отрабатывать, но вместе с уменьшением размера будет расти количество файлов, соответственно, будет замедляться подгрузка файлов средствами ОС.
nronnie
28.12.2023 09:57+3"Разделяй и "властвуй" это будет:
public static bool IsEven(int n) => n switch { < 0 => IsEven(-n), 0 => true, 1 => false, _ => IsEven(n / 2) && IsEven(n - n /2) || IsOdd(n / 2) && IsOdd(n - n / 2) } public static bool IsOdd(int n) => !IsEven(n);
DrGluck07
28.12.2023 09:57Тоже сразу подумал про несколько DLL. Или можно вообще ничего не генерировать заранее, а создавать код в рантайме для диапазонов по миллиону чисел, например. Тогда exe-шник будет маленький, и даже не очень много памяти попросит.
Upd: Кстати, это позволит не ограничивать себя 32-битами.
UGivi
28.12.2023 09:57Первая мысль при чтении про невлезание в размер "а когда-то для такого использовались оверлеи".
Dredlock
28.12.2023 09:57А зачем писать столько много?
Ведь можно отбросить все цифры, кроме последней. И работать с ней. Всего 10 if.
А можно и двумя обойтись
if(n==1||3||5.... И тд
krabdb
28.12.2023 09:57-2А когда русскоязычное написание фамили Денниса как «Ритчи» сменили на «Ричи»? А Кернигана тоже на кого-то поменяли?
glebe
28.12.2023 09:57-2А разве недостаточно было проверять только последнюю цифру числа. Десяток ифов всего.
nochkin
28.12.2023 09:57+3С таким успехом мы можем скатиться до позорной проверки младшего бита. Это не наш стиль. Мы должны дать отпор возрастающей мощности современных вычислительных систем.
Moog_Prodigy
28.12.2023 09:57+2Надо было просто на CUDA все переложить. Я думаю, последние ускорители типа N100 должны справиться с подсчетом четных чисел. /s . Далее нам понадобится суперкомпьютер из топ100 для подсчета числа счастливых билетов.
Ну честно, какая то машина Голдберга получается с этими подходами)
belch84
28.12.2023 09:57-1Вот, с помощью BING'а набросал нечто подобное на SQL
Код для определения четности/нечетности числа на TRANSACT SQL
-- Create a stored procedure named CheckEven with one int parameter
CREATE PROCEDURE CheckEven @num int
AS
BEGIN
-- Declare a variable to store the result of the query
DECLARE @result int, @numint ;-- Create a table named EvenNumbers with one field of int type
CREATE TABLE EvenNumbers (
Number int
);-- Set a variable to store the current number
SET @num = 2;-- Use a while loop to insert numbers from 2 to 32766 into the table
WHILE @num <= 32766
BEGIN
-- Insert the current number into the table
INSERT INTO EvenNumbers (Number) VALUES );-- Increment the current number by 2
SET @num = @num + 2;
END-- Select the count of the number from the EvenNumbers table
SELECT @result = COUNT(Number) FROM EvenNumbers
-- Use the parameter as the filter condition
WHERE Number = @num;-- If the result is greater than zero, the number exists in the table
IF @result > 0
BEGIN
-- Print 'even' as the output
PRINT 'even';
END
-- Else, the number does not exist in the table
ELSE
BEGIN
-- Print 'odd' as the output
PRINT 'odd';
END
ENDПреимущество этого кода в том, что данные для определения четности можно хранить во внешней памяти. Не ручаюсь за выполнимость кода, но идея должна быть понятной - создаем таблицу, заполняем ее четными числами, потом определяем, есть ли искомое число в этой таблице
nronnie
28.12.2023 09:57WITH OddOrEven(Num, IsEven) AS ( SELECT CAST(0 AS int) Num, CAST(1 AS bit) IsEven UNION ALL SELECT oev.Num + 1 Num, CASE WHEN oev.IsEven = 0 THEN CAST(1 AS bit) ELSE Cast(0 AS bit) END IsEven FROM OddOrEven oev WHERE oev.Num < POWER(CAST(2 AS bigint), 31) - 1 ) SELECT IsEven FROM OddOrEven WHERE Num = @num;
iboltaev
28.12.2023 09:57-3Я понимаю, что это чисто поржать, но хоть бы массив забил что ли битовый статический, чтоб за о(1), или каскадировал через <, чтоб хотяб за логарифм...
debagger
28.12.2023 09:57+4Тут уже предлагали выше решить такую задачу на микросервисах. Я предлагаю пойти дальше. Чтобы по-настоящему хайпануть на трендах, надо взять какую-нибудь LLM архитектуру где-нибудь на 40B параметров и обучить исключительно на эту задачу. Считаю что это будет гораздо эпичнее.
Melirius
28.12.2023 09:57+5И получить после обучения на пятизначное число долларов точность ответа более 90%!
bolk
28.12.2023 09:57+2Думаю, нужно сделать клиентское приложение, которое надо качать и ставить себе. Установившие такие приложения становятся нодами единой сети. Нода будет брать задачи из единого реестра, вычислять чётность/нечётность и отдавать результат в сеть. Задачу должны взять себе несколько нод, так чтобы один из ответов (чёт или нечет) был больше 50% мощности сети.
Error1024
28.12.2023 09:57Я сторонник высокопроизводительного кода, поэтому решил реализовать это на языке программирования C, потому что он и сегодня остаётся самым быстрым языком в мире с большим отрывом от других (благодаря гению Денниса Ричи).
Мне кажется, или тут полное не понимание того, что секрет скорости не в некой «гениальности» си, а в миллиардах, вбуханных, в конкретные компиляторы? Странно такое видеть от человека, заявляющего что он «сторонник высокопроизводительного кода». Впрочем, современные последователи карго культа «блейзинг фаст» +/- все что-то подобное заявляют.
DimaFromMai
28.12.2023 09:57Не стоит преуменьшать заслуги Ричи, всегда считал, что секрет скорости ЯП в близости к железу, правда стоит уточнить, чем дальше от железа, тем быстрее разработка зато. Автор молодец, так заморочиться, спасибо, интересно было почитать.
mayorovp
28.12.2023 09:57+3Если бы автор написал как-то по-другому, ему не удалось бы написать шутку про Python ниже по тексту. А зачем вы пытаетесь искать глубокое понимание чего бы то ни было в откровенно стёбной статье?
Kelbon
28.12.2023 09:57эм, причём тут компиляторы, если питон в любом случае будет медленнее. На С можно писать код так, что его будет практически невозможно оптимизировать (т.к. он будет оптимален)
alexeyinkin
28.12.2023 09:57Даже если каждое сравнение будет использовать меньше одного байта, файл всё равно будет слишком тяжёлым.
Не факт.
Panzerschrek
28.12.2023 09:57https://godbolt.org/z/7qE9863j4
Clang с O2 оптимизирует цепочку сравнений до выборки указателя из таблицы с последующим вызовом puts. Другие компиляторы не осиливают оригинальный код и оставляют кучу инструкций ветвления.
AleksejMsk
28.12.2023 09:57+1На C# я могу хоть триллион IF сделать.
Шаг №1 - Генерирую DLL на N штук IF - загружаю в память и использую
...
Шfг №M - Генерирую DLL на N штук IF - загружаю в память и использую
В итоге N * F операторов IF.
Вуаля !
Nikolyanich
28.12.2023 09:57-6А не проще проверять последний бит числа
Если 1 четное иначе нечётное?
Всего 1 строка...
Serdjuk
28.12.2023 09:57-7Простите, это что за наркомания ?
Value And 1 для слабаков ?
Проверка нулевого бита, алле...DrGluck07
28.12.2023 09:57+4Этот комментарий пост-мета-ирония? Правда же?
Serdjuk
28.12.2023 09:57Нет
starik-2005
28.12.2023 09:57Ну так задача же стояла сдделать так, как в тиктоках, а не так, как правильно. Ито же стеб над стебом, но с позиции силы.
И да, программа бесполезная, но рабочая. Неужели это приходится объяснять?
Wesha
28.12.2023 09:57+12Мы всегда знали, что лучший способ отделить людей от роботов — это обсуждать шутки юмора. Вот ты и попался, железяка!
z3apa3a
28.12.2023 09:57Тема с оптимизацией алгоритмов не раскрыта КМК, можно было бы на питоне сгенерировать дерево if'ов. Код конечно слегка вырастет, зато какой прирост производительности!
Maccimo
28.12.2023 09:57Не совсем корректный ассемблерный код
Судя по подсветке синтаксиса, это вообще код на 1С ;)
Считаю, что о читаемости кода забывать нельзя и потому вместоINC EAXобязательно нужно было использоватьSETE EAX.я решил отобразить файл в адресное пространство, а не читать его целиком. Сделав так, мы притворимся, что весь файл уже находится в памяти
Досовские com-файлы восстают из пепла под 64-битной виндой, это ли не новогоднее чудо???
Автор выбрал другие хабы, там 5 ограничение, а так да может подойти.
@denis-19 «Ненормального программирования» здесь всё же больше, чем «алгоритмов».
P.S. При переводе потерялась часть шуток-прибауток из оригинала, читайте оригиналы!
akaluth
28.12.2023 09:57Прошу рассмотреть возможность оформить это как npm-пакет через ffi, постоянно возникает такая задача
yri066
28.12.2023 09:57+2Когда учился универе, было групповое задние на семестр заниматься разработкой 16-бит ОС (не обязательно чтобы была полностью рабочей), и у меня было одно из заданий: реализовать динамическое распределение памяти malloc. При работе нужно было для теста выводить в консоль распределение памяти, но при этом была проблема, что функция для печати числа использовала память для перевода его в строку при печати. Для того чтобы тестировать память и печатать числа без выделения памяти, пришлось сгенерировать файл на 40к строк:
if(num == 123) {kprint("123");};
x67
28.12.2023 09:57+1Ну, нет предела совершенству, можно же через if-else реализовать бинарные деревья, что сохранит нам один условный оператор и сильно увеличит скорость выполнения программы
kh0
28.12.2023 09:57+2Шикарная статья, получил море удовольствия, жду следующую:
"жервуем дисковым пространством ради скорости проверки на четность", где автор забьет ССД файлами с именами четных чисел и потом будет проверять четность наличием файла на диске.
Можно значительно уменьшить пенальти времени поиска файла, если хранить файлы не в виде папки с файлами, а в виде дерева подпапок с файлами, чтобы в каждой папке было не больше. Это был путь слабых.
А путь сильных это создать 4Гб файл на диске из 1 и 0, и при провере сикать по параметру сразу на позицию чтения. Смех-смехом, но подобная парадигма скорей всего это будет самой быстрой проверкой чисел "на простоватость".)
AtmosferaVA
28.12.2023 09:57Очень любопытная тема с написанием огрызка компилятора Си/Ассемблера на Питоне который собирает исходники прямо в код процессора!
Существуют ли примеры компиляторов прямо в машинный код написанных на Питоне?
nronnie
28.12.2023 09:57+1Еще вариант (C#) - для
intтут не получается (из-за встроенного лимита на длину массивов), но дляshortвполне:using System.Linq.Expressions; var param = Expression.Parameter(typeof(short)); var trueFalse = new[] { Expression.Constant(true), Expression.Constant(false) }; var body = Expression.Switch( param, defaultBody: trueFalse[1], Enumerable.Range(0, short.MaxValue + 1) .Select(i => Expression.SwitchCase( body: trueFalse[i % 2], Expression.Constant((short)i))) .ToArray()); var isEven = Expression.Lambda<Func<short, bool>>(body, param).Compile(); for (short i = 0; i <= 42; i++) { Console.WriteLine($"{i}: {isEven(i)}"); }
maxcat
28.12.2023 09:57можно создать массив с длиной расзмером с long или же int64, но конечно не через Enumerable.Range(..)
nronnie
28.12.2023 09:57+1Не, по-моему таки нельзя. Для одномерных массивов максимальное число элементов ограничено значением свойства Array.MaxLength - и, во-первых, оно уже объявлено как
intи больше чемint.MaxValueбыть не может, во-вторых, если покопаться в исходниках, то выясняется, что там оно захардкожено как0X7FFFFFC7, что даже немного меньше чемint.MaxValue. Для многомерных массивов теоретически методы классаArrayподдерживают размеры вlong, но, на деле (опять-таки, если посмотреть в исходники) этотlongтам везде приводится кint, и если он в него не влезает, то мы сразу получаемArgumentOutOfRangeException, и, даже более того, если он помещается вint, но не помещается вArray.MaxLengthто тогда получаемOutOfMemoryExceptionс сообщением "Array dimensions exceeded supported range."
EDIsaev
28.12.2023 09:57Не уж то чудооптимизатор сей не соптимизировал мильён ифов? Не пробовали? Просто интересно... Он, порой, такие оптимизации лепит, что суть всего алгоритма меняет)
amberovsky
28.12.2023 09:57Как насчёт использования оптимизированной функции в if-ах
bool optimised_is_even(int number) { bool res = true; for (int i = 0; i < number; i++) res = !res; return res; }
wasd_0
28.12.2023 09:57Очень познавательная статья, добавил в закладки везде, даже на микроволновке!
Жду реализацию программы "FizzBuzz". Планируете ли выпускать книгу по вашим работам?
lgorSL
ОС могла закешировать часть файла и не читать каждый раз (например, первые 10 Гб), во вторых ssd на m.2 обычно заметно быстрее (на уровне 3 или даже 7 гигабайт в секунду на чтение).
Но исходный код в начале статьи вообще на питоне, его исполнение было бы ещё медленнее на несколько порядков.
falcon4fun
Именно. Про файл маппинг в память видимо кто-то не слышал. Ох уж этот мир девопсеров.
atd
Чтобы что-то замапить в память, надо это прочитать с диска, магическим образом байты в рам не залетают. При размере файла 40гб, рам 32гб и линейном чтении файловый кэш поучаствовать не сможет (даже при всём желании, ну разве что перед измеряющим запуском несколько раз запустить программу и нажать Ctrl+C до того, как она завершится, если подгадать момент, тогда можно успеть оставить бОльшую часть файла в кэше фс).
rexen
Погодите, маппинг в память и кэширование - это не одно и то же. Первое - это лишь таблица трансляции виртуальных адресов, доступных программе в реальные, доступные ОС.
atd
А где я заявлял, что это одно и то же?
Профит от маппинга будет только если файл уже где-то лежит в памяти (например, в кэше ФС), если его там нет, то данные придётся читать с диска.
kh0
так автор же писал, что, несколько раз запускал код с разными параметрами от меньших к большим, т.о. на третьем пуске закэшировалось Х первых гигабайт, и на четвертом Х первых гигабайт вычитало прям из кэша, а дальше как обычно.
echo10
добавьте еще ELSE к IFам, пожалуйста, а то получается какой-то брут-форс )))
saboteur_kiev
а что изменится?
boldape
Ну судя по тому что время работы программы у чела меняется в зависимости от введённого значения, то на асме он таки добавил элсы.
Без элсов любой запуск будет тратить одно и тоже время и считывать весь файл, а с элсами он будет считывать до ИФА с совпадающим значенияем введённого числа. Без элсов это аналог алгоритма каунт (посчитать все вхождения), а с элсами алгоритм фаинд (найти первое совпадение).
vldF
О, заодно и константную ассимтотику можно получить так!