Hilfe für Sortiermethode gesucht

Bashar

Da es vermutlich relativ unwahrscheinlich ist, dass zwei Strings bis auf Klein/Großschreibung identisch sind, würde ich den zweiten Vergleich nicht immer pauschal mitlaufen lassen, sondern erst danach im Fall des Falles durchführen.

happystudent

Ok, vielen Dank für die Antworten

Werd das mit euren Tipps gleich nochmal neu angehen

happystudent

Hallo nochmal,

ich hab es zwar jetzt so hingekriegt dass die List so sortiert wird wie ich will, aber so richtig glücklich bin ich noch nicht mit der Lösung...

Hab jetzt dass hier:

struct Comparator
{
	public:
		bool operator()(std::string const &first, std::string const &second) const
		{
			if (std::lexicographical_compare(first.begin(), first.end(), second.begin(), second.end(), sort_method))
				return true;
			// Dass hier sollte möglichst selten auftreten
			if (!std::lexicographical_compare(second.begin(), second.end(), first.begin(), first.end(), sort_method))
				return std::lexicographical_compare(second.begin(), second.end(), first.begin(), first.end(), sort_method_case);
			return false;
		}

	private:
		static bool sort_method(char c1, char c2)
		{
			if (c1 == '_')
				c1 = 123;
			if (c2 == '_')
				c2 = 123;

			return (tolower(c1) < tolower(c2));
		}
		static bool sort_method_case(char c1, char c2)
		{
			if (c1 == '_')
				c1 = 123;
			if (c2 == '_')
				c2 = 123;

			return c1 < c2;
		}
};

Problem ist, dass der Code ab dem Kommentar im Code halb so oft aufgerufen wird wie der davor. Also ich hab eine List mit etwa 6000 Elementen.

Das erste lexicographical_compare wird dann etwa 120000 mal aufgerufen (was ja schon eine ganze Menge ist). Das zweite lexicographical_compare wird aber auch 60000 mal aufgerufen. Dabei gibt es nur extrem wenige Elemente die bis auf Groß/Kleinschreibung gleich sind, vielleicht insgesamt 5.

Nur wegen diesen paar Einträgen hab ich jetzt einfach mal 50% mehr Rechenaufwand

Sieht hier jemand noch Optimierungspotential? Am besten um sich möglichst oft das zweite lexicographical_compare zu sparen (das sollte ja eigentlich nur in den aller-wenigsten Fällen gebraucht werden)...

Schreibe ein lexicographical_compare selbst. Sieht ungefähr so aus:

template<iteratorkram>
bool comp(it s1, it e1, it s2, it e2, case_insensitive_comparer){
    auto bs1 = *s1;
    auto bs2 = *s2;
    while (s1 != e1 && s2 != e2){
        if (tolower(*s1) < tolower(*s2))
            return true;
        else if (tolower(*s1) > tolower(*s2))
            return false;
        else{
            s1++;
            s2++;
        }
    return comp(bs1, e1, bs2, e2, case_sensitive_comparer);
    }
}

Damit gehst du 2 mal über den String. Einmal geht auch, aber dann muss man in der Schleife doppelte Arbeit machen, das bringts bestimmt nicht.
Vielleicht wäre auch die richtige Design-entscheidung einfach eine weniger komplizierte Vorschrift zu nehmen.

happystudent

nwp3 schrieb:

Vielleicht wäre auch die richtige Design-entscheidung einfach eine weniger komplizierte Vorschrift zu nehmen.

Ja, also ich bin gerne offen für Vorschläge. Die Sache ist halt die, ich habe zwei Anforderungen an den Sortiermechanismus:

1.) Die Wörter sollen Case-Insensitiv Sortiert werden (das ist bereits gegeben)
2.) Die Sortierung muss eindeutig sein

Dabei bereitet der zweite Punkt eben Probleme. Denn wenn ich einfach nur Case-Insensitiv sortiere (wie im ersten Post dargestellt), dann ist die Sortierung nicht eindeutig, da die Sortierung dann nicht nur vom Inhalt der unsortierten Liste abhängt sondern auch von deren Element-Reihenfolge.

Wenn ich also folgende unsortierte Liste habe:

