Google Treasure Hunt 2 - MapReduce?

Para resolver o Google Treasure Hunt 2, decidi usar um velho programa para busca de arquivos implementado em C++ usando multi-threading. Eu mudei algumas partes do código, só para garantir que possa fazer a busca pelos 2 padrões especificados no problema, e escolhi usar o framework Qt (da Trolltech) que tem algumas funções muito legais para lidar com arquivos, e isso é realmente verdade – você não precisa de mais nada, a não ser as classes QFile e QDir e derivadas delas.

Se você gosta de programação distribuída, talvez você já tenha ouvido falar no modelo MapReduce, desenvolvido pela Google (www.google.com). De acordo com Jeffrey Dean e Sanjay Ghemawat, em um artigo (“Distributed Programming with MapReduce”) escrito para o interessante livro “Beautiful Code” (O’Reilly, 2007), “MapReduce was developed as a way of simplifying the development of large-scale computations at Google.” (tradução: “O MapReduce foi desenvolvido como uma forma de simplicar o desenvolvimento de processamento em larga-escala no Google”) Acredito que esse problema proposto no Google Treasure Hunt não seja realmente um “processamento em larga-escala”, mas eu gostei da forma como o MapReduce funciona, e decidi aplicar esse conceito ao meu programa.

Aqui está o problema número 2 do Google Treasure Hunt:

Here is a random zip archive for you to download:
GoogleTreasureHunt08_14338682343771558225.zip

Unzip the archive, then process the resulting files to obtain a numeric result. You'll be taking the sum of lines from files matching a certain description, and multiplying those sums together to obtain a final result. Note that files have many different extensions, like '.pdf' and '.js', but all are plain text files containing a small number of lines of text.

Sum of line 4 for all files with path or name containing BCD and ending in .js
Sum of line 5 for all files with path or name containing foo and ending in .xml
Hint: If the requested line does not exist, do not increment the sum.

Multiply all the above sums together and enter the product below.
(Note: Answer must be an exact, decimal representation of the number.)

Se você der uma olhada no código fonte, existem 2 threads; o primeiro (Mapper) obtêm a lista de arquivos com um padrão de nomes fornecido (no meu caso, nomes contendo “BCD” e com extensão “.js”, ou contendo “foo” e terminando com “.xml”); o segundo thread (Reducer) utiliza a lista com nomes de arquivos do thread Mapper e faz uma outra busca mais profunda dentro de cada um dos arquivos pré-selecionados (para obter os valores de números nas linhas de número “4”). O principal método do Mapper é o seguinte:

bool FileSearchMap::depthFirstTraversal(const QString& currentDir)

{

QDir dirP(currentDir);

QString temp;

QString fileName;

QStringList entryP = dirP.entryList();

QStringListIterator entryL(entryP);

while (entryL.hasNext())

{

producerMutex.lock();

if (myFileCount == 5)

{

bufferNotFull.wait(&producerMutex);

} // if - mutex and signal

producerMutex.unlock();

fileName.clear();

temp = entryL.next();

if ((temp != ".") && (temp != ".."))

{

fileName = currentDir;

fileName.append('\\');

fileName.append(temp);

if (isDirectory(fileName))

{

depthFirstTraversal(fileName);

}

else

{

if (isRegular(fileName))

{

unsigned int ftype = 0;

if ( ( fileName.endsWith(".js") ) &&

( fileName.contains("BCD") ) )

ftype = TXT_FILE_PATTERN;

else if ( ( fileName.endsWith(".xml") ) &&

( fileName.contains("foo") ) )

ftype = XML_FILE_PATTERN;

if ( ftype != 0 )

{

DirEntry dentry( fileName, ftype );

queueMutex.lock();

textFiles.push(dentry);

queueMutex.unlock();

producerMutex.lock();

++myFileCount;

producerMutex.unlock();

bufferNotEmpty.wakeAll();

}

}

} // if - isDirectory / isRegular

} // if

} // while

return true;

}

