Classificação por gravidade:Isso é possível programaticamente?[fechado]

https://stackoverflow.com/questions/2489190

21-09-2019
|

Pergunta

Tenho pensado recentemente em usar o design Orientado a Objetos no algoritmo de classificação.No entanto, não consegui encontrar uma maneira adequada de chegar mais perto na criação desse algoritmo de classificação que faz a classificação em tempo O(n).

Ok, aqui está o que estou pensando há uma semana.Eu tenho um conjunto de dados de entrada.Atribuirei uma massa a cada um dos dados de entrada (suponha que os dados de entrada sejam um tipo de Mass e um tipo de Sphere.Se assumirmos que todos os objetos são objetos perfeitamente esféricos com formas proporcionais à sua massa, o mais pesado toca o solo primeiro.).Colocarei todos os meus dados de entrada no espaço, todos à mesma distância da Terra.E eu os farei cair em queda livre.De acordo com a lei gravitacional, o mais pesado atinge o solo primeiro.E a ordem em que eles acertaram me dará os dados classificados.Isso é engraçado de certa forma, mas no fundo sinto que isso deveria ser possível usando o OO que aprendi até agora

É realmente possível fazer uma técnica de classificação que use um cenário semelhante ao da atração gravitacional ou sou estúpido/louco?

Editar: Acontece que todos os objetos atingem o solo ao mesmo tempo, por isso introduzi o conceito de objeto esférico.

Solução

O problema é que, embora um dos Ideias De OOP pode ser modelar o mundo real, isso não significa que há uma correspondência direta entre quanto tempo algo leva no mundo real e quanto tempo levaria para simulá -lo com um computador.

Imagine as etapas reais necessárias para o seu procedimento:

Um objeto deve ser construído para cada item em seu conjunto de dados. Na maioria dos hardware moderno, isso por si só exigiria iteração e, portanto, tornaria sua estratégia o (n) em melhor.
O efeito da gravidade precisaria ser simulado para cada objeto. Novamente, a maneira mais óbvia e direta de implementar isso seria iterar.
O tempo em que cada objeto pousa na superfície da "Terra" em seu modelo de programação teria que ser capturado e, por meio de algum mecanismo específico da implementação, o objeto correspondente precisaria ser inserido em uma lista ordenada como resultado.

Considerando o problema, introduz ainda mais complicações adicionais. Pergunte a si mesmo: quão alto você precisa posicionar esses objetos para começar? Obviamente alto o suficiente para que o maior seja realmente cai; ou seja, mais longe da terra do que o raio do maior objeto. Mas como você sabe quão longe isso é? Você precisaria primeiro determinar o maior objeto da coleção; Isso, novamente, (provavelmente) exigiria a iteração. Além disso, pode-se imaginar que essa simulação poderia ser multithread para tentar simular o comportamento em tempo real da noção de objetos na realidade queda; Mas você estará tentando adicionar itens a uma coleção (uma operação que obviamente leva um tempo diferente de zero) potencialmente ao mesmo tempo em que novas colisões estão sendo detectadas. Portanto, isso criará problemas de rosca também.

Em suma, tenho problemas para imaginar como essa idéia pode ser implementada corretamente, simplesmente usando o OOP sem hardware especial. Dito isto, realmente é uma boa ideia. Isso me lembra, de fato, de Tipo de contas-Um algoritmo que, embora não seja o mesmo que sua idéia, também é uma solução de classificação que aproveita o conceito muito físico de gravidade e, não surpreendentemente, requer hardware especializado.

Outras dicas

Você acabou de reafirmar o problema. Calcular a ordem dos efeitos gravitacionais terá, na melhor das hipóteses, o O dos algoritmos de classificação que você está tentando vencer.

O cálculo da gravitação é gratuito apenas no mundo real. No Programm, você precisa modelá -lo. Será outro n no mínimo de complexidade

A classificação de uso geral é provavelmente, na melhor das hipóteses, O (n log n).Para melhorar isso, você precisa saber algo sobre os dados além de apenas como comparar valores.

Se os valores forem todos números, classificação de raiz dá O(n) assumindo que você tem limites superiores e inferiores para os números.Essa abordagem pode ser estendida para lidar com qualquer número – e, em última análise, todos os dados em um computador são representados por números.Por exemplo, você pode classificar strings radix, em cada passagem, classificando por um caractere como se fosse um dígito.

Infelizmente, lidar com tamanhos variáveis de dados significa fazer um número variável de passagens pela classificação radix.Você acaba com O(n log m) onde m é o maior valor (já que k bits fornece um valor de até (2^k)-1 para não assinado, metade disso para assinado).Por exemplo, se você estiver classificando os números inteiros de 0 a m-1, bem - você terá O(n log n) novamente.

