私は弦のセットを持っています。それらの 90% は で始まる URL です"http://www."。アルファベット順に並べたい。
現在、C++ std::sort() を使用しています。しかし、std::sort は比較に基づくクイック ソートの変形であり、長い共通プレフィックスを持つ 2 つの文字列を比較することは効率的ではありません。ただし、（私が思うに）基数ソートも機能しません。これは、共通のプレフィックスが長いため、ほとんどの文字列が同じバケットに入れられるためです。
この問題に対して、通常のクイックソート/基数ソートよりも優れたアルゴリズムはありますか?
URL の平均の長さを考えると、URL ごとに 10 文字程度の一般的なプレフィックスを悪用しようとして費やした処理時間は、元に戻らないのではないかと思います。
完全に標準的な並べ替えを試してみてください。それが十分に速くない場合は、完全に標準的な並べ替えを並列化または分散することを検討してください。それはうまくいく簡単なアプローチです。
Common Prefixs は、トライ データ構造が役立つ可能性があることを自然に暗示しているようです。したがって、アイデアは、すべての単語のトライを構築し、各ノードをソートすることです。順序付けは、特定のノードの子がリストに存在し、ソートされるようにする必要があります。特定のノードでは子をソートするだけでよいため、これは簡単に実行できます。そのため、自然に再帰的なソリューションが明らかになります。さらなるインスピレーションについては、http: //goanna.cs.rmit.edu.au/~jz/fulltext/acsc03sz.pdfを参照してください。