Como posso ordenar os números lexicographically?

votos
12

Aqui está o cenário.

Eu sou dado um array 'A' de inteiros. O tamanho da matriz não é fixo. A função que eu deveria escrever pode ser chamado uma vez com uma variedade de apenas alguns inteiros enquanto outro tempo, pode mesmo conter milhares de números inteiros. Além disso, cada número inteiro não necessita de conter o mesmo número de dígitos.

Eu sou suposto 'tipo' os números na matriz de tal forma que a matriz resultante tem os inteiros ordenada de forma lexicográfica (ou seja, eles são classificadas com base em suas representações de seqüência. Aqui 123 é a representação de cadeia de 123). Por favor, note que a saída deve conter apenas números inteiros, e não os seus equivalentes de cordas.

Por exemplo: se a entrada é:

[12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000]

Então, a saída deve ser:

[1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654]

Minha abordagem inicial: I convertido cada inteiro ao seu formato de cadeia, e depois acrescentou zeros ao seu direito de fazer todos os inteiros contêm o mesmo número de dígitos (este foi o passo confuso uma vez que envolveu rastreamento etc tornando a solução muito ineficiente) e, em seguida, fez radix sort. Finalmente, removeram os zeros acolchoadas, as cordas convertido de volta para os seus números inteiros e colocá-los na matriz resultante. Esta era uma solução muito ineficiente.

Fui levado a acreditar que a solução não precisa de estofamento etc e não há uma solução simples, onde você só tem que processar os números de alguma forma (alguns bits de processamento?) Para obter o resultado.

Qual é a solução espaço-wise mais eficiente que você pode pensar? Time-sábio?

Se você está dando o código, eu prefiro Java ou pseudo-código. Mas se isso não combina com você, qualquer tipo de linguagem deve ser fino.

Publicado 19/05/2009 em 14:59
fonte usuário
Em outras línguas...                            


14 respostas

votos
9

Pseudo-código executável (aka Python): thenumbers.sort(key=str). Sim, eu sei que o uso de Python é uma espécie de batota - é apenas muito poderosa ;-). Mas, falando sério, isso também significa: se você pode classificar uma matriz de seqüências lexicographically, como Python do tipo intrinsecamente pode, em seguida, basta fazer o "string chave" fora de cada número e tipo matriz que auxiliar (você pode, em seguida, reconstruir a matriz de números desejada por um STR-> transformação int, ou fazendo o tipo sobre os índices via indirecta, etc etc); isso é conhecido como DSU (Decorar, Sort, undecorate) e é o que o key=argumento para implementos de ordenação do Python.

Em mais detalhe (pseudocódigo):

  1. alocar uma matriz de char ** auxenquanto a numbersmatriz
  2. para i de 0 a length of numbers-1,aux[i]=stringify(numbers[i])
  3. atribuir uma matriz de int indicesdo mesmo comprimento
  4. para i de 0 a length of numbers-1,indices[i]=i
  5. tipo indices, utilizando comocmp(i,j) strcmp(aux[i],aux[j])
  6. atribuir uma matriz de int resultsdo mesmo comprimento
  7. para i de 0 a length of numbers-1,results[i]=numbers[indices[i]]
  8. memcpy resultsmaisnumbers
  9. gratuito todas aux[i], e também aux, indices,results
Respondeu 19/05/2009 em 15:02
fonte usuário

votos
4

Desde que você mencionou Java é a linguagem real em questão:

Você não precisa converter de e para strings. Em vez disso, definir o seu próprio comparador e usar isso na classificação.

Especificamente:

Comparator<Integer> lexCompare = new Comparator<Integer>(){
   int compareTo( Integer x, Integer y ) {
      return x.toString().compareTo( y.toString() );
   }
};

Depois, você pode classificar a matriz como este:

int[] array = /* whatever */;
Arrays.sort( array, lexCompare );

(Nota: A int/ Integerincompatibilidade funciona automaticamente através de auto-boxing)