O método acima sera chamado exatamente uma vez, a partir do método “run” da minha implementação do QThread no Mapper. Colocando o método depthFirstTraversal para rodar, primeiramente ele obtêm todos os arquivos do diretóro, chamando o método entryList, da classe QDir. Então um iterator é instanciado sobre a lista de arquivos anteriormente obtida, e, enquanto estiver iterando sobre os arquivos, e antes que qualquer coisa eu faço uma chamada à função wait da estrutura QWaitCondition: a “wait condition” é um tipo de variável de condição usada para sincronizar threads, interrompendo-o no caso de ter obtido 5 arquivos (claro, pode ser qualquer número que você queira). Porque obter exatamente 5 arquivos e interromper a execução, esperando para que a estrutura QWaitCondition seja liberada? Isso é usado de forma a criar um buffer com capacidade para 5 arquivos (no máximo), a partir do qual o thread Reducer pode iterar sobre cada um dos arquivos listados pelo thread Mapper, abrir cada um desses arquivos, e procurar pelo critério de busca dado. Dessa forma, o thread Reducer pode lidar apenas com uma lista de 5 arquivos, esgotá-la, e depois permitir que o Mapper preencha com mais alguns novos arquivos encontrados. Essa é a primeira regra usada para sincronizar os 2 threads: “Mapper, comece a cobrir o buffer com os nomes dos arquivos encontrados, até que ele tenha 5 elementos. Daí, espere até que o Reducer consuma alguns desses arquivos, pois a partir disso você pode obter mais alguns arquivos. Faça isso até o fim dos tempos”. Agora, o thread Reducer, obtendo todos os arquivos que o Mapper consiga procurar:

void KeySearchReduce::run()

{

DirEntry dirEntry;

int cnt = 0;

do

{

prod->producerMutex.lock();

if (prod->myFileCount == 0)

{

prod->bufferNotEmpty.wait(&prod->producerMutex);

if (prod->isSearchDown())

{

prod->producerMutex.unlock();

return;

}

}

prod->producerMutex.unlock();

prod->queueMutex.lock();

dirEntry = prod->getFirstTextFile();

prod->queueMutex.unlock();

QFile infile(dirEntry.getFileName());

if (!infile.open(QIODevice::ReadOnly | QIODevice::Text) )

continue;

QString line;

unsigned int i = 0;

QTextStream in(&infile);

if ( dirEntry.getFileType() ==

FileSearchMap::TXT_FILE_PATTERN ) {

while (!in.atEnd())

{

line = in.readLine();

++i;

if ( i == 4 ) {

lineP2Count += atol(line.toLocal8Bit().constData());

++foundCount;

break;

}

} // while

} else if ( dirEntry.getFileType() ==

FileSearchMap::XML_FILE_PATTERN ) {

while (!in.atEnd())

{

line = in.readLine();

++i;

if ( i == 5 ) {

lineP1Count += atol(line.toLocal8Bit().constData());

++foundCount;

break;

}

} // while

} // if - getFileType()

infile.close();

prod->producerMutex.lock();

prod->myFileCount--;

prod->producerMutex.unlock();

prod->bufferNotFull.wakeAll();

} while (!prod->isSearchDown());

}

O Reducer na primeira linha do comando “do” diz o seguinte: “Ei Mapper, você tem algum arquivo para que eu possa procurar pelo informação numérica na linha X? Caso você não tenha arquivo algum, eu esperarei um pouco, até que você tenha algo para mim...” Então, para cada arquivo que o thread Reducer processa, ele avisará ao Mapper, de forma a que ele possa alimentar mais o buffer. No caso do Mapper estiver dormindo em um buffer cheio com 5 elementos, ele será acordado e então recomeçará a cobrir o buffer com arquivos – isso é feito com uma chamada a prod->bufferNotFull.wakeAll(), encontrado no fim do loop principal do Reducer. A chamada a wakeAll faz com que todos os threads que estejam dormindo sobre essa variável de condição acordem imediatamente (ou quase). Com isso, o Mapper pode estar dormindo na linha bufferNotFull.wait(&producerMutex), no início do loop de busca, e essa chamada à função wakeAll a partir do Reducer pode liberar o bufferNotFull (uma instância do QWaitCondition), permitindo ao Mapper reiniciar o processo de completar o seu buffer de 5 elementos de novo. Tudo o que o Mapper tem que fazer é cobrir o buffer com nomes de arquivos.

