3

つまり、'symbols' と 'volumes' という 2 つの財務データ ファイルがあります。シンボルには、次のような文字列があります。

FOO
BAR
BAZINGA
...

ボリュームには、次のような整数値があります。

0001387
0000022
0123374
...

アイデアは、株式シンボルがファイル内で繰り返され、各株式の総量を見つける必要があるということです。したがって、foo を観察する各行では、ボリュームで観察された値だけ foo の総ボリュームを増やします。問題は、これらのファイルが非常に大きくなる可能性があることです。簡単に 5 ～ 1 億レコードになります。典型的な 1 日には、ファイル内に最大 1,000 個の異なるシンボルが含まれる場合があります。

新しい行ごとにシンボルに対して strcmp を使用すると、非常に非効率的になります。連想配列を使用することを考えていました---文字列キーを許可するハッシュテーブルライブラリ---uthashまたはGlibのハッシュテーブルなど。

についてかなり良いことを読んでいJudy arraysますか？この場合、ライセンスに問題はありますか?

効率的なハッシュテーブルの実装の選択について何か考えはありますか? また、ハッシュ テーブルをまったく使用する必要があるのか​​、それともまったく別のものを使用する必要があるのか​​。

うーん..前の省略をお詫びします。純粋な C ソリューションが必要です。

ありがとう。

4

4 に答える 4

0

を使用MapしC++ STLます。擬似コードは次のようになります。

map< string, long int > Mp;
while(eof is not reached)
{
    String stock_name=readline_from_file1();

    long int stock_value=readline_from_file2();

    Mp[stock_name]+=stock_value;
}
for(each stock_name in Mp)
   cout<<stock_name<<" "<<stock_value<<endl;

あなたが提供したデータの量に基づいて、それは少し非効率的かもしれませんが、実装がはるかに簡単なので、これをお勧めします.

ソリューションが に厳密に実装される場合はC、hashingが最適なソリューションになります。しかし、ハッシュ テーブルの実装と回避するコードの記述collisionsが複雑だと思われる場合は、 を使用する別のアイデアがありtrieます。奇妙に聞こえるかもしれませんが、これも少しは役に立ちます。

これを読むことをお勧めします。trieaとは何か、それをどのように構築するかについての素晴らしい説明があります。Cでの実装もそこに与えられました。volumesそのため、 for eachをどこに保存すればよいか疑問に思うかもしれませんstock。この値は の最後に保存でき、stock string必要なときにいつでも簡単に更新できます。

しかし、あなたが C を初めて使うと言うように、使用して実装してhash tableから、これを試してみることをお勧めします。

于 2013-06-20T08:27:28.943 に答える
0

連想配列のアイデアに固執しない理由を考えてみてください。実行の最後に、集計された値を含む一意の名前のリストが必要だと思います。以下は、すべての一意の名前を保持するためのメモリがある限り機能します。もちろん、これはそれほど効率的ではないかもしれませんが、データのパターンに応じて実行できるトリックはほとんどありません。

Consolidate_Index =0;

struct sutruct_Customers
{
name[];
value[];
}

sutruct_Customers Customers[This_Could_be_worse_if_all_names_are_unique]

void consolidate_names(char *name , int value)
{
    for(i=0;i<Consolidate_Index;i++){
        if(Customers[i].name & name)
            {
            Customers[i].value+= Values[index];

            }
    else
    {
    Allocate memory for Name Now!
    Customers[Consolidate_Index].name = name;
    Customers[Consolidate_Index].value = Value;
    Consolidate_Index++;
    }
    }
}

main(){

sutruct_Customers buffer[Size_In_Each_Iteration]

while(unless file is done){

file-data-chunk_names to buffer.name
file-data-chunk_values to buffer.Values

for(; i<Size_In_Each_Iteration;i++)
consolidate_names(buffer.Names , buffer.Values);

}
于 2013-06-20T10:11:47.493 に答える