Respondeu 19/05/2009 em 15:25
fonte usuário

votos
3

A classificação real pode ser feito por qualquer algoritmo que você gosta. A chave para este problema é encontrar a função de comparação que irá identificar corretamente quais os números devem ser "menos do que" os outros, de acordo com este esquema:

bool isLessThan(int a, int b)
{
    string aString = ToString(a);
    string bString = ToString(b);

    int charCount = min(aString.length(), bString.length())
    for (charIndex = 0; charIndex < charCount; charIndex++)
    {
        if (aString[charIndex] < bString[charIndex]) { return TRUE; }
    }

    // if the numbers are of different lengths, but identical
    // for the common digits (e.g. 123 and 12345)
    // the shorter string is considered "less"
    return (aString.length() < bString.length());
}
Respondeu 19/05/2009 em 15:15
fonte usuário

votos
3

Eu tinha acabado de transformá-los em cordas, e em seguida, classificar em seguida, classificar usando strcmp, que faz comparações lex.

Alternativamente, você pode escrever uma função "lexcmp" que compara dois números usando% 10 e / 10, mas isso é basicamente a mesma coisa que chamar atoi muitas vezes, por isso não é uma boa ideia.

Respondeu 19/05/2009 em 15:08
fonte usuário

votos
2

Você definitivamente não precisa pad o resultado. Não vai mudar a ordem do lexicographical comparar, será mais propenso a erros, e isso só vai desperdiçar ciclos de CPU. O método mais eficiente de "espaço-wise" seria converter os números para strings quando são comparados. Dessa forma, você não teria necessidade de alocar uma matriz adicional, os números seriam comparados no lugar.

Você pode obter uma razoavelmente boa implementação rapidamente por apenas convertendo-os em cordas, conforme necessário. Stringifying um número não é particularmente caro e, desde que você está lidando apenas com duas cordas ao mesmo tempo, é bastante provável que eles vão permanecer no cache da CPU em todos os momentos. Assim, as comparações será muito mais rápido do que o caso em que você converter a matriz inteira de cordas, uma vez que não precisará ser carregado a partir da memória principal para a cache. As pessoas tendem a esquecer que a CPU tem um cache e que os algoritmos que fazer um monte de seu trabalho em uma pequena área local de memória vão beneficiar muito o acesso ao cache muito mais rápido. Em algumas arquiteturas, o cache é muito mais rápido do que a memória que você pode fazer centenas de operações em seus dados no tempo que teria levado para carregá-lo da memória principal. Assim fazendo mais trabalho na função de comparação realmente pode ser significativamente mais rápido do que o pré-processamento do array. Especialmente se você tem uma grande variedade.

Tente fazer a serialização corda e comparação em uma função de comparação e benchmark que. Eu acho que vai ser uma boa solução. Exemplo pseudo-código Java-ish:

public static int compare(Number numA, Number numB) {
    return numA.toString().compare(numB.toString());
}

Eu acho que qualquer bit comparações sábios fantasia que você poderia fazer teria de ser aproximadamente equivalente ao trabalho envolvido na conversão de números para strings. Portanto, você provavelmente não iria obter benefício significativo. Você não pode simplesmente fazer um pouco direto para comparação bit, que lhe daria uma ordem diferente do tipo lexicográfica. Você precisa ser capaz de descobrir cada dígito para o número de qualquer maneira, por isso é mais simples de apenas torná-los cordas. Pode haver algum truque liso, mas todos os caminhos que eu posso pensar em cima da minha cabeça é complicado, propenso a erros, e muito mais trabalho do que vale a pena.

Respondeu 19/05/2009 em 15:14
fonte usuário

votos
2

Minha tentação seria dizer que o int a conversão de cadeia que aconteceria no código comparitor em vez da granel. Embora isso possa ser mais elegante de um código de perspectiva que eu teria que dizer que o esforço de execução seria maior à medida que cada número pode ser comparado várias vezes.

