-1

キーと値のペアを持つリストがあるとします。キーも値もペアも一意である必要はありません。

次の例

a -> 1
b -> 2
c -> 3
a -> 3
b -> 1

有効です。

ここで、任意のキーと値のペア (k->v) に、次のプロパティを持つ別の値 V を関連付けたいとします。

  • キーが同一であれば、2 つのペアで同じです。
  • リスト全体のキーと値のペアのセットによって一意に決定されます

これは抽象的なように聞こえますが、たとえば、合計、最大、およびカウント関数は例として適格です

 Pair    SUM    MAX  COUNT
a -> 1    4      3     2
b -> 2    3      2     2
c -> 3    3      3     1
a -> 3    4      3     2
b -> 1    3      2     2

リスト全体でそのような関数を計算するための高速なメソッド/データ構造を探しています。

キーを並べ替えることができる場合、単純にリストを並べ替えてから、並べ替えられたリストを反復処理し、同一のキーを使用して各ブロックの関数 V を計算できます。

値が比較できない場合、またはエントリの順序を変更したくない場合に、これを行うための優れた方法があるかどうかを尋ねています。

いくつかの考え：

  1. もちろん、ソート可能なキーを取得するために、キーにハッシュ関数を適用することもできます。
  2. もちろん、各ペアの元の位置を保存し、並べ替えを行い、関数を計算し、最後に並べ替えを元に戻すこともできます。

したがって、本質的に、質問はすでに回答されています。ただし、おそらくいくつかの適応データ構造を使用した、よりエレガントなソリューションがあるかどうかに興味があります

編集: Sunny Agrawal のコメントを明確にするために、アソシエイトとは何を意味するのかを説明します。これは、データ構造を適切に配置する方法に関する問題の一部でもあります。私の例では、(k->v) をキーとして、V を値として別のリスト/マップを取得します。ただし、データをそのように配置しない方がよい場合もあります。V は、特定の k に対して V を取得するのに一定の時間を必要とするような方法で保存する必要があります。

4

1 に答える 1

1

2DS維持

1. List< Pair< Key_Type, Value_Type > >
2. Map<Key_Type, Stats>

ここで、Stats は次のような構造体です

struct Stats
{
    int Sum;
    int Count;
    int Max;
};

最初の DS には、保存する順序ですべてのキーと val のペアが含まれ、2 番目には、例に示すように各キーのデータ統計が保持されます

挿入は次のように機能します (疑似 C++ コード)

void Insert(key,val)
{
    list.insert(Pair(key,val))

    Stats curr;
    if(map.contains(key))
    {
        curr = map[key];
        curr.Max = Max(curr.Max, val);
        curr.Count++;
        curr.Sum += val;
    }
    else
    {
        curr.Max = val
        curr.Count = 1;
        curr.Sum = val;
    }
    map[key] = curr; 
}

複雑さは、リストを更新する場合は O(1)、マップを更新する場合は O(lgM) になります。ここで、M は一意のキーの数であり、N がリスト内のオブジェクトの総数の場合、挿入の合計時間は O(N) + O(NlogM) になります。

注: これは、挿入のみの場合に機能します。削除の場合、Max の更新は困難になります。

于 2013-10-07T14:51:03.573 に答える