Traduzir um problema para outro pode ser uma abordagem muito boa, mas às vezes é apenas adicionar outra camada de complexidade e sobrecarga.

A idéia pode parecer simples, mas a diferença entre o mundo real e a modelada neste caso é que, no mundo real, tudo está acontecendo em paralelo. Para modelar a classificação gravitacional ao descrever, teria que começar pensando que cada objeto em um thread separado com uma maneira segura de thread para adicioná -los a uma lista na ordem em que terminar. Realisticamente, em termos de classificação de desempenho, você provavelmente usaria uma classificação rápida nos tempos, ou como eles estão à mesma distância a taxa de queda. No entanto, se sua fórmula for proporcional à massa, você apenas pularia tudo isso e classificar a massa.

Em um "computador gravitacional" fictício, esse tipo de classificação levaria O (1) a ser resolvido. Mas com os computadores reais como a conhecemos, seu pensamento lateral não ajudaria.

Depois de calcular todas as vezes que eles levam para atingir o chão, você ainda precisará classificar esses valores. Você não está realmente ganhando nada, está apenas classificando números diferentes depois de realizar um cálculo desnecessário extra.

EDITAR: Gritos. Esqueci a física 101. É claro que todos eles chegarão ao mesmo tempo. :)

Qualquer tipo de modelagem como essa apenas transforma um problema de classificação em outro. Você não vai ganhar nada.

Ignorando todas as falhas que todos os outros mencionaram, essencialmente se resume a um O(n^2) Algoritmo, não O(n). Você teria que iterar sobre todas as "esferas", encontrar o "mais pesado" ou o "maior" e depois empurrá -lo para uma lista, depois enxágue e repita. ou seja, para encontrar o que atinge o chão primeiro, você precisa iterar em toda a lista, se for o último, levaria O(n) tempo, o segundo poderia levar O(n-1), etc ... mas pior do que isso, você precisa executar um monte de operações matemáticas a cada vez apenas para calcular algum valor inútil "tempo" quando você poderia ter classificado o valor em que estava interessado em primeiro lugar.

Hmmmm. Classificação da gravidade.

Ignorar seu modelo específico de gravidade está errado, vamos ver para onde essa idéia nos leva.

A realidade física tem 10^80 processadores.

Sabe -se que os limites inferiores reais são log (n) se você tiver processadores N/2 para classificar N objetos.

Se você tiver vários núcleos de CPU disponíveis, não há razão para que você não consiga o Mergesort em vários threads.

Na verdade, existe um algoritmo de classificação bastante famoso chamado Spaghetti, que é semelhante ao seu. Você pode conferir algumas das muitas análises na web. por exemplo cstheory.

spaghetti

Definitivamente, deve ser apenas você deve ter hardware adequado suportado para ele. Caso contrário, isso parece uma ideia muito legal. Espero que alguém apresente um papel IEEE para tornar esse sonho louco visualizado.

Eu amo a ideia! É inteligente. Enquanto sim, o que os outros estão dizendo é no geral correto, que o limite o (n log n) é um limite comprovadamente menor do problema de classificação em geral, precisamos ter em mente que esse limite inferior é verdadeiro apenas para comparação baseada em comparação modelos. O que você está propondo aqui é um modelo completamente diferente, ele merece mais pensamento.

Além disso, como James e Matrix apontaram, a mais pesada não viaja mais rápido que a mais leve, você obviamente precisa adaptar o modelo a algo em que o objeto mais pesado (número) realmente viajaria mais rápido/mais além disso) para que você possa distinguir de alguma forma os números (uma centrífuga também vem à mente).

Requer mais pensamento, mas sua ideia é nítida!

(Editar) Agora, olhando para a ideia do Phys2D de Enrique, acho que faz muito mais sentido.

Uma coisa que eu sugeriria é definitivamente ignorar o aspecto da eficiência por enquanto. (Eu sei, eu sei que esse era todo o objetivo). É um novo modelo, e primeiro precisamos preencher a lacuna entre a idéia e sua implementação. Somente então podemos compreender o que a complexidade do tempo significa até para esse modelo.

Eu acho que o problema pode ser mais simples assim: você deseja colocar o fundo das esferas em diferentes alturas, para que, quando caídas em gravidades idênticas, o maior atinja o chão primeiro, o segundo maior, etc. Isso é essencialmente equivalente a usar Linhas em vez de esferas ... Nesse caso, você pode simplesmente dizer que HightOfftheground = max_value - Mass.

