complexity - sorting algorithms gif




Como emparelhar meias de uma pilha de forma eficiente? (20)

Ontem eu estava emparelhando as meias da lavanderia limpa e descobri o modo que eu estava fazendo isto não é muito eficiente. Eu estava fazendo uma pesquisa ingênua - escolhendo uma meia e "iterando" a pilha para encontrar seu par. Isso requer iteração sobre n / 2 * n / 4 = n 2/8 meias em média.

Como cientista da computação, eu estava pensando no que poderia fazer? A classificação (de acordo com o tamanho / cor / ...) naturalmente veio à mente para alcançar uma solução O (NlogN).

Hashing ou outras soluções não-in-loco não são uma opção, porque eu não sou capaz de duplicar minhas meias (embora possa ser bom se eu puder).

Então, a questão é basicamente:

Dada uma pilha de n pares de meias, contendo 2n elementos (suponha que cada meia tenha exatamente um par correspondente), qual é a melhor maneira de combiná-los de forma eficiente com um espaço extra logarítmico? (Eu acredito que posso lembrar essa quantidade de informação, se necessário.)

Eu aprecio uma resposta que aborda os seguintes aspectos:

  • Uma solução teórica geral para um enorme número de meias.
  • O número real de meias não é tão grande, não acredito que minha esposa e eu tenhamos mais de 30 pares. (E é bastante fácil distinguir entre minhas meias e as dela; isso pode ser usado também?)
  • É equivalente ao problema de nitidez do elemento ?

Como a arquitetura do cérebro humano é completamente diferente de uma CPU moderna, essa questão não faz sentido prático.

Os seres humanos podem ganhar algoritmos de CPU usando o fato de que "encontrar um par correspondente" pode ser uma operação para um conjunto que não é muito grande.

Meu algoritmo:

spread_all_socks_on_flat_surface();
while (socks_left_on_a_surface()) {
     // Thanks to human visual SIMD, this is one, quick operation.
     pair = notice_any_matching_pair();
     remove_socks_pair_from_surface(pair);
}

Pelo menos é isso que estou usando na vida real, e acho isso muito eficiente. A desvantagem é que requer uma superfície plana, mas geralmente é abundante.


Como uma solução prática:

  1. Rapidamente faça pilhas de meias facilmente distinguíveis. (Diga por cor)
  2. Quicksort cada pilha e use o comprimento da meia para comparação. Como um ser humano, você pode tomar uma decisão relativamente rápida, a qual usar para particionar evita o pior caso. (Você pode ver várias meias em paralelo, use isso a seu favor!)
  3. Pare de classificar as pilhas quando elas atingirem um limite no qual você se sentirá à vontade para encontrar instantaneamente pares de pares e meias não parciais instantaneamente

Se você tem 1000 meias, com 8 cores e uma distribuição média, você pode fazer 4 pilhas de cada 125 meias em c * n tempo. Com um limiar de 5 meias, podes ordenar cada pilha em 6 corridas. (Contando 2 segundos para jogar uma meia na pilha certa, você levará pouco menos de 4 horas.)

Se você tiver apenas 60 meias, 3 cores e 2 tipos de meias (sua / sua esposa), você pode classificar cada pilha de 10 meias em 1 tirada (Novamente limiar = 5). (Contando 2 segundos, você levará 2 min).

A ordenação inicial do bucket irá acelerar o seu processo, porque ele divide seus n socks em k buckets em c*n time, então você só terá que fazer c*n*log(k) work. (Não levando em conta o limite). Então, tudo o que você faz a respeito do trabalho n*c*(1 + log(k)) , onde c é o momento de jogar uma meia em uma pilha.

Esta abordagem será favorável em comparação com qualquer método c*x*n + O(1) , aproximadamente, desde que log(k) < x - 1 .

Na ciência da computação, isso pode ser útil: temos uma coleção de n coisas , uma ordem sobre elas (comprimento) e também uma relação de equivalência (informações extras, por exemplo, a cor das meias). A relação de equivalência nos permite fazer uma partição da coleção original e, em cada classe de equivalência, nossa ordem ainda é mantida. O mapeamento de uma coisa para sua classe de equivalência pode ser feito em O (1), então somente O (n) é necessário para atribuir cada item a uma classe. Agora usamos nossas informações extras e podemos proceder de qualquer maneira para classificar todas as classes. A vantagem é que os conjuntos de dados já são significativamente menores.

