Ir para conteúdo
Fórum Script Brasil

Tharso

Membros
  • Total de itens

    3
  • Registro em

  • Última visita

Sobre Tharso

Tharso's Achievements

0

Reputação

  1. Faz um tempo já que me interessei pelo paradigma MapReduce que foi desenvolvido pelo Google. Comecei então a dar uma lida nos frameworks MapReduce para multi-core, e encontrei Metis, que está desenvolvido em C. Comecei a fazer algumas pequenas mudanças no código de acordo com o objetivo que eu queria. Utilizando um programa de Contar Palavras, Metis paralelamente usando threads por cores, vai armazenando cada palavra em uma estrutura de dados do tipo tabela Hash, onde cada entrada da tabela hash possui uma árvore B+tree. A maioria das outras soluções que eu havia encontrado utilizam arrays nas entradas da tabela hash. A B+Tree é uma variação da árvore B. Em uma árvore-B+, contrastando com uma árvore-B, todos os dados são gravados nas folhas. Os nodos internos contêm apenas chaves e apontadores da árvore. Todas as folhas estão no mesmo nível mais baixo. Os nodos das folhas também estão ligados entre si como uma lista enlaçada para efectuar consultas facilmente. Uma das modificações que eu estava tentando fazer é em cada entrada da tabela hash, onde existe uma b+tree, pegar todas as chaves armazenadas ali e serializo elas, ou seja, meto em um array, para pode guardar em um arquivo, já que a idéia de guardar toda a estrutura não me interessa, só preciso dos dados. Para isso eu preciso recorrer toda a árvore e ir trazendo as chaves e os valores nela armazenada. Eu posso recorrer ela de 2 maneiras, a primeira é como uma árvore normal, a segunda é utilizando a lista enlaçada entre as folhas, que me parece muito mais interessante. O problema é que nesse momento eu não estou sabendo como saltar de um nó para o outro através do ponteiro da lista enlaçada, ou seja, eu só consigo imprimir os valores do nó mais a esquerda, e não consigo imprimir os outros. A estrutura de dados que a aplicação utiliza é essa: typedef struct { int map_rows; int map_cols; htable_entry_t **mbks; } mapper_t; typedef struct { btree_t v; } htable_entry_t; typedef struct { uint64_t nkeys; short nlevel; btnode_t *root; } btree_t; typedef struct { short nkeys; void *parent; keyvals_t arr[2 * order + 2]; //order é igual 3 void *next; } btnode_t; typedef struct { void *key; void **vals; unsigned len; unsigned alloc_len; unsigned hash; } keyvals_t; A função que eu estava desenvolvendo para percorrer a árvore é essa int H_table_entry_Verify() { block_key unique_key; int i,j; for(j=0;j<mapper.map_rows;j++) { for(i=0;i<mapper.map_cols;i++){ htable_entry_t *bufferHKey = &mapper.mbks[j][i]; btree_t *bptree = &mapper.mbks[j][i].v; btnode_t *node = bptree->root; printf("btreeroot %d btreenkeys %d btreenlevel %d Nodenkeys %d Nodenext %d NodeParent %d\n",bptree->root, bptree->nkeys, bptree->nlevel, node->nkeys, node->next, &node->parent); for(int u = 0; u <= bptree->nlevel; u++){ btnode_t *node = bptree->root; for(int h = 0; h < node->nkeys; h++){ printf("%s -- ",node->arr[h].key); if(h==node->nkeys -1) printf("\n\n"); } } } } return 1; } Com essa função eu consigo acessar a entrada hash desejada, descer pela árvore e imprimir as chaves que estão no nó mais a esquerda. Dai em diante eu não sei como avançar para os outros nós, onde estão as outras chaves. Alguém sabe como eu posso fazer isso, como manipulo os ponteiros para saltar ao próximo nó? Teoricamente btnode_t.next é quem tem esse ponteiro.
  2. Tharso

    [DUV]Matrizes

    Esse é um exemplo que eu achei em algum lugar já tem um tempinho e estava pronto, você pode modifica-lo já que a lógica já está ai, e você so tem que acertar os detalhes para ficar como você quer. Espero ter ajudado. #include <stdio.h> #include <stdlib.h> void main(void) { int i,j,k,l,c; float m[10][10]; float m1[10][10]; float maux[10][10]; printf("digite a quntidade de linhas das matrizes \n"); scanf("%i",&l); printf("\n\n"); printf("Digite a quantidade de colunas das matrizes\n"); scanf("%i",&c); printf("\n\n"); printf("Digite os elementos da matriz 1"); printf("\n\n"); for(i=0;i<l;i++) { for(j=0;j<c;j++) { printf("elemento %i%i -->",i,j); scanf("%f",&m[i][j]); } } printf("\n\n"); printf("Digite os elementos da matriz 2"); printf("\n\n"); for(i=0;i<l;i++) { for(j=0;j<c;j++) { printf("elemento %i%i -->",i,j); scanf("%f",&m1[i][j]); maux[i][j]=0; } } for(i=0;i<l;i++) { for(j=0;j<c;j++) { for(k=0;k<l;k++) { maux[i][j]=maux[i][j]+(m[i][k]*m1[k][j]); } } } printf("\n\n"); printf("As matrizes multiplicadas geram a matriz abaixo"); printf("\n\n"); for(i=0;i<l;i++) { printf("\n"); for(j=0;j<c;j++) { printf("% 6.2f",maux[i][j]); } } printf("\n\n"); }
  3. Tharso

    Utilizando mmap

    Olá pessoal. Estou trabalhando em uma aplicação de contar palavras de um arquivo que está no disco, e utiliza a estratégia do produtor/consumidor e double buffer, utilizando um thread para fazer o trabalho do produtor e outro thread para fazer o trabalho do consumidor. No geral o produtor é mais lento que o consumidor, já que ele lê os dados disco e os armazena em uma matriz, e já que os dados estão em memoria o consumidor é mais rápido em validar cada palavra, e disponibilizar a posição da matriz novamente para o produtor colocar outra palavra ali. Com a idéia de fazer o produtor trabalhar mais rápido, resolvi utilizar mmap, que mapea meu arquivo em uma região de memória. Até ai tudo lindo, funciona muito bem, diminui em 20% o tempo da minha aplicação para inputs grandes. Porém analizando a aplicação comecei a rever a estratégia em que o meu produtor preenche a minha matriz, e comecei a fazer modificações sobre isso, ai começa o meu problema. Ignorando o mmap, a minha estratégia lendo diretamente o arquivo do disco seria a seguinte: ao invés de preencher a minha matriz, 1 caracter por vez como eu faço atualmente, eu vou preencher ela com uma string de 10 caracteres por vez, não dando importância se existe espaço, ponto, ou qualquer outro tipo de sujeira, isso eu vou elimar em um pós-processamento. Para essa situação eu utilizei um código parecido com o abaixo, onde vou controlando a posição do ponteiro para saltar em blocos de 10bytes sabendo que cada char é 1byte. FILE *arquivo = open ("testesmr.txt", O_RDONLY); char buffPart[10]; if (lseek (arquivo, 10, SEEK_SET) < 0) { perror ("lseek"); exit(1); } read(arquivo, buffPart, 10); printf("String %s\n",buffPart); Agora quando eu coloco o mmap no meio, não sei como mover esse "ponteiro" pra onde eu quero, no caso, move-lo de 10 em 10 bytes. Para utilizar o mmap eu acrescentei as seguintes linhas de código: char *arquivoMap; struct stat sb; arquivoMap = mmap (0, sb.st_size, PROT_READ, MAP_SHARED, arquivo, 0); if (arquivoMap == MAP_FAILED) { perror ("mmap"); exit(1); } Quando eu utilizo o read() para ler o conteúdo do "arquivoMap", ele não me retorna nada, ou seja, como eu faço pra ler os dados que estão mapeados pelo mmap? Como eu faço para fazer a mesma coisa que demonstrei no código acima, porém utilizando o mmap no contexto ?
×
×
  • Criar Novo...