Melhor maneira de classificar um array
https://stackoverflow.com/questions/41733
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Digamos que eu tenha uma série de registros que desejo classificar com base em um dos campos do registro.Qual é a melhor maneira de conseguir isso?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
Solução
Você pode adicionar ponteiros para os elementos do array em um TList, Em seguida, ligue TList.Sort com uma função de comparação e, finalmente, crie um novo array e copie os valores do TList na ordem desejada.
No entanto, se você estiver usando a próxima versão, D2009, há uma nova biblioteca de coleções que pode classificar arrays.É preciso um opcional IComparer<TExample> implementação para ordens de classificação personalizadas.Aqui está em ação para o seu caso específico:
TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
function(const Left, Right: TExample): Integer
begin
Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
end));
Outras dicas
(Eu sei que isso foi um ano depois, mas ainda é útil.)
A sugestão de Skamradt para preencher valores inteiros pressupõe que você classificará usando uma comparação de string.Isso seria lento.Chamando format() para cada inserção, ainda mais lento.Em vez disso, você deseja fazer uma comparação de números inteiros.
Você começa com um tipo de registro:
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
Você não declarou como os registros foram armazenados ou como deseja acessá-los depois de classificados.Então, vamos supor que você os colocou em um Dynamic Array:
var MyDA Array of TExample;
...
SetLength(MyDA,NewSize); //allocate memory for the dynamic array
for i:=0 to NewSize-1 do begin //fill the array with records
MyDA[i].SortOrder := SomeInteger;
MyDA[i].SomethingElse := SomeString;
end;
Agora você deseja classificar esse array pelo valor inteiro SortOrder.Se o que você deseja é um TStringList (para que você possa usar o método ts.Find), adicione cada string à lista e adicione SortOrder como um ponteiro.Em seguida, classifique no ponteiro:
var tsExamples: TStringList; //declare it somewhere (global or local)
...
tsExamples := tStringList.create; //allocate it somewhere (and free it later!)
...
tsExamples.Clear; //now let's use it
tsExamples.sorted := False; //don't want to sort after every add
tsExamples.Capacity := High(MyDA)+1 //don't want to increase size with every add
//an empty dynamic array has High() = -1
for i:=0 to High(MyDA) do begin
tsExamples.AddObject(MyDA[i].SomethingElse,TObject(MyDA[i].SortOrder));
end;
Observe o truque de converter o Integer SortOrder em um ponteiro TObject, que é armazenado na propriedade TStringList.Object.(Isso depende do fato de que Integer e Pointer são do mesmo tamanho.) Em algum lugar devemos definir uma função para comparar os ponteiros TObject:
function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;
Agora, podemos classificar o tsList em .Object chamando .CustomSort em vez de .Sort (que classificaria o valor da string).
tsExample.CustomSort(@CompareObjects); //Sort the list
O TStringList agora está classificado, então você pode iterá-lo de 0 a .Count-1 e ler as strings na ordem de classificação.
Mas suponha que você não queira um TStringList, apenas um array em ordem de classificação.Ou os registros contêm mais dados do que apenas uma string neste exemplo e sua ordem de classificação é mais complexa.Você pode pular a etapa de adição de cada string e apenas adicionar o índice do array como itens em uma TList.Faça tudo acima da mesma maneira, exceto usar um TList em vez de TStringList:
var Mlist: TList; //a list of Pointers
...
for i:=0 to High(MyDA) do
Mlist.add(Pointer(i)); //cast the array index as a Pointer
Mlist.Sort(@CompareRecords); //using the compare function below
function CompareRecords(Item1, Item2: Integer): Integer;
var i,j: integer;
begin
i := integer(item1); //recover the index into MyDA
j := integer(item2); // and use it to access any field
Result := SomeFunctionOf(MyDA[i].SomeField) - SomeFunctionOf(MyDA[j].SomeField);
end;
Agora que Mlist está classificado, use-o como uma tabela de pesquisa para acessar o array na ordem de classificação:
for i:=0 to Mlist.Count-1 do begin
Something := MyDA[integer(Mlist[i])].SomeField;
end;
À medida que iteramos no TList, recuperamos os índices do array em ordem de classificação.Só precisamos convertê-los de volta para números inteiros, já que o TList pensa que são ponteiros.
Gosto de fazer dessa maneira, mas você também pode colocar ponteiros reais para elementos do array no TList adicionando o endereço do elemento do array em vez de seu índice.Então, para usá-los, você os lançaria como ponteiros para registros TExample.Isso é o que Barry Kelly e CoolMagic disseram em suas respostas.
Se você precisar classificar por string, use classificado TStringList e adicione o registro por TString.AddObject(string, Pointer(int_val)).
Mas se precisar classificar por campo inteiro e string - use TObjectList e depois de adicionar todos os registros ligue TObjectList.Sort com funções classificadas necessárias como parâmetro.
Tudo isso depende do número de registros que você está classificando.Se você estiver classificando apenas menos de algumas centenas, os outros métodos de classificação funcionam bem; se você estiver classificando mais, dê uma boa olhada no antigo e confiável Turbo Power SysTools projeto.Existe um algoritmo de classificação muito bom incluído na fonte.Um que faz um trabalho muito bom classificando milhões de registros de maneira eficiente.
Se você for usar o método tStringList para classificar uma lista de registros, certifique-se de que seu número inteiro esteja preenchido à direita antes de inseri-lo na lista.Você pode usar o formato('%.10d',[rec.sortorder]) para alinhar à direita com 10 dígitos, por exemplo.
O algoritmo quicksort é frequentemente usado quando uma classificação rápida é necessária.Delphi está (ou estava) usando-o para List.Sort, por exemplo.A Lista Delphi pode ser usada para classificar qualquer coisa, mas é um contêiner pesado, que supostamente se parece com um array de ponteiros em estruturas.É pesado mesmo se usarmos truques como Guy Gordon neste tópico (colocar índice ou qualquer coisa no lugar de ponteiros, ou colocar valores diretamente se eles forem menores que 32 bits):precisamos construir uma lista e assim por diante...
Conseqüentemente, uma alternativa para classificar de maneira fácil e rápida um array de struct pode ser usar função de tempo de execução qsort C de msvcrt.dll.
Aqui está uma declaração que pode ser boa (Aviso:código portátil apenas no Windows).
type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';
Exemplo completo aqui.
Observe que a classificação direta da matriz de registros pode ser lenta se os registros forem grandes.Nesse caso, classificar uma matriz de ponteiros para os registros pode ser mais rápido (de alguma forma, como a abordagem de lista).
Com uma matriz, eu usaria quicksort ou possivelmente heapsort, e apenas altere a comparação para usar TExample.SortOrder, a parte de troca ainda atuará apenas no array e trocará ponteiros.Se a matriz for muito grande, você pode querer uma estrutura de lista vinculada se houver muitas inserções e exclusões.
Rotinas baseadas em C, existem várias aquihttp://www.yendor.com/programming/sort/
Outro site, mas tem fonte pascalhttp://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
Use um dos algoritmos de ordenação propostos por Wikipédia.A função Swap deve trocar os elementos do array usando uma variável temporária do mesmo tipo dos elementos do array.Use uma classificação estável se desejar que as entradas com o mesmo valor inteiro SortOrder permaneçam na ordem em que estavam inicialmente.
TStringList tem um método de classificação eficiente.
Se você quiser classificar, use um TStringList objeto com Sorted propriedade como True.
OBSERVAÇÃO:Para mais velocidade, adicione objetos em um formato não classificado TStringList e no final altere a propriedade para True.
OBSERVAÇÃO:Para classificar por campo inteiro, converta para String.
OBSERVAÇÃO:Se houver valores duplicados, este método não é válido.
Cumprimentos.
Se você possui Delphi XE2 ou mais recente, você pode tentar:
var
someVar: array of TExample;
list: TList<TExample>;
sortedVar: array of TExample;
begin
list := TList<TExample>.Create(someVar);
try
list.Sort;
sortedVar := list.ToArray;
finally
list.Free;
end;
end;
Criei um exemplo bem simples que funciona corretamente se o campo de classificação for uma string.
Type
THuman = Class
Public
Name: String;
Age: Byte;
Constructor Create(Name: String; Age: Integer);
End;
Constructor THuman.Create(Name: String; Age: Integer);
Begin
Self.Name:= Name;
Self.Age:= Age;
End;
Procedure Test();
Var
Human: THuman;
Humans: Array Of THuman;
List: TStringList;
Begin
SetLength(Humans, 3);
Humans[0]:= THuman.Create('David', 41);
Humans[1]:= THuman.Create('Brian', 50);
Humans[2]:= THuman.Create('Alex', 20);
List:= TStringList.Create;
List.AddObject(Humans[0].Name, TObject(Humans[0]));
List.AddObject(Humans[1].Name, TObject(Humans[1]));
List.AddObject(Humans[2].Name, TObject(Humans[2]));
List.Sort;
Human:= THuman(List.Objects[0]);
Showmessage('The first person on the list is the human ' + Human.name + '!');
List.Free;
End;
