Mariel Frank e Sonny Li, autores do curso Learn C++, da Codecademy, tiveram recentemente a chance de entrevistar com a Dra.
Como parte da entrevista, ele respondeu às perguntas C++ mais votadas no Avance Network. Embora toda a entrevista valha a pena ler, a Codecademy generosamente nos permitiu republicar a parte de Perguntas e Respostas da entrevista.
Se você já se perguntou se uma resposta no Avance Network era definitiva, aqui está sobre o mais próximo que você vai chegar de certo (embora esperamos que alguém discorde).
Por que processar uma matriz classificada é mais rápido do que processar uma matriz não classificada?
Isso soa como uma pergunta de entrevista. É verdade? Como você sabe? É uma má ideia responder perguntas sobre eficiência sem antes fazer algumas medições, por isso é importante saber medir.
Então, eu tentei com um vetor de um milhão de inteiros e consegui:
Already sorted 32995 milliseconds
Shuffled 125944 milliseconds
Already sorted 18610 milliseconds
Shuffled 133304 milliseconds
Already sorted 17942 milliseconds
Shuffled 107858 milliseconds
Eu corri isso algumas vezes para ter certeza. Sim, o fenômeno é real. Meu código-chave era:
void run(vectorint v, const string label)
{
auto t0 = system_clock::now();
sort(v.begin(), v.end());
auto t1 = system_clock::now();
cout label
duration_castmicroseconds(t1 — t0).count()
” milliseconds”;
}
void tst()
{
vectorint v(1’000’000);
iota(v.begin(), v.end(), 0);
run(v, “already sorted “);
std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
run(v, “shuffled “);
}
Pelo menos o fenômeno é real com este compilador, biblioteca padrão e configurações otimizadoras. Diferentes implementações podem e dão respostas diferentes. Na verdade, alguém fez um estudo mais sistemático (uma rápida pesquisa na web vai encontrá-lo) e a maioria das implementações mostram esse efeito.
Uma das razões é a previsão de ramificação: a operação chave no algoritmo de classificação é “if(v[i] pivot]) …” ou equivalente. Para uma sequência classificada, esse teste é sempre verdadeiro, enquanto, para uma sequência aleatória, o ramo escolhido varia aleatoriamente.
Outra razão é que quando o vetor já está classificado, nunca precisamos mover elementos para sua posição correta. O efeito desses pequenos detalhes é o fator de cinco ou seis que vimos.
Quicksort (e classificação em geral) é um estudo complexo que tem atraído algumas das maiores mentes da ciência da computação. Uma boa função de classificação é resultado tanto da escolha de um bom algoritmo quanto da atenção ao desempenho do hardware em sua implementação.
Se você quiser escrever código eficiente, você precisa saber um pouco sobre arquitetura de máquina.
O que é o — em C++?
Essa é uma velha pergunta. Não há — em C++. Considerar:
if (p–m == 0) f(p);
Certamente parece que há um —- e por declaração adequada p e m, você pode até mesmo obter isso para compilar e executar:
int p = 2;
int m = 0;
if (p–m == 0) f(p);
Isso significa: veja se p– é maior que m (é), e então compare o resultadotruea 0. Bem true != 0, então o resultado é false e f() não é chamado. Em outras palavras:
if ((p–) m == 0) f(p);
Por favor, não perca muito tempo com essas perguntas. Eles têm sido populares para os novatos confusos desde antes de C++ ser inventado.
O Guia e Lista definitiva do Livro C++
Infelizmente, não há uma lista de livros C++definido. Não pode haver um. Nem todos precisam da mesma informação, nem todos têm o mesmo histórico, e as melhores práticas C++ estão evoluindo.
Fiz uma pesquisa na web e encontrei um conjunto desconcertante de sugestões. Muitos estavam seriamente desatualizados e alguns eram ruins desde o início. Um novato procurando um bom livro sem orientação ficará muito confuso!
Você precisa de um livro porque as técnicas que tornam o C++ eficaz não são facilmente captadas em alguns blogs sobre tópicos específicos — e, claro, os blogs também sofrem de erros, datados e explicações ruins. Muitas vezes, eles também se concentram em coisas novas avançadas e ignoram os fundamentos essenciais.
Recomendo minha Programação: Princípios e Práticas Usando C++ (2ª Edição) para pessoas que estão começando a aprender a programar, e um Tour de C++ (2ª Edição) para pessoas que já são programadoras e precisam saber sobre o C++moderno. Pessoas com forte formação matemática podem começar com “Descobrindo C++: Um Curso Intensivo para Cientistas, Engenheiros e Programadores” de Peter Gottschling.
Uma vez que você começa a usar C++ de verdade, você precisa de um conjunto de diretrizes para distinguir o que pode ser feito e o que é uma boa prática. Para isso, recomendo as Diretrizes C++ Core no GitHub.
Para boas explicações breves sobre recursos individuais da linguagem e funções de biblioteca padrão, recomendo www.cppreference.com.
#4. Quais são as diferenças entre uma variável de ponteiro e uma variável de referência em C++?
Ambos são representados na memória como um endereço de máquina. A diferença está no uso deles.
Para inicializar um ponteiro, você dá-lhe o endereço de um objeto:
int x = 7;
int* p1 = x;
int* p2 = new int{9};
Para ler e escrever através de um ponteiro, usamos o operador de dereferência (*):
*p1 = 9; // write through p1
int y = *p2; // read through p2
Quando atribuímos um ponteiro a outro, ambos apontarão para o mesmo objeto:
p1 = p2; // now p1 p2 both point to the int with the value 9
*p2 = 99; // write 99 through p2
int z = *p1; // reading through p1, z becomes 99 (not 9)
Observe que um ponteiro pode apontar para diferentes objetos durante sua vida útil. É uma grande diferença de referências. Uma referência é vinculada a um objeto quando é criado e não pode ser feita para se referir a outro.
Para referências, o dereferenciamento está implícito. Você inicializa uma referência com um objeto e a referência leva seu endereço.
x = 7;
int r1 = x;
int r2 = *new int{9};
Operador novo retorna um ponteiro, então eu tive que dereferencia-lo antes de atribuí-lo usando-o para inicializar a referência.
Para ler e escrever através de uma referência, basta usar o nome da referência (sem dereferemento explícito):
r1 = 9; // write through r1
int y = r2; // read through r2
Quando atribuímos uma referência a outra, o valor referido será copiado:
r1 = r2; // now p1 and p2 both have the value 9
r1 = 99; // write 99 through r1
int z = r2; // reading through r2, z becomes 9 (not 99)
Tanto as referências quanto os ponteiros são frequentemente usados como argumentos de função:
void f(int* p)
{
if (p == nullptr) return;
// …
}
void g(int r)
{
// …
}
int x = 7;
f(x);
g(x);
Um ponteiro pode ser o nullptrentão temos que considerar se ele aponta para alguma coisa. Uma referência pode ser assumida para se referir a algo.
#5. Como eu iterado sobre as palavras de uma corda?
Use um stringstreammas como você define “uma palavra”? Considere “Mary tinha um pouco de cordeiro.” É a última palavra “cordeiro” ou “cordeiro”? Se não houver pontuação, é fácil:
vectorstring split(const string s)
{
stringstream ss(s);
vectorstring words;
for (string w; ssw; ) words.push_back(w);
return words;
}
auto words = split(“here is a simple example”); // five words
for (auto w : words) cout w ‘’;
ou apenas:
for (auto w : split(“here is a simple example”)) cout w ‘’;
Por padrão, o pula o espaço branco. Se queremos conjuntos arbitrários de delimitadores, as coisas ficam um pouco mais confusas:
templatetypename Delim
string get_word(istream ss, Delim d)
{
string word;
for (char ch; ss.get(ch); ) // skip delimiters
if (!d(ch)) {
word.push_back(ch);
break;
}
for (char ch; ss.get(ch); ) // collect word
if (!d(ch))
word.push_back(ch);
else
break;
return word;
}
O d é uma operação que diz se um personagem é um delimitador e eu volto “” (a corda vazia) para indicar que não havia uma palavra para retornar.
vectorstring split(const string s, const string delim)
{
stringstream ss(s);
auto del = [](char ch) { for (auto x : delim) if (x == ch) return true; return false; };
vectorstring words;
for (string w; (w = get_word(ss, del))!= “”; ) words.push_back(w);
return words;
}
auto words = split(“Now! Here is something different; or is it? “, “!.,;? “);
for (auto w : words) cout w ‘’;
Se você tem a biblioteca C++20 Range, você não precisa escrever algo assim sozinho, mas pode usar um split_view.
Bjarne Stroustrup é Bolsista Técnica e Diretora Executiva do Morgan Stanley em Nova York e professora visitante na Columbia University. Ele também é o criador do C++.
Para mais informações sobre C++20: https://isocpp.org.
Já leu esse post incrível? Temos algo divertido para você. O Strong The One está de volta! Venha conferir!
