将编译器基于“字典”的非静态版本创建,其中键是类型

4

有一个非常简单的技巧,可以创建一个类似于字典的结构,其中键是类型。 该结构就像一个Dictionary<Type, T?>,其中键是Type对象,值是相应类型的实例。

这种奇妙的结构与变量或数组一样快,因为编译器/JITter只需要进行一次“查找”,并将适当的值引用编译到您的程序中。

    public static class MyDict<T> {
        public static T Value { get; set; }
    }

您可以像这样使用该结构:
MyDict<string>.Value = MyDict<int>.Value.ToString();
问题在于这个“字典”是全局的。创建不同的字典的唯一方法是创建不同的类。
如何创建类似的(最快的“查找”,没有装箱)非静态结构?(不使用代码生成。)
简单地说:我想要拥有多个Dictionary<Type, object>-like对象,无需查找成本、强制类型转换和装箱。

1
移除 static 关键字? - Khan
1
我不明白。一个仅存储一个值的类有什么意义?为什么不能只使用一个简单的变量... - andleer
@ChrisSinclair 我也怀疑,但我的一些“不可能”的泛型相关谜题最终都被解决了。https://dev59.com/QmnWa4cB1Zd3GeqP15KQ#12926979 http://stackoverflow.com/questions/12877550/delegates-to-generic-operations-where-the-generic-type-is-unknown-how-to-create/12967076#12967076 - Ark-kun
@ChrisSinclair “我不确定变量/名称(如a、b、c、MyMethod)在你的问题中是如何涉及的。” 不同之处在于变量和方法是静态类型和编译时解析的,而字典和其他存储库是运行时解析的,并且经常失去静态类型的好处。 - Ark-kun
@ChrisSinclair "你这里有特定的性能问题吗,还是说这是过早优化的情况?" 我需要这个针对性能关键部分的代码:操作员存储库。我需要存储和查找不同类型组合的算术操作处理程序。public static MyMonad<T> operator +(MyMonad<T> a, MyMonad<T> b) {return new MyMonad<T>(Operators.Addition<T, T, T>.Handler(a, b)); } - Ark-kun
显示剩余11条评论
8个回答

2
这里有一种方法可以扩展问题中描述的方法:

以下是具体步骤:

public class TypeDict
{
    public T Get<T>()
    {
        return MyDict<T>.Values[this];
    }
    public void Set<T>(T value)
    {
        MyDict<T>.Values[this] = value;
    }
    private static class MyDict<T>
    {
        public static Dictionary<TypeDict, T> Values { get; private set; }

        static MyDict()
        {
            Values = new Dictionary<TypeDict, T>();
        }
    }
}

现在我们可以像这样使用TypeDict:
void X()
{
    var a = new TypeDict();
    var b = new TypeDict();

    a.Set<int>(1);
    a.Set<double>(3.14);
    a.Set("Hello, world!");

    //Note that type inference allows us to omit the type argument
    b.Set(10);          
    b.Set(31.4);  
    b.Set("Hello, world, times ten!");

    Console.WriteLine(a.Get<int>());
    Console.WriteLine(a.Get<double>());
    Console.WriteLine(a.Get<string>());

    Console.WriteLine();
    Console.WriteLine(b.Get<int>());
    Console.WriteLine(b.Get<double>());
    Console.WriteLine(b.Get<string>());
}

它仍然具有字典查找(这种方法的另一个问题(包括我的答案)是GC预防)。但解决方案非常美丽!我喜欢它的简单性,静态类型索引,缺少强制转换和装箱以及[this]索引。 - Ark-kun

1
Ark-kun正在使用泛型在编译时生成唯一类型。对于泛型类型,任何静态成员都是唯一的,只属于该特定的封闭泛型类型。这样处理速度就像标准静态成员查找一样快。
上述用法相当于以下内容:
public static class MyDict_String 
{
    public static string Value { get; set; }
}

public static class MyDict_Int32
{
    public static int Value { get; set; }
}

MyDict_String.Value = MyDict_Int32.Value.ToString();

