文字列配列を数えてソートする最良の方法は何ですか

Question

検索する（出現回数を数える）良い方法があるかどうかを調べ、効率的な方法で文字列配列をソートしようとしています。組み込みシステム（32Mb）でうまくいく方法

例：文字A、B、Cなどを使用して、後のソートのためにその結果を保存する回数を数えなければならない...

public int count（String searchDomain、char searchValue）メソッドを使用してカウントできますが、各文字列はすべてのアルファベット文字を含む必要があります。

"This is a test string" 
A:1,B:0,C:0,D:0,E:1,I:3,F:0,... 
"ACAAGATGCCATTGTCCCCCGGCCTCCTGCTGCTGCTGCTCTCCGGGGCCACGGCCACCGCTGCCCTGCC" 
A:7,B:0,C:22,G:18 

私のソート方法は、のようなものにお答えできるようにする必要があります：それはアプリケーションのためだ、これは宿題のためではありません旅館

することにより、そのサブドメインをようでソート最初のように、BS の数でソートして、並べ替えること携帯電話で実行する必要があります、私はこれが効率的である必要があります、私の現在の実装はあまりにも遅く、あまりにも多くのメモリを使用しています。

Answer 1

Javaの（非常に効率的な）組み込み機能を利用したいと思います。で起動するには、あなたの文字列とそのメタデータを格納する単純なクラスを定義します。

class Item 
{ 
    // Your string. It's public, so you can get it if you want, 
    // but also final, so you can't accidentally change it. 
    public final String string; 

    // An array of counts, where the offset is the alphabetical position 
    // of the letter it's counting. (A = 0, B = 1, C=2...) 
    private final short[] instanceCounts = new short[32]; 

    public Item(String string) 
    { 
     this.string = string; 
     for(char c : string.toCharArray()) 
     { 
      // Increment the count for this character 
      instanceCounts[(byte)c - 65] ++; 
     } 
    } 

    public int getCount(char c) 
    { 
     return instanceCounts[(byte)c - 65]; 
    } 
} 

これは、（検索や表示用）あなたの文字列を保持し、一致した文字の数とショートパンツの配列を設定します。 （の場合、実際にはのメモリが不足していて、文字列に255文字以上の文字が含まれていることがわかっている場合は、これをバイト配列に変更することもできます）。shortは16バイトであるため、あなたの文字列の複雑さにかかわらず、64バイトすべてを一緒に取る。毎回カウントを計算するためのパフォーマンスヒットを得るには、配列を取り除いてgetCount（）メソッドを置き換えることができますが、頻繁にガベージコレクションされたメモリ、これは大きなパフォーマンスヒットです。:)

コンパレータを使用して検索するルールを定義します。

class CompareByNumberOfA implements Comparator<Item> 
{ 
    public int compare(Item arg0, Item arg1) 
    { 
     return arg1.getCount('A') - arg0.getCount('A'); 
    } 
} 

最後に、配列内のアイテムのすべてを貼り、およびソートする（と非常に効率的なメモリ）配列方法で構築された使用：たとえば、あなたの文字列の中の数でソートします。例：

public static void main(String args[]) 
{ 
    Item[] items = new Item[5]; 
    items[0]= new Item("ABC"); 
    items[1]= new Item("ABCAA"); 
    items[2]= new Item("ABCAAC"); 
    items[3]= new Item("ABCAAA"); 
    items[4]= new Item("ABBABZ"); 

    // THIS IS THE IMPORTANT PART! 
    Arrays.sort(items, new CompareByNumberOfA()); 

    System.out.println(items[0].string); 
    System.out.println(items[1].string); 
    System.out.println(items[2].string); 
    System.out.println(items[3].string); 
    System.out.println(items[4].string); 
} 

コンパレータを一括して定義し、好きなように使用できます。

Javaでコーディングすることについて覚えておくべきことの1つは、あまりにも巧妙になることではありません。コンパイラは、それらを利用する限り、プラットホームの最適化のための素晴らしい仕事をします。（Arrays.sortを含む組み込みAPIのような）最適化。

多くの場合、賢明になりすぎると、効果的なソリューションから自分自身を最適化するだけです。 :)

Answer 2

私はphp /擬似コード、ハッシュマップ、または連想配列をサポートできます。最後に

$hash=""; 

$string = "ACAAGATGCCATTGTCCCCCGGCCTCCTGCTGCTGCTGCTCTCCGGGGCCACGGCCACCGCTGCCCTGCC" 
while (read each $char from $string) { 

    if (isset($hash[$char])) { 
     $hash[$char] = $hash[$char]+1 
    } else { 
     $hash[$char]=1 
    } 
} 

