Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу: "Предложите код, который бы выводил на печать числа в убывающем порядке от n до 0, не используя (скрыто или явно) операторы сравнения (реализация функции вывода на печать не в счет)". Несмотря на то, что ко мне эта задача не имела отношения, она меня заняла и я решил подумать над способами ее решения (хотя, кому и при решении какой задачи может понадобиться такой метод оптимизации кода, мне осталось неизвестно, но тем не менее ).
Первое, что пришло на ум, — попытаться использовать шаблоны. Например так
template<int n>
void print()
{
printf("%d\n", n);
print<n - 1>();
}
template<>
void print<0>()
{
printf("0\n");
}
int main(int argc, char* argv[])
{
print<N>();
return 0;
}Проблема в том, что программирование это инженерная дисциплина, а не оккультная, и если "что-то" должно в системе происходить, то "оно" должно быть описано и под это должны быть выделены ресурсы, и в данном случае, поскольку отработка шаблонов происходит на этапе компиляции, есть ограницения на вложенность подобного рода конструкций (и это хорошо и правильно, и Слава Богу, что так есть), и компилятор совершенно справедливо выдал "fatal error C1202: recursive type or function dependency context too complex" при размере N больше 2000.
Следующее, что пришло в голову, использовать классический метод с указателями на функции.
typedef void(*PrintFunc)(int);
void printZero(int);
void printNumber(int n);
PrintFunc g_functors[] = {printZero, printNumber};
void printZero(int)
{
printf("0\n");
}
void printNumber(int n)
{
printf("%d\n", n--);
g_functors[!!n](n);
}
int main(int argc, char* argv[])
{
printNumber(N);
return 0;
}Но и тут ограничения, накладываемые на нас законом природы, дали о себе знать, и поскольку вложенность вызовов функций ограничена размерами стека, то при значении N > 4630 был получен законный "Stack overflow".
На этом месте разочарование и злоба полностью завладели мной и я понял, что для полноценного решения этой задачи не стоит гнушаться ни чем, в том числе самыми грязными трюками. Проблема в том, что при определенных значениях N нам нужно передавать управление на нужные участки кода. И в этом нет никаких проблем, когда у нас в распоряжении есть условные операторы, но когда их нет, приходиться прибегать к колдовству. В стародавние времена это можно было решить методом goto, но с тех пор охотники на ведьм и другие драконоборцы сильно ограничили его функциональность (и это также хорошо и правильно) и мы бы хотели написать что то типа этого
g_functors[0] = [](int){print("0\n"); goto end; }
g_functors[1] = [](int n){print("%d\n", n); goto begin; }
begin:
g_functors[!!n](n--);
end:но не можем.
Поэтому, хотя мне и запретили заниматься черной магией, в этом случае я решил сделать исключение, добавив к предыдущему примеру чуточку волшебства.
void printZero(int);
void printNumber(int n);
PrintFunc g_functors[] = {printZero, printNumber};
void printZero(int)
{
printf("0\n");
throw 0;
}
void printNumber(int n)
{
printf("%d\n", n);
}
int main(int argc, char* argv[])
{
int n = N;
try{
begin:
g_functors[!!n](n--);
goto begin;
}
catch (...){}
return 0;
}И это полностью решило проблему (при любых N).
P.S.: Буду рад услышать о других методах решения этой задачи
Комментарии (69)
redial
31.10.2018 14:27-1Я не знаю, как работает перехват деления на 0 в С. Да и синтаксис С — не очень помню.
Циклов нет, значит только goto. Печатаем i вычитаем единичку, делим любое число на i. При перехвате деления на 0 — заканчиваем программу, если нет перехвата — переходим в начало.
{
:begin
println i
i=i-1
try {j=10/i}
catch {goto end}
goto begin
:end
}prika148
31.10.2018 14:47Проблема в том, что в С нет исключений, т.е. Ваш код не компилируется. Но даже и в C++, где есть исключения, деление на ноль — UB и может не бросать исключений (обычно и не бросает)
ixSci
01.11.2018 15:42Мы не знаем условий задачи. А раз не знаем, то почему мы должны ограничиваться стандартом? SEH на Windows, и сигналы на Linux должны дать требуемый результат. В реальных проектах такого использовать, конечно же, нельзя, но почему на идиотскую задачу нельзя дать соответствующий ответ?
Sun-ami
31.10.2018 14:57Выражение !!n — это и есть неявное сравнение n==0. А циклы по условию задачи никто использовать не запрещал, так что если предположить, что разрешено !!n — можно написать
или, что то же самое,while( !!n ) printf( "%d ", n-- );while( n ) printf( "%d ", n-- );d_ilyich
31.10.2018 15:33+1Но в while-то тоже происходит неявное сравнение.
Более того, что подразумевается под «реализация функции вывода на печать не в счет»?
Предлагается ещё реализовать функцию отрисовки что ли? Если нет, то тогда в чём вообще проблема? В функции, осуществляющей печать, можно делать что угодно.
konshyn
31.10.2018 15:46+2С каких пор в циклах не происходит сравнения?
Странно0xd34df00d
31.10.2018 18:37+1Так оно и не в цикле происходит вон у вас в
main, компилятор радостно генерируетcmp.
Смысл утверждения был не в том, что можно использовать циклы, а в том, что если можно использовать
!!n, то от использования циклов вы уже ничего не теряете.Druu
31.10.2018 19:18А лямбды на сишке можно полноценно эмулировать без условий? Тогда можно просто задачу в кодировке Черча переписать.
0xd34df00d
31.10.2018 19:41Ну, на плюсах я бы ковырял в сторону дженерик лямбд (собственно, я так туплы делал через Church encodings ещё до того, как узнал про Church encodings туплов, оказалось существенно эффективнее std::tuple с точки зрения времени компиляции). На сишечке, наверное, можно там void* обмазаться и передавать указатели на функции туда-сюда и кастовать их.
domix32
31.10.2018 19:32+1Вы же понимаете что оно неявно преобразуется к виду `!!n == true. Аналогично if и switch, хотя для switch clang умеет генерировать таблицу сдвигов
0xd34df00d
31.10.2018 19:42+2Я понимаю, и поэтому я согласен, что
!!n— это читерство в любом виде.domix32
01.11.2018 00:10Не, сама конструкция с преобразованием нормально, но в цикле оно неявно сравнивается
Sun-ami
31.10.2018 23:24В while сравнение неявное, так же как в !!n, это прекрасно видно в ассемблерной выдаче, которую Вы привели в пример. А цикл без сравнения — запросто:
Вместо exit можно использовать longjmp. Хотя, конечно, — это платформо-зависимый код.#include <stdio.h> #include <stdlib.h> #include <stdint.h> union Index { int32_t n; struct {int32_t : 31, sign : 1; }; }; void dummy(int){} typedef void (*F)(int); F check[2] = { dummy, exit }; int main() { Index index; for( index.n = 100500;;index.n-- ) { check[ index.sign ](0); printf( "%d ", index.n ); } return 0; }
Reptor Автор
31.10.2018 17:13+2Дорогие друзья, это задание пришло ко мне так же как и к Вам, поэтому не могу дать ему более внятные разъяснения чем понял сам. Я рассудил так, что в самом коде получения числа и выбор ветки кода не должно встречаться условных операторов т.е. if, for, while, do...while(скрытые операторы) и т.д., а вот за код отвечающий за печать (внутренности printf и пр.) мы не отвечаем.
Если бы можно было использовать for, while и прочее, то задачи бы не было.
hdfan2
31.10.2018 15:14+1#include <stdio.h> #include <stdlib.h> void not0(int i) {printf("%d\n", i);} void is0(int i) {printf("0\n"); exit(0); } void (*func[2])(int)={is0,not0}; void main() { for (int i=100;;i--) { unsigned int j=((unsigned short*)&i)[0] | ((unsigned short*)&i)[1]; j=((unsigned char*)&j)[0] | ((unsigned char*)&j)[1]; j=(j&1)|((j&2)>>1)|((j&4)>>2)|((j&8)>>3)|((j&0x10)>>4)|((j&0x20)>>5)|((j&0x40)>>6)|((j&0x80)>>7); func[j](i); } }vesper-bot
31.10.2018 15:27Вообще, вызов func[(int)(bool)i](i) должен работать куда лучше этого странного кода.
hdfan2
31.10.2018 15:32А разве (bool)i не является неявным сравнением?
vesper-bot
31.10.2018 15:48Нет, это тайпкаст. Да, мы здесь пользуемся тем, что ((bool)i == true) === (i != 0), но сравнением это не является, мало того, даже при трансляции этого куска в асм в коде может не оказаться jz/jnz (например, четыре раза вызвать popcnt eax, eax приведет к переводу любого не-нуля в 1, хотя скорее всего код будет похож на or eax, eax; jz всторону; inc ebx и дальше).
Reptor Автор
31.10.2018 17:16да exit(0) пожалуй здравое решение. В остальном это тоже решение. Спасибо.
4eyes
31.10.2018 15:28-1Добавим чуть фантазии и дотошности, вместо "!!" вспомним математику:
int isNonNull (float n) { return (int)(n / (n + 0.1) + 0.1); } int isNegative(int n) { return (int)(n - sqrt(n*n)); } int main() { int n = 3; while(isNonNull(n) && !isNegative(n)) printf("%d", n--); }
Куда слать резюме?masterspline
31.10.2018 15:39+1
сравнение в чистом виде, поэтому «мы вам позвоним».while( condition )
multiprogramm
31.10.2018 15:36+6Подход с шаблонами сразу не прокатит, т.к. нужно знать n именно во время компиляции. А если мы знаем n во время компиляции, то мы просто можем написать
n+1 раз.print(n--);
Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу
Это задачка с искусственными ограничениями (в том плане, что вряд ли они встретятся в реальной задаче компании), поэтому давать её на собеседовании, конечно, можно, но ИМХО только в случае собеседования в клуб извращенцев.Habra_nik
31.10.2018 20:44> Это задачка с искусственными ограничениями (в том плане, что вряд ли они встретятся в реальной задаче компании)
Ограничение вполне-таки естественное, просто сформулировано упрощено, чтобы кандидат не парил голову понапрасну. Ветвления меняют время выполнения, а это часто недопустимо.
masterspline
31.10.2018 15:37+2Преобразуем текущее n в отрицательное, берем знак и используем его в качестве индекса по массиву из двух функций.
Рабочий код#include <stdio.h> #include <stdlib.h> typedef void (*Funcs)(int); void printZero(int) { printf("0\n"); exit(0); } void printNumber(int n) { printf("%d\n", n); } Funcs g_functors[] = {printZero, printNumber}; #define N 100000 int main(int argc, char* argv[]) { int n = N; begin: unsigned index = (unsigned(-n))>>(8*sizeof(n)-1); g_functors[index](n--); goto begin; return 0; }interprise
31.10.2018 15:44+1отличный вариант. я думаю лучший.
PS для тех кто не понял, преобразования к отрицательному будет давать в старшем бите 1 в любом случае кроме того когда изначальное значение 0. Следовательно, сдвинут на (8*sizeof(n)-1) мы получим либо 0 в случае когда изначально был 0 либо 1 в случае любого другого числа. Дальше просто при вызове «нулевой» функции делаем exit.
Reptor Автор
31.10.2018 17:21Спасибо. exit(0) — делает все гораздо более элегантным, но в остальном это решение того же качества, оно не дает ничего нового. Это тот же метод. Но все равно спасибо за улучшение.
4eyes
01.11.2018 04:27Есть новый подход в честь наступающей пятницы, моего провала с while() и тяги к прекрасному:
* без выделения памяти и конструирования объектов
* без exit(), чтобы не нарушать красивый ход исполнения кода
* без функторов и ограничения глубины рекурсии
* без явных и неявных сравнений включая, но не ограничиваясь: приведения к bool, operator!(), и всякие cmovz / jcxz в ассемблерном коде.
Расплатиться пришлось небольшой ассемблерной вставкой, 1 WinAPI, капелькой магии и крупинкой надежды:#include <cstdio> #include <cstdint> #include <windows.h> int isNegative(int n) { return (unsigned int)n >> (sizeof(n) * 8 - 1); } void f(int number) { uint16_t hope = 0; m1: int isNeg = isNegative(number); uint32_t fmt = 0x000a6400 | ((1 - isNeg) * '%'); printf((char*)&fmt, number--); uint16_t magic = hope ^ (0x6F6F * isNeg + 0x0100); __asm { mov ecx, m2; mov ax, [magic]; or [hope], ax; xor [ecx], ax; mov eax, m1; m2: jmp ecx; } } int main() { DWORD old; VirtualProtect(GetModuleHandle(nullptr), 0x16000, PAGE_EXECUTE_READWRITE, &old); // this might work VirtualProtect(GetModuleHandle(nullptr), 0x2000, PAGE_EXECUTE_READWRITE, &old); // ... this one will fix when previous fails int n = 30; f(n); }
JerleShannara
31.10.2018 16:46Без сравнений — хорошо, код будет только описан, и работать мы будем в BareMetal x86, ну или под ДОСом, или в Ring-0
1) Пишем свой обработчик на ошибку division by zero, оный должен увеличить сохраненный адрес возврата на длину команд присваивания, деления и безусловного перехода(надо посмотреть в листинге)
2) Закидываем его в таблицу прерываний
3) Далее адов говнокод:
void destroy (int n) { int i=99; int j; n++; hitbyvelociraptor: n--; printf("%x\n",n); j=i/n; goto hitbyvelociraptor; printf("done\n"); }
Задачей обработчика деления на ноль будет перепрыгнуть через goto. И никаких сравнений тут вообще нигде не будет делаться.
Griboks
31.10.2018 17:00+1Я бы написал так
begin:
print(N);
N=N/N*(N-1);
goto begin;
Программа напечатает числа от N до 0, а потом прекратит работу.JerleShannara
31.10.2018 19:42Но завершение будет аварийным, хотя в ТЗ про то, что выход должен быть штатным
Griboks
31.10.2018 19:58Предложите код, который бы выводил на печать числа в убывающем порядке от n до 0, не используя (скрыто или явно) операторы сравнения (реализация функции вывода на печать не в счет)
Videoman
31.10.2018 17:58Можно добавить немного С++
struct Item { Item() { printf ("%d ", N - (this - items)) - 1; } static void Do() { exit(0)} static const size_t N = 100; static const Item items[N+ 1]; }; const Item Item::items[] = {}; void main() { Item::Do(); }
hdfan2
31.10.2018 18:06+1И на шаблонах тоже можно для любого N:
Заголовок спойлера#include <stdio.h> template <int N> void print(int base) { print<N/2>(base); print<N-N/2>(base-N/2); } template <> void print<0>(int) {} template <> void print<1>(int base) { printf("%d\n", base); } #define N 100 int main() { print<N+1>(N); return 0; }sena
31.10.2018 19:42+3С++ без извращений#include <iostream> struct printnum { printnum() { std::cout << nump-- << "\n"; } static unsigned nump; }; unsigned printnum::nump; int main() { printnum::nump = 10000000; printnum * pa = new printnum[printnum::nump+1]; }
динамическое выделения памяти, чтобы обойти ограничение по стеку
static не разрешит задавать размер динамичскиsena
31.10.2018 20:43+1Придумал С++ решение без реального выделения памяти и без ограничений по размеру
C++ без извращений и без ограничений по памяти#include <iostream> struct printnum { printnum() { std::cout << nump-- << "\n"; } static unsigned long nump; }; unsigned long printnum::nump; char* memory[10]; int main() { printnum::nump = 10000000000000; printnum * pa = new(memory) printnum[printnum::nump+1]; }mapron
31.10.2018 21:05На самом деле, «скрытая» проверка условий таки есть — в реализации оператора new. тут вопрос к применимости исходного ограничения — где таки можно иметь эти самые сравнения — в коде генерации самого компилятора? рантайма? стандартной библиотеки?
А то я тоже могу просто написать std::transform(nullptr, nullptr + n, (ничего не делающий output it), (функция вывода))
(но за хак я плюс поставил)sena
01.11.2018 01:59В условии стоит запрет на неявное сравнение, так что этот вариант (а равно и все остальные варианты с массивами и контейнерами) нарушают это условие.
mapron
31.10.2018 20:59Почти 1:1 подход который я решил применить — конструкторы в динамической памяти. Разница в том что я не делал статичную переменную, а передавал в конструктор ссылку на коллбек:
#include <iostream> #include <vector> #include <functional> struct Caller { std::function<void()> & m_f; Caller( std::function<void()> & f) : m_f(f) {} ~Caller() { m_f(); } }; int main() { int n = 500; std::function<void()> counter ([&n] { std::cout << n-- << std::endl; }); std::vector<Caller> v(n, Caller(counter)); return 0; }
OvO
31.10.2018 22:30с89:
void main (int n, char **argv)
{
void (*f[])()={&exit,&printf};
int func_n;
loop:
func_n= n;
func_n|=func_n>>1;
func_n|=func_n>>2;
func_n|=func_n>>4;
func_n|=func_n>>8;
func_n|=func_n>>16;
f[func_n&1]("%d ",--n);
goto loop;
}
oleg1977
31.10.2018 23:47Сразу подумал, что на С++ элементарно, а вот на С нужно подумать. Но вижу, что все пишут на плюсах, поэтому мой вариант:
#include <iostream> class A { public: A() { std::cout << n << "\n"; --n; } static void set(size_t i) { n = i; } private: static size_t n; }; size_t A::n; void print_n_0(size_t n) { A::set(n); delete[] new A[n+1]; } int main() { print_n_0(10); return 0; }
and_cesbo
01.11.2018 00:49-1#include <stdio.h> int step(int i) { printf("%d\n", i--); return (i && step(i)) || 0; } int main(void) { printf("%d\n", step(5)); return 0; }
Ivaneo
01.11.2018 04:38Если уж использовать С++, то все проще некуда.
int main() { const int n = 10; int count = n; std::generate_n(std::ostream_iterator(std::cout, " "), n, [&count]() { return count--; }); return 0; }
sena
01.11.2018 13:42На первый взгляд конечно да, запрета на использование стандартных библиотек не было, но всё же запрет на неявный оператор сравнения всё портит — внутре он там конечно есть.
3aicheg
01.11.2018 06:53Если уж падать в stack overflow, то зачем так переусложнять? Почему просто не написать что-то вроде:
int prt(int n) { std::cout << n << "\t"; return n && prt(n - 1); }
Можно, конечно, сказать, что && — скрытый оператор сравнения. Ну так, например, изначальный вариант автора поста на шаблонах — это, фактически, составное определение функции Haskell-style (отдельно для нуля, отдельно для всего остального, не помню уже, как именно оно называется в функциональных языках, нувыпонели), там тоже по-любому скрытый оператор сравнения (сравнить аргумент с нулём, по результатам выполнить либо то, либо это).
stalcker
01.11.2018 12:14Давно не трогал руками C и C++, такой вариант первым пришел в голову:
void print_a(int len){ cout << "\n===" << len << "\n"; float tmp = 5 / (len); print_a(len - 1); } void handler(int a) { exit (0); } int main ( ) { int len = 100000; signal(SIGFPE, handler); print_a(len); return 0; }
vesper-bot
01.11.2018 12:46Только len нужно передавать по ссылке внутрь print_a, и не len-1, а len--.
stalcker
01.11.2018 12:49Да, так будет даже лучше.
Добавлено чуть позже — В смысле меньше локальных переменных вызвать. Но не факт что вообще лучше — все же по ссылке и с len-- мы будем менять переменную извне, что может быть не гуд. Можно и еще компактнее и надежнее(в память не упремся из-за рекурсии):
void handler(int a) { exit (0); } int main ( ) { int len = 100000; signal(SIGFPE, handler); l1: cout << "\n===" << len-- << "\n"; float tmp = 5 / len; goto l1; }vesper-bot
01.11.2018 12:59А, тормознул, у вас же там рекурсия, там пофиг как передавать, зато можно зациклить внутри print_a через goto, все равно выход из цикла по сигналу.
sergio_nsk
01.11.2018 13:04Цикл for с тем же !!n, и нет сравнения ведь?
for (int n = N; !!n; --n) printf("%d\n", n); printf("%d\n", 0);
Можно было просто написать рекурсивную функцию
void out(int n) { if (!n) return; printf("%d\n", n); out(n-1); } printf("%d\n", 0);
Хвостовая рекурсия оптимизируется, и не будет никакой рекурсии в ассемблере.
4eyes
01.11.2018 13:21Как же нет сравнения, если оно есть: godbolt.org/z/QAM3jR
!n это то же самое, что n==0;
А еще, среди целых чисел бывают такие, как -1, -2…
genew
01.11.2018 14:27А что, с exception нельзя?
int main() { int n = 10; try { while(1) { printf("%d\n", n); n -= n / n; } } catch(...){} return 0; }stalcker
01.11.2018 14:36Не знаю как дела обстоят сейчас, но раньше такой код не работал. Точнее работал не так, как ожидается — при делении на ноль программа вылетала. Не отлавливается такое исключение — неопределенное поведение по стандарту.
genew
01.11.2018 14:52Действительно, неопределенное поведение, но в VS 2008 почему-то прекрасно работает.
По-идее, при делении на 0, CPU должен сгенерировать INT 0 и windows должна завершить процесс.
Но этого не происходит.stalcker
01.11.2018 14:57Это исключение не определено, уберите обёртку из try catch и программа должна упасть.
ihost
Интересное решение, хотя при использовании C extensions (gcc), можно обойтись без функторов вообще — за счет Label Values. Эта функциональность применяется в низкоуровневых модулях высоконагруженных приложений для организации переходов без ветвления, хотя в зависимости от ситуации может быть оптимальнее использовать if в сочетании с builtin_expect для мануальной настройки branch prediction. Вместо отрицания, возможно, применить более подходящий оптимальный intrinsic
Reptor Автор
Спасибо за интересную возможность. Не знал.