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.

algorithm search(V, k)
1.  for i from 1 to |V| do
2.      if V(i) = k then
3.          return i
4.  return 0

Caso o elemento $k$ não esteja no conjunto $V$, 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 1 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(n)=(n+1)c_1 + n c_2 + c_4\text{ .}$$

NOTA - É um erro comum achar que a linha 1 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 4.

É 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_1+c_2$ e a constante $b=c_1+c_4$. 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