O método também pode ser aninhado, se tivermos múltiplas relações de equivalência -> fazer pilhas de cores, do que dentro de cada partição de pilha na textura, do que classificar no comprimento. Qualquer relação de equivalência que crie uma partição com mais de dois elementos com tamanho igual trará uma melhoria de velocidade em relação à classificação (desde que possamos atribuir diretamente uma meia à sua pilha), e a classificação pode acontecer muito rapidamente em conjuntos de dados menores.


Isso está fazendo a pergunta errada. A pergunta certa a fazer é: por que estou gastando tempo arrumando meias? Quanto custa anualmente, quando você valoriza seu tempo livre para X unidades monetárias de sua escolha?

E muitas vezes, isso não é apenas um tempo livre, é o tempo livre da manhã , que você poderia passar na cama, ou tomar um café, ou sair um pouco mais cedo e não ser pego no trânsito.

Muitas vezes é bom dar um passo para trás e pensar uma maneira de contornar o problema.

E há um caminho!

Encontre uma meia que você gosta. Leve em consideração todas as características relevantes: cor em diferentes condições de iluminação, qualidade geral e durabilidade, conforto em diferentes condições climáticas e absorção de odores. Também é importante que eles não percam elasticidade no armazenamento, portanto os tecidos naturais são bons e devem estar disponíveis em um invólucro de plástico.

É melhor se não houver diferença entre as meias do pé esquerdo e direito, mas não é crítico. Se as meias são simétricas esquerda-direita, encontrar um par é a operação O (1), e classificar as meias é a operação aproximada O (M), onde M é o número de lugares em sua casa, que você tem cheio de meias, idealmente pequeno número constante.

Se você escolher um par chique com meia diferente para a esquerda e para a direita, fazer um balde cheio para baldes de pé esquerdo e direito tomará O (N + M), onde N é o número de meias e M é o mesmo que acima. Alguém pode dar a fórmula para as iterações médias de encontrar o primeiro par, mas o pior caso para encontrar um par com busca cega é N / 2 + 1, o que se torna astronômico para casos razoáveis ​​de N. Isso pode ser acelerado usando imagens avançadas. algoritmos de reconhecimento e heurística, ao escanear a pilha de meias não triadas com Mk1 Eyeball .

Então, um algoritmo para atingir a eficiência de emparelhamento da meia O (1) (assumindo a meia simétrica) é:

  1. Você precisa estimar quantos pares de meias precisará para o resto de sua vida, ou talvez até se aposentar e mudar para climas mais quentes, sem precisar usar meias nunca mais. Se você é jovem, também pode estimar quanto tempo levará até que todos nós tenhamos robôs de classificação de meias em nossas casas, e todo o problema se torne irrelevante.

  2. Você precisa descobrir como você pode encomendar sua meia selecionada em massa, e quanto custa, e eles entregam.

  3. Encomende as meias!

  4. Livre-se das suas velhas meias.

Um passo alternativo 3 envolveria comparar os custos de comprar a mesma quantidade de meias talvez mais baratas alguns pares de cada vez ao longo dos anos e adicionar o custo de ordenar meias, mas tome minha palavra: comprar a granel é mais barato! Além disso, as meias armazenadas aumentam de valor à taxa de inflação dos preços das ações, o que é mais do que você obteria em muitos investimentos. Então, novamente, há também o custo de armazenamento, mas as meias realmente não ocupam muito espaço na prateleira de cima de um armário.

Problema resolvido. Então, pegue novas meias, jogue / doe suas velhas para longe e viva feliz para sempre, sabendo que está economizando dinheiro e tempo todos os dias pelo resto da vida.


O limite teórico é O (n) porque você precisa tocar em cada meia (a menos que algumas já estejam emparelhadas de alguma forma).

