C sollicitatiegesprek – casten en vergelijken

Ik werd geconfronteerd met een lastige (IMO) vraag. Ik moest twee MAC-adressenop de meest efficiënte manier vergelijken.

De enige gedachte die op dat moment bij me opkwam, was de triviale oplossing – een for-lus en het vergelijken van locaties, en dat deed ik ook, maar de interviewer wilde casten.

De MAC-definitie:

typedef struct macA {
   char data[6];
} MAC;

En de functie is (degene die ik moest implementeren):

int isEqual(MAC* addr1, MAC* addr2)
{
    int i;
    for(i = 0; i<6; i++)
    {
        if(addr1->data[i] != addr2->data[i]) 
            return 0;
    }
    return 1;
}

Maar zoals gezegd, hij mikte op casting.

Dit betekent, om op de een of andere manier het MAC-adres dat aan een int is gegeven te casten, beide adressen te vergelijken en terug te keren.

Maar bij het casten, int int_addr1 = (int)addr1;, worden er maar vier bytes gecast, toch? Moet ik de overige controleren? Betekent locaties 4 en 5?

Zowel charals intzijn integer-types, dus casten is legaal, maar wat gebeurt er
in de beschreven situatie?

Antwoord 1, autoriteit 100%

Als hij echt ontevreden is over deze aanpak (wat in wezen een hersenscheet is, aangezien je geen megabytes of gigabytes aan gegevens vergelijkt, dus je hoeft je in dit geval niet echt zorgen te maken over “efficiëntie” en “snelheid” ), vertel hem gewoon dat je de kwaliteit en snelheid van de standaardbibliotheek vertrouwt:

int isEqual(MAC* addr1, MAC* addr2)
{
    return memcmp(&addr1->data, &addr2->data, sizeof(addr1->data)) == 0;
}

Antwoord 2, autoriteit 39%

Als uw interviewer eist dat u ongedefinieerd gedrag vertoont, zou ik waarschijnlijk ergens anders een baan zoeken.

De juiste initiële benadering zou zijn om het MAC-adres op te slaan in zoiets als een uint64_t, in ieder geval in het geheugen. Dan zijn vergelijkingen triviaal en efficiënt uitvoerbaar.

Antwoord 3, autoriteit 14%

Cowboytijd:

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);
}

Antwoord 4

Functie memcmp zal uiteindelijk de lus zelf doen. Dus door het te gebruiken, zou je dingen in feite gewoon minder efficiënt maken (vanwege de extra functie-aanroep).

Hier is een optionele oplossing:

typedef struct
{
    int x;
    short y;
}
MacAddr;
int isEqual(MAC* addr1, MAC* addr2)
{
    return *(MacAddr*)addr1 == *(MacAddr*)addr2;
}

De compiler zal deze code hoogstwaarschijnlijk omzetten in twee vergelijkingen, aangezien de MacAddr-structuur twee velden bevat.

Cavity: tenzij uw CPU niet-uitgelijnde laad-/opslagbewerkingen ondersteunt, moeten addr1 en addr2 worden uitgelijnd op 4 bytes (d.w.z. ze moeten zich bevinden in adressen die deelbaar zijn door 4). Anders zal er hoogstwaarschijnlijk een geheugentoegangsfout optreden wanneer de functie wordt uitgevoerd.

U kunt de structuur verdelen in 3 velden van elk 2 bytes, of 6 velden van elk 1 byte (waardoor de uitlijningsbeperking wordt teruggebracht tot respectievelijk 2 of 1). Maar onthoud dat een enkele vergelijking in uw broncode niet noodzakelijkerwijs een enkele vergelijking in de uitvoerbare afbeelding is (d.w.z. tijdens runtime).

Trouwens, niet-uitgelijnde laad-/opslagbewerkingen op zichzelf kunnen runtime-latentie toevoegen als ze meer “nops” in de CPU-pijplijn vereisen. Dit is echt een kwestie van CPU-architectuur, waarvan ik betwijfel of ze zo ver wilden “graven” in je sollicitatiegesprek. Om echter te beweren dat de gecompileerde code dergelijke bewerkingen niet bevat (als ze inderdaad “duur” zijn), kunt u ervoor zorgen dat de variabelen altijd zijn uitgelijnd op 8 bytes ENvoeg een #pragma toe ( compiler-richtlijn) die de compiler zegt “hier geen zorgen over te maken”.

Antwoord 5

Misschien had hij een definitie van MAC in gedachten die unsigned char gebruikte en dacht hij aan:

int isEqual(MAC* addr1, MAC* addr2) { return strncmp((*addr1).data,(*addr2).data,6)==0; }

wat een cast impliceert van (unsigned char *) naar (char *).
Hoe dan ook een slechte vraag.

Antwoord 6

Trouwens, voor degenen die echt op zoek zijn naar een performant antwoord, het volgende is branchless, en hoewel het meer ophaalt (één per char), zouden ze allemaal van dezelfde cacheregel moeten zijn, dus niet erg duur.

p>

int isEqual(MAC* addr1, MAC* addr2)
{
    return
      (addr1->data[0] == addr2->data[0])
    & (addr1->data[1] == addr2->data[1])
    & (addr1->data[2] == addr2->data[2])
    & (addr1->data[3] == addr2->data[3])
    & (addr1->data[4] == addr2->data[4])
    & (addr1->data[5] == addr2->data[5])
    ;
}

Bekijk het live (en branchless) hier