あなたは1キー/文字と連想配列は を発見し、ハッシュ値にあなたが出現箇所

のカウントはそれはPHP（または他の言語ではありませんがありますがありますそのためには原則が役立つはずです。

Answer 3

私はあなたがしているのはツリー構造であり、実際には「カウント」や「ソート」ではなく長い連続した文字列を索引付けするためにツリー構造について書き直すのがよいと思います。

これが解決策か質問の再表示であるかわかりません。木構造のデータ構造が必要ですか。 26のサブツリー、1つは 'A'で始まる文字列、もう1つは 'B'の子、などです。 「A」の子供は、例えば、 "AB"、 "AC"、 "AT"などを表す20人の子供。子供を代表する子どもに至るまで。 "ABALXYZQ"。各子はカウントを表す整数フィールド、すなわちサブストリングが発生する回数を含む。これはあなたがCPU時間のためのメモリとのトレードオフの方法を模索しているはずだが、それは行うことは難しいかもしれないその後、あまりにも多くのメモリを使用している場合

class AdamTree { 
    char ch; 
    List<AdamTree> children; 
    int count; 
} 

は...何も心に来ることはありません。

Answer 4

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm KMPアルゴリズムを見てください。これはかなり一般的なプログラミング上の問題です。あなたの上には、可能な限り最速の解決法があります。理解しやすく実装する。

挿入後にマージソートを行うか、配列/ etcがソートされていることがわかっている場合は、バイナリ検索/方向挿入を使用してください。

Answer 5

多分、ある深さが与えられた文字に対応する一種の木構造を使うことができます。したがって、ツリー内の各ノードは、文字+その文字の出現回数に対応する。このノード（およびその親ノード）に一致する文字列が1つだけの場合、そのノードに格納されます。それ以外の場合、ノードには次の文字と文字数の子ノードがあります。これは、アレイ・カウント・ソリューションよりも低いコストだが、少なくともあなたはすべての文字列のすべての文字のカウントを保存する必要はありません

A:  0     1     3   ... 
     |    / \   / \ 
B:  0    0  1   1  3 
    /\   heaven / \  barracuda ababab 
C: 0 1     0  1 
    foo cow    bar  bac 

わからない（：

これにより、このような何かを与えるだろう手紙は数える一意の文字列を識別する際、ツリーはおそらく兄弟

Answer 6

せずに長い枝を切断して、それを最適化することができ

あなたは

0123の下にJavaでコードを試みることができる）を停止します

int[] data = new int[254];//we have 254 different characters 
void processData(String mString){ 

    for (int i=0 ; i< mString.length;i++){ 
     char c = mString.charAt(i); 
     data[c]++; 
    } 
} 
int getCountOfChar(char c){ 
    return data[c]; 
} 

Answer 7

申し訳ありません申し訳ありませんが、これをより良い方法で書く時間がありません。スペースを最小限に抑えるために、私は2メートルX N（緻密）アレイ、1バイトになるだろうし、一方の短：

• mは
• nは各文字列内の文字の数である入力文字列の数です。この次元は、バイト配列は、カウントが< 256を保証されている場合は

、あなただけの1つのmxnx 2バイト配列を使用することができ

短い配列は、その文字のカウントが含まれている文字が含まれてい

行ごとに変わります。

使用している文字の集合が密である場合、つまりANY文字列で使用されるALL文字の集合が、各文字列で使用される文字集合よりはるかに大きくない場合、バイト配列を取り除くことができます文字からインデックスにマップする関数で固定の "n"（上記）を使用します。これはずっと速いでしょう。

これは、Q句のあるクエリの場合、この配列の2Qトラバーサルを必要とします。うまくいけば、これは十分に速いでしょう。

Answer 8

あなたの要件と目標が何かに混乱があるようです。

検索結果に余裕がある場合は、結果を「圧縮して圧縮」しないでください。ハッシュ関数のようなもの。次に、結果を取得する必要がある場合、ハッシュはより長い検索アルゴリズムで適切に検索する必要がある文字列のサブセットを示します。

実際にStringオブジェクトを格納していて、文字列が実際に人間が判読できるテキストの場合は、検索とインデックスとすべてを完了した後にjava.util.zipでそれらを収縮させることができます。 の場合、実際にを小さくしておきたい場合は、実際にStringオブジェクトを受け取らず、26種類の文字しか持っていないと言いますが、それらを5ビットのグループに圧縮して保存することができます。これにはCharSequenceインターフェイスを使用します。