Você pode conseguir O (n) com ordenação radix . Você só precisa escolher alguns atributos para os baldes.

  1. Primeiro você pode escolher (dela, meu) - dividi-los em 2 pilhas,
  2. então use cores (pode ter qualquer ordem para as cores, por exemplo, alfabeticamente pelo nome da cor) - divida-as em pilhas por cor (lembre-se de manter a ordem inicial do passo 1 para todas as meias na mesma pilha),
  3. então comprimento da meia,
  4. então textura, ....

Se você pode escolher um número limitado de atributos, mas atributos suficientes que podem identificar exclusivamente cada par, você deve ser feito em O (k * n), que é O (n) se considerarmos que k é limitado.


Soluções de classificação foram propostas, mas a classificação é um pouco demais : não precisamos de ordem; nós só precisamos de grupos de igualdade .

Então o hashing seria suficiente (e mais rápido).

  1. Para cada cor de meias, forme uma pilha . Iterar todas as meias em sua cesta de entrada e distribuí-las nas pilhas de cores .
  2. Iterar sobre cada pilha e distribuí-la por alguma outra métrica (por exemplo, padrão) no segundo conjunto de pilhas
  3. Aplique este esquema recursivamente até distribuir todas as meias em pilhas muito pequenas que você pode processar visualmente imediatamente

Esse tipo de particionamento hash recursivo está realmente sendo feito pelo SQL Server quando ele precisa unir hash ou agregação de hash em grandes conjuntos de dados. Ele distribui seu fluxo de entrada de construção em muitas partições que são independentes. Este esquema é dimensionado para quantidades arbitrárias de dados e várias CPUs linearmente.

Você não precisa de particionamento recursivo se puder encontrar uma chave de distribuição (chave de hash) que forneça intervalos suficientes para que cada depósito seja pequeno o suficiente para ser processado muito rapidamente. Infelizmente, não acho que as meias tenham essa propriedade.

Se cada meia tivesse um inteiro chamado "PairID", poderia facilmente distribuí-las em 10 baldes de acordo com PairID % 10 (o último dígito).

O melhor particionamento real que consigo imaginar é criar um retângulo de pilhas : uma dimensão é cor, a outra é o padrão. Por que um retângulo? Porque precisamos de O (1) acesso aleatório às pilhas. (Um cuboid 3D também funcionaria, mas isso não é muito prático.)

Atualizar:

E o paralelismo ? Múltiplos seres humanos podem combinar as meias mais rapidamente?

  1. A estratégia de paralelização mais simples é ter vários funcionários pegando a cesta de entrada e colocar as meias nas pilhas. Isso só aumenta tanto - imagine 100 pessoas brigando por 10 pilhas. Os custos de sincronização (manifestando-se como colisões de mão e comunicação humana) destroem a eficiência e a aceleração (veja a Lei de Escalabilidade Universal !). Isso é propenso a deadlocks ? Não, porque cada trabalhador só precisa acessar uma pilha de cada vez. Com apenas um "bloqueio" não pode haver um impasse. Livelocks pode ser possível dependendo de como os humanos coordenam o acesso às pilhas. Eles podem usar apenas backoffs aleatórios como placas de rede que fazem isso em um nível físico para determinar qual placa pode acessar exclusivamente o fio da rede. Se funcionar para NICs , também deve funcionar para os humanos.
  2. Ele escala quase indefinidamente se cada trabalhador tiver seu próprio conjunto de pilhas . Os trabalhadores podem, então, retirar grandes quantidades de meias da cesta de entrada (muito pouca contenção, já que raramente fazem isso) e não precisam sincronizar ao distribuir as meias (porque elas têm pilhas locais de encadeamentos). No final, todos os trabalhadores precisam unir suas pilhas. Acredito que isso pode ser feito em O (log (contagem de trabalhadores * pilhas por trabalhador)) se os trabalhadores formarem uma árvore de agregação .

E quanto ao problema de nitidez do elemento ? Como o artigo afirma, o problema de nitidez do elemento pode ser resolvido em O(N) . Isso é o mesmo para o problema de meias (também O(N) , se você precisar de apenas uma etapa de distribuição (eu propus várias etapas apenas porque os seres humanos são ruins em cálculos - basta um passo se você distribuir em md5(color, length, pattern, ...) , ou seja, um hash perfeito de todos os atributos)).

