Sortier Array von Strukturen in C
https://stackoverflow.com/questions/4245546
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe eine Struktur:
typedef struct book{
double rating;
double price;
double relevance;
int ID;
}B;
ein Array
list* B;
und eine Datei dieser so in den Dateien mit diesem
lesenint read_file(char* infile, int N)
{
int c;
if((fp=fopen(infile, "rb")))
{
fscanf(fp, "%*s\t%*s\t%*s\t%*s\n");
c=0;
while((!feof(fp))&&(c<N))
{
fscanf(fp, "%lf\t%lf\t%lf\t%d\n", &list[c].rating, &list[c].price, &list[c].relevance, &list[c].ID);
c++;
}
fclose(fp);
}
else
{
fprintf(stderr,"%s did not open. Exiting.\n",infile);
exit(-1);
}
return(c);
}
und eine Vergleichsmethode
int comp_on_price(const void *a, const void *b)
{
if ((*(B *)a).price < (*(B *)b).price)
return 1;
else if ((*(B *)a).price > (*(B *)b).price)
return -1;
else
return 0;
}
Ich möchte eine stabile Art mit nlog (n) Zeit vielleicht fusionieren Art in der Reihenfolge der niedrigsten prie höchsten
Ich brauche nur die 20 günstigsten Preisen anzubieten.
Wie würde ich zu Methode, dies mit meinem vergleichen implementieren?
Dank
Lösung 7
ich habe schließlich diese eine Zählung mit Art es mehr als 100 Zeilen Code in c nahm.
ich habe es dann in einer Zeile in einem Shell-Skript
sort -NK 2,2 -s Wodehouse.txt | Art -rnk 3,3 -s | Art -rnk 1,1 -s | Kopf -20
Andere Tipps
würde ich eine stabile mag Art mit nlog (n) Zeit vielleicht fusionieren Art in der Reihenfolge der niedrigsten prie höchsten
Ich brauche nur die 20 günstigsten Preisen anzubieten.
Dann können Sie dies in O (n) Zeit. Sie können die ersten 20 Werte in O (N) Zeit dann sortieren diejenigen O (1) finden.
qsort ist dein Freund :). (Während es nicht Nlog (N) im schlimmsten Fall, es ist schwierig, alles tut, tut schneller)
Da Sie C und nicht C ++ erwähnt, würde ich sagen, Sie als Ihre eigene Version von etwas Ähnliches wie die Umsetzung qsort () .
Schauen Sie, wie der Komparator für qsort definiert. Sie würden etwas Ähnliches für sich selbst definieren müssen? Für die eigentliche Sortierung, müssten Sie Ihre eigene Version von StableSort () von Grund auf neu implementieren.
Die Funktion, die Sie verwenden möchten, ist qsort . C kommt mit einer völlig akzeptabel Art, die tut genau , was Sie scheinen zu müssen.
qsort selbst ist keine stabile Art (na ja, es können werden für eine gegebene Implementierung, aber der Standard es ist keine Garantie), aber es kann in einem mit einigen Tricks gemacht werden. Ich habe das getan, bevor sie durch einen Zeiger auf die Array-Elemente hinzugefügt, die zunächst mit der Adresse des Elements selbst (oder einem zunehmenden Integer-Wert, wie Sie die Datei wahrscheinlich tun wird hier lesen) gefüllt wird.
Dann können Sie, dass als Nebenschlüssel verwenden, die Elemente mit dem gleichen Hauptschlüssel sichergestellt, um gehalten werden.
Wenn Sie nicht , um die Mühe machen wollen, die Strukturen zu verändern, ist Algorithmist ein guter Ort, um Code von bekommen. Ich selbst neigen dazu, kleinere Änderungen an Re-Implementierungen zu bevorzugen.
Um es wirklich stabil machen, ändern Sie Ihre Struktur:
typedef struct book {
double rating;
double price;
double relevance;
int ID;
int seq; // Added to store sequence number.
} B;
und Ihre Datei Lesecode ändern:
fscanf(fp, "%lf\t%lf\t%lf\t%d\n", ...
list[c].seq = c; // Yes, just add this line.
c++;
dann Vergleichsfunktion wird so etwas wie:
int comp_on_price(const void *a, const void *b) {
B *aa = (B*)a;
B *bb = (B*)b;
if (aa->price < bb->price)
return 1;
if (aa->price > bb->price)
return -1;
return (aa->seq < bb->seq) ? 1 : -1; // Cannot compare equal.
}
Sie haben nicht zu qsort alles brauchen. Erstellen Sie einfach ein leeres B * Array für die 20 niedrigsten Aufzeichnungen, kopieren Sie die ersten Seite <= 20 Datensätze dort und qsort sie, wenn es dann mehr als 20 ist, wie Sie Iterierte über Ihre Elemente sich zu dem höchsten in den ersten 20 vergleichen: if mehr dann weiter sonst nächsthöhere usw. zurück auf die niedrigsten dann verschieben die anderen Zeiger zu machen Platz für Ihren nächsten Eintrag in der Low-20 zu vergleichen. Sie einen deterministischen Vergleich müssen - hört an dieser Front paxdiablo:. Eine Eingabedatensatznummer oder etwas zu unterscheiden Datensätze hinzufügen
Es ist nur eine leichte Änderungen an Ihrer comparizon Funktionsbibliothek qsort stabil zu machen. Siehe Link hier
Wie etwas unterhalb sollte den Trick (ungetestet, seien Sie vorsichtig) tun:
int comp_on_price(const void *a, const void *b)
{
if ((*(B *)a).price < (*(B *)b).price)
return 1;
else if ((*(B *)a).price > (*(B *)b).price)
return -1;
else
// if zero order by addresses
return a-b;
}
Das würde funktionieren, wenn Sie a und b in demselben Adressraum (zwei Zeiger im selben Array) garantieren können und dass alle Vergleiche eine größere Gesamtordnung des Arrays geben, Adressen von unteren Strukturen neigen dazu, noch langsamer zu werden . Dies gilt für die Blase Arten oder ähnliches. Das wäre auch für eine triviale Implementierung von QucikSort arbeiten (die qsort nicht). Doch für andere Algorithmen oder jeden Algorithmus zusätzlichen Adressraum für die temporäre Speicherung verwenden (vielleicht zur Optimierung Zweck), wird diese Eigenschaft nicht wahr sein.
Wenn das, was Sie Art enthalten einen eindeutigen Bezeichner in Vergleich Positionen (im aktuellen Beispiel, das für das Feld ID wahrscheinlich wahr ist), ein weiteres Verfahren der Art stabil diese Elemente zu vergleichen wäre zu machen. Sie könnten auch zu diesem Zweck einen solchen eindeutigen Schlüssel in ein neues Feld hinzufügen, aber da es mehr Speicher verwendet, sollten Sie die dritte Option unter dem betrachten beschrieben, bevor Sie.
Meine bevorzugte Methode wäre noch ein dritte sein, nicht direkt Art ein Array von Strukturen, aber Art eines Array von Zeigern auf tatsächliche Strukturelemente. Dies hat mehrere gute Eigenschaften. Zuerst können Sie Arrays der Struktur vergleichen, zeigten auf, da es nicht ändern und es wird die Art stabil machen.
Die Vergleichsfunktion wird wie etwas werden:
int comp_on_price(const void *a, const void *b)
{
if ((*(B **)a)->price < (*(B **)b)->price)
return 1;
else if ((*(B **)a)->price > (*(B **)b)->price)
return -1;
else
// if zero, order by addresses
return *(B **)a-*(B **)b;
}
Andere gute Eigenschaften ist, dass es Strukturen um vermeiden zu bewegen, während das Sortieren, es müssen nur bewegende Zeiger, und das kann Zeit rettend sein. Sie können auch mehrere solcher Zeiger-Arrays halten, und die auf Array-Elemente gleichzeitig mehrere geordnete Zugriffe ermöglichen.
Die Nachteile sind, dass es einige Speicher und dass der Zugriff auf Elemente nimmt geringfügig langsamer (ein Dereferenzierungsebene mehr).