Unsortiert		Case-Insensitiv Sortiert

zzz				abc
abc				ABC
AC				AC
ABC				zzz

Wenn ich jetzt die gleiche Liste in einer anderen Startkonfiguration habe und diese dann nach dem gleichem Prinzip sortiere erhalte ich:

Unsortiert		Case-Insensitiv Sortiert

ABC				ABC // <- Unterschiedlich!
zzz				abc
abc				AC	
AC				zzz

Und genau dass ist mein Problem. Ich brauche (zwingend) einen Sortieralgorithmus der für zwei gleiche Listen auch immer die gleiche Sortierung zurückgibt, unabhängig von der Startkonfiguration der Listen.

Also zwei Listen die exakt die gleichen Elemente enthalten, aber in Unterschiedlicher Reihenfolge, müssen nach dem Sortieren exakt gleich sortiert sein so dass sie Elementweise identisch sind.

Das ist leider durch eine reine Case-Insensitive Sortierung nicht gegeben.

Das ist das eigentlich Problem was ich hier zu lösen versuche. Gibt es dafür bessere Wege?

cooky451

happystudent schrieb:

1.) Die Wörter sollen Case-Insensitiv Sortiert werden (das ist bereits gegeben)
2.) Die Sortierung muss eindeutig sein

Ja wie gesagt, dafür steht die Lösung in der ersten Antwort. (Wenn du das "eigentliche Problem" im 1. Beitrag erklärt hättest, hättest du viel Zeit gespart.)

happystudent

cooky451 schrieb:

Ja wie gesagt, dafür steht die Lösung in der ersten Antwort.

Seit wann ist bitte "geht so nicht" eine praktikable Lösung?

cooky451 schrieb:

(Wenn du das "eigentliche Problem" im 1. Beitrag erklärt hättest, hättest du viel Zeit gespart.)

Gut, dann sag mir doch bitte wie ich das Problem am besten löse?

Immerhin wurde hier bereits angemerkt dass es sich bei meiner jetzigen Lösung um eine komplizierte Vorschrift handelt. Nur wie kann ich es sonst machen?

Wenn ich eine List sortiere, dann soll das Ergebnis unabhängig vom Initial-Zustand der List sein. Das ist doch eine relativ "normale" Forderung, oder nicht?

cooky451

happystudent schrieb:

Seit wann ist bitte "geht so nicht" eine praktikable Lösung?

Seitdem direkt dadrüber die praktikable Lösung steht. <.<

happystudent schrieb:

Gut, dann sag mir doch bitte wie ich das Problem am besten löse?

Siehe 1. Beitrag.

happystudent schrieb:

Immerhin wurde hier bereits angemerkt dass es sich bei meiner jetzigen Lösung um eine komplizierte Vorschrift handelt. Nur wie kann ich es sonst machen?

Siehe 1. Beitrag.

happystudent schrieb:

Wenn ich eine List sortiere, dann soll das Ergebnis unabhängig vom Initial-Zustand der List sein. Das ist doch eine relativ "normale" Forderung, oder nicht?

Ja, ist es.

volkard

happystudent schrieb:

Wenn ich eine List sortiere, dann soll das Ergebnis unabhängig vom Initial-Zustand der List sein. Das ist doch eine relativ "normale" Forderung, oder nicht?

Wenn ein char(123) im String vorkommt, ist er bei Dir gleich zum '_'.

happystudent

cooky451 schrieb:

Seitdem direkt dadrüber die praktikable Lösung steht. <.<

Oh, das funktioniert ja wirklich genauso wie ich es will, das ist ja perfekt. Ich hatte direkt deinen Edit gelesen und da der ja unter der Lösung steht dachte ich der bezieht sich darauf. War nicht ganz so offensichtlich.

Dann muss man gar nicht zweimal über die Strings iterieren, super

volkard schrieb:

Wenn ein char(123) im String vorkommt, ist er bei Dir gleich zum '_'.

Ja, das ist eigentlich ein Hack, ich weiß schon. Aber da char(123) nie in der Liste vorkommt (auch nicht vorkommen darf) passt das schon, denke ich.

Danke auf jeden Fall für die Hilfe an alle, Problem ist gelöst