Claramente, não se pode ir mais rápido que O(N) , então alcançamos o limite inferior ideal .

Embora as saídas não sejam exatamente as mesmas (em um caso, apenas um booleano. No outro caso, os pares de meias), as complexidades assintóticas são as mesmas.


Caso 1 : Todas as meias são idênticas (isto é o que eu faço na vida real por sinal).

Escolha dois deles para fazer um par. Tempo constante.

Caso 2 : Há um número constante de combinações (propriedade, cor, tamanho, textura, etc.).

Use radix sort . Este é apenas o tempo linear, pois a comparação não é necessária.

Caso 3 : O número de combinações não é conhecido antecipadamente (caso geral).

Nós temos que fazer uma comparação para verificar se duas meias vêm em par. Escolha um dos algoritmos de ordenação baseados na comparação O(n log n) .

No entanto, na vida real, quando o número de meias é relativamente pequeno (constante), esses algoritmos teoricamente ótimos não funcionariam bem. Pode demorar ainda mais tempo do que a pesquisa sequencial, que teoricamente requer tempo quadrático.


Você está tentando resolver o problema errado.

Solução 1: Toda vez que você colocar meias sujas no cesto de roupa suja, amarre-as em um pequeno nó. Dessa forma, você não terá que fazer qualquer classificação após a lavagem. Pense nisso como registrar um índice em um banco de dados do Mongo. Um pouco de trabalho pela frente para algumas economias de CPU no futuro.

Solução 2: Se é inverno, você não precisa usar meias iguais. Nós somos programadores. Ninguém precisa saber, desde que funcione.

Solução 3: Espalhe o trabalho. Você deseja executar um processo de CPU tão complexo de forma assíncrona, sem bloquear a interface do usuário. Pegue aquela pilha de meias e enfie-as em uma sacola. Procure apenas um par quando precisar. Dessa forma, a quantidade de trabalho necessária é muito menos perceptível.

Espero que isto ajude!


Abordagem do mundo real:

Tão rapidamente quanto possível, retire as meias da pilha não classificada, uma de cada vez, e coloque-as em pilhas à sua frente. As pilhas devem ser organizadas de maneira um pouco eficiente no espaço, com todas as meias apontando na mesma direção; o número de pilhas é limitado pela distância que você pode alcançar facilmente. A seleção de uma pilha na qual colocar uma meia deve ser - o mais rápido possível - colocando uma meia em uma pilha de meias aparentemente iguais; o tipo ocasional I (colocar uma meia em uma pilha a que não pertence) ou o tipo II (colocar uma meia em sua pilha quando há uma pilha de meias iguais) o erro pode ser tolerado - a consideração mais importante é a velocidade. Quando todas as meias estiverem em pilhas, passe rapidamente pelas pilhas de várias meias, criando pares e removendo-os (estes estão indo para a gaveta). Se houver meias não correspondentes na pilha, empilhe-as novamente na melhor pilha possível (dentro da pilha mais rápida possível). Quando todas as pilhas multi-meia tiverem sido processadas, combine as meias pares que não foram emparelhadas devido a erros do tipo II. Whoosh, você está feito - e eu tenho muitas meias e não as lavo até que uma grande parte esteja suja. Outra nota prática: eu abro o topo de um dos pares de meias sobre o outro, aproveitando suas propriedades elásticas, para que eles fiquem juntos enquanto são transportados para a gaveta e enquanto estão na gaveta.


Considere uma tabela de hash de tamanho 'N'.

Se assumirmos distribuição normal, o número estimado de 'inserções' para ter pelo menos uma meia mapeada para um intervalo é NlogN (ou seja, todos os blocos estão cheios)

Eu tinha derivado isso como parte de outro quebra-cabeça, mas ficaria feliz em provar que estava errado. Aqui está o meu artigo no blog sobre o mesmo

Deixe 'N' corresponder a um limite superior aproximado no número de número de cores exclusivas / padrão de meias que você tem.

Depois de ter uma colisão (aka: um jogo) basta remover esse par de meias. Repita o mesmo experimento com o próximo lote de meias NlogN. A beleza disso é que você pode estar fazendo comparações paralelas NlogN (resolução de colisão) por causa da maneira como a mente humana funciona. :-)