Nós estamos lidando aqui com recursos compartilhados, e os mutexes são de uso obrigatório (veja as referências às instâncias de QMutex no código fonte) uma vez que essa aplicação é multithreaded, e não queremos que ocorram condições de corrida.

Colocando tudo junto:

FileSearchMap* mapper = new FileSearchMap;

KeySearchReduce* reducer = new KeySearchReduce;

mapper->setDirectory( dir );

reducer->setMapper( mapper );

mapper->start();

reducer->start();

mapper->wait();

reducer->wait();

long long a1, a2;

cout << argv[1] << " contains " <<>getFoundCount()

<< " files that contains " <<>getLineCount()

<< " lines for the pattern 1 ( " << (a1 = reducer->getLineP1Count()) <<

" ) and pattern 2 ( " << (a2 = reducer->getLineP2Count()) << " )." << endl;

long long response = a1*a2;

cout << "Response: (" <<>")" << endl;

Aqui, a chamada getLineP1Count() retorna a soma de todos os numeros na linha 4, nos arquivos com o primeiro padrão; e getLineP2Count() faz o mesmo para o padrão de busca 2.

Claro, dá pra resolver o problema todo sem usar capacidade de multithread, mas aí não tem graça! :)

Doctor Dobb's Code Talk

Para quem gosta de ler coisas sobre programação, um excelente site sempre foi o da revista Doctor Dobb's Journal [www.ddj.com]. Agora eles disponibilizaram um serviço de blog para os leitores. As discussões são sempre muito interessantes, para quem gosta de coisas como otimização de código, "thread-local heaps", arrays multi-dimensionais, desenvolvimento de software distribuído, e qual a melhor máquina para programar. Quem tiver a fim de participar, começa dando uma olhada no meu blog:
http://dobbscodetalk.com/index.php?option=com_myblog&task=view&id=531&Itemid=29

Vejo vocês lá!

Google Treasure Hunt 4

O Google resolveu disponibilizar uma espécie de competição, onde são propostos problemas e pede-se a solução deles, cujas respostas sugerem (na verdade, praticamente obrigam) a aplicação de algum recurso computacional. Até onde eu sei, os problemas são únicos para cada candidato, o que inviabiliza qualquer tentativa de “trabalho em conjunto”. Chama-se de “Google Treasure Hunt 2008” [http://treasurehunt.appspot.com/]. O conjunto de problemas apresentado (atualmente, contando com apenas 4) assemelha-se aos vistos em outros campeonatos de programação, como o International Collegiate Programming Contest (ICPC), da Association for Computing Machinery (ACM) [www.acm.org]. Resolvi o último desses problemas (o quarto), e detalho aqui como cheguei à solução.

O problema proposto foi o seguinte:

“Find the smallest number that can be expressed as

the sum of 11 consecutive prime numbers,

the sum of 25 consecutive prime numbers,

the sum of 513 consecutive prime numbers,

the sum of 1001 consecutive prime numbers,

the sum of 1129 consecutive prime numbers,

and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as

the sum of 3 consecutive primes (11 + 13 + 17 = 41) and

the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).”

