Индексируется в коллекции с O(1) временем поиска
Предположим, я хочу сделать одну коллекцию класса, имеющую 10 свойств. Эта коллекция содержит около 10 миллионов предметов.
Теперь я хочу найти эту коллекцию с O(1) временной сложностью или около O(1) по любому свойству Class.(Не только по одному свойству, например, ID или Имя)
Если я использую List, чем он по запросу LINQ, это потребует O(n) временной сложности, поэтому его нельзя использовать.
В C# есть словарь, который может быть проиндексирован только одним типом ключа. Так что это также не может быть использовано.
В качестве одного решения я могу сделать 10 словарей, проиндексированных для каждого свойства, но для этого решения потребуется большой объем памяти, поскольку в нем 10 миллионов элементов. Так что это было бы неосуществимо.
PS Я хочу только в решении для памяти (без базы данных), и коллекцию можно искать по любому отдельному свойству класса (например, MyCollection[2] или MyCollection["John"] или MyCollection["12/12/2013"] и т. Д.) и время поиска должно быть близко к O(1).
Так как я могу реализовать такую структуру данных?
1 ответ
Ты не можешь. Вы должны сделать обмен между памятью или временем. Либо создайте свои 10 различных индексов (т.е. 10 внутренних словарей), чтобы получить время поиска O(1), либо выполните линейный поиск, чтобы предотвратить любое увеличение объема памяти.
Это ваш выбор. Там нет волшебной пули, которая дает вам лучшее из обоих здесь.