Custo: Mover meias -> alto, encontrar / procurar meias em linha -> pequeno

O que queremos fazer é reduzir o número de movimentos e compensar com o número de pesquisas. Além disso, podemos utilizar o ambiente multithreded do Homo Sapiens para armazenar mais coisas no cache de descrições.

X = Yours, Y = Seus cônjuges

Da pilha A de todas as meias:

Escolha duas meias, coloque a meia X correspondente na linha X e a meia Y na linha Y na próxima posição disponível.

Faça até que A esteja vazio.

Para cada linha X e Y

  1. Escolha a primeira meia em linha, procure ao longo da linha até encontrar a meia correspondente.

  2. Coloque na linha de meias correspondente.

  3. Opcional Enquanto você está pesquisando a linha e a meia atual que você está olhando é idêntica à anterior, faça o passo 2 para estas meias.

Opcionalmente para o passo um, você pega duas meias daquela linha em vez de duas, já que a memória cache é grande o suficiente, podemos identificar rapidamente se a meia corresponde à atual na linha que você está observando. Se você tiver a sorte de ter três braços, você poderá analisar três meias ao mesmo tempo, uma vez que a memória do objeto é grande o suficiente.

Faça até que ambos X e Y estejam vazios.

Feito

No entanto, como isso tem uma complexidade semelhante à seleção de seleção, o tempo gasto é muito menor devido às velocidades de E / S (meias móveis) e de pesquisa (procurando a linha por uma meia).


Eu tomei medidas simples para reduzir meu esforço em um processo levando O (1) tempo.

Ao reduzir minhas entradas para um dos dois tipos de meias (meias brancas para recreação, meias pretas para o trabalho), só preciso determinar qual das duas meias tenho em mãos. (Tecnicamente, como eles nunca são lavados juntos, reduzi o processo para o tempo O (0))

Algum esforço inicial é necessário para encontrar meias desejáveis ​​e comprar em quantidade suficiente para eliminar a necessidade de suas meias existentes. Como eu fiz isso antes da minha necessidade de meias pretas, meu esforço foi mínimo, mas a quilometragem pode variar.

Tal esforço inicial foi visto muitas vezes em um código muito popular e eficaz. Exemplos incluem # DEFINIR o pi a vários decimais (existem outros exemplos, mas é esse que vem à mente agora).


Meias, sejam as reais ou alguma estrutura de dados análoga, seriam fornecidas em pares.

A resposta mais simples é antes de permitir que o par seja separado, uma única estrutura de dados para o par deveria ter sido inicializada contendo um ponteiro para a meia esquerda e direita, permitindo que as meias sejam referidas diretamente ou via par. Uma meia também pode ser estendida para conter um ponteiro para seu parceiro.

Isso resolve qualquer problema de emparelhamento computacional, removendo-o com uma camada de abstração.

Aplicando a mesma ideia ao problema prático de emparelhar meias, a resposta aparente é: não permita que suas meias sejam desemparelhadas. As meias são fornecidas como um par, colocadas na gaveta como um par (talvez balançando-as juntas), usadas como um par. Mas o ponto em que o desemparelhamento é possível é na lavadora, então tudo que é necessário é um mecanismo físico que permita que as meias permaneçam juntas e sejam lavadas com eficiência.

Existem duas possibilidades físicas:

Para um objeto 'par' que mantenha um ponteiro para cada meia, poderíamos ter um saco de pano que usamos para manter as meias juntas. Isso parece ser uma sobrecarga enorme.

Mas para cada meia manter uma referência à outra, há uma solução perfeita: um popper (ou um 'botão de pressão' se você for americano), como estes:

http://www.aliexpress.com/compare/compare-invisible-snap-buttons.html

Então tudo o que você faz é encaixar suas meias logo após tirá-las e colocá-las na cesta de lavagem, e novamente você removeu o problema de precisar emparelhar suas meias com uma abstração física do conceito de 'par'.