据我所知,类型是“静态的”(也就是说,你不能定义多个这样的类型),因此我不知道有什么方法可以绕过这个问题并保持与静态编译成员查找相同的性能。
否则,你最好创建一个通用实例类型,它包装了自己的字典,该字典使用System.Type作为其键和System.Object作为其值,当插入/检索值时必须进行装箱/强制转换。
编辑:这里是一个简单的实现,包装了一个字典:
public class MyTypedDict
{
    private Dictionary<Type, object> Values = new Dictionary<Type, object>();

    public T Get<T>()
    {
        object untypedValue;
        if (Values.TryGetValue(typeof(T), out untypedValue))
            return (T)untypedValue;
        return default(T);
    }

    public void Set<T>(T value)
    {
        Values[typeof(T)] = value;
    }
}

再仔细考虑一下,可能可以通过一些巧妙的方法使用ExpandoObjecthttp://msdn.microsoft.com/en-us/library/system.dynamic.expandoobject.aspx)实现更类似属性的语法,但我觉得这样做可能会非常滥用,而且很容易在运行时出错。(此外,在编译时它不会为您提供任何帮助)

编辑x2:如果您真的想要有不同的值集,您可以将其嵌套在另一个泛型类型中:

public static class ValueSets<T>
{
    public static class MyDict<U>
    {
        public static U Value { get; set; }
    }
}

使用方式如下:

ValueSets<int>.MyDict<string>.Value = "Hello ";
ValueSets<bool>.MyDict<string>.Value = "World!";

string helloworld = ValueSets<int>.MyDict<string>.Value + ValueSets<bool>.MyDict<string>.Value;
Console.WriteLine(helloworld);//Hello World!

但是在这种情况下,初始类型intbool变得“神奇”且没有意义,此外您需要为每个不同的值集提供唯一的类型。此外,您无法将其传递并修改为实例变量,而是可以静态访问(只要您可以使用类型T)。因此,也许您可以声明具有含义的最小可见类型并使用它们:

internal class MyFirstWords {}
internal class MySecondWords {}

ValueSets<MyFirstWords>.MyDict<string>.Value = "Hello ";
ValueSets<MySecondWords>.MyDict<string>.Value = "World!";

string helloworld = ValueSets<MyFirstWords>.MyDict<string>.Value + ValueSets<MySecondWords>.MyDict<string>.Value;
Console.WriteLine(helloworld);//Hello World!

无论如何,我认为这很古怪,我不建议这样做。


EDITx2是一个非常有趣的解决方案。由于类型索引是无需查找的,所以我想要的双重索引可以通过双重类型索引来实现。(虽然由于无法在运行时创建新类型,这并不是非常实用。但是可以使用反射来创建类型...)。 - Ark-kun

1
一个更复杂的版本。不知道是否更接近:
定义一个通用字典:
public class MyDictionary<T>
{
    Dictionary<string, T> dict;

    public MyDictionary()
    {
        dict = new Dictionary<string, T>();
    }

    public T this[string name]
    {
        get
        {
            if (dict.ContainsKey(name))
                return dict[name];
            else
                return default(T);//or throw
        }
        set
        {
            dict[name] = value;
        }
    }
}

然后创建一个存储这些字典的仓库:

public class MyRepository
{
    List<object> repo;

    public MyRepository()
    {
        repo = new List<object>();
    }

    public void Add<T>(string name, T value)
    {
        if (!repo.OfType<MyDictionary<T>>().Any())
            repo.Add(new MyDictionary<T>());
        var dict = repo.OfType<MyDictionary<T>>().FirstOrDefault();
        dict[name] = value;
    }

    public T GetValue<T>(string name)
    {
        if (!repo.OfType<MyDictionary<T>>().Any())
            return default(T);//or throw
        else
        {
            var dict = repo.OfType<MyDictionary<T>>().FirstOrDefault();
            return dict[name];
        }
    }
}

最后,您可以使用此存储库:

        MyRepository repo = new MyRepository();
        repo.Add("A", 1);
        repo.Add("B", 1);
        int i = repo.GetValue<int>("A") + repo.GetValue<int>("B");

在这个例子中,将MyDictionary<T>装箱为object
另一方面,如果您正在使用某些特定类型,则可能根本不使用此存储库类。而是利用单独的字典。
MyDictionary<int> intDict = new MyDictionary<int>();
intDict["A"] = 1;
intDict["B"] = 2;
int i = intDict["A"] + intDict["B"];

