Home

Performance Measure

Donald Knuth, em seu livro The Art of Computer Programming, define como uma das propriedades básicas de algoritmos a finitude (finiteness). Um algoritmo possui essa propriedade se as regras aplicadas por ele concluem em um período de tempo razoável. Como quantificar o que é razoável ou não depende do problema o qual o algoritmo tenta resolver e do quão rápidos são os algoritmos já conhecidos que resolvem esse problema.

O desempenho de algoritmos quanto a finitude pode ser representado por equações que representam seu tempo de execução. Por exemplo, dado o problema de busca por um elemento $k$ em um dado conjunto $V$, sabe-se que o algoritmo que tem como princípio comparar $k$ com todos os elementos de $V$ possui tempo de execução proporcional à $|V|$ (cardinalidade de $V$). Considere o seguinte algoritmo.

$\text{algorithm search}(V, k)$
1.$\qquad n \leftarrow |V|$
2.$\qquad \text{for } i \text{ from } 1 \text{ to } n \text{ do}$
3.$\qquad|\qquad \text{if } V[i] = k \text{ then}$
4.$\qquad|\qquad|\qquad \text{return } i$
5.$\qquad \text{return } 0$

Caso o elemento $k$ não esteja no conjunto $V$, tem-se que o laço de repetição não irá terminar prematuramente com um retorno na linha 4. Nesse cenário, denominado pior caso, o tempo de execução desse algoritmo depende apenas da quantidade de elementos em $V$, uma vez que o laço de repetição da linha 2 irá iterar sobre todos os elementos de $V$. Considerando $n=|V|$ , e que o custo de execução em segundos da linha $i$ é dados por $c_i$, tem-se que o tempo de execução do algoritmo nesse caso pode ser representado pela equação $$T_w(n)=c_1 + (n+1)c_2 + n c_3 + c_5\text{ ,}$$ onde o $w$ em $T_w(n)$ indica que o tempo é o de pior caso (do inglês, worst).

NOTA - É um erro comum achar que a linha 2 executa apenas $n$ vezes. Como o laço de repetição precisa de uma condição de parada, o valor de $i$ chega até $|V| + 1$ e, nesse caso, o laço verifica que a condição de continuidade não é mais satisfeita e o algoritmo segue sua execução para a linha 5.

É possível reorganizar os termos da equação de forma a chegar na equação $$T(n)=na+b \text{ ,}$$ onde a constante $a=c_2+c_3$ e a constante $b=c_1+c_2+c_5$. Nesse documento, é descrito como é possível verificar esse resultado a partir da implementação desse algoritmo em quatro em linguagens de programação distintas.

C

SYNOPSIS
       #include <time.h>

       int clock_gettime(clockid_t clockid, struct timespec *tp);

struct timespec {
    time_t   tv_sec;        /* seconds */
    long     tv_nsec;       /* nanoseconds */
};

#include <stdio.h>
#include <time.h>
#include <unistd.h>

int main(int argc, char **argv)
{
    struct timespec a, b;
    unsigned int t;

    clock_gettime(CLOCK_MONOTONIC, &b);
    sleep(1);
    clock_gettime(CLOCK_MONOTONIC, &a);

    t = (a.tv_sec * 1e9 + a.tv_nsec) - (b.tv_sec * 1e9 + b.tv_nsec);

    printf("%u\n", t);

    return 0;
}

int search(int *v, unsigned int n, int k)
{
    while (n-- > 0)
    {
        if (v[n] == k)
            return n;
    }
    return -1;
}

Java

import java.lang.System;
import java.lang.Thread;

public class Measure
{
    public static void main(String[] args) throws InterruptedException 
    {
        long a, b, t;

        b = java.lang.System.nanoTime();
        java.lang.Thread.sleep(1000);
        a = java.lang.System.nanoTime();

        t = (a - b);

        java.lang.System.out.println(t);
    }
}

public class Measure
{
    public static int search(ArrayList<Integer> v, int k)
    {
        int n = v.size();

        while (n-- > 0)
        {
            if (v.get(n) == k)
                return n;
        }

        return -1;
    }
}

Python

import time

if __name__ == "__main__":

    b = time.time_ns()
    time.sleep(1)
    a = time.time_ns()

    t = a - b

    print(t)

def search(v, k):
    n = len(v)
    while (n > 0):
        n = n - 1
        if v[n] == k:
            return n
    return -1

Rust

use std::{thread, time};

fn main()
{
    let duration = time::Duration::from_secs(1);

    let now = time::Instant::now();
    thread::sleep(duration);
    let measure = now.elapsed();

    println!("{}", measure.as_nanos());
}

fn search(v: &mut Vec<i32>, k: i32) -> i32
{
    let mut n = v.len();

    while n > 0
    {
        n = n - 1;

        if v[n] == k
        {
            return n as i32;
        }
    }

    return -1;
}

Comparação

References

[1] Donald Knuth. The Art of Computer Programming.