Se a operação "move" for bastante cara, e a operação "compare" for barata, e você precisar mover todo o conjunto de qualquer maneira, em um buffer onde a procura é muito mais rápida que no armazenamento original ... apenas integre a classificação na obrigatória mover.

Eu encontrei a integração do processo de classificação em suspensão para secar torna uma brisa. Eu preciso pegar cada meia de qualquer jeito, e pendurá-la (mover) e não me custa nada pendurá-la em um lugar específico nas cordas. Agora, apenas para não forçar a pesquisa de todo o buffer (as cordas), escolho colocar meias por cor / sombra. Agora, antes de pendurar cada meia, eu olho na sua "vizinhança direita" se uma correspondência já está lá - isso limita a "digitalização" para 2-3 outras meias - e se é , Eu penduro o outro bem próximo a ele. Então eu rolo-os em pares ao remover das cordas, quando seco.

Agora, isso pode não parecer tão diferente de "formar pilhas por cor" sugerido pelas respostas principais, mas primeiro, não escolhendo pilhas discretas, mas intervalos, não tenho problema algum em classificar se "roxo" vai para pilha "vermelha" ou "azul"; apenas vai entre. E então, ao integrar duas operações (pendurar para secar e classificar), a sobrecarga de classificação, enquanto pendurado, é de 10% do que seria a separação em separado.


Aqui está um limite inferior do Omega (n log n) no modelo baseado em comparação. (A única operação válida é comparar duas meias.)

Suponha que você saiba que suas meias 2n estão dispostas desta forma:

p 1 p 2 p 3 ... p n p f (1) p f (2) ... p f (n)

onde f é uma permutação desconhecida do conjunto {1,2, ..., n}. Saber isso não pode dificultar o problema. Existem n! possíveis saídas (correspondências entre primeira e segunda metade), o que significa que você precisa de comparações log (n!) = Omega (n log n). Isso é obtido por classificação.

Desde que você está interessado em conexões para o problema de distinção de elementos: provar que o limite de Omega (n log n) para a distinção de elementos é mais difícil, porque a saída é binária sim / não. Aqui, a saída tem que ser uma correspondência e o número de saídas possíveis é suficiente para obter um limite decente. No entanto, há uma variante ligada à distinção de elementos. Suponha que você receba 2n meias e pense se elas podem ser unidas em pares. Você pode obter uma redução de ED enviando (a 1 , a 2 , ..., a n ) para (a 1 , a 1 , a 2 , a 2 , ..., a n , a n ). (Parenthetically, a prova de dureza de ED é muito interessante,via topologia .)

Eu acho que deve haver um Omega (n 2 ) ligado para o problema original, se você permitir apenas testes de igualdade. Minha intuição é: considere um gráfico em que você adiciona uma aresta após um teste e argumente que, se o gráfico não for denso, a saída não será determinada exclusivamente.


De sua pergunta, é claro que você não tem muita experiência real com a roupa :). Você precisa de um algoritmo que funcione bem com um pequeno número de meias não paráveis.

As respostas até agora não fazem bom uso de nossas capacidades de reconhecimento de padrões humanos. O jogo de Set fornece uma pista de como fazer isso bem: coloque todas as meias em um espaço bidimensional para que você possa reconhecê-las bem e facilmente alcançá-las com as mãos. Isso limita você a uma área de cerca de 120 x 80 cm. A partir daí, selecione os pares que você reconhece e remova. Coloque meias extras no espaço livre e repita. Se você lavar para pessoas com meias facilmente reconhecíveis (crianças pequenas vêm à mente), você pode fazer uma classificação de base selecionando essas meias primeiro. Este algoritmo funciona bem apenas quando o número de meias individuais é baixo


Espero poder contribuir com algo novo para este problema. Notei que todas as respostas negligenciam o fato de que existem dois pontos em que você pode executar o pré-processamento , sem diminuir o desempenho geral da lavanderia.

Além disso, não precisamos assumir um grande número de meias, mesmo para famílias grandes. Meias são retiradas da gaveta e são usadas, e são jogadas em um lugar (talvez uma lixeira) onde ficam antes de serem lavadas. Enquanto eu não chamaria a dita bin de LIFO-Stack, eu diria que é seguro assumir que

  1. as pessoas jogam as duas meias na mesma área da caixa,
  2. o bin não é randomizado em nenhum ponto e, portanto,
  3. qualquer subconjunto retirado da parte superior desse compartimento geralmente contém as duas meias de um par.

