Sortierung verbessern/beschleuningen?

  • C++

Es gibt 14 Antworten in diesem Thema. Der letzte Beitrag () ist von RodFromGermany.

    Sortierung verbessern/beschleuningen?

    Hey,

    ich habe einen vector<string> mit CD-Namen, diesen sortiere ich alphabetisch und wenn eine Nummer am Ende ist, wird das auch numerisch sortiert. Dauert mir aber ein wenig lange, schon auf Windows, es soll später auf einem Raspi laufen, da wirds noch länger dauern, schon allein weil von Micro-SD gelesen wird.

    Beispiel Ergebnis der Sortierung
    ACD_1
    aCD_2
    ACD_2
    ACD_12
    BCD_1
    BCD_12
    bCD_2
    usw. ....

    So sortiere ich das:

    C-Quellcode

    1. bool IsCharLess(char c1, char c2)
    2. {
    3. return tolower(static_cast<unsigned char>(c1)) < tolower(static_cast<unsigned char>(c2));
    4. }
    6. bool Comparer(const string& s1, const string& s2)
    7. {
    8. smatch m1, m2;
    9. regex r("\\d+$");
    10. if (regex_search(s1, m1, r) && regex_search(s2, m2, r))
    11. {
    12. string a(m1.prefix());
    13. string b(m2.prefix());
    14. if (a.compare(b) == 0)
    15. {
    16. return stoi(m1.str()) < stoi(m2.str());
    17. }
    18. }
    19. return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), IsCharLess);
    20. }


    C-Quellcode

    1. vector<string> albums = vector<string>();
    2. //albums füllen;
    3. sort(albums.begin(), albums.end(), Comparer);


    Ohne Sortierung dauert der Vorgang(Daten aus dem Dateisystem hohlen) < 1 Sekunde, mit sortierung mehr als 10, die Sortierung ist also der Flaschenhals. Kann man die Sortierung irgendwie schneller hinkriegen?

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Takafusa“ ()

    @Takafusa Ich denke mal, lexicographical_compare() dauert sehr lange.
    Den Algorithmus würde ich in VB.NET oder C# optimieren, da geht das Optimieren schneller.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Leider kann ich nicht so einfach auf Net.Core umsteigen. Ich habe mir mit SDL2 eine Control-Biliothek in C++ erschaffen(bzw. bin noch dran, werde irgendwie nie fertig) läuft wunderbar auf Windows und Linux, das alles zu portieren würde mir zu lange dauern, arbeite schon sicher 1 jahr oder mehr an meinem "Kleinen-Framework".

    Jemand hat mir empfohlen sqlite zu implementieren um so nicht immer neu alles einzulesen(beim Programmstart), die Daten dann sortiert aus der DB hohlen. Wollte ich zwar nicht, weil ich noch keine Ahnung hab von DBs mit C++, aber es scheint es wäre angebracht mich mal mit sqlite unter C++ zu beschäftigen, mit Java habe ich vor langer Zeit mal damit gearbeitet. Da war Eclipse noch die Android IDE.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Takafusa“ ()

    @Takafusa Du sollst nicht umsteigen, sondern den Algorithmus in einer anderen Sprache entwickeln und optimieren.
    Danach überträgst Du den Algorithmus nach C++.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Achso hast du das gemeint. Ich habe noch ein paar Tests gemacht, Regex ist hier der Falschenhals, hab das auskommentiert so das der returnwert von lexicographical_compare direkt zurückgeht. Kaum ein merkbarer Unterschied mit und ohne Sortierung.

    Takafusa schrieb:

    Regex ist hier der Falschenhals
    Oha.
    Lässt sich das evtl. umgehen?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Ich überlege gerade wie ich das umbaue. Ich denke ich werde die beiden strings von hinten nach vorne parsen, sollte am Ende beider strings eine Nummer sein und beide strings ohne diese Nummern identisch sein, beide Zahlen durch stoi jagen und vergleichen welche Nummer kleiner ist. Ich probier das mal.

    Also die Strings sind Ordnernamen von Musik-CD-Ordnern, bestehend aus Artist und Albumname getrennt mit einem - . (siehe Anhang)

    Edit: @RodFromGermany
    Ich hab jetzt einen Prototypen fertig, geht deutlich flotter. Noch verschönern dann geht das wohl, bin aber für andere Vorschläge oder verbesserungen offen.
    Dirty Prototype:

    C-Quellcode

    1. bool IsCharLess(char c1, char c2)
    2. {
    3. return tolower(static_cast<unsigned char>(c1)) < tolower(static_cast<unsigned char>(c2));
    4. }
    6. bool Comparer(const string& s1, const string& s2)
    7. {
    8. string str1, str2;
    9. bool s1EndsWithNumber = false;
    10. bool s2EndsWithNumber = false;
    11. for (int i = s1.length() - 1; i > -1; i--)
    12. {
    13. const unsigned char c = s1[i];
    14. if (isdigit(c))
    15. {
    16. str1 += c;
    17. }
    18. else
    19. {
    20. break;
    21. }
    22. }
    23. if (str1.length() > 0)
    24. {
    25. s1EndsWithNumber = true;
    26. reverse(str1.begin(), str1.end());
    27. }
    28. for (int i = s2.length() - 1; i > -1; i--)
    29. {
    30. const unsigned char c = s2[i];
    31. if (isdigit(c))
    32. {
    33. str2 += c;
    34. }
    35. else
    36. {
    37. break;
    38. }
    39. }
    40. if (str2.length() > 0)
    41. {
    42. s2EndsWithNumber = true;
    43. reverse(str2.begin(), str2.end());
    44. }
    45. if (s1EndsWithNumber && s2EndsWithNumber)
    46. {
    47. string s1a = s1.substr(0, s1.length() - str1.length());
    48. string s2a = s2.substr(0, s2.length() - str2.length());
    49. if (s1a.compare(s2a) == 0)
    50. {
    51. return stoi(str1) < stoi(str2);
    52. }
    53. }
    54. return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), IsCharLess);
    55. }

    Bilder

    • Unbenannt.jpg

      117,39 kB, 175×868, 73 mal angesehen

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Takafusa“ ()

    Takafusa schrieb:

    C-Quellcode

    1. if (isdigit(c))
    Drehe die if-Logik um und nimm das else raus.
    Wenn die Namen alle so aussehen, arbeite mit Split und nimm dann die Teile unter die Lupe.
    Somit wäre Regex überflüssig.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Es kann aber muss keine Nummer am Ende sein. Der numerische vergleich soll nur wenn Nummern am Ende sind stattfinden, daher teste ich ob die strings ohne diese Nummern also "Artist - Albenname [entfernte nummer]" gleich sind.

    Bedingungen angepasst, ist ein wenig besser jetzt. Alles viel schneller, die Sortierung stimmt auch.

    C-Quellcode

    1. bool Comparer(const string& s1, const string& s2)
    2. {
    3. string str1, str2;
    4. unsigned char c;
    5. for (int i = s1.length() - 1; i > -1; i--)
    6. {
    7. c = s1[i];
    8. if (!isdigit(c))
    9. {
    10. break;
    11. }
    12. str1 += c;
    13. }
    14. for (int i = s2.length() - 1; i > -1; i--)
    15. {
    16. c = s2[i];
    17. if (!isdigit(c))
    18. {
    19. break;
    20. }
    21. str2 += c;
    22. }
    23. if (str1.length() > 0 && str2.length() > 0)
    24. {
    25. reverse(str2.begin(), str2.end());
    26. reverse(str1.begin(), str1.end());
    27. string s1a = s1.substr(0, s1.length() - str1.length());
    28. string s2a = s2.substr(0, s2.length() - str2.length());
    29. if (s1a.compare(s2a) == 0)
    30. {
    31. return stoi(str1) < stoi(str2);
    32. }
    33. }
    34. return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), IsCharLess);
    35. }


    @RodFromGermany Danke für den Stups in die richtige Richtung, wäre heute sicher nicht auf die Idee gekommen regex rauszuwerfen. Nach deinem Tipp, einen Algo selbst zu erstellen, kam ich erstmal auf die Idee den Regex-Teil auszukommentieren, sonst hätte ich heute nicht mehr geschnallt das dies der Flaschenhals war.

    Konnte mich also wieder mal davor drücken, DBs mit C++ in Angriff zu nehmen. :D
    Bilder

    • Unbenannt.png

      5,49 kB, 483×325, 69 mal angesehen

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Takafusa“ ()

    Also so wie ich es verstanden habe ist alles was du möchtest es lexikalisch zu sortieren?

    C-Quellcode

    1. bool compare(const std::string &left, const std::string &right)
    2. {
    3. using CharPtr = std::string::const_pointer;
    5. CharPtr lch = left .data();
    6. CharPtr rch = right.data();
    8. for (;;)
    9. {
    10. if (*lch == '\0' || *rch == '\0')
    11. {
    12. return *lch < *rch;
    13. }
    15. if (*lch != *rch)
    16. {
    17. return *lch < *rch;
    18. }
    20. (void) ++lch;
    21. (void) ++rch;
    22. }
    23. }


    Das Glück ist das auch nummerische Werte in der ASCII-Tabelle enthalten sind, daher kann man direkt nach diesem Wert gehen.
    Ich hoffe mal ich hab da jetzt keinen Schnitzer reingeworfen, ich hab das nämlich am Smartphone geschrieben und getestet. (da geht schnell mal einiges Panflöten)

    Hier is' halt so dass das ASCII-compliant ist, wenn andere Enkodierungen verwendet werden, ist das natürlich ein wenig anders!

    Es gibt auch noch eine STL variante, die so trivial wie auch effizient ist:

    C-Quellcode

    1. std::sort(vec.begin(), vec.end(), [](const std::string &str1, const std::string &str2) { return str1 < str2; });


    Das Glück hier ist das std::string einen größer-kleiner operator anbietet der dies für dich übernimmt.
    Ich würde warscheinlich diesen Wählen, da meiner zu ungetestet ist.

    Und hier auch noch ein Benchmark zwischen deinem, meinem und dem STL-Algorithmus:
    quick-bench.com/q/auKpfOpUnDU0qjaaAuMuOs_XHMQ

    Edit: hab erst gar nicht gemerkt dass du nicht nur lexikalisch sondern auch numerisch sortierst, das geht mit meinem und dem STL algorithmus natürlich nicht!
    Das hier hat aber 4 Tests bestanden:

    C-Quellcode

    1. inline constexpr char numZero = '0';
    2. inline constexpr char numNine = '9';
    4. bool isNumeric(char val)
    5. {
    6. return val >= numZero && val <= numNine;
    7. }
    9. int getNumVal(char val)
    10. {
    11. return val - numZero;
    12. }
    14. bool compare(const std::string &left, const std::string &right)
    15. {
    16. using CharPtr = std::string::const_pointer;
    18. CharPtr lch = left .data();
    19. CharPtr rch = right.data();
    21. for (;;)
    22. {
    23. if (*lch == '\0' || *rch == '\0')
    24. {
    25. return *lch < *rch;
    26. }
    28. if (isNumeric(*lch) && isNumeric(*rch))
    29. {
    30. int number_1 = 0;
    31. int number_2 = 0;
    33. if (*lch == '0' && *rch != '0')
    34. {
    35. while (*lch == '0')
    36. {
    37. if (*(++lch) == '\0')
    38. {
    39. return true;
    40. }
    41. }
    42. }
    43. else if (*lch != '0' && *rch == '0')
    44. {
    45. while (*rch == '0')
    46. {
    47. if (*(++rch) == '\0')
    48. {
    49. return false;
    50. }
    51. }
    52. }
    54. for (;;)
    55. {
    56. if (isNumeric(*lch) != isNumeric(*rch))
    57. {
    58. return !isNumeric(*lch);
    59. }
    61. if (!isNumeric(*lch) && !isNumeric(*rch))
    62. {
    63. if (number_1 != number_2)
    64. {
    65. return (number_1 < number_2);
    66. }
    68. break;
    69. }
    71. number_1 = (number_1 * 10 + getNumVal(*lch));
    72. number_2 = (number_2 * 10 + getNumVal(*rch));
    74. (void) ++lch;
    75. (void) ++rch;
    76. }
    78. continue;
    79. }
    81. if (*lch != *rch)
    82. {
    83. return *lch < *rch;
    84. }
    86. (void) ++lch;
    87. (void) ++rch;
    88. }
    89. }


    Neuer benchmark:
    quick-bench.com/q/yd43QDdR2OmYFFJBiVgIkTZBLKE
    Bilder

    • Screenshot_20210618_130107.png

      14,27 kB, 909×441, 70 mal angesehen
    ----------------------------------------------------------------------------------------------------------------------

    Hier könnte meine Signatur stehen, aber die ist mir abfußen gekommen.

    ----------------------------------------------------------------------------------------------------------------------

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „Elanda“ ()

    Hey Elanda,

    das sieht soweit sehr überzeugend aus. Ich werde heute Abend mal schauen ob die Sortierung passt, gegebenenfalls anpassen und übernehmen. Ich denke das lexicographical_compare bei mir noch bremst, merkt man aber kaum, ein Paar Tausend Ordner(ohne inhalte) sind in < 1.5 - 2 Sekunden eingelesen. Die Inhalte werden beim erst selektieren eines Albums in der GUI eingelesen.

    Ich danke Dir :)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Takafusa“ ()

    @Elanda Der Code ist wirklich schnell, die Sortierung passt nicht ganz. Weil kleingeschrieben Char erst nach dem großen Z in der Ausgabe sind. Werde einfach wenn char >= 97 && char <= 122, 32 abziehen.


    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Takafusa“ ()

    Takafusa schrieb:

    Werde einfach wenn char >= 97 && char <= 122, 32 abziehen.
    Da musst Du nix testen, sondern Du machst ein bitweises Not: & ~32 und feddich.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

Facebook
Telefonspende