sorting - 巨大な文字列の文字を並べ替える

Question

区切り記号のない文字と数字の 1 つの巨大な文字列を含む 16 MB のテキスト ドキュメントがあります。抜粋: 「as81jsa8sm1o1kmka9s93m1l」

台本を書かなくても、すべての文字をアルファベット順に並べ替える簡単な方法はありますか? ファイルの重さでJSがクラッシュするのではないかと心配しています。

ありがとう。

Answer 1

文字列に文字と数字のみが含まれていることがわかっている場合は、バケット ソートを使用して良好なパフォーマンスを実現できます。

使用している言語がわからないので、文字列を 1 文字ずつ読み取れると仮定します。私の解決策は疑似コードです

int[] buckets = int[36]; // 26 for letters, 10 for numbers; assuming only lowercase characters
while(string.hasNext()) {
  char x = next character in string;
  if(x.isAlpha()) {
    buckets[x-'a']++;
  }else {
    buckets[26 + x - '0']++
  }

}

ソートされた文字列を出力するには:

string s = ""; // at the end of the loops, s will contain the sorted string
for(int i =0 ; i < 26; ++i) {
  int y = buckets[i];
  for(int j = 0; j < y; ++j) {
    s+=(y+'a');
  }

}
for(int i =0 ; i < 10; ++i) {
  int y = buckets[i+26];
  for(int j = 0; j < y; ++j) {
    s+=(y+'0');
  }

}