J'ai eu une interview aujourd'hui où ils m'ont demandé d'écrire deux fonctions "C", une pour extraire un seul bit et autre pour extraire une gamme de morceaux d'un personnage. J'ai pris un peu de temps et j'ai proposé ces méthodes. Mais l'intervieweur m'a demandé si je pouvais accélérer le code plus loin (en termes de cycles de la CPU) et s'il y a une portée de optimisation que je pouvais faire pour y parvenir.
J'étais manifeste clairement et je suis curieux de savoir comment feriez-vous cela?
6 Réponses :
Dans ExtractBit, si vous changez d'abord, vous pouvez masquer avec Dans la deuxième fonction, j'affirmerais que 1 au lieu de (1 << POS) .
Considérant que POS est un argument de la fonction, qui économise un calcul.
retour (octet >> POS) & 1;
démarrage et offset sont à la fois positifs au lieu d'affirmer que leur somme est positive, il est plus logique de ce sens.
Je les ferais juste non signé INT s.
Ouais. Pour l'extraction d'une première pensée, il s'agissait d'une table de recherche, mais cela sera probablement plus efficace sur les processeurs modernes. Vous pouvez également déclarer la fonction comme inline dans C ++ ou C99, qui enregistrera l'appel de fonction. Comme Pete dit, vous pouvez rendre les ARG non signé Ints. Ou vous pouvez lancer les valeurs de test de cette manière dans les affirmations et éliminer les tests contre zéro - par exemple. affirmer (((non signé INT) (décalage de départ)) <8)); - Les valeurs négatives se transformeront en très grandes valeurs positives et se transforment vraiment simplement en un opcode de comparaison de la machine légèrement différente.
une table de recherche?
Pour l'extraction unique, vous auriez besoin d'une table de 256 entrées pour chacun de 8 bits possibles - qui est une table de 2 Ko si elle est stockée dans des caractères (256 octets si vous comprenez tout et utilisez des opérations de bits pour obtenir les valeurs - mais ensuite Vous êtes de retour à l'endroit où vous avez commencé). Pour les gammes, vous ne pouvez pas définir sensiblement les tables pour toutes les 36 plages possibles de bits. Bien sûr, si vous avez une autre structure que celle d'une table de recherche indexée par la valeur de l'octet et la position du bit (ou la plage de bits), il peut y avoir des alternatives, mais vous devez expliquer cela.
Un autre que vous faites dans la gamme de bits: comme << 1 n'est rien d'autre que * 2 , vous pouvez Faites cette opération sur votre constante (laquelle si vous travaillez sur Signle Byte est simplement en train de vous débarrasser de LSB).
Astuce. Une autre façon serait d'injecter (8-décalsets) zéros à gauche par quelque chose comme (non signé INT) 0XFF >> (8 - décalage) , cela signifie qu'il y a toujours Une opération arithmétique sur décalse mais elle enregistre l'opération à 1 complément.
Vous pouvez accélérer la première fonction en tournant d'abord à droite, puis masquant le bit: ceci vous permet d'économiser une opération. pour la deuxième question , Je suppose que Bien sûr, vous devez faire attention aux gammes, comme vous l'avez fait dans votre code. EDIT: Si vous veulent démarrage est le premier bit du morceau que vous souhaitez extraire et offset est le nombre de bits dans le morceau dont vous avez besoin.
Ensuite, vous pouvez utiliser ceci: extractivité (b, i, 0) pour se comporter comme extractebit (b, i) et extraire un seul bit en position I, cette variante fait que:
Devrait-il être «retour (octet >> de départ) & (1U << (offset + 1))" Etant donné que le décalage commence à partir de zéro? ExtractBitRange (3,0) équivaut à l'extracteur (3), tandis que l'extraction (3,1) récupérerait des bits (3,4)?
J'ai supposé offset est combien de bits dont vous avez besoin. Si vous voulez l'équivalence extractivité (x, i, 0) == Extrexitbit (x, i), modifiez-le ensuite à revenir (octet >> de départ) & ((1 << (offset + 1)) -1) Notez que < code> (1 << howmany) -1 est un moyen pratique d'obtenir howmany des bits consécutifs, par exemple (1 << 3) -1 = 2 ** 3-1 = 8-1 = 7, trois consécutifs. Ceci est utile pour le masquage.
Si vous voulez être vraiment rapide, vous pouvez utiliser une table de recherche. Je suppose que c'est ce que l'intervieweur allait (comme une réponse finale à «Comment puis-je faire cela plus rapide»).
Fondamentalement, cela signifie que vous créez à l'avance une énorme table, cartographiant toutes les combinaisons possibles de paramètres à le résultat approprié. Par exemple, vous auriez: évidemment, il faudrait être placé dans des structures de données C valides (tableaux, indexés par l'octet et le POS). Cela vous permettrait, dans votre fonction, de retourner une place dans un tableau, en fonction du système d'indexage que vous choisissez. pour la première fonction, cela ne prendrait pas trop de mémoire. Nous parlons d'une valeur d'un octet de valeurs (un octet peut avoir 256 valeurs différentes) fois 8 valeurs possibles pour le démarrage de POS, qui fait un tableau de 2048. Je suppose que l'intervieweur vient de vouloir Pour répondre à ce que ce soit un moyen de l'accélérer, puis de fournir la réflexion ci-dessus pour tenter d'estimer la quantité d'espace qu'elle coûterait par rapport au temps sauvegardé.
int extractBit(int byte, int pos)
{
if( !((pos >= 0) && (pos < 16)) )
{
return 0;
}
return ( ( byte & (1<<pos) ) >> pos);
}
int _tmain()
{
// TODO: Please replace the sample code below with your own.
int value;
signed int res,bit;
value = 0x1155;
printf("%x\n",value);
//Console::WriteLine("Hello World");
//fun1();
for(bit=15;bit>=0;bit--)
{
res =extractBit(value,bit);
printf("%d",res);
}
return 0;
}
L'utilisation de C ++ TMP donnerait une vitesse d'exécution incroyable.
:)Je ne pense pas que les modèles ajouteraient quoi que ce soit. Un compilateur devrait pouvoir optimiser l'enfer de ces fonctions si elles sont appelées avec des constantes ...
Pour éviter les problèmes de transfert et d'opérations logiques sur des valeurs signées, je ferais tous les paramètres aux fonctions
non signé . En plus, s'ils ne sont pas signés, vous n'avez pas besoin de rechercher> = 0 .@rajacan: Notez que l'intervieweur était probablement plus intéressé par la manière dont vous avez réagi à l'inconnu et à être contesté et poussé pour plus d'informations qu'il n'était dans la réponse à la question spécifique. Comment réagissez-vous sous pression? Dans quelle mesure pensez-vous sur vos pieds? C'est ce que vous devez travailler, bien plus que la réponse à cela, ou toute autre question de twidding.
@sth: "TMP" représente une programmation de modèle-méta. Cela calcule la valeur au moment de la compilation et met simplement le résultat dans le code. Je ne suis pas au courant de nombreuses autres techniques d'optimisation qui donnent exactement le temps d'exécution zéro.
:)