Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

O que é o algoritmo de ordenação Spreadsort

0 votos
87 visitas
perguntada Dez 18, 2020 em Economia por Philippe Azevedo (16 pontos)  
editado Dez 19, 2020 por Philippe Azevedo

Introduza o algoritmo de ordenação SpreadSort. Discuta a ideia, escopo, complexidade e implemente o algoritmo na linguagem de sua escolha.

Compartilhe

1 Resposta

0 votos
respondida Dez 19, 2020 por Philippe Azevedo (16 pontos)  

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")
...