Você também não precisa se preocupar com a aceleração ao longo do tempo ... como não se importa com a rapidez com que eles estão indo ou realistas, você pode dar a todos uma velocidade inicial X e ir a partir daí.

O problema é que, basicamente, acabamos de reafirmar o problema e resolveu assim (pseudocode):

int[] sortedArray; // empty
int[] unsortedArray; // full of stuff
int iVal = MAX_INT_VALUE;
while (true)
{
    foreach (currentArrayValue in sortedArray)
    {
        if (iVal = current array value
        {
            put it in my sortedArray
            remove the value from my unsortedArray
        }
    }
    if (unsortedArray is empty)
    {
        break;  // from while loop
    } 
    iVal--
}

O problema é que, para executar o mecanismo de física, você deve iterar sobre cada vez que será o O (1) ... com um muito Grande constante ... o número constante de valores delta em que o sistema será executado. A desvantagem é que, para a grande maioria desses valores delta, você estará essencialmente não se aproximando da resposta: em qualquer iteração, é muito provável que todas as esferas/linhas/o que quer que tenham movido ... mas nenhum vai acertar.

Você pode tentar apenas dizer, bem, vamos pular muitas etapas intermediárias e ir à frente até que um acerte! Mas isso significa que você precisa saber qual é o maior ... e voltará ao problema de classificação.

Vou adaptar um pouco a sua ideia. Temos nossos objetos, mas eles não diferem em peso, mas em velocidade. Assim, no início, todos os objetos estão alinhados na linha de partida e no tiro inicial, todos se moverão com suas respectivas velocidades até o final.

Claro o suficiente: o primeiro objeto no acabamento emitirá um sinal, dizendo que está lá. Você pega o sinal e escreve para o artigo de resultados quem era.

Ok, então você vai querer simular isso.

Tomamos a duração do seu campo para ser L=1. Com tamanho de etapa ∆t cada um dos seus N objetos move um comprimento de vᵢ∙∆t de uma vez. Isso significa que cada objeto precisa sᵢ = L / (vᵢ∙∆t) Passos antes de chegar ao acabamento.

O ponto é agora, para distinguir entre dois objetos com velocidades muito próximas, você precisará ter um tamanho de etapa diferente para todos os seus objetos.

Agora, no melhor Caso, isso significa que o objeto 1 termina em uma etapa, objeto 2 em dois e assim por diante. Portanto, o número total de etapas é S = 1 + 2 + … + N = N∙(N + 1)/2. Isso é de ordem N∙N.

Se não for o melhor caso e as velocidades não estão igualmente próximas uma da outra, você terá que diminuir o tamanho da etapa e, com efeito, iterar muito mais vezes.

Se fosse construído um computador que classificasse objetos com base em alguns critérios (o que não é totalmente ridículo de se pensar), então acredito que a ordem de complexidade não teria nada a ver com o número de objetos, mas sim com a taxa de aceleração local. devido à gravidade.Supondo que seja modelado na Terra, a complexidade seria O(g₀) onde g₀ é:

$alt text$

O raciocínio simples é que o número de objetos esféricos (n) é irrelevante se seus centros estiverem alinhados no início.Além disso, a aceleração da gravidade terá um impacto muito maior do que a própria altura à medida que aumenta.Por exemplo, se aumentarmos a altura de todos os objetos em 10x, eles não levariam 10x o tempo para atingir o solo, mas muito menos.Isto inclui várias aproximações desprezíveis, uma vez que a aceleração depende, na verdade, da distância entre dois objetos, mas isso pode ser ignorado, pois estamos mais interessados numa imagem mais ampla do que num valor específico.

Mesmo assim, uma ideia brilhante.

Além disso, adoro o vídeo de classificação de moedas postado por @Jeremy.E, finalmente, a orientação a objetos seria a menor das minhas preocupações na construção de tal máquina.Pensando mais sobre isso, aqui estão meus estúpidos dois centavos na construção de tal máquina:

~~O 0 o O o~~

. . . . .
. . . . .
. . . . .
= = = = =

Todos os objetos têm tamanhos variados, proporcionais aos critérios pelos quais queremos classificar.Eles são inicialmente mantidos juntos horizontalmente por uma haste fina que passa pelo centro de cada esfera.O = na parte inferior são especialmente projetados para registrar um valor (opcionalmente sua posição) em algum lugar assim que colidirem com uma esfera.Depois que todas as esferas colidirem, teremos nossa ordem de classificação com base nos valores registrados.

a partir de Resposta de Debilski:

Vou adaptar um pouco a sua ideia. Temos nossos objetos, mas eles não diferem em peso, mas em velocidade. Assim, no início, todos os objetos estão alinhados na linha de partida e no tiro inicial, todos se moverão com suas respectivas velocidades até o final.

Claro o suficiente: o primeiro objeto no acabamento emitirá um sinal, dizendo que está lá. Você pega o sinal e escreve para o artigo de resultados quem era

Eu simplificaria um passo adiante e diria que esses objetos são inteiros positivos aleatórios. E queremos classificá -los em uma ordem ascendente à medida que se aproximam de zero, para que tenham um distância de zero d que inicialmente é igual ao próprio número inteiro.

Supondo que a simulação ocorra em etapas de tempo discretas, ou seja, quadros, em cada quadro, a nova distância de todo objeto seria: d = d - v e um objeto seria adicionado à lista quando seu d ≤ 0. Essa é uma subtração e uma condicional. Duas etapas discretas para cada objeto, portanto os cálculos parecem ser O (n): lineares.

A captura é, é linear para um quadro só! É multiplicado pelo número de quadros f necessário para terminar. A própria simulação é O (NF): quadrática.

No entanto, se tomarmos a duração de um quadro como argumento t Temos a capacidade de afetar o número de quadros f de maneira inversamente proporcional. Podemos aumentar t reduzir f Mas isso tem ao custo da precisão, mais aumentamos t, quanto mais a probabilidade de que dois objetos terminem no mesmo período de tempo, portanto, sejam listados como equivalentes, mesmo que não sejam. Portanto, obtemos um algoritmo com precisão ajustável (como é na maioria dos contextos de simulação de elementos finitos)

Podemos refinar ainda mais isso transformando -o em um algoritmo adaptativo+recursivo. No código humano seria:

function: FESort: arguments: OriginalList, Tolerance
  define an empty local list: ResultList

  while OriginalList has elements
    define an empty local list: FinishedList
    iterate through OriginalList
      decrement the distance of each object by Tolerance
      if distance is less than or equal to zero, move object from OriginalList to FinishedList

    check the number of elements in FinishedList
      when zero
        set Tolerance to double Tolerance
      when one
        append the only element in FinishedList to ResultList
      when more
        append the result of FESort with FinishedList and half Tolerance to ResultList

  return ResultList

Estou me perguntando se há alguma implementação semelhante que funcione para alguém.

Assunto interessante de fato :)