Como todas as máquinas de lavar roupa que eu conheço são limitadas em tamanho (independentemente de quantas meias você tem que lavar), e a randomização real ocorre na lavadora, não importa quantas meias tenhamos, sempre temos pequenos subconjuntos que quase não contêm singletons.

Nossas duas etapas de pré-processamento são "colocar as meias no varal" e "Tirar as meias do varal", o que temos que fazer para obter meias que não só são limpas, mas também secas. Tal como acontece com as máquinas de lavar, os varais são finitos, e eu suponho que temos toda a parte da linha onde colocamos nossas meias à vista.

Aqui está o algoritmo para put_socks_on_line ():

while (socks left in basket) {
 take_sock();
 if (cluster of similar socks is present) { 
   Add sock to cluster (if possible, next to the matching pair)
 } else {
  Hang it somewhere on the line, this is now a new cluster of similar-looking socks.      
  Leave enough space around this sock to add other socks later on 
 }
}

Não desperdice seu tempo movendo meias ou procurando a melhor combinação, tudo isso deve ser feito em O (n), o que também seria necessário para colocá-los na linha sem classificação. As meias ainda não estão emparelhadas, só temos vários clusters de similaridade na linha. É útil termos um conjunto limitado de meias aqui, pois isso nos ajuda a criar clusters "bons" (por exemplo, se houver apenas meias pretas no conjunto de meias, o agrupamento por cores não seria o caminho a seguir)

Aqui está o algoritmo para take_socks_from_line ():

while(socks left on line) {
 take_next_sock();
 if (matching pair visible on line or in basket) {
   Take it as well, pair 'em and put 'em away
 } else {
   put the sock in the basket
 }

Devo salientar que, a fim de melhorar a velocidade das etapas restantes, é aconselhável não escolher aleatoriamente a meia seguinte, mas sequencialmente tirar meia após meia de cada cluster. Ambas as etapas de pré-processamento não levam mais tempo do que apenas colocar as meias na linha ou na cesta, o que temos que fazer, não importa o que aconteça, então isso deve melhorar muito o desempenho da lavanderia.

Depois disso, é fácil fazer o algoritmo de particionamento de hash. Normalmente, cerca de 75% das meias já estão emparelhadas, deixando-me com um subconjunto muito pequeno de meias, e este subconjunto já está (de certa forma) em cluster (não introduzo muita entropia no meu cesto depois dos passos de pré-processamento). Outra coisa é que os aglomerados restantes tendem a ser pequenos o suficiente para serem manuseados de uma só vez, então é possível tirar todo um cluster da cesta.

Aqui está o algoritmo para sort_remaining_clusters ():

while(clusters present in basket) {
  Take out the cluster and spread it
  Process it immediately
  Leave remaining socks where they are
}

Depois disso, restam apenas algumas meias. É aqui que eu introduzo meias não-pareadas no sistema e procuro as meias restantes sem qualquer algoritmo especial - as meias restantes são muito poucas e podem ser processadas visualmente muito rapidamente.

Para todas as meias restantes, suponho que suas contrapartes ainda não foram lavadas e guardadas para a próxima iteração. Se você registrar um crescimento de meias não pareadas ao longo do tempo (um "vazamento de meias"), você deve verificar o seu bin - ele pode ser randomizado (você tem gatos que dormem lá?)

Eu sei que esses algoritmos levam um monte de suposições: uma caixa que funciona como uma espécie de pilha LIFO, uma máquina de lavar roupa limitada e normal, e um varal normal, mas isso ainda funciona com um grande número de meias.

Sobre o paralelismo: contanto que você jogue as duas meias na mesma lixeira, você pode facilmente paralelizar todas essas etapas.


Minha solução não corresponde exatamente às suas necessidades, pois exige formalmente O(n)espaço "extra". No entanto, considerando as minhas condições, é muito eficiente na minha aplicação prática. Assim, acho que deveria ser interessante.

Combine com outra tarefa

A condição especial no meu caso é que eu não use máquina de secagem, apenas pendure minhas roupas em um secador de pano comum. Panos pendurados requerem O(n)operações (a propósito, eu sempre considero o problema de empacotamento aqui) e o problema, por sua natureza, requer o espaço "extra" linear. Quando eu pego uma nova meia do balde, eu tento pendurá-la ao lado do par, se o par já estiver pendurado. Se for uma meia de um novo par, deixo algum espaço ao lado dela.

Oracle Machine é melhor ;-)