Para solucionar o problema proposto, resolvi utilizar a linguagem de programação C++, pelos recursos que a STL oferece (estruturas como set’s, vector’s, operações sobre conjuntos, etc.). Antes de tudo, o grande problema foi o de gerar os números primos. De modo que o problema não se refere a um limite razoável para a quantidade de números primos que a solução envolva, gerar uma tabela com todos os números primos até o limite considerável de 100.000, por exemplo, resolvi obter uma listagem pronta com o todos os números primos abaixo de 100 mil [http://members.aol.com/MICRO46/primes_1.zip], um total de exatamente 78498 primos. A razão de usar uma tabela pronta foi que o método que eu estava usando para gerar essa lista de primos demorava algo em torno de 4 minutos... Posteriormente, otimizei o procedimento para durar menos de 0,5 segundos, e gerei o resultado em disco. Contudo, quem não tiver afim de gerar essa quantidade de primos, esses arquivos prontos são uma mão na roda. Com o conjunto de primos em mãos, apliquei o procedimento seguinte:

1) Calcular as somas dos números primos em cada um dos intervalos (11, 25, 513, 1001, 1129) – isso implica em somar os primos em todos os subintervalos de tamanho 11, por exemplo, dentro do conjunto de primos, o que gerou uma seqüência de 78488 intervalos de tamanho 11, até 77.370 subintervalos de tamanho 1129;

2) Fazer uma intersecção de conjuntos, 2 a 2, com os conjuntos resultantes da operação acima (por exemplo, as somas de todos os subintervalos de tamanho 11 geram um conjunto) – o objetivo é obter as somas que são comuns entre esses conjuntos de somatórios de primos;

3) Ordenar o conjunto intersecção resultante e mostrar o primeiro valor (ou seja, o menor).

Para as etapas 1 e 2, o método que usei foi o seguinte:

void

sum_subintervals(const vector<long>& primes, unsigned long max,

set<long>* pivot)

{

unsigned long soma = 0, j = 0, old_sum = 0;

set<long> sums;

for (j = 0; j <>

{

soma += primes.at(j);

} // for

sums.insert(soma);

while ( (j <>

{

old_sum = soma;

soma = old_sum - primes.at(j-max) + primes.at(j);

++j;

sums.insert(soma);

}

set<long> s;

if (pivot->size() != 0)

{

set_intersection(sums.begin(), sums.end(), pivot->begin(),

pivot->end(), inserter(s, s.end()) );

pivot->clear();

copy(s.begin(), s.end(), inserter(*pivot, pivot->begin()));

}

else

{

copy( sums.begin(), sums.end(), inserter(*pivot, pivot->end()) );

}

}

O código é pouco óbvio, mas eu explico: o que ele faz é pegar intervalos de um certo tamanho (11, 25, 513, etc.) e somar os elementos nesse intervalo. Uma solução bastante elementar seria tentar somar diretamente todos os valores, e fazer isso para cada intervalo. Computacionalmente, no entanto, esse método repete desnecessariamente operações de soma (a maior parte dos elementos seriam somados duplicados entre subintervalos consecutivos). Foi exatamente nessas somas supérfluas que o algoritmo que eu fiz gerou otimizações. Por exemplo, o primeiro subintervalo de tamanho 11 é o seguinte:

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}

O próximo subintervalo é assim:

{3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}

Qual a diferença entre os 2? No segundo, inseriu-se o 37 e removeu-se o 2. De forma geral, cada subintervalo adiciona à seqüência anterior o próximo elemento primo, e remove o primeiro elemento da sequência anterior do resultado. Aplicando esse método iterativamente, foi possível reduzir a complexidade da solução de uma exponencial (em função do quadrado do conjunto de primos) para uma solução linear, com o esforço de execução variando apenas sobre o tamanho da tabela de primos.

Pra finalizar, a parte mais simples do código apenas mostra o algoritmo acima rodando em cima de cada constante do problema:

set<long> all_sums;

int nums[5] = { 11, 25, 513, 1001, 1129 };

int i;

for (i = 0; i < 5; i++)

{

sum_subintervals(primes, nums[i], &all_sums);

}

if (all_sums.size() > 0)

cout << "Solution: " << *(all_sums.begin()) << endl;

Nem precisei ordenar o conjunto resultante, porque a classe template “set” da Standard Template Library já adiciona os elementos em ordem na estrutura. Quando tudo dá certo, na submissão aparece isso:

Correct answer: XXXXXXXXXX
Your answer was: Correct

Your answer was correct! Congratulations, you're part-way there.
There will more questions over the coming weeks, and the first person to answer them all correctly will win a prize, so keep trying!

Boa sorte!