предисловие
Одной из причин популярности lodash является его отличная вычислительная производительность. И его производительность может иметь такую выдающуюся производительность, большая часть которой зависит от используемого алгоритма — ленивых вычислений. В этой статье будут описаны принцип и реализация ленивых вычислений в исходном коде lodash.
Во-первых, принципиальный анализ ленивых вычислений
Ленивая оценка, также переводится как ленивый расчет, ленивая оценка, также известная как вызов по необходимости, является концепцией в компьютерном программировании, ее цель состоит в том, чтобыМинимизируйте работу, которую должен выполнять компьютер. Аргументы в ленивом вычислении не оцениваются до тех пор, пока они не потребуются. Эта процедура на самом делеОбратное исполнение с концаиз. Это определит, что им нужно, чтобы вернуться и продолжать делать, поэтому необходимо определить, какие значения назад.
Ниже приведеныКак ускорить Lo-Dash ×100? Представляем ленивую оценку.Пример в статье наглядно демонстрирует ленивое вычисление.
function priceLt(x) {
return function(item) { return item.price < x; };
}
var gems = [
{ name: 'Sunstone', price: 4 },
{ name: 'Amethyst', price: 15 },
{ name: 'Prehnite', price: 20},
{ name: 'Sugilite', price: 7 },
{ name: 'Diopside', price: 3 },
{ name: 'Feldspar', price: 13 },
{ name: 'Dioptase', price: 2 },
{ name: 'Sapphire', price: 20 }
];
var chosen = _(gems).filter(priceLt(10)).take(3).value();
Цель программы состоит в том, чтобыgemsотфильтровать и выбрать 3priceданные меньше 10.
1.1 Общая практика
если ты уйдешьlodashЭта библиотека инструментов позволяет реализовать обычным образомvar chosen = _(gems).filter(priceLt(10)).take(3); Затем вы можете использовать:
_(gems)Получите набор данных и кэшируйте его.
повторно выполнитьfilterметод, траверсgemsМассив (длина 10), вынесите данные, соответствующие условиям:
[
{ name: 'Sunstone', price: 4 },
{ name: 'Sugilite', price: 7 },
{ name: 'Diopside', price: 3 },
{ name: 'Dioptase', price: 2 }
]
Затем выполнитеtakeметод, извлеките первые 3 данных.
[
{ name: 'Sunstone', price: 4 },
{ name: 'Sugilite', price: 7 },
{ name: 'Diopside', price: 3 }
]
Общее количество обходов равно:10+3.
Пример графика выполнения выглядит следующим образом:
1.2 Методы ленивой оценки
Есть проблема с общим подходом: каждый метод делает свое дело, и много ресурсов тратится впустую без согласования.
Не лучше ли было бы сначала записать в небольшой блокнотик, что нужно сделать😎, а потом подождать, пока данные действительно выйдут, а потом использовать наименьшее количество раз для достижения цели.
Ленивые вычисления делают именно это.
Идея реализации следующая:
-
_(gems)Получить набор данных и кэшировать его - встретить
filterметод, помните - встретить
takeметод, помните - встретить
valueметод, время пришло - Достаньте маленькие книги и посмотрите на требования: вынуть 3 числа, цена
- использовать
filterметод сужденияpriceLtСудебное решение по данным
[
{ name: 'Sunstone', price: 4 }, => priceLt裁决 => 符合要求，通过 => 拿到1个
{ name: 'Amethyst', price: 15 }, => priceLt裁决 => 不符合要求
{ name: 'Prehnite', price: 20}, => priceLt裁决 => 不符合要求
{ name: 'Sugilite', price: 7 }, => priceLt裁决 => 符合要求，通过 => 拿到2个
{ name: 'Diopside', price: 3 }, => priceLt裁决 => 符合要求，通过 => 拿到3个 => 够了，收工！
{ name: 'Feldspar', price: 13 },
{ name: 'Dioptase', price: 2 },
{ name: 'Sapphire', price: 20 }
]
Как показано выше, всего выполняется всего 5 раз, и получается результат.
Пример графика выполнения выглядит следующим образом:
1.3 Резюме
Из приведенного выше примера мы можем получить характеристики ленивого вычисления:
- Расчет задержки, кэшировать вычисление, которое должно быть выполнено первым, и не выполнять его
- конвейер данных, пройдите метод «оценки» один за другим, в этом процессе, аналогичном проверке безопасности, выполните операцию очистки и, наконец, оставьте только те данные, которые соответствуют требованиям.
-
Время запуска, кэш метода, то для запуска выполнения необходим метод. lodash использовать
valueметод, уведомление фактически запускает расчет
Во-вторых, реализация ленивой оценки
В соответствии с приведенными выше характеристиками я разделил реализацию ленивого вычисления lodash на следующие части:
2.1 Реализация кешей для ленивых вычислений
выполнить_(gems). Для семантической ясности я используюlazy(gems)заменять.
var MAX_ARRAY_LENGTH = 4294967295; // 最大的数组长度
// 缓存数据结构体
function LazyWrapper(value){
this.__wrapped__ = value;
this.__iteratees__ = [];
this.__takeCount__ = MAX_ARRAY_LENGTH;
}
// 惰性求值的入口
function lazy(value){
return new LazyWrapper(value);
}
-
this.__wrapped__кешировать данные -
this.__iteratees__Методы «арбитража» в кэшированных конвейерах данных -
this.__takeCount__Запишите количество наборов данных, которые соответствуют требованиям, которые необходимо принять
Таким образом, базовая структура завершена.
2.2 Реализацияfilterметод
var LAZY_FILTER_FLAG = 1; // filter方法的标记
// 根据 筛选方法iteratee 筛选数据
function filter(iteratee){
this.__iteratees__.push({
'iteratee': iteratee,
'type': LAZY_FILTER_FLAG
});
return this;
}
// 绑定方法到原型链上
LazyWrapper.prototype.filter = filter;
filterметод, будет решать методiterateeкешировать это. Важным моментом здесь является необходимость записиiterateeтипtype.
Потому чтоlodashв иmapМетод фильтрации данных и т. д. также будет рассматриваться как метод суждения.iteratee. из-заfilterМетоды иmapМетоды скрининга разные, поэтому используйтеtypeотметка.
Вот еще одна хитрость:
(function(){
// 私有方法
function filter(iteratee){
/* code */
}
// 绑定方法到原型链上
LazyWrapper.prototype.filter = filter;
})();
Методы прототипа сначала объявляются с помощью обычной функции, а затем привязываются к прототипу. Если инструмент необходимо использоватьfilter, используется объявленный закрытый метод.
Преимущество этого в том, что если внешнийLazyWrapper.prototype.filter, не влияет на внутреннюю часть инструмента.
2.3 Реализацияtakeметод
// 截取n个数据
function take(n){
this.__takeCount__ = n;
return this;
};
LazyWrapper.prototype.take = take;
2.4 Реализацияvalueметод
// 惰性求值
function lazyValue(){
var array = this.__wrapped__;
var length = array.length;
var resIndex = 0;
var takeCount = this.__takeCount__;
var iteratees = this.__iteratees__;
var iterLength = iteratees.length;
var index = -1;
var dir = 1;
var result = [];
// 标签语句
outer:
while(length-- && resIndex < takeCount){
// 外层循环待处理的数组
index += dir;
var iterIndex = -1;
var value = array[index];
while(++iterIndex < iterLength){
// 内层循环处理链上的方法
var data = iteratees[iterIndex];
var iteratee = data.iteratee;
var type = data.type;
var computed = iteratee(value);
// 处理数据不符合要求的情况
if(!computed){
if(type == LAZY_FILTER_FLAG){
continue outer;
}else{
break outer;
}
}
}
// 经过内层循环，符合要求的数据
result[resIndex++] = value;
}
return result;
}
LazyWrapper.prototype.value = lazyValue;
Важным моментом здесь является:заявление этикетки
outer:
while(length-- && resIndex < takeCount){
// 外层循环待处理的数组
index += dir;
var iterIndex = -1;
var value = array[index];
while(++iterIndex < iterLength){
// 内层循环处理链上的方法
var data = iteratees[iterIndex];
var iteratee = data.iteratee;
var type = data.type;
var computed = iteratee(value);
// 处理数据不符合要求的情况
if(!computed){
if(type == LAZY_FILTER_FLAG){
continue outer;
}else{
break outer;
}
}
}
// 经过内层循环，符合要求的数据
result[resIndex++] = value;
}
Реализация конвейера данных текущего метода на самом деле является внутренним слоемwhileцикл. извлекая кеш вiterateesМетод вынесения решения в выборках, по текущим даннымvalueсделать постановление.
Если результатом решения является несоблюдение, т.false. Тогда в это время нет необходимости использовать последующие методы суждения для вынесения суждений. Вместо этого он должен выйти из текущего цикла.
И если вы используетеbreakПосле прыжка из внутренней петли во внешнюю петлюresult[resIndex++] = value;все равно будет выполняться, чего мы не хотим видеть.
Правильно выпрыгивать из внутренней и внешней петель одновременно и продолжать внешнюю петлю.
Оператор label как раз может удовлетворить это требование.
2.5 Малый тест
var testArr = [1, 19, 30, 2, 12, 5, 28, 4];
lazy(testArr)
.filter(function(x){
console.log('check x='+x);
return x < 10
})
.take(2)
.value();
// 输出如下：
check x=1
check x=19
check x=30
check x=2
// 得到结果： [1, 2]
2.6 Резюме
Реализация всей ленивой оценки сосредоточена на конвейере данных. И магия заявления лейбла здесь. На самом деле способ реализации не только текущий. Однако основными являются три упомянутых выше пункта. Освойте суть, ее легко изменить.
Эпилог
Ленивая оценка, это я читаюlodashВ исходниках самая большая точка возгорания найдена.
В начале я не очень хорошо разбирался в ленивых вычислениях, и хотел увидеть реализацию javascript, но нашел в интернете только один упомянутый выше документ.
Оставшийся вариант — рассекать lodash. И из-за этого родилась эта статья.
Надеюсь, эта статья поможет вам. Дайте звезду, если можете :)
Напоследок прилагается упрощенный вариант реализации этой статьиlazy.jsПолный исходный код:GitHub.com/wall — хотел/хотел бы посмотреть…
Друзья, которым нравятся мои статьи, могут подписаться на меня следующими способами:
- "звезда"или"смотреть"мойGitHub blog
- RSS-канал моего личного блога:База мистера Вана