Obviamente, é necessário algum trabalho extra para verificar se a meia correspondente já está pendurada em algum lugar e se processaria a solução O(n^2)com coeficiente 1/2para um computador. Mas neste caso o "fator humano" é na verdade uma vantagem - eu geralmente consigo (quase O(1)) identificar rapidamente a meia correspondente se ela já estava pendurada (provavelmente algum cache imperceptível dentro do cérebro está envolvido) - considerá-la uma espécie de "oracle" limitado como no Oracle Machine ;-) Nós, os humanos, temos essas vantagens sobre as máquinas digitais em alguns casos ;-)

Já quase O(n)!

Assim, conectando o problema de emparelhar meias com o problema de pendurar panos eu recebo O(n)"espaço extra" de graça, e tenho uma solução que está O(n)no tempo, requer apenas um pouco mais de trabalho do que simples panos e permite acessar imediatamente um par completo de meias mesmo em uma manhã de segunda-feira muito ruim ... ;-)


O problema de ordenar seus pares de meias é O (n) . Antes de jogá-los no cesto de roupa suja , você passa o esquerdo para o direito. Ao tirá-los, você corta o fio e coloca cada par em sua gaveta - 2 operações em n pares, então O (n).

Agora a próxima pergunta é simplesmente se você faz sua própria roupa e sua esposa faz o dela. Esse é provavelmente um problema em um domínio totalmente diferente de problemas . :)


Quando eu ordenar meias, eu faço um tipo aproximado de radix , derrubando meias perto de outras meias do mesmo tipo de cor / padrão. Exceto no caso em que eu possa ver uma correspondência exata no / perto do local que estou prestes a largar a meia, eu extraio o par naquele ponto.

Quase todos os outros algoritmos (incluindo a resposta de pontuação superior por usr ) ordenam e, em seguida, removem pares. Acho que, como ser humano, é melhor minimizar o número de meias sendo consideradas de uma só vez.

Eu faço isso por:

  1. Escolhendo uma meia distinta (o que me chama a atenção primeiro na pilha).
  2. Começando um tipo radix daquele local conceitual, retirando as meias da pilha com base na semelhança com aquela.
  3. Coloque a nova meia perto da pilha atual, com uma distância baseada em quão diferente ela é. Se você estiver colocando a meia em cima da outra porque é idêntica, forme o par lá e remova-a. Isso significa que comparações futuras exigem menos esforço para encontrar o local correto.

Isso tira proveito da capacidade humana de correspondência fuzzy no tempo O (1), que é um pouco equivalente ao estabelecimento de um mapa de hash em um dispositivo de computação.

Ao puxar as meias distintas primeiro, você deixa espaço para "ampliar" os recursos que são menos distintos, para começar.

Depois de eliminar o fluro colorido, as meias com listras, e os três pares de meias compridas, você pode acabar com meias quase brancas classificadas pelo quão gastas elas são.

Em algum momento, as diferenças entre as meias são pequenas o suficiente para que outras pessoas não percebam a diferença, e qualquer esforço adicional de correspondência não é necessário.


Sempre que você pegar uma meia, coloque-a em um só lugar. Então, a próxima meia que você pegar, se não corresponder à primeira meia, coloque-a ao lado da primeira. Se isso acontecer, há um par. Dessa forma, não importa quantas combinações existem, e há apenas duas possibilidades para cada meia que você recebe - ou tem uma correspondência que já está na sua coleção de meias, ou não, o que significa que você adicione-o a um lugar na matriz.

Isso também significa que você quase nunca terá todas as suas meias no array, porque as meias serão removidas quando forem correspondidas.





matching