Производительность LINQ в оперативной памяти
Сначала давайте определим функцию, которая будет возвращать случайное число от min (включительно) до max (исключение). Мы можем сделать это, потому что min всегда будет установлен на 0, а max всегда будет установлен на длину нового списка - 1
const random = curry((min, max) => Math.floor(Math.random() * (max - min) - min));
Тогда нам нужна функция, которая будет принимать список и возвращает две вещи (в массиве):
- случайно выбранный элемент
- новый список без этого элемента
const takeFromList = converge(
converge(pair, [nth, flip(remove)(1)]) [compose(random(0), length), identity]);
Сбор всего вместе:
Как вы можете видеть, если запрошенный размер выборки больше, чем фактический размер списка, он вернет весь список, но в случайном порядке.
const {curry, min, nth, identity, converge, pair, flip, compose, length, remove, flatten} = R;
const random = curry((min, max) => Math.floor(Math.random() * (max - min) - min));
const takeFromList = converge(converge(pair, [nth, flip(remove)(1)]), [compose(random(0), length), identity]);
const sampleSize = curry((size, list) => {
const [el, newList] = takeFromList(list);
const len = min(size, list.length);
return len - 1 > 0 ? flatten([el, sampleSize(len - 1, newList)]) : [el];
});
console.log(sampleSize(2, [1,2,3,4,5]));
console.log(sampleSize(2, [1,2,3,4,5]));
console.log(sampleSize(2, [1,2,3,4,5]));
console.log(sampleSize(20, [1,2,3,4,5]));
console.log(sampleSize(20, [1,2,3,4,5]));<script src="https://cdnjs.cloudflare.com/ajax/libs/ramda/0.26.1/ramda.min.js"></script>3 ответа
Даже с распараллеливанием, это все еще O (n). Постоянный множитель отличался бы (в зависимости от Вашего количества ядер), но поскольку n варьировался, общее время будет все еще варьироваться линейно.
Конечно, Вы могли записать свои собственные реализации различных операторов LINQ по Вашим собственным типам данных, но они только будут соответствующими в очень определенных ситуациях - необходимо было бы знать наверняка что предикат, только управляемый на оптимизированных аспектах данных. Например, если у Вас есть список людей, это заказано возрастом, он не собирается помогать Вам с запросом, который пытается найти кого-то с конкретным именем :)
Для исследования предиката необходимо было бы использовать деревья выражений вместо делегатов, и жизнь станет намного более трудной.
Я подозреваю, что обычно добавлял бы новые методы, которые делают это очевидным, что Вы используете indexed/ordered/whatever природу типа данных, и который будет всегда работать соответственно. Вы не могли легко вызвать те дополнительные методы от выражений запроса, конечно, но можно все еще использовать LINQ с записью через точку.
Да, универсальный случай всегда O (n), как заявил Sklivvz.
Однако много особых случаев методов LINQ для того, когда объект, реализовывая IEnumerable на самом деле реализует, например, ICollection. (Я видел это для IEnumerable. Содержит, по крайней мере.)
На практике это означает тот LINQ IEnumerable. Содержит называет быстрый HashSet. Содержит, например, если IEnumerable на самом деле является HashSet.
IEnumerable<int> mySet = new HashSet<int>();
// calls the fast HashSet.Contains because HashSet implements ICollection.
if (mySet.Contains(10)) { /* code */ }
Можно использовать отражатель для проверки точно, как методы LINQ определяются, именно так я понял это.
О, и также LINQ содержит методы IEnumerable. ToDictionary (отображает ключ к единственному значению), и IEnumerable. ToLookup (отображает ключ к нескольким значениям). Этот словарь/справочная таблица может быть создан однажды и много раз использоваться, который может ускорить некоторый LINQ-интенсивный код порядками величины.
Да, это должно быть, потому что единственный способ получить доступ к любому члену IEnumerable при помощи его методов, что означает O (n).
Это походит на классический случай, в котором разработчики языка решили обменять производительность на общность.