0

X 点と Y 点のリストを格納するがあるとList<Point>しますが、これらを順序付けしたいとします。X 値と Y 値の定義域が事前にわからないとしlongます。そのため、目的に十分な大きさの値を使用します。

任意の時点で、リストには非常に多くのポイントまたは非常に少ないポイントが含まれる可能性があり、これらのポイントは非常にまばらに分布している可能性がありますが、特定のポイントがリストに存在する場合は、それらを非常に効率的に取得および挿入できる必要があります。

過去に、私は と を使用IComparable<>しList.BinarySearch()て大成功を収めました。残念ながら、 X 値と Y 値の両方に基づいて挿入および取得できる必要があります。

X と Y の定義域が事前にわかっていて、その定義域が十分に小さい場合は、これらの数値と、他の定義域の次のべき乗で累乗した数値を足すだけで済みます。これにより、衝突がなくなり、値を効率的に取得/挿入できます。たとえば、X と Y が両方とも 0 から 9 の間にある場合は、 で比較でき10 * X + Yます。私のデータ型はすべて 64 ビット整数であるため、これを実際に行うことはできません。

ドメインを制限せずに、この機能を実現する他の方法はありますか?

確実に機能する 1 つの方法は、X.ToString("N19") + Y.ToString("N19") で比較することですが、これは現在、数値比較ではなく文字列比較であるため、パフォーマンスが大幅に低下します。

編集:「N19」が必要です。そうしないと、(X = 1234、Y = 5) が (X = 1、Y = 2345) と同じに解決されるためです。その間の他のすべての衝突。

4

1 に答える 1

1

比較のためにベクトルの複数のコンポーネントを 1 つのスカラー値に結合する代わりに、各コンポーネントを比較することができます。

int CompareTo(Point p)
{
    if (this.X < p.X)
    {
        return -1;
    }
    else if (this.X > p.X)
    {
        return 1;
    }
    else
    {
        return this.Y.CompareTo(p.Y);
    }        
}
于 2013-05-13T06:44:36.193 に答える