Eu estaria inclinado a criar uma nova matriz contendo tanto o int e representação em cadeia (não tenho certeza de que você precisa para preencher as versões de cordas para a comparação de string para produzir a ordem que você deu), tipo que na corda e depois copiar o int valores de volta para a matriz original.

Eu não posso pensar de uma maneira matematicamente inteligente de classificar isso como por sua própria declaração de que deseja classificar lexicographically então você precisa para transformar os números para cordas para fazer isso.

Respondeu 19/05/2009 em 15:08
fonte usuário

votos
1

A questão não indica como tratar inteiros negativos na ordem de agrupamento lexicográfica. Os métodos baseados em strings apresentados anteriormente normalmente irá classificar os valores negativos para a frente; por exemplo, {-123, -345, 0, 234, 78} é deixado nessa ordem. Mas se os sinais de menos deveriam ser ignorado, a ordem de saída deve ser {0, -123, 234, -345, 78}. Pode-se adaptar um método baseado em cadeia para produzir esse fim por meio de testes adicionais tanto-pesados.

Pode ser mais simples, na teoria e código, para usar um comparador que compara partes fracionárias de logaritmos comuns de dois inteiros. Ou seja, ele irá comparar os mantissas da base 10 logaritmos de dois números. Um comparador baseada logaritmo irá correr mais rápido ou mais lento do que um comparador baseado em texto, dependendo de especificações de desempenho de ponto flutuante de um CPU e na qualidade das implementações.

O código Java, indicada no fim desta resposta inclui dois comparadores à base de logaritmo: alogComparee slogCompare. O ex ignora sinais, de modo produziria {0, -123, 234, -345, 78} a partir de {-123, -345, 0, 234, 78}.

O número do grupos apresentados a seguir são a saída produzida pelo programa Java.

A secção “Rand dar” mostra uma matriz de dados aleatório darcomo gerado. Lê-se transversalmente e, em seguida, para baixo, 5 elementos por linha. Nota, matrizes sar, larae larsinicialmente são cópias não ordenados de dar.

A seção “espécie dar” é dar, após separação via Arrays.sort(dar);.

A secção “sar lex” mostra matriz sarapós separação com Arrays.sort(sar,lexCompare);, onde lexCompareé semelhante ao Comparatormostrado na resposta de Jason Cohen.

A secção de “log Lar s” mostra matriz larsapós separação por Arrays.sort(lars,slogCompare);, que ilustra um método à base de logaritmo que dá a mesma ordem como fazer lexComparee outros métodos baseados em corda.

A secção “LAR um log” mostra matriz laraapós separação por Arrays.sort(lara,alogCompare);, que ilustra um método à base de logaritmo que ignora sinais de menos.

dar rand    -335768    115776     -9576    185484     81528
dar rand      79300         0      3128      4095    -69377
dar rand     -67584      9900    -50568   -162792     70992

dar sort    -335768   -162792    -69377    -67584    -50568
dar sort      -9576         0      3128      4095      9900
dar sort      70992     79300     81528    115776    185484

 sar lex    -162792   -335768    -50568    -67584    -69377
 sar lex      -9576         0    115776    185484      3128
 sar lex       4095     70992     79300     81528      9900

lar s log    -162792   -335768    -50568    -67584    -69377
lar s log      -9576         0    115776    185484      3128
lar s log       4095     70992     79300     81528      9900

lar a log          0    115776   -162792    185484      3128
lar a log    -335768      4095    -50568    -67584    -69377
lar a log      70992     79300     81528     -9576      9900

código Java é mostrado abaixo.

// Code for "How can I sort numbers lexicographically?" - jw - 2 Jul 2014
import java.util.Random;
import java.util.Comparator;
import java.lang.Math;
import java.util.Arrays;
public class lex882954 {
// Comparator from Jason Cohen's answer
    public static Comparator<Integer> lexCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            return x.toString().compareTo( y.toString() );
        }
    };