然而,这与使用相同

Dictionary<string, int> intDict = new Dictionary<string, int>();

因此,MyRepository 类可以被编辑为使用 Dictionary<string, T> 而不是 MyDictionary<T>


非常接近,但仍有一個查找。但是你的解決方案給了我一個靈感。也許這真的是可以解決的! - Ark-kun

1
@Konstantin的回答让我想起了一种非常快速的查找方法 - 数组索引。这个简陋的PoC代码展示了所需结构的一个变体。
    public class TypeDictionary {
        static int _maxId = 0;
        int _id;

        static class Store<T>{
            internal static List<T> Values = new List<T>();
        }

        public TypeDictionary() {
            _id = _maxId++;
        }

        public T GetValue<T>() {
            return Store<T>.Values[_id];
        }

        public void SetValue<T>(T value) {
            while(Store<T>.Values.Count < _id) {
                Store<T>.Values.Add(default(T));
            }
            Store<T>.Values[_id] = value;
        } 
    }

这段代码可以按照以下方式使用:

        var dict1 = new TypeDictionary();
        dict1.SetValue("my string");
        string result = dict1.GetValue<string>();

这个解决方案的问题在于存储库不是稀疏的,导致了它的内存使用。这也使得第一次设置值更加昂贵。

是的,我已经用索引替换了哈希/等于查找。数组元素是最接近变量的东西。感谢您提醒内存泄漏问题,我没有考虑到这个问题(尽管我今年一直在防止由事件引起的.Net内存泄漏)。并不是说我实际上会在任何地方使用这样的代码。另一方面,这些技术是有价值的,我学到了新东西。我已经调查了可能的解决方案并分析了问题。我的代码可能会保持静态变量或使用“Dictionary<Type, object>”。 - Ark-kun
如果想要使用数组索引并且不介意进行Object的强制转换,我认为更好的方法是让每个对象持有一个Object[],并且将数组索引作为与类型相关联的序列号(即第一次尝试使用特定类型时,原子地读取和递增到目前为止使用的类型数量,将该值存储在与类型相关联的某个位置)。试图访问与特定类型相关联的信息的代码将需要检查数组大小,并可能需要扩展数组,但可以直接访问数组。 - supercat
然后将数组索引设置为与类型相关联的序列号,这样我们就有了一种将“Type”映射到“int”的方法。我知道的唯一方法是使用“Dictionary<Type, int>”。 - Ark-kun
但如果我们反过来呢?我们将拥有一个全局的 T[] 数组和与 对象 相关联的序列号。这就是我得出这个答案的方式。同时,数组索引应该是与类型相关联的序列号。 - Ark-kun
基本上,字典查找是 .GetHashCode 加上一个或多个数组索引操作。我的 TypeDictionary 代码只有一个单一的数组索引操作。而 MyDict<T> 或类似类型根本没有运行时索引操作。 - Ark-kun
显示剩余2条评论

0

在 @phoog 的示例基础上,结合了 @supercat 的建议

public class TypeDict
{
    public T Get<T>() where T : class
    {
        T value;
        InnerDict<T>.Values.TryGetValue(this, out value);
        return value;
    }
    public void Set<T>(T value) where T : class
    {
        var cwt = InnerDict<T>.Values;
        // lock+remove+add https://github.com/dotnet/coreclr/issues/4545
        lock (cwt)
        {
            cwt.Remove(this);
            cwt.Add(this, value);
        }
    }
    private static class InnerDict<T> where T : class
    {
        public static ConditionalWeakTable<TypeDict, T> Values { get; private set; }

        static InnerDict()
        {
            Values = new ConditionalWeakTable<TypeDict, T>();
        }
    }
}

0

试试这个:

public class MyDictionary
{
    List<object> values;

    public MyDictionary()
    {
        values = new List<object>();
    }

    public T GetValue<T>()
    {
        return values.OfType<T>().FirstOrDefault();
    }

    public bool Add<T>(T value)
    {
        if (values.OfType<T>().Any())
            return false;
        else
        {
            values.Add(value);
            return true;
        }
    }
}

并使用它:

var md = new MyDictionary();
md.Add("!!!");
string s = md.GetValue<string>();

