{"id":2424,"date":"2019-12-21T10:27:33","date_gmt":"2019-12-21T07:27:33","guid":{"rendered":"http:\/\/demensdeum.com\/blog\/?p=2424"},"modified":"2024-12-16T22:32:31","modified_gmt":"2024-12-16T19:32:31","slug":"lexicompare","status":"publish","type":"post","link":"https:\/\/demensdeum.com\/blog\/fr\/2019\/12\/21\/lexicompare\/","title":{"rendered":"Algorithme de comparaison lexicographique"},"content":{"rendered":"<p>L&#8217;algorithme de comparaison de cha\u00eenes lexicographiques fonctionne tr\u00e8s simplement\u00a0: les codes de caract\u00e8res sont compar\u00e9s en boucle et le r\u00e9sultat est renvoy\u00e9 si les caract\u00e8res ne sont pas \u00e9gaux.<\/p>\n<p>Un exemple pour le langage C peut \u00eatre trouv\u00e9 ici\u00a0:<br \/><a href=\"https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libiberty\/memcmp.c\">https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libiberty\/memcmp.c<\/a><\/p>\n<p>Il convient de prendre en compte le fait que vous devez comparer les caract\u00e8res dans un seul encodage statique, par exemple dans Swift, j&#8217;ai utilis\u00e9 la comparaison caract\u00e8re par caract\u00e8re en UTF-32. L&#8217;option de tri de tableau utilisant memcmp fonctionnera exactement pour les caract\u00e8res \u00e0 un octet, dans d&#8217;autres cas (codages de longueur variable), l&#8217;ordre peut \u00eatre incorrect. Je n&#8217;exclus pas la possibilit\u00e9 d&#8217;une impl\u00e9mentation bas\u00e9e sur des encodages de longueur variable, mais ce sera tr\u00e8s probablement un ordre de grandeur plus compliqu\u00e9.<\/p>\n<p>La complexit\u00e9 temporelle de l&#8217;algorithme est O(1) dans le meilleur des cas, O(n) dans la moyenne et le pire des cas<\/p>\n<h3>Sources<\/h3>\n<p><a href=\"https:\/\/ru.wikipedia.org\/wiki\/Lexicographic_order\" target=\"_blank\" rel=\"noopener\">https:\/\/ru.wikipedia.org\/wiki\/Lexicographic_order<\/a> <\/p>\n<h3>Sources<\/h3>\n<p><a href=\"https:\/\/gitlab.com\/demensdeum\/algorithms\/blob\/master\/lexiCompare\/lexiCompare.swift\" target=\"_blank\" rel=\"noopener\">https:\/\/gitlab.com\/demensdeum \/algorithms\/blob\/master\/lexiCompare\/lexiCompare.swift<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>L&#8217;algorithme de comparaison de cha\u00eenes lexicographiques fonctionne tr\u00e8s simplement\u00a0: les codes de caract\u00e8res sont compar\u00e9s en boucle et le r\u00e9sultat est renvoy\u00e9 si les caract\u00e8res ne sont pas \u00e9gaux. Un exemple pour le langage C peut \u00eatre trouv\u00e9 ici\u00a0:https:\/\/github.com\/gcc-mirror\/gcc\/blob\/master\/libiberty\/memcmp.c Il convient de prendre en compte le fait que vous devez comparer les caract\u00e8res dans un<a class=\"more-link\" href=\"https:\/\/demensdeum.com\/blog\/fr\/2019\/12\/21\/lexicompare\/\">Continue reading <span class=\"screen-reader-text\">&#8220;Algorithme de comparaison lexicographique&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[61,52],"tags":[131,135],"class_list":["post-2424","post","type-post","status-publish","format-standard","hentry","category-techie","category-tutorials","tag-algorithms","tag-lexicompare","entry"],"translation":{"provider":"WPGlobus","version":"3.0.2","language":"fr","enabled_languages":["en","ru","zh","de","fr","ja","pt","hi"],"languages":{"en":{"title":true,"content":true,"excerpt":false},"ru":{"title":true,"content":true,"excerpt":false},"zh":{"title":true,"content":true,"excerpt":false},"de":{"title":true,"content":true,"excerpt":false},"fr":{"title":true,"content":true,"excerpt":false},"ja":{"title":true,"content":true,"excerpt":false},"pt":{"title":true,"content":true,"excerpt":false},"hi":{"title":false,"content":false,"excerpt":false}}},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2424","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/comments?post=2424"}],"version-history":[{"count":13,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2424\/revisions"}],"predecessor-version":[{"id":3929,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/posts\/2424\/revisions\/3929"}],"wp:attachment":[{"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/media?parent=2424"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/categories?post=2424"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/demensdeum.com\/blog\/fr\/wp-json\/wp\/v2\/tags?post=2424"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}