A complexidade empírica da minha implementação de "classificação de biblioteca" não parece corresponder a nada como O (n log n)

9

Eu ouvi recentemente sobre o tipo de Biblioteca e como tenho que fazer meus alunos trabalharem no Serção de detecção (da qual a classificação da biblioteca é derivada), decidi criar um exercício para eles sobre esse novo tópico. O melhor é que esse algoritmo alega ter uma complexidade O (n log n) (veja o título Insertion Sort é O (n log n) ou o texto na página da Wikipédia no link acima).

Estou ciente de que as medições empíricas nem sempre são confiáveis, mas tentei fazer o meu melhor e estou um pouco desapontado com o seguinte enredo (azul é o tipo Biblioteca, verde é o quicksort in-loco de Rosetta Code ); eixos verticais é o tempo médio computado como a média de muitas tentativas diferentes; eixos horizontais é o tamanho da lista. As listas aleatórias de tamanho n têm elementos inteiros entre 0 e 2n. A forma da curva realmente não parece algo relacionado a O (n log n).

Aquiestáomeucódigo(incluindoapartedeteste);eusentifaltadealgumacoisa?

#-*-coding:utf8-*-deflibrary_sort(l):#Initializationd=len(l)k=[None]*(d<<1)m=d.bit_length()#floor(log2(n)+1)foriinrange(d):k[2*i+1]=l[i]#mainloopa,b=1,2foriinrange(m):#Becausemultiplicationby2occursatthebeginningoftheloop,#thefirstelementwillnotbesortedatfirstpass,wichiswanted#(becauseasingleelementdoesnotneedtobesorted)a<<=1b<<=1forjinrange(a,min(b,d+1)):p=2*j-1s=k[p]#Binarysearchx,y=0,pwhiley-x>1:c=(x+y)>>1ifk[c]!=None:ifk[c]<s:x=celse:y=celse:e,f=c-1,c+1whilek[e]==None:e-=1whilek[f]==None:f+=1ifk[e]>s:y=eelifk[f]<s:x=felse:x,y=e,fbreak#Insertionify-x>1:k[(x+y)>>1]=selse:ifk[x]!=None:ifk[x]>s:y=x#casemayoccurfor[2,1,0]whiles!=None:k[y],s=s,k[y]y+=1else:k[x]=sk[p]=None#Rebalancingifb>d:breakifi<m-1:s=pwhiles>=0:ifk[s]!=None:#Inthefollowingline,theorderisveryimportant#becausesandpmaybeequalinwhichcasewewant#k[s](whichisk[p])toremainunchangedk[s],k[p]=None,k[s]p-=2s-=1return[xforxinkifx!=None]defquicksort(l):array=list(l)_quicksort(array,0,len(array)-1)returnarraydef_quicksort(array,start,stop):ifstop-start>0:pivot,left,right=array[start],start,stopwhileleft<=right:whilearray[left]<pivot:left+=1whilearray[right]>pivot:right-=1ifleft<=right:array[left],array[right]=array[right],array[left]left+=1right-=1_quicksort(array,start,right)_quicksort(array,left,stop)importrandom,timedeftest(f):print"Testing", f.__name__,"..."
    random.seed(42)
    x = []
    y = []
    for i in [ 25, 50, 100, 200, 300, 500, 1000, 5000,
               10000, 15000, 25000, 40000, 50000, 100000 ]:
        n = 100000//i + 1
        m = 2*i
        x.append(i)
        t = time.time()
        for j in range(n):
            f( [ random.randrange(0,m) for _ in range(i) ] )
        y.append( (time.time()-t)/n )
    return x,y

import matplotlib.pyplot as plt
x1, y1 = test(library_sort)
x2, y2 = test(quicksort)
plt.plot(x1,y1)
plt.plot(x2,y2)
plt.show()

Edit: Eu calculei mais valores, mudei para o interpretador pypy para poder computar um pouco mais ao mesmo tempo; aqui está outro enredo; Eu também adicionei curvas de referência. É difícil ter certeza disso, mas ainda parece um pouco mais com O (n²) do que com O (n log n) ...

    
por Thomas Baruchel 21.11.2015 в 06:04
fonte

2 respostas

1

Link para um arquivo pdf que usa um algoritmo diferente para o que ele também descreve como uma classificação de biblioteca na página 7:

link