这个类最多可以存储一个类型为 T 的值。但可能存在派生类和接口的特殊情况。如果符合你的需求,你可以检查它并根据需要进行修改,如果它基本上符合你的需求。


我认为最好按照问题中提到的方式实现为 Dictionary<Type, object>。但是它也存在问题,就是查找和装箱(强制转换已经固定)。 - Ark-kun
@Ark-kun,这仍然需要从OfType<T>进行转换。这也不是一个Dictionary查找:它将取决于存储的类型数量n,时间复杂度为O(n)。在Add方法中还会存在继承问题。 - Chris Sinclair

0
你所描述的使用案例与添加到.NET 4.0的ConditionalWeakTable<TKey, TValue>的目的非常相似。对于你描述的目的,你应该在一个静态泛型类中包含这样一张表,并且对于每个应该包含特定类型项目引用的类对象,你将存储一个指向包含该项的对象的引用,以及一个指向该项或一个简单项持有者对象的引用存储到该类型的表中(请注意,ConditionalWeakTable中的条目将在对象停止存在时消失,但否则是不可变的,因此如果您想要可变的关联,您需要创建一个对象来保存它)。

假設 internal static class MyDictionaryHelper<T> { internal ConditionalWeakTable<MyDictType,T[]> theTable; },那麼 MyDict<int>.Value = 1 實際上會執行為 MyDictionaryHelper<int>.theTable.GetValue(MyDict, (x)=> new int[0])[0] = 1。從語意上看,這段程式碼的行為就像項目被存儲在 MyDict 中一樣,且程式碼的一切都是完全類型安全的 [如果需要,可以定義一個值保持者類別而不是使用陣列]。你還想要什麼? - supercat
从语义上讲,使用任何字典类型的代码是相同的,就像来自https://dev59.com/8mzXa4cB1Zd3GeqPVJEJ#14064051的第二个代码块一样 - 这是一个基于“Dictionary <Type,object>”的简单结构。我在这里看不到区别。MyDict Dictionary / ConditionalWeakTable之间的区别在于超快的编译时索引(根本没有索引)。 - Ark-kun
@Ark-kun:使用ConditionalWeakTable的代码是完全类型安全的,而Dictionary<Type, Object>则不是。您所寻求的根本是基于对象引用和类型的组合检索某些内容,因此无论是快速检索通用类型的静态对象的快速方法,还是检索对象的已知个别字段的快速方法都不适用。可以有一个internal static class Fetchers<TDummy> { public class Holders<T> { static T Value; } public static T GetValue<TValue>() {return Holders<T>.Value;} },然后... - supercat
@Ark-kun:...让每个MyDict实例创建一个不同的虚拟类型,用于查找[上面的代码不太对],理论上可以消除运行时索引的需要。但实际上,这样折磨类型系统几乎肯定会使事情变慢而不是更快。.NET类型系统可以处理数千种类型的运行时创建,但随着类型数量的增加,它会越来越陷入困境。 - supercat
泛型类型中的静态字段由类型进行“索引”。 泛型类型中的静态数组字段由类型进行“索引”,然后由整数索引进行“索引”。 泛型类型中的静态Dictionary<TObj, T>字段由类型进行“索引”,然后通过对象引用进行哈希索引。 - Ark-kun
显示剩余6条评论

0
你所寻找的在C#中是不可能实现的。这种语言不支持一个容器能够存储不同类型的多个对象,同时还提供了一种不需要转换、装箱或拆箱的查找方法。你可以通过C++中的宏,或通过像JavaScript这样的语言来实现类似的功能,因为这些语言的类型结构可以在运行时改变。

如果您查看答案,您会发现有几个这样的容器被提到。有原始静态的“字典”(我们可以创建多个“实例”),https://dev59.com/8mzXa4cB1Zd3GeqPVJEJ。还有一个“双类型索引”的“字典”,https://dev59.com/8mzXa4cB1Zd3GeqPVJEJ#14064051。这些都没有任何查找。有一个带有“数组索引”查找的容器,https://dev59.com/8mzXa4cB1Zd3GeqPVJEJ#14064329。最后,有一个美丽的基于字典的解决方案,没有强制转换或装箱:https://dev59.com/8mzXa4cB1Zd3GeqPVJEJ#14064463。 - Ark-kun

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接