Я столкнулся с непростым (ИМО) вопросом. Мне нужно было сравнить два
C собеседование - литье и сравнение
Ответ 1
Если он действительно недоволен этим подходом (который по сути является мозговым пердуном, поскольку вы не сравниваете мегабайты или гигабайты данных, поэтому на самом деле не стоит беспокоиться о "эффективности" и "скорости" в этом случае), просто скажите ему, что вы доверяете качеству и скорости стандартной библиотеки:
int isEqual(MAC* addr1, MAC* addr2)
{
return memcmp(&addr1->data, &addr2->data, sizeof(addr1->data)) == 0;
}
Ответ 2
Если ваш интервьюер требует, чтобы вы выполняли поведение undefined, я, вероятно, искал бы работу в другом месте.
Правильный первоначальный подход состоял в том, чтобы сохранить MAC-адрес в чем-то вроде uint64_t, по крайней мере, в памяти. Тогда сравнения будут тривиальными и эффективными.
Ответ 3
Время ковбоя:
typedef struct macA {
char data[6];
} MAC;
typedef struct sometimes_works {
long some;
short more;
} cast_it
typedef union cowboy
{
MAC real;
cast_it hack;
} cowboy_cast;
int isEqual(MAC* addr1, MAC* addr2)
{
assert(sizeof(MAC) == sizeof(cowboy_cast)); // Can't be bigger
assert(sizeof(MAC) == sizeof(cast_it)); // Can't be smaller
if ( ( ((cowboy_cast *)addr1)->hack.some == ((cowboy_cast *)addr2)->hack.some )
&& ( ((cowboy_cast *)addr1)->hack.more == ((cowboy_cast *)addr2)->hack.more ) )
return (0 == 0);
return (0 == 42);
}
Ответ 4
Нет ничего плохого в эффективной реализации, поскольку все, что вы знаете, было определено как горячий код, который называется много раз. И, во всяком случае, для вопросов, связанных с собеседованием, должно быть нечетное ограничение.
Логическое И является априорным инструкцией ветвления из-за оценки короткого замыкания, даже если он не компилируется таким образом, поэтому позволяет избежать этого, нам это не нужно. Нам также не нужно преобразовать наше возвращаемое значение в истинное значение bool (true или false, а не 0 или что-либо, что не равно нулю).
Вот быстрое решение на 32-битном: XOR будет фиксировать различия, ИЛИ будет записывать разницу в обеих частях, а NOT будет отрицать условие в EQUALS, а не UNEQUAL. LHS и RHS являются независимыми вычислениями, поэтому суперскалярный процессор может делать это параллельно.
int isEqual(MAC* addr1, MAC* addr2)
{
return ~((*(int*)addr2 ^ *(int*)addr1) | (int)(((short*)addr2)[2] ^ ((short*)addr1)[2]));
}
ИЗМЕНИТЬ
Цель вышеприведенного кода заключалась в том, чтобы показать, что это можно сделать эффективно без разветвления. В комментариях указано, что С++ классифицирует это как поведение undefined. Хотя верно, VS справляется с этим штрафом. Без изменения определения структуры интервьюера и сигнатуры функции, чтобы избежать поведения undefined, должна быть сделана дополнительная копия. Таким образом, способ поведения без undefined без ветвления, но с дополнительной копией будет выглядеть следующим образом:
int isEqual(MAC* addr1, MAC* addr2)
{
struct IntShort
{
int i;
short s;
};
union MACU
{
MAC addr;
IntShort is;
};
MACU u1;
MACU u2;
u1.addr = *addr1; // extra copy
u2.addr = *addr2; // extra copy
return ~((u1.is.i ^ u2.is.i) | (int)(u1.is.s ^ u2.is.s)); // still no branching
}
Ответ 5
Это будет работать на большинстве систем и будет быстрее вашего решения.
int isEqual(MAC* addr1, MAC* addr2)
{
return ((int32*)addr1)[0] == ((int32*)addr2)[0] && ((int16*)addr1)[2] == ((int16*)addr2)[2];
}
тоже хорошо встраивается, может быть удобно в центре цикла в системе, где вы можете проверить, что детали жизнеспособны.
Ответ 6
Не переносное решение для литья.
В платформе, используемой на основе PIC24, существует тип int48, поэтому для безопасного предположения char используется 8 бит и обычные требования к выравниванию:
int isEqual(MAC* addr1, MAC* addr2) {
return *((int48_t*) &addr1->data) == *((int48_t*) &addr2->data);
}
Конечно, это невозможно использовать на многих платформах, но тогда также существует ряд решений, которые не являются переносимыми, в зависимости от предполагаемого размера int, no padding и т.д.
Самое высокое портативное решение (и достаточно быстрое с учетом хорошего компилятора) - это memcmp(), предлагаемое @H2CO3.
Переход на более высокий уровень проектирования и использование достаточно широкого целочисленного типа типа uint64_t вместо struct macA, как это предлагает Kerrek SB, очень привлекательно.
Ответ 7
У вас есть структура MAC (которая содержит массив из 6 байтов),
typedef struct {
char data[6];
} MAC;
Что согласуется с этой статьей о typedef для массива байтов с фиксированной длиной.
Наивный подход состоял бы в том, чтобы предположить, что MAC-адрес выровнен по слову (что, вероятно, и требовало интервьюера), хотя и не гарантировано.
typedef unsigned long u32;
typedef signed long s32;
typedef unsigned short u16;
typedef signed short s16;
int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1); //check for NULL args
u32 m1 = *(u32*)mac1->data;
U32 m2 = *(u32*)mac2->data;
if( m1 != m2 ) return (s32)m1 - (s32)m2;
u16 m3 = *(u16*)(mac1->data+4);
u16 m2 = *(u16*)(mac2->data+4);
return (s16)m3 - (s16)m4;
}
Чуть более безопасным было бы интерпретировать char [6] как короткое [3] (MAC, скорее всего, выровнен на четных границах байтов, чем нечетный),
typedef unsigned short u16;
typedef signed short s16;
int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1); //check for NULL args
u16* p1 = (u16*)mac1->data;
u16* p2 = (u16*)mac2->data;
for( n=0; n<3; ++n ) {
if( *p1 != *p2 ) return (s16)*p1 - (s16)*p2;
}
return(0);
}
Не принимайте ничего и копируйте в хранилище с выравниванием слов, но единственная причина для приведения типов здесь - удовлетворить интервьюера,
typedef unsigned short u16;
typedef signed short s16;
int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1); //check for NULL args
u16 m1[3]; u16 p2[3];
memcpy(m1,mac1->data,6);
memcpy(m2,mac2->data,6);
for( n=0; n<3; ++n ) {
if( m1[n] != m2[n] ) return (s16)m1[n] - (s16)m2[n];
}
return(0);
}
Сэкономьте много работы,
int
MACcmp(MAC* mac1, MAC* mac2)
{
if(!mac1 || !mac2) return(-1);
return memcmp(mac1->data,mac2->data,6);
}
Ответ 8
Функция memcmp в конечном итоге сделает сам цикл. Таким образом, используя это, вы в основном просто делаете вещи менее эффективными (из-за дополнительного вызова функции).
Вот необязательное решение:
typedef struct
{
int x;
short y;
}
MacAddr;
int isEqual(MAC* addr1, MAC* addr2)
{
return *(MacAddr*)addr1 == *(MacAddr*)addr2;
}
Компилятор скорее всего преобразует этот код в два сравнения, так как структура MacAddr содержит два поля.
Полость: если ваш процессор не поддерживает операции выравнивания нагрузки/хранения, addr1 и addr2 должны быть выровнены по 4 байтам (т.е. они должны быть расположены в адресах, которые делятся на 4). В противном случае нарушение прав доступа к памяти, скорее всего, произойдет, когда функция будет выполнена.
Вы можете разделить структуру на 3 поля по 2 байта каждый или по 6 полей по 1 байт (уменьшение ограничения выравнивания до 2 или 1 соответственно). Но не забывайте, что одно сравнение в исходном коде не обязательно является единственным сравнением в исполняемом изображении (то есть во время выполнения).
BTW, самостоятельные операции загрузки/хранения сами по себе могут добавить задержку времени выполнения, если они требуют больше "nops" в конвейере CPU. На самом деле это вопрос архитектуры процессора, и я сомневаюсь, что они хотели "заглянуть" в это интервью. Однако, чтобы утверждать, что скомпилированный код не содержит таких операций (если они действительно "дороги" ), вы можете убедиться, что переменные всегда выровнены с 8 байтами И добавить #pragma ( компилятор), говоря компилятору "не беспокоиться об этом".
Ответ 9
Возможно, он имел в виду определение MAC, которое использовало unsigned char и думал:
int isEqual(MAC* addr1, MAC* addr2) { return strncmp((*addr1).data,(*addr2).data,6)==0; }
что подразумевает литье из (без знака char *) в (char *). В любом случае, плохой вопрос.
Ответ 10
Для правильного ввода текста вам необходимо использовать объединение. В противном случае вы нарушите строгое наложение правил, которым следуют некоторые компиляторы, и результат будет undefined.
int EqualMac( MAC* a , MAC* b )
{
union
{
MAC m ;
uint16_t w[3] ;
} ua , ub ;
ua.m = *a ;
ub.m = *b ;
if( ua.w[0] != ub.w[0] )
return 0 ;
if( ua.w[1] != ub.w[1] )
return 0 ;
if( ua.w[2] != ub.w[2] )
return 0 ;
return 1 ;
}
В соответствии с C99 безопасно читать из члена объединения, который не является последним, используемым для хранения значения в нем.
Если элемент, используемый для чтения содержимого объекта объединения, не совпадает с элементом, используемым последним для хранения значения в объекте, соответствующая часть представления объекта значения переинтерпретируется как представление объекта в новый тип, как описано в 6.2.6 (процесс, иногда называемый "пингом типа" ). Это может быть ловушечное представление.