Ps. O pseudocódigo acima é a minha idéia de pseudocódigo, sinta -se à vontade para reescrevê -lo de uma maneira mais legível ou conforme, se houver.

Algumas semanas atrás, eu estava pensando na mesma coisa.

Eu pensei em usar Phys2D biblioteca para implementá -lo. Pode não ser prático, mas apenas por diversão. Você também pode atribuir pesos negativos aos objetos para representar números negativos. Com a biblioteca Phys2D, você pode definir a gravidade, de modo que objetos com peso negativo vão para o telhado e os objetos com peso positivo cairão. Então organize todos os objetos no meio entre o piso e o teto com a mesma distância entre o piso e o teto. Suponha que você tenha uma matriz resultante r [] de comprimento = número de objetos. Toda vez que um objeto toca o teto, você o adiciona no início da matriz r [0] e incrementa o contador, da próxima vez que um objeto toca o teto que você o adiciona em r [1], toda vez que um objeto atinge o piso que você Adicione-o no final da matriz R [R.Length-1], da próxima vez que você o adicionar em R [R.Length-2]. No final, os objetos que não se moveram (permaneceram flutuando no meio) podem ser adicionados no meio da matriz (esses objetos são os 0s).

Isso não é eficiente, mas pode ajudá -lo a implementar sua ideia.

Eu acredito que é bom mencionar/consultar: Qual é a relação entre P vs. NP e a capacidade da natureza de resolver problemas de NP com eficiência?Classificar é O(nlog(n)), por que não tentar resolver problemas difíceis de NP?
Pelas leis dos objetos de física caem com proporções para oconstante gravitacional A massa é insignificante.
Simular um processo físico pode afetar a complexidade do tempo real.

Analise: (1) Todos os centros de esferas estão alinhados no início (2) maior número ==> massa superior ==> raio maior ==> Distância do solo inferior (3) no 'vácuo' mesma aceleração = a mesma evolução da velocidade = => A mesma distância para o centro ==> quão maior de raio ... quão anterior a esfera atingirá o chão ==> conceitualmente ok, boa técnica física se quando uma esfera atingir o chão, ela pode enviar um sinal de indentificação + tempo de acertar tempo ... que dará a lista classificada praticamente ... não uma técnica numérica 'boa'

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow