Apresentação
Conforme Steven Ross, a ordenação de elementos é uma das operações básicas da ciência da computação com uma aplicabilidade ampla, sendo bastante aplicado em bando de dados, compressão de dados e buscas na internet.
Prof. Knuth indica que a complexidade θ(nlog(n)) é mais eficiente para o caso geral de ordenação, dependendo dos métodos de comparação[5]. No entanto, as premissas utilizadas para essa conclusão estão equivocadas, sendo necessária uma revisão das premissas utilizadas para obter uma conclusão adequada.
Premissa 1: A operação de comparação tem sempre um custo constante.
Essa afirmação é desconstruída quando se observa a arquitetura computacional utilizada em relação aos tipos de dados utilizado na comparação. Por exemplo, os números grandes (big numbers) podem ser representados em 64 bits ou mais, por exemplo 128 bits, mas dependendo da arquitetura do processador utilizada, atualmente está em 64 bits, o seu custo (tempo) é alterado de acordo com o tamanho do tipo de dados utilizado.
Premissa 2: A ordenação deve ser baseada em comparação de valores:
Essa premissa considera que um algoritmo baseado em comparação obtém o menor número de comparações. No entanto, esses algoritmos de ordenação ainda possuem operações de ordem O(n), que não alteram sua complexidade. Ainda, estudos de complexidade de ordenação tem geralmente direcionado para minimizar o número de vezes que fazemos comparações entre chaves enquanto se ordenam n elementos.
Idéia
Adaptar o algoritmo de ordenação a arquitetura computacional utilizada. Por exemplo, considerar o tamanho da chave de comparação em função do sistema utilizado.
Unir as vantagens de outros métodos de ordenação, em especial do quicksort que divide os dados em duas cestas. Mas qual seria esse número de cestas ideal?
Escopo
O algoritmo utiliza conceitos de algoritmos de ordenação baseado em distribuição tal como o radix sort e bucket sort, além de incluir conceitos de particionamento de algoritmos de ordenação de comparação tal como quicksort e mergesort.
Muitos algoritmos de ordenação baseados em comparação tem como fundamento alguma variante da técnica dividir para conquistar, no qual a lista é dividida recursivamente pela metade até que cada peça seja pequena o suficiente para ser ordenada rapidamente. Em seguida a lista é remontada de forma ordenada. No entanto, raramente é perguntado por qual número essa lista deve ser dividida. Seria apenas por 2, ou por que não 3, 4 ou um número maior? Qual seria o melhor número para a divisão em cada passo?
Spreadsort utiliza a teoria que o número ótimo de cestas é uma fração de n. Esse número é determinado ao minimizar a soma da média do excesso de tempo das cestas e o tempo médio de ordenação de cada cesta, sendo cada um desses tempos função do número de cestas.
Esse número de cestas foi encontrado empiricamente no intervalo de n/4 a n/8 na maioria do sistemas. No nosso código utilizamos n/8.
Asssim o Spreadsort é um algoritmo de divisão e conquista diferente, pois a lista é dividida por uma fração de n, ao invés de 2. É ainda um algoritmo recursivo como outros de divisão e conquista.
A parte recursiva do algoritmo inicia calculando os valores máximo e mínimo da distribuição – O(n) de complexidade, então dividindo uniformemente a distribuição dos valores chave possíveis (m) entre n/c cestas (sendo c um inteiro positivo).
Cada valor-chave do item é dividido por um fator calculado previamente (m/(n/c)) para decidir em qual cesta colocar. Assim, n itens são mapeados para (n/c) cestas (com complexidade O(n)).
Dessa forma, o tamanho da distribuição para cada cesta é dividido por (n/c) e o número médio de itens em cada cesta é c.
Em seguida, uma série de testes é aplicada: se o número de cestas é maior ou igual ao intervalo de chaves, se os dados da cesta já estão ordenados e se não será necessário testes entre as cestas. Se as cestas não estiverem ordenadas completamente, a seguinte comparação é realizada:
\[\frac{(log_2 n)^2}{2} < log_2(m)\]
Se a verificação acima é verdadeira, então o pior caso pra aplicação recursiva do Spreadsort (considerando comparações constantes no tempo) é pior do que o caso normal para o Quicksort. Assim o Quicksort é utilizado. Caso contrário, a aplicação recursiva do Spreadsort pode continuar, dividindo o problema de ordenação em termos do tamanho da chave e concentração.
Complexidade
A aplicação recursiva tem o pior caso de performance que pode ser calculada considerando a ramificação de estrutura da árvore, com uma divisão entre duas peças de igual tamanho por operação recursiva:
x - número de operações recursivas do SpreadSort necessára para ordernar um lista no pior caso.
x é o menor inteiro tal que
\[\frac{m}{\left(\frac{n}{c2^0}*\frac{n}{c2^0}*\frac{n}{c2^1}*...*\frac{n}{c2^x}\right)} \leq 1\]
Considerando o caso onde os lados são igual e ao multiplicar as séries, x pode ser resolvido para
\[m = \frac{n^x}{c^x2^{(x(x-1))}}\]
\[log_2(m) = x(log_2(n)- x(x-1)log_2(2)) - log_2(c) = 0\]
\[ -x^2 + x(log_2\left(\frac{n}{c}\right) -1) - log_2(m) = 0 \]
Logo
\[ x = \frac{\left( log_2\left(\frac{n}{c} \right) - 1 \right) \pm \sqrt[2]{
\left(\left(\frac{n}{c}\right) -1\right)^2 - 4log_2(m)}}{2}\]
Para x existir, requer que :
\[\left(log_2\left(\frac{n}{c}\right) -1\right)^2 \geq 4log_2(m)\]
Se a condição acima for verdadeira, x é sempre menor que \[log_2(n)\], conforme inspeção abaixo:
\[\frac{\left( log_2\left(\frac{n}{c} \right)- 1 \right)}{2} < log_2(n)\]
À medida que
\[\left(log_2\left( \frac{n}{c}\right) -1 \right)^2 \geq 4log_2(m)\]
é verdadeiro, então os dado são ordernados mais raidamente pelo Spreadsort. Quando não for verdade, utiliza-se o método Quicksort.
Distribuições de dados que permitam chegar ao resultado acima são bastante comuns, levando o Spreadsort possuir uma performance melhor que comparações de complexidade O(nlogn).
Resolvendo a equação em x, obtem-se aproximadamente que
\[ x \approx \frac{log_2\left(m\right)}{\left(log_2\left(\frac{n}{c}\right) - 1 \right)}\]
ao utilizar a aproximação abaixo:
\[\sqrt[]{1 - x} \approx 1 - \frac{x}{2} \]
Considerando que o número de operações é n mais n o número de chamadas recursivas x ,a complexidade do Spreadsort é: O(n + nx)
Utilizando a aproximação de x acima, temos que a complexidade é :
\[O(n + nlog_n(m))\]
import sys
import math
import random
#https://www.javatips.net/api/kanzi-master/java/src/kanzi/util/sort/SpreadSort.java
# A lightweight slice implementation for int[]
class SliceIntArray:
# def __init__(self):
# self.__array = []
# self.__lenght = 0
# self.__index = 0
def __init__(self,array, index):
if not array:
raise Exception("Lista Vazia")
if index < 0:
raise Exception("Índice não pode ser vazio")
self.__array = array
self.__lenght = len(array)
self.__index = index
def getArray(self):
return self.__array
def getLenght(self):
return self.__lenght
def getIndex(self):
return self.__index
def setArray(self):
self.__array
def setLenght(self,lenght):
self.__lenght = lenght
def setIndex(self,idx):
self.__index = idx
def __eq__(self,other):
if not self.__array:
raise Exception("Lista Vazia")
return ((self.__array == other.array) and
(self.__lenght == other.length) and
(self.__index == other.index))
def __hash__(self):
return hash(self.__array)
def hashCode(self):
return self.__hash__()
def __str__(self):
txt = "["
txt = txt + str(self.__array)
txt = txt + ","
txt = txt + str(self.__lenght)
txt = txt + ","
txt = txt + str(self.__index)
txt = txt + "]"
return txt
def isValid(self):
if(self.__array == []):
return False
if(self.__index < 0):
return False
if (self.__lenght < 0):
return False
return (self.__index + self.__lenght <= len(self.__array))
class Bin:
def __init__(self):
self.position = 0
self.count = 0
# SpreadSort parameters
MAX_SPLITS = 11
LOG_CONST = 4
LOG_MEAN_BIN_SIZE = 2
LOG_MIN_SPLIT_COUNT = 9
def roughLog2(x):
shift = 0
x = (x + (x >> 31)) ^ (x >> 31) #abs(x)
while ((x>>shift) != 0):
shift+=1
return shift
def getMaxCount(logRange,count):
logSize = roughLog2(count)
if (logSize > MAX_SPLITS):
logSize = MAX_SPLITS
relativeWidth = (LOG_CONST*logRange)/logSize
#Don't try to bitshift more than the size of an element
if (relativeWidth >= 4):
relativeWidth = 3
shift = (relativeWidth, LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) [(relativeWidth < LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)]
return (1 << shift)
def findExtremes(sia, count, minMax):
dados = sia.getArray()
end = sia.getIndex() + count
min = dados[sia.getIndex()]
max = min
for i in range(sia.getIndex(),end):
val = dados[i]
if (val > max):
max = val
elif (val < min):
min = val
minMax[0] = min
minMax[1] = max
def spreadSortCore(sia, count, minMaxCount):
# This step is roughly 10% of runtime but it helps avoid worst-case
# behavior and improves behavior with real data. If you know the
# maximum and minimum ahead of time, you can pass those values in
# and skip this step for the first iteration
findExtremes(sia, count, minMaxCount)
max = minMaxCount[1]
min = minMaxCount[0]
if (max == min):
return None
logRange = roughLog2(max-min)
logDivisor = logRange - roughLog2(count) + LOG_MEAN_BIN_SIZE
if (logDivisor < 0):
logDivisor = 0
# The below if statement is only necessary on systems with high memory
# latency relative to processor speed (most modern processors)
if (logRange-logDivisor > MAX_SPLITS):
logDivisor = logRange - MAX_SPLITS
divMin = min >> logDivisor
divMax = max >> logDivisor
binCount = divMax - divMin + 1
# Allocate the bins and determine their sizes
bins = [Bin() for i in range(binCount)]
array = sia.getArray()
count8 = count & -8
end8 = sia.getIndex() + count8
# Calculating the size of each bin , number 8 was defined empirically
for i in range(sia.getIndex(), end8, 8):
bins[(array[i] >>logDivisor)-divMin].count+=1
bins[(array[i+1]>>logDivisor)-divMin].count+=1
bins[(array[i+2]>>logDivisor)-divMin].count+=1
bins[(array[i+3]>>logDivisor)-divMin].count+=1
bins[(array[i+4]>>logDivisor)-divMin].count+=1
bins[(array[i+5]>>logDivisor)-divMin].count+=1
bins[(array[i+6]>>logDivisor)-divMin].count+=1
bins[(array[i+7]>>logDivisor)-divMin].count+=1
for i in range(count8, count):
bins[(array[sia.getIndex()+i]>>logDivisor)-divMin].count +=1
#Assign the bin positions
bins[0].position = sia.getIndex()
for i in range(binCount-1):
bins[i+1].position = bins[i].position + bins[i].count
bins[i].count = bins[i].position - sia.getIndex()
bins[binCount-1].count = bins[binCount-1].position - sia.getIndex()
# Swap into place. This dominates runtime, especially in the swap
for i in range(0,count):
idx = sia.getIndex() + i
currBin=bins[(array[idx]>>logDivisor) - divMin]
while(currBin.count > i):
tmp = array[currBin.position]
array[currBin.position] = array[idx]
array[idx] = tmp
currBin.position += 1
currBin = bins[(array[idx]>>logDivisor) - divMin]
# Now that we have found the item belonging in this position,
# increment the bucket count
if (currBin.position == idx):
currBin.position += 1
minMaxCount[0] = min
minMaxCount[1] = max
minMaxCount[2] = binCount
#If we have bucket sorted, the array is sorted and we should skip recursion
if (logDivisor == 0):
return None
return bins
def spreadSortBins(sia, minMaxCount, bins, maxCount):
binCount = minMaxCount[2]
for i in range(binCount):
n = (bins[i].position - sia.getIndex()) - bins[i].count
#Don't sort unless there are at least two items to compare
if (n < 2):
continue
if (n < maxCount):
sort1(sia.getArray(), sia.getIndex()+bins[i].count, bins[i].position)
else:
_sort(sia.getArray(), sia.index+bins[i].count, n)
def sort1(arr, initPos,fimPos):
arr[initPos:fimPos] = sorted(arr[initPos:fimPos])
def spreadsort(array, idx,count):
if (count < 2):
return True
# Array containing min, max and bin count
minMaxCount = [-1,-1,-1]
sia = SliceIntArray(array, idx)
bins = spreadSortCore(sia, count, minMaxCount)
if (bins == None):
return False
maxCount = getMaxCount(roughLog2(minMaxCount[1]-minMaxCount[0]), count)
spreadSortBins(sia, minMaxCount, bins, maxCount)
return True
# Generate list with a number of unique elements in range of begin and end
def createRandomSortedList(num, inicio = 1, fim = 100):
arr = []
tmp = random.randint(inicio, fim)
for x in range(num):
while tmp in arr: # quando o número gerado não estiver na lista
tmp = random.randint(inicio, fim)
arr.append(tmp) # adicione-o
return arr
def confere(lista):
ok = True
for i in range(0,len(lista)-1):
if lista[i] > lista[i+1]:
ok = False
return ok
if __name__ == "__main__":
# criar uma lista de 1000, 10000 e 100000 elementos aleatórios com valores de 0 a 2 x o tamanho da lista.
n = 1000
for i in range(3):
n=n*10
lista = createRandomSortedList(n, 0, 5*n)
print(lista)
spreadsort(lista, 0, len(lista))
print(lista)
print(confere(lista))
print("sair")