// Comparator that uses "abs." logarithms of numbers instead of strings
    public static Comparator<Integer> alogCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
            Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
            Double xf=xl-xl.intValue();
            return xf.compareTo(yl-yl.intValue());
        }
    };
// Comparator that uses "signed" logarithms of numbers instead of strings
    public static Comparator<Integer> slogCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
            Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
            Double xf=xl-xl.intValue()+Integer.signum(x);
            return xf.compareTo(yl-yl.intValue()+Integer.signum(y));
        }
    };
// Print array before or after sorting
    public static void printArr(Integer[] ar, int asize, String aname) {
        int j;
        for(j=0; j < asize; ++j) {
            if (j%5==0)
                System.out.printf("%n%8s ", aname);
            System.out.printf(" %9d", ar[j]);
        }
        System.out.println();
    }
// Main Program -- to test comparators
    public static void main(String[] args) {
        int j, dasize=15, hir=99;
        Random rnd = new Random(12345);
        Integer[] dar = new Integer[dasize];
        Integer[] sar = new Integer[dasize];
        Integer[] lara = new Integer[dasize];
        Integer[] lars = new Integer[dasize];

        for(j=0; j < dasize; ++j) {
            lara[j] = lars[j] = sar[j] = dar[j] = rnd.nextInt(hir) * 
                rnd.nextInt(hir) * (rnd.nextInt(hir)-44);
        }
        printArr(dar, dasize, "dar rand");
        Arrays.sort(dar);
        printArr(dar, dasize, "dar sort");
        Arrays.sort(sar, lexCompare);
        printArr(sar, dasize, "sar lex");
        Arrays.sort(lars, slogCompare);
        printArr(lars, dasize, "lar s log");
        Arrays.sort(lara, alogCompare);
        printArr(lara, dasize, "lar a log");
    }
}
Respondeu 02/07/2014 em 17:38
fonte usuário

votos
1

Se todos os números são inferiores a 1E + 18, você poderia lançar cada número para UINT64, multiplique por dez e adicione um, e, em seguida, multiplicar por dez até que eles são pelo menos 1E + 19. Em seguida, classificar os. Para receber de volta os números originais, dividir cada número por dez até o último dígito é diferente de zero (que deve ser um) e depois dividir por dez mais uma vez.

Respondeu 27/06/2012 em 15:41
fonte usuário

votos
1

Se você quiser tentar uma melhor pré-processar-sort-postprocess, em seguida, note que um int é no máximo 10 dígitos decimais (ignorando assinou-ness para o momento).

Assim, os dados binários-codificado-decimal para que ele se encaixa em 64 bits. Mapa dígitos 0-> 1, 1-> 2 etc, e usar 0 como um terminador NUL (para garantir que "1" sai a menos de "10"). Mudar cada dígito, por sua vez, começando com o menor, no topo de uma longa. Organizar os longs, que sairá em ordem lexicográfica para os ints originais. Em seguida, converter de volta, deslocando um dígitos de cada vez para fora do topo de cada longa:

uint64_t munge(uint32_t i) {
    uint64_t acc = 0;
    while (i > 0) {
        acc = acc >> 4;
        uint64_t digit = (i % 10) + 1;
        acc += (digit << 60);
        i /= 10;
    }
    return acc;
}

uint32_t demunge(uint64_t l) {
    uint32_t acc = 0;
    while (l > 0) {
        acc *= 10;
        uint32_t digit = (l >> 60) - 1;
        acc += digit;
        l << 4;
    }
}

Ou algo assim. Como o Java não tem ints não assinados, você teria que modificá-lo um pouco. Ele usa uma grande quantidade de memória (o dobro do tamanho da entrada) de trabalho, mas que ainda é menor do que a sua abordagem inicial. Pode ser mais rápido do que a conversão para cordas em tempo real na comparação, mas ele usa mais memória de pico. Dependendo da GC, pode produzir o seu caminho através menos memória total, embora, e exigem menos coleção.

