Как работает эта функция сортировки?

Question

Как часть моей работы, мне иногда приходится оценивать кандидатов на должности программиста.Фрагмент кода недавно прошел через мой стол, и мои первые мысли были о том, что я не уверен, что такой код будет даже компилировать больше.Но скомпилируйте, и это сработает.

Кто-нибудь может объяснить, почему и как это работает?Мандат состоял в том, чтобы предоставить функцию для сортировки пяти целочисленных значений.

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 года), ноКто-нибудь может придумать какие-либо преимущества?Я не решаюсь уволить его из-под контроля, но прежде чем мы решим, следует ли возвращать этого человека на второй раунд, я хотел бы знать, есть ли у него какие-либо функции выкупа, помимо обеспечения безопасности работы для автора.

Answer 1

Это полностью развернутая пузырьковая сортировка с трюком XOR-swap, выраженным в строке.Я скомпилировал его с несколькими вариантами, надеясь, что он создаст какой-то потрясающий компактный код, но на самом деле он не такой впечатляющий.Я добавил несколько ключевых слов __restrict__, чтобы компилятор знал, что ни одно из *a не может псевдонимов друг друга, что очень помогает.В целом, я думаю, что предпринятая хитрость зашла настолько далеко от нормы, что компилятор действительно не очень хорошо оптимизирует код.

Я думаю, что единственным преимуществом здесь является новизна.Это, безусловно, попалось на глаза!Я был бы более впечатлен злоупотреблениями более современной современной технологии, такой как сортировка с MMX / SSE или графическим процессором, или использование 5 потоков, которые борются, чтобы попытаться вставить свои элементы в нужное место.Или, возможно, внешняя сортировка слиянием, на тот случай, если массив из 5 элементов не может поместиться в ядре.

Answer 2

Трюк xor просто заменяет два целых числа.Гото это имитация цикла.Преимущества?Ничего, кроме того, чтобы показать, как запутанный код вы можете написать.Параметр после функции () является устаревшей функцией.И иметь под рукой массив и иметь 5 разных указателей, указывающих на каждый элемент массива, просто ужасно.Подводя итог: Yuck!:)

Answer 3

недостаточная читаемость и удобство сопровождения для тех, кто родился после 1970 года

Чем лучше люди, рожденные до 1970 года, поддерживают нечитаемый код?Если так, это хорошо, потому что я был и это может быть только точка продажи.

, прежде чем мы решим, возвращать ли этого человека обратно во 2 раунд, я хотел бы знать, если этоимеет любые функции погашения, кроме обеспечения безопасности работы для автора.

Код имеет нет одну функцию погашения s .Он причудливо использует технику свопирования xor, единственная потенциальная возможность выкупа которой - экономия пространства стека одного целого числа.Однако даже это сводится на нет пятью указателями, которые определены, и неиспользуемым int.В нем также есть безвозмездное использование оператора запятой.

Обычно я бы также сказал «goto, yuck», но в этом случае он использовался довольно элегантно, как только вы понимаетеалгоритм используется.Фактически можно утверждать, что он делает алгоритм сортировки гномов более понятным, чем использование индексной переменной (за исключением того, что он не может быть обобщен на n элементов).Таким образом, у вас есть функция выкупа, которая заставляет goto выглядеть хорошо:)

Что касается "вы вернете кандидата на второе собеседование".Если бы фрагмент кода сопровождался подробным комментарием, объясняющим, как работает алгоритм и мотивация автора для его использования, я бы определенно сказал, что да.Если нет, то я, вероятно, позвоню ему и задам эти вопросы.

Примечание: фрагмент кода использует объявления параметров в стиле K & R.Это означает, что автор, вероятно, не программировал на C в течение 10-15 лет или скопировал его из Интернета.

Answer 4

Вы не можете уволить кого-то из-под контроля за такой ответ. Это могло быть предоставлено насмешливо.

Вопрос очень искусственный, требующий искусственных ответов.

Вам нужно выяснить, как кандидат решит больше реальных проблем.

Answer 5

Это сложная реализация сортировки гномов для пяти предметов.

Вот как садовый гном сортирует линию цветочных горшков.В основном он смотрит на цветочный горшок рядом с ним и предыдущий;если они находятся в правильном порядке, он шагает на один горшок вперед, в противном случае он меняет их местами и делает один горшок назад.Граничные условия: если предыдущего банка нет, он делает шаг вперед;если рядом с ним нет банка, он готов.

«Шаг вперед на один банк» осуществляется путем провала до следующего if.goto сразу после каждого свопа XOR выполняет «шаг назад на один банк».