DEV Community: Caio Vidal

Codility GenomicRangeQuery (Resolvido)

Caio Vidal — Thu, 07 May 2020 20:08:31 +0000

Depois de um tempo pensando na solução performática para o desafio do codility GenomicRangeQuery. Consegui resolve-lo com O(n+m).

O desafio é esse: https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

Lendo a questão, a primeira solução que me veio a cabeça, de cara, era muito lenta resultando time complexity de O(n*m), dando timeout em alguns cenários.

Então comecei a pensar em outra possibilidade e cheguei a seguinte solução:

Peguei todas as letras de S e montei a seguinte estrutura:
Supondo o input: "CAGCCTA"

dna: {
   "C": [1,1,1,2,2,2,2],
   "A": [0,1,1,1,1,1,2],
   "G": [0,0,1,1,1,1,1],
   "T": [0,0,0,0,0,1,0]
}

Como podemos ver, montei um array, somando a ocorrência em cada index, dessa forma temos uma linha do tempo e caso queiramos saber qual o menor valor entre dois intervalos, basta fazer:

   for(let l = 0; l < letters.length; l++){
             let letter = letters[l];


             let startSumValue = start > 0 ? dnaMap[letter].sums[start - 1] : 0;
             if(startSumValue != dnaMap[letter].sums[end]){
                result.push(dnaMap[letter].value);
                break;
            }
        }

A solução final ficou assim:

function solution(S, P, Q) {

    var dnaMap = {
        'A': {value:1, last:0, sums:[] },
        'C': {value:2, last:0, sums:[] },
        'G': {value:3, last:0, sums:[] },
        'T': {value:4, last:0, sums:[] },
    }

    var letters = [..."ACGT"];

    var result = [];

    for(let i = 0; i < S.length; i++){
       let dna = S[i];


       letters.forEach((letter)=>{
            var lastValue = dnaMap[letter].last;

            if(S[i] == letter){
                lastValue++;
                dnaMap[letter].last += 1;
            }
            dnaMap[letter].sums.push(lastValue);
       })
    }


    for(let i = 0; i < P.length; i++){

        let start = P[i];
        let end = Q[i];

        if(start == end){
            result.push(dnaMap[S[start]].value);
            continue;
        }

        for(let l = 0; l < letters.length; l++){
             let letter = letters[l];


             let startSumValue = start > 0 ? dnaMap[letter].sums[start - 1] : 0;
             if(startSumValue != dnaMap[letter].sums[end]){
                result.push(dnaMap[letter].value);
                break;
            }
        }


    }

    return result;
}

BinaryGap em duas linhas

Caio Vidal — Thu, 06 Feb 2020 19:06:21 +0000

Depois de solucionar o 1° desafio do codility: BinaryGap, resolvi postar aqui o algoritmo final que usei.

A desafio é o seguinte: Dado um número N, deve-se transforma-lo em binário e retornar o tamanho do maior número de zeros entre 1's.
Com exemplo fica mais fácil entender, olha só:

O número 152 em binário fica: 1 00 11000 - Ele possui apenas 1 bloco com dois zeros, então o retorno seria 2.
O número 15 em binário fica: 1111 - Ele não possui nenhum bloco de zeros, então o retorno seria 0.
O número 3561 em binário fica: 11 0 1111 0 1 00 1- Ele possui 2 blocos com um zero e um bloco com dois zeros, o retorno então seria 2.

Dado o desafio, depois de um tempo tentando soluções com loop e contadores, cheguei a minha 1ª solução que achei aceitável:

function solution(N) {
    const n = "X" + N.toString(2) + "X";
    const list = n.split("1");

    let max = 0;

    list.forEach((i) => {
        if (i.indexOf("X") == -1) {
            max = i.length > max ? i.length : max;
        }
    })

    return max;
}

Depois dessa solução, ficou fácil, bastou alterar o forEach para um map e um reduce, olha aí:

function solution(N) {
    const n = "X" + N.toString(2) + "X";

    return n.split("1").map((i) => i.indexOf("X") == -1 ? i.length : 0)
        .reduce((a, b) => Math.max(a, b))

}

O map retorna o length de cada bloco e o reduce retorno o maior número do array.
Lembrando que embora a solução final tenha ficado mais elegante, a solução mais performática é a 1ª pois existe apenas uma iteração.

Um abraço e até a próxima.

Multiprogramming, Multiprocessing e multitasking

Caio Vidal — Wed, 29 Jan 2020 17:25:49 +0000

Comecei a estudar sobre o assunto e resolvi escrever um pouco sobre o entendimento que tive durante esse tempo. Então, tentarei explicar de maneira simples e clara sobre esses conceitos.

Multiprogramming

Multiprogramming é um dos aspectos mais importante nos sistemas operacionais modernos, ele funciona da seguinte forma:

Sabemos que os sistemas operacionais atuais possuem múltiplos processos a serem executados, como a memória principal é muito pequena para armazenar todos eles, esses processos são inicialmente armazenados numa fila chamada job pool.

O CPU, então, seleciona um desses jobs (processos), armazena na memória principal e começa a executá-lo até que esse processo seja interrompido por algum fator externo ou inicie alguma tarefa de I/O.
No momento da interrupção, o CPU então seleciona outro job no job pool e executa até que o mesmo seja interrompido, fazendo assim uma espécie de rodízio.
Dessa forma o CPU não fica ocioso aguardando os jobs executarem seus trabalhos de I/O (leitura e escrita no disco, comunicação em rede).

Como podemos ver na imagem acima, em nenhum momento o processador ficou ocioso

Multiprocessing

Como vimos, com um CPU, apenas um processo executava por vez.
Hoje em dia, a maioria dos computadores possuem processadores com múltiplos cores permitindo assim que vários processos sejam executados de forma paralela.

Supondo um processador dual-core, dois processos serão executados simultaneamente. Um quad-core executaria 2x mais rápido que um dual-core e 4x mais rápido que um processador com um único core.

Dessa forma podemos concluir que quando falamos de paralelismo, estamos tendo como referência o hardware. Em resumo é a capacidade do CPU executar mais de um processo de forma simultânea através dos múltiplos cores.

Multitasking

Multitasking como o próprio nome já diz, seria a capacidade de executar múltiplas tarefas ao mesmo tempo.
Multitasking é uma extensão lógica de multiprogramming. A maior diferença entre eles é que em multiprogramming havia uma mudança de contexto entre os processos através de uma interrupção, já multitasking é baseado em tempo de compartilhamento (time slicing ou time sharing)

Num modelo de compartilhamento de tempo, o CPU separa um quantum de tempo para cada processo. Por exemplo, 4 processos (A, B, C e D) executam de forma alternada a cada 4 nanosegundos.
Quando o tempo do processo expira, o CPU faz a troca de contexto para outro processo.
Nesse modelo, a troca de contexto acontece de uma forma tão rápida que dá a ilusão que os processos estão sendo executados de forma paralela. Dessa forma o usuário consegue interagir com os processos de forma separada.

Podemos então concluir que os processos estão sendo executados de forma concorrente.

Concorrência vs Paralelismo

Baseado nos conceitos apresentados, vamos então montar uma tabela comparativa entre os dois:

	Concorrência	Paralelismo
Definição	Execução de vários processos em um único core usando compartilhamento de tempo (time slicing)	Execução de múltiplos processos de forma simultânea usando múltiplos cores
Objetivo	Simular paralelismo usando menos recurso de hardware	Paralelismo real e mais performático
Perspectiva	Software Design	Hardware

Bom, é isso. Espero que tenha conseguido explicar da melhor forma esses conceitos tão usados no mundo da programação.

Até a próxima