Как работает эта функция сортировки?
В рамках моей работы мне иногда приходится оценивать кандидатов на должности программиста. Фрагмент кода недавно прошел через мой стол, и мои первые мысли были о том, что я не был уверен, что такой код даже скомпилируется. Но скомпилируйте это, и это также работает.
Кто-нибудь может объяснить, почему и как это работает? Мандатом было предоставить функцию для сортировки пяти целочисленных значений.
void order5(arr) int *arr; {
int i,*a,*b,*c,*d,*e;
a=arr,b=arr+1,c=arr+2,d=arr+3,e=arr+4;
L1: if(*a >*b){*a^=*b;*b^=*a;*a^=*b;}
L2: if(*b >*c){*b^=*c;*c^=*b;*b^=*c;goto L1;}
L3: if(*c >*d){*c^=*d;*d^=*c;*c^=*d;goto L2;}
if(*d >*e){*d^=*e;*e^=*d;*d^=*e;goto L3;}
}
Теперь я вижу недостатки этого подхода (отсутствие читабельности и ремонтопригодности для тех, кто родился после 1970 года), но может ли кто-нибудь придумать какие-либо преимущества? Я не решаюсь уволить его из-под контроля, но прежде чем мы решим, следует ли возвращать этого человека во второй раунд, я хотел бы знать, есть ли у него какие-либо функции выкупа, помимо обеспечения безопасности работы для автора.
5 ответов
Это полностью развернутая пузырьковая сортировка с трюком XOR-swap, выраженным в строке. Я скомпилировал его с несколькими вариантами, надеясь, что он создаст какой-то потрясающий компактный код, но на самом деле он не такой впечатляющий. Я бросил в некоторых __restrict__ ключевые слова, чтобы компилятор знал, что ни один из *a может псевдоним друг друга, что очень помогает. В целом, хотя, я думаю, что предпринятая хитрость зашла настолько далеко от нормы, что компилятор действительно не очень хорошо оптимизирует код.
Я думаю, что единственным преимуществом здесь является новизна. Это наверняка попалось на глаза! Я был бы более впечатлен злоупотреблением более современными технологиями, такими как сортировка с MMX/SSE или GPU, или использование 5 потоков, которые борются за то, чтобы попытаться вставить свои элементы в нужное место. Или, возможно, внешняя сортировка слиянием, на тот случай, если массив из 5 элементов не может поместиться в ядре.
Трюк XOR просто меняет два целых числа. Гото это имитация цикла. Преимущества? Ничего, кроме того, чтобы показать, как запутанный код вы можете написать. Параметр после функции () является устаревшей функцией. И иметь массив под рукой и иметь 5 разных указателей, указывающих на каждый элемент массива, просто ужасно. Подводя итог: Фу!:)
Вы не можете уволить кого-то из-под контроля за такой ответ. Это могло быть предоставлено насмешливо.
Вопрос очень искусственный, подталкивающий надуманные ответы.
Вам нужно выяснить, как кандидат будет решать больше реальных проблем.
Это сложная реализация сортировки Gnome для пяти элементов.
Вот как садовый гном сортирует линию цветочных горшков. В основном он смотрит на цветочный горшок рядом с ним и предыдущим; если они находятся в правильном порядке, он шагает на один горшок вперед, иначе он меняет их местами и делает один горшок назад. Граничные условия: если предыдущего банка нет, он делает шаг вперед; если рядом с ним нет горшка, он готов.
"Шаг вперед на один банк" осуществляется путем перехода к следующему if, goto сразу после каждого XOR-свопа происходит "шаг назад на один банк".
отсутствие читабельности и ремонтопригодности для тех, кто родился после 1970 года
Разве люди, родившиеся до 1970 года, лучше поддерживают нечитаемый код? Если это так, это хорошо, потому что я был, и это может быть только точка продажи.
прежде чем мы решим, возвращать ли этого человека во второй раунд, я хотел бы знать, есть ли у него какие-либо функции для погашения, помимо обеспечения безопасности работы автора.
В коде нет ни одной функции выкупа. Он причудливо использует технику свопа xor, единственная потенциальная возможность выкупа которой - экономия пространства стека одного целого числа. Однако даже это сводится на нет пятью указателями, которые определены, и неиспользуемым int. Он также имеет безвозмездное использование оператора запятой.
Обычно я бы также сказал "goto, yuck", но в этом случае он использовался довольно элегантно, когда вы понимаете используемый алгоритм сортировки. Фактически, вы можете утверждать, что он делает алгоритм сортировки гномов более понятным, чем использование индексной переменной (за исключением того, что он не может быть обобщен на n элементов). Так что у вас есть функция выкупа, это делает Goto хорошо выглядеть:)
Что касается "ты возвращаешь кандидата на второе собеседование". Если бы фрагмент кода сопровождался подробным комментарием, объясняющим, как работает алгоритм и мотивация автора для его использования, я бы определенно сказал, что да. Если нет, я, вероятно, позвоню ему и задам эти вопросы.
Примечание: фрагмент кода использует объявления параметров в стиле K&R. Это означает, что автор, вероятно, не программировал на C от 10 до 15 лет, или он скопировал его из Интернета.