Executando verificação de segurança...
7

Meu projeto de Sorting List

Olá!
A sorting que estou criando é a Trotsky Sorting, não foi pensada para ser uma sorting tradicional de que "existe um estado inicial e o final, organizaremos sua lista até que chegue ao estado final".
Em cenários reais da computação, a ideia de "ordenação final" perde totalmente o sentido quando estruturas, streams de dados ou sistemas reativos recebem inserções todo momento,** a lista está sempre mudando, o custo de reordenar tudo é, praticamente, inviável.**
Já essa sorting que estamos falando, que, inicialmente, iremos chamar de trotsky sorting, segue o modelo da ordenação contínua, onde a lista nunca é considerada "finalizada", mantida em um processo de ordenação até que entre em um estado de organização aceitável.
Esse é o processo que Trotsky faz:
A lista é submetida a uma divisão de blocos de tamanho fixo, cada bloco sendo uma região independente, onde é possível medir o nível de desordem.
Ao invés de assumir que o bloco precisa ser ordenado, o sistema mede a desordem local, observando quantas inversões existem em elementos adjacentes. Essa medida é avaliada entre 0 e 1, representando o quão instável o trecho está. Somente os blocos com trechos com uma avaliação grande o suficiente para ser considerado "instável" são reordenados.
Além disso, é usado o sistema de passos de estabilização (revolution steps), que corrige apenas partes específicas da lista. Ao longo do tempo, se não houver perturbações na lista, ela tende a convergir a um estado mais ordenado. Caso novos elementos sejam adicionados, o sistema reage localmente, sem reiniciar todo o processo.

!!O nome NÃO foi para apoiar QUAISQUER políticas que sejam, foi apenas uma semelhança com as ideias de Trotsky de revolução permanente e organização social e política da URSS!!

Carregando publicação patrocinada...
2

Qual a utilidade deste sorting, que dor sua ela resolve ou é apenas um pet project ?
Gostei dessa abordagem "trotsky sorting", talvez eu possa pensar na utilidade disso se eu tivesse uma fila enorme de eventos que foram gerados por exemplo por um dispositivo, e quero priorizar processar certos tipos de eventos em detrimento de outros.

Por exemplo, trabalhei com rastreadores de veículos, estes geram diferentes tipos de eventos para diferentes coisas que acontecem no veículo. Ex: Abertura de porta direita, esquerda, traseira, ignição ligada/desligada, sensor de carona ativado, etc.

Imagina o cenário onde eu tenho milhares de veículos rastreados, gerando trocentos eventos e enviando para minha infra e e quero priorizar processar os eventos de abertura de porta por algum motivo.

Teoricamente eu poderia fazer um "ORDER BY" em uma tabela de um banco RDBMS e a situação estaria resolvida, OU, aplicar este trotsky a uma estrutura mais efêmera, onde os dados estão sendo recebidos mais ainda não armazenados em banco para processamento futuro.

1

Antes de qualquer resposta sobre, o projeto vai ter outras alterações.
as alterações que desejo fazer por agora:
pesos dinâmicos;
prioridade contextual;
aging (eventos antigos sobem);
integração com filas / streams;

A ideia do projeto não é substituir um 'ORDER BY' ou algum outro mais clássico. Ele faz mais sentido antes do banco, em estruturas efêmeras, onde os dados estão chegando continuamente e ainda não foram persistidos.

A proposta não é apenas organizar, mas manter uma fila viva aceitavelmente organizada, enquantos novos eventos continuam mudando (as prioridades podem mudar dependendo do contexto)
o mecanismo funciona assim:
os eventos entram em qualquer ordem,
cada evento pode ter um peso ou relevância,
o sistema aplica correções locais e incrementais,
eventos mais críticos tendem a emergir para o topo com o tempo,
sem bloquear ingestão e sem exigir um estado final “perfeitamente ordenado”.