O arquivo pdf descreve uma classificação de contagem e inserção híbrida, que parece significativamente diferente do artigo da wiki, mesmo que o arquivo pdf mencione o artigo da wiki. Por causa da fase de contagem, os chamados intervalos são exatamente dimensionados para que o array de destino tenha o mesmo tamanho do array original, em vez de ter que ser maior por algum fator constante, como mencionado no artigo do wiki.

Por exemplo, um método para executar o que o arquivo pdf chama de classificação de biblioteca em uma matriz de inteiros, usando o byte mais significativo de cada inteiro, é criada uma matriz de contagens == matriz de tamanhos de bucket. Eles são convertidos em uma matriz de índices iniciais para cada bloco por soma acumulativa. Em seguida, a matriz de índices iniciais é copiada para uma matriz de índices finais para cada depósito (o que significaria que todos os depósitos estão inicialmente vazios). A classificação começa então, para cada número inteiro da matriz de origem, seleciona o bloco pelo byte mais significativo e, em seguida, faz uma classificação de inserção com base nos índices inicial e final desse intervalo e, em seguida, incrementa o índice final.

O arquivo pdf menciona algum tipo de hash para selecionar buckets para objetos genéricos. O hash teria que preservar a ordem de classificação.

Meu palpite é que a complexidade de tempo seria o tempo para fazer as classificações de inserção, que é O (bucket_size ^ 2) para cada intervalo, pois o passo para criar os índices de contagem / bucket é linear.

Para números inteiros, uma vez que a maior parte da lógica para a ordenação contando-radix já está lá, pode também executar uma classificação multi-pass menos significativa para a contagem mais significativa byte-radix e esquecer de fazer a classificação por inserção.

Voltando ao artigo wiki, não há explicação sobre como detectar uma lacuna vazia. Supondo que nenhum valor de sentinela para representar uma lacuna vazia esteja disponível, uma terceira matriz poderia ser usada para indicar se uma localização na segunda matriz continha dados ou estava vazia.

    
por rcgldr 21.11.2015 / 10:37
fonte
1

Há dois problemas com seu código test() , não com a implementação library_sort() :

  • parar o horário inclui a geração dos valores (inline), consulte o gráfico abaixo
  • produzindo muitos valores iguais ('vales dobrados' no código abaixo) para intervalos limitados usando aleatório: você provavelmente não pretendia ter > 20% de valores repetidos com m = 2*i .
def rand_n(n, short_rnd):
    m = (2 * n) if short_rnd else (2**30)  # >20 % repeated if m just 2*n
    return [random.randrange(0, m) for _ in range(n)]

def get_time_over_n(f, vals_inline, short_rnd):
    exp = 4 if f == sorted else 3
    a = 2 * 10**exp
    l_n = [a*1, a*2, a*5, a*10, a*20, a*50]
    ll_vals = []
    for n in l_n:  # values for non-inline
        ll_vals.append(rand_n(n, short_rnd))
    n_tests = len(ll_vals)
    x = []
    y = []
    for i, l_vals in enumerate(ll_vals):
        n = len(l_vals)
        print('%10i (still %2i)' % (n, n_tests - i), end=': ')
        x.append(n / 1000)
        t = time.time()
        if vals_inline:
            f(rand_n(n, short_rnd))
        else:
            f(l_vals)
        dt = time.time() - t
        print("%8.3f s" % dt)
        y.append(1000 * dt / n)
    return x, y

COLS = ['green', 'blue', 'red', 'black']
plt.rc('axes', prop_cycle=(plt.cycler('color', COLS)))
WHAT = ['ok', 'outside, but repeated vals', 'many vals, but inline', 'inline & repeated vals']
params = [(0, 0), (0, 1), (1, 0), (1, 1)]

f = sorted  # built-in
#f = library_sort
for i_plot in range(4):
    print("%s(), %s (%s)..." % (f.__name__, WHAT[i_plot], COLS[i_plot]))
    x, y = get_time_over_n(f, *params[i_plot])
    plt.plot(x, y, label=WHAT[i_plot])
plt.xlabel('n values / 1000')
plt.ylabel('time * 1000 / n [s]')
plt.legend(bbox_to_anchor=(1, 1.025), ncol=2, bbox_transform=plt.gcf().transFigure)
plt.show()

    
por thoku 21.11.2015 / 15:32
fonte