La mejor manera de ordenar una matriz
https://stackoverflow.com/questions/41733
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Digamos que tengo una serie de registros que quiero ordenar según uno de los campos del registro.¿Cuál es la mejor manera de lograr esto?
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
var SomeVar : array of TExample;
Solución
Puede agregar punteros a los elementos de la matriz a un TList, luego llame TList.Sort con una función de comparación y, finalmente, cree una nueva matriz y copie los valores de TList en el orden deseado.
Sin embargo, si está utilizando la próxima versión, D2009, hay una nueva biblioteca de colecciones que puede ordenar matrices.Se necesita una opción IComparer<TExample> Implementación de órdenes de clasificación personalizadas.Aquí está en acción para su 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));
Otros consejos
(Sé que esto es un año después, pero sigue siendo material útil).
La sugerencia de Skamradt de rellenar valores enteros supone que vas a ordenar usando una comparación de cadenas.Esto sería lento.Llamar a format() para cada inserción, más lento aún.En su lugar, desea hacer una comparación de números enteros.
Comienzas con un tipo de registro:
TExample = record
SortOrder : integer;
SomethingElse : string;
end;
No indicó cómo se almacenaron los registros ni cómo deseaba acceder a ellos una vez ordenados.Entonces supongamos que los coloca en una matriz dinámica:
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;
Ahora desea ordenar esta matriz por el valor entero SortOrder.Si lo que desea es una TStringList (para que pueda usar el método ts.Find), entonces debe agregar cada cadena a la lista y agregar SortOrder como puntero.Luego ordene según el puntero:
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;
Tenga en cuenta el truco de convertir Integer SortOrder en un puntero TObject, que se almacena en la propiedad TStringList.Object.(Esto depende del hecho de que Integer y Pointer tengan el mismo tamaño). En algún lugar debemos definir una función para comparar los punteros TObject:
function CompareObjects(ts:tStringList; Item1,Item2: integer): Integer;
var i,j: integer;
begin
Result := integer(ts.Objects[i]) - integer(ts.Objects[j];
end;
Ahora, podemos ordenar tsList en .Object llamando a .CustomSort en lugar de .Sort (lo que ordenaría según el valor de la cadena).
tsExample.CustomSort(@CompareObjects); //Sort the list
TStringList ahora está ordenado, por lo que puede iterarlo de 0 a .Count-1 y leer las cadenas en orden.
Pero supongamos que no desea una TStringList, solo una matriz ordenada.O los registros contienen más datos que solo una cadena en este ejemplo, y su orden de clasificación es más complejo.Puede omitir el paso de agregar cada cadena y simplemente agregar el índice de la matriz como Elementos en una TList.Haga todo lo anterior de la misma manera, excepto usar TList en lugar 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;
Ahora que Mlist está ordenado, utilícelo como una tabla de búsqueda para acceder a la matriz en orden:
for i:=0 to Mlist.Count-1 do begin
Something := MyDA[integer(Mlist[i])].SomeField;
end;
A medida que itero sobre TList, obtenemos los índices de la matriz en orden.Sólo necesitamos volver a convertirlos en números enteros, ya que TList cree que son punteros.
Me gusta hacerlo de esta manera, pero también puedes poner punteros reales a elementos de la matriz en TList agregando la dirección del elemento de la matriz en lugar de su índice.Luego, para usarlos, debería convertirlos como punteros a registros TExample.Esto es lo que Barry Kelly y CoolMagic dijeron que hicieran en sus respuestas.
Si necesita ordenar por cadena, utilice ordenado TStringList y
Agregar registro por TString.AddObject(string, Pointer(int_val)).
Pero si es necesario ordenar por campo entero y cadena, utilice TObjectList y después de agregar todos los registros llame TObjectList.Sort con funciones ordenadas necesarias como parámetro.
Todo esto depende de la cantidad de registros que esté ordenando.Si solo está clasificando menos de unos pocos cientos, entonces los otros métodos de clasificación funcionan bien; si va a clasificar más, entonces eche un vistazo al viejo y confiable Turbo Power. Herramientas del sistema proyecto.Hay un algoritmo de clasificación muy bueno incluido en la fuente.Uno que hace un muy buen trabajo clasificando millones de registros de manera eficiente.
Si va a utilizar el método tStringList para ordenar una lista de registros, asegúrese de que su número entero esté relleno hacia la derecha antes de insertarlo en la lista.Puedes usar el formato('%.10d',[rec.sortorder]) para alinear a la derecha con 10 dígitos, por ejemplo.
El algoritmo de clasificación rápida se utiliza a menudo cuando se requiere una clasificación rápida.Delphi lo está (o estaba) usando para List.Sort, por ejemplo.La Lista Delphi se puede utilizar para ordenar cualquier cosa, pero es un contenedor pesado, que se supone que debe verse como una serie de punteros en estructuras.Es pesado incluso si usamos trucos como Guy Gordon en este hilo (Poner índice o cualquier cosa en lugar de punteros, o poner directamente valores si son menores de 32 bits):necesitamos construir una lista y así sucesivamente...
En consecuencia, una alternativa para ordenar fácil y rápidamente una matriz de estructura podría ser utilizar función de tiempo de ejecución qsort C de msvcrt.dll.
Aquí hay una declaración que podría ser buena (Advertencia:código portátil sólo en Windows).
type TComparatorFunction = function(lpItem1: Pointer; lpItem2: Pointer): Integer; cdecl;
procedure qsort(base: Pointer; num: Cardinal; size: Cardinal; lpComparatorFunction: TComparatorFunction) cdecl; external 'msvcrt.dll';
Ejemplo completo aquí.
Tenga en cuenta que ordenar directamente la matriz de registros puede resultar lento si los registros son grandes.En ese caso, ordenar una matriz de punteros a los registros puede ser más rápido (de alguna manera, como el enfoque de Lista).
Con una matriz, usaría cualquiera de los dos quicksort o posiblemente heapsort, y simplemente cambie la comparación para usar TExample.SortOrder, la parte de intercambio seguirá actuando sobre la matriz y los punteros de intercambio.Si la matriz es muy grande, es posible que desee una estructura de lista vinculada si hay muchas inserciones y eliminaciones.
Rutinas basadas en C, hay varias aquí.http://www.yendor.com/programming/sort/
Otro sitio, pero tiene fuente pascal.http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html
Utilice uno de los algoritmos de clasificación propuestos por Wikipedia.La función Intercambiar debería intercambiar elementos de la matriz utilizando una variable temporal del mismo tipo que los elementos de la matriz.Utilice una clasificación estable si desea que las entradas con el mismo valor entero de SortOrder permanezcan en el orden en que estaban en primer lugar.
TStringList tener un método de clasificación eficiente.
Si desea ordenar utilice un TStringList objeto con Sorted propiedad a Verdadero.
NOTA:Para mayor velocidad, agregue objetos en un orden no ordenado TStringList y al final cambie la propiedad a True.
NOTA:Para ordenar por campo entero, conviértalo a cadena.
NOTA:Si hay valores duplicados, este método no es válido.
Saludos.
Si tienes Delphi XE2 o más reciente, puedes probar:
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;
Creé un ejemplo muy simple que funciona correctamente si el campo de clasificación es una cadena.
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;
