pseudocode - 辞書を逆にする方法は?

Question

リソースが限られている C ベースのカスタム言語を使用しています (C のようなものもあれば、他の言語に基づいて追加されたものもあります)。非動的な配列と行列だけがあり、辞書、スタック、キューとヒープ、if、for、while cicle もあります。

私の問題は、キー: 'a' (int) と値: 'b'(int) を持つ辞書を持ち、これらの非動的構造を使用して、辞書を簡単な方法で反転するにはどうすればよいですか?次のような新しい辞書: キー: 'b'(int)、値: 'a'(int[ ])

Answer 1

非動的メモリを最大の問題とし、処理時間や中間アーティファクトのサイズを気にしない場合は、次のようになります。

1) 元の辞書を別の順序でタプルのリストに注ぎます。次に並べ替えます。

{'a': 1, 'b': 1, 'c': 2}

生産する

[[1, 'a'], [1, 'b'], [3, 'c']]

2) このリストをウォークスルーし、一意の最初の値を反復処理して、マップされた値 (つまり、元のキー) のリストを作成します。

... 生産する

{'1': ['a', 'b'], '2':['c']}

3) 中間リストを破棄し、そのメモリを再利用します。

物事のサイズと必要な速度に応じて、中間リストを調べてすべてのメモリ要件を把握し、各要素に適切なサイズのリストを事前に割り当てるステップ (1.5) を追加することもできます。繰り返しになりますが、これは動的メモリの不足を最も懸念しており、最初から「適切なサイズ」の最終結果を見つけようとしています。

Answer 2

できません。または、少なくともすべきではありません。なんで？同じ値を持つ 2 つのキーがあるとします...

それ以外の場合は、擬似コードで:

create dictionary BAR
for each key in dictionary FOO
    BAR[FOO[key]] = key