Respondeu 19/05/2009 em 16:24
fonte usuário

votos
1

Pseudo-código:

sub sort_numbers_lexicographically (array) {
    for 0 <= i < array.length:
        array[i] = munge(array[i]);
    sort(array);  // using usual numeric comparisons
    for 0 <= i < array.length:
        array[i] = unmunge(array[i]);
}

Então, quais são mungee unmunge?

mungeé diferente dependendo do tamanho inteiro. Por exemplo:

sub munge (4-bit-unsigned-integer n) {
    switch (n):
        case 0:  return 0
        case 1:  return 1
        case 2:  return 8
        case 3:  return 9
        case 4:  return 10
        case 5:  return 11
        case 6:  return 12
        case 7:  return 13
        case 8:  return 14
        case 9:  return 15
        case 10:  return 2
        case 11:  return 3
        case 12:  return 4
        case 13:  return 5
        case 14:  return 6
        case 15:  return 7
}

Esentially que munge está fazendo é dizer que ordem 4 bits inteiros vêm em quando classificadas lexigraphically. Tenho certeza que você pode ver que há um padrão aqui --- Eu não tive que usar um interruptor --- e que você pode escrever uma versão mungeque lida com 32 bit inteiros razoavelmente facilmente. Pense em como você iria escrever versões mungepara 5, 6 e 7 bit inteiros, se você não pode ver imediatamente o padrão.

unmungeé o inverso da munge.

Então você pode evitar converter qualquer coisa para uma string --- você não precisa de qualquer memória extra.

Respondeu 19/05/2009 em 15:35
fonte usuário

votos
0

Um método realmente hacky (usando C) seria:

  • gerar uma nova matriz de todos os valores convertidos para flutuadores
  • fazer uma espécie usando os bits (significando) mantissa para a comparação

Em Java (a partir de aqui ):

long bits = Double.doubleToLongBits(5894.349580349);

boolean negative = (bits & 0x8000000000000000L) != 0; 
long exponent = bits & 0x7ff0000000000000L >> 52;
long mantissa = bits & 0x000fffffffffffffL;

assim você iria classificar na longa mantissaaqui.

Respondeu 19/05/2009 em 17:13
fonte usuário

votos
0
#!/usr/bin/perl

use strict;
use warnings;

my @x = ( 12, 2434, 23, 1, 654, 222, 56, 100000 );

print $_, "\n" for sort @x;

__END__

Alguns horários ... Primeiro, com @x vazio:

C:\Temp> timethis s-empty
TimeThis :  Elapsed Time :  00:00:00.188

Agora, com 10.000 elementos gerados aleatoriamente:

TimeThis :  Elapsed Time :  00:00:00.219

Isso inclui o tempo necessário para gerar os elementos 10.000, mas não o tempo para enviá-las para o console. A saída adiciona cerca de um segundo.

Então, poupar algum tempo programador ;-)

Respondeu 19/05/2009 em 15:20
fonte usuário

votos
0

otimização possível: em vez disso:

Eu converti cada inteiro ao seu formato de cadeia, e depois acrescentou zeros ao seu direito de fazer todos os inteiros contêm o mesmo número de dígitos

você pode multiplicar cada número por (10 ^ N - log10 (número)), sendo n um número maior do que log10 de qualquer um dos seus números.

Respondeu 19/05/2009 em 15:19
fonte usuário

votos
0

Se você estiver indo para a eficiência do espaço-wise, eu tentaria apenas fazendo o trabalho na função de comparação do tipo

int compare(int a, int b) {
   // convert a to string
   // convert b to string
   // return -1 if a < b, 0 if they are equal, 1 if a > b
}

Se ele é muito lento (é mais lento do que o pré-processamento, com certeza), acompanhar as conversões em algum lugar para que a função de comparação não manter ter que fazê-las.

Respondeu 19/05/2009 em 15:12
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more