4

順序どおりに範囲を広げる決定的な方法を探していますGo map。

Golangの仕様には次のように記載されています。

マップの反復順序は指定されておらず、反復ごとに同じであるとは限りません。まだ達していないマップ エントリが反復中に削除されると、対応する反復値は生成されません。反復中にマップ エントリが作成された場合、そのエントリは反復中に生成されるか、スキップされる可能性があります。選択は、作成されたエントリごとに、また反復ごとに異なる場合があります。マップが nil の場合、反復回数は 0 です。

ここで StackOverflow と Google で見つけたのは、私が気に入らない( imho ) 回避策だけです。

マップを繰り返し処理し、挿入された順序でアイテムを取得する確実な方法はありますか?

私が見つけた解決策は次のとおりです。

  • キーと値を 2 つの別々のスライスで追跡します。これは、「マップを使用しない」ように聞こえ、マップを使用する利点がすべて失われます。

  • マップを使用しますが、別のスライスでキーを追跡します。これはデータの重複を意味し、データの不整合につながる可能性があり、最終的には大量のバグと面倒なデバッグをもたらす可能性があります。

何を指示してるんですか？

重複フラグの可能性に応じて編集します。

私の質問と提供された質問 (この質問だけでなく、この質問も)にはわずかな違いがあります。代わりに、私は具体的に尋ねました：

マップを反復処理し、挿入された順序でアイテムを取得する確実な方法はありますか?

@gramme.ninjaこれは辞書式ではないため、質問とは異なります。

キーを順番に並べたり、マップを並べ替えたりして、キーが順番に並べられ、値が対応するようにするにはどうすればよいですか?

4

1 に答える 1

10

順番に と キーが必要な場合map、これらは 2 つの異なるものであり、その機能を提供するには 2 つの異なる (データ) タイプが必要です。

キースライス付き

これを実現する最も簡単な方法は、別のスライスでキーの順序を維持することです。新しいペアをマップに配置するときはいつでも、最初にキーが既にそこにあるかどうかを確認してください。そうでない場合は、新しいキーを別のスライスに追加します。要素を順番に並べる必要がある場合は、キー スライスを使用できます。もちろん、ペアを削除するときは、スライスからも削除する必要があります。

キー スライスにはキーのみが含まれていればよい (値は含まれていない) ため、オーバーヘッドはほとんどありません。

この新しい機能 (マップ + キー スライス) を新しい型にラップしてメソッドを提供し、マップとスライスを非表示にします。そうすれば、データの不整合は発生しません。

実装例:

type Key int   // Key type
type Value int // Value type

type Map struct {
    m    map[Key]Value
    keys []Key
}

func New() *Map {
    return &Map{m: make(map[Key]Value)}
}

func (m *Map) Set(k Key, v Value) {
    if _, ok := m.m[k]; !ok {
        m.keys = append(m.keys, k)
    }
    m.m[k] = v
}

func (m *Map) Range() {
    for _, k := range m.keys {
        fmt.Println(m.m[k])
    }
}

それを使用して：

m := New()
m.Set(1, 11)
m.Set(2, 22)
m.Range()

Go Playgroundで試してみてください。

リンクリストを実装する値ラッパーを使用

別のアプローチは、値をラップし、実際の値に沿って次/前のキーも格納することです。

たとえば、次のようなマップが必要だとしますmap[Key]Value。

type valueWrapper struct {
    value Value
    next  *Key // Next key
}

ペアをマップに追加するときはいつでもvalueWrapper、値としてa を設定し、これを前の (最後の) ペアにリンクする必要があります。リンクするnextには、最後のラッパーのフィールドがこの新しいキーを指すように設定する必要があります。これを簡単に実装するには、最後のキーも保存することをお勧めします (検索する必要がないようにするため)。

要素を挿入順に反復処理する場合は、最初から開始し (これを保存する必要があります)、関連付けられvalueWrapperているキーが次のキーを (挿入順に) 教えてくれます。

実装例:

type Key int   // Key type
type Value int // Value type

type valueWrapper struct {
    v    Value
    next *Key
}

type Map struct {
    m           map[Key]valueWrapper
    first, last *Key
}

func New() *Map {
    return &Map{m: make(map[Key]valueWrapper)}
}

func (m *Map) Set(k Key, v Value) {
    if _, ok := m.m[k]; !ok && m.last != nil {
        w2 := m.m[*m.last]
        m.m[*m.last] = valueWrapper{w2.v, &k}
    }
    w := valueWrapper{v: v}
    m.m[k] = w
    if m.first == nil {
        m.first = &k
    }
    m.last = &k
}

func (m *Map) Range() {
    for k := m.first; k != nil; {
        w := m.m[*k]
        fmt.Println(w.v)
        k = w.next
    }
}

使い方は同じです。Go Playgroundで試してみてください。

注:好みに合わせていくつかの変更を加えることができます。

  • のように内部マップを宣言することができるm map[Key]*valueWrapperので、新しい を割り当てることなくフィールドをSet()変更できます。nextvalueWrapper

  • firstタイプのlastフィールドを選択できます*valueWrapper

  • nextあなたはタイプであることを選択することができます*valueWrapper

比較

追加のスライスを使用したアプローチは、より簡単でクリーンです。しかし、「ソートされていない」スライスでキーを見つける必要があるため、マップが大きくなると、そこから要素を削除するのが遅くなる可能性があるため、O(n)複雑になります。

prev構造体にフィールドを追加すると、マップが大きい場合でも、value-wrapper でのリンクされたリストを使用したアプローチを簡単に拡張して、高速な要素の削除をサポートできますvalueWrapper。したがって、要素を削除する必要がある場合は、ラッパー ( O(1)) を超高速で見つけ、前と次のラッパーを更新して (相互に指すように)、簡単なdelete()操作を実行できO(1)ます。

map[Key]int最初のソリューション (スライスを使用) での削除は、スライス ( )内のキーからキーのインデックスにマップされる追加のマップを 1 つ使用することで引き続き高速化できることに注意してくださいO(1)。より複雑。速度を上げるためのもう 1 つのオプションは、マップ内の値をラッパーに変更することです。ラッパーは、実際の値とスライス内のキーのインデックスを保持できます。

関連する質問を参照してください: Go でマップを挿入順に反復処理できないのはなぜですか?

于 2016-09-12T12:34:30.157 に答える