From afe30ca642823c811f0a270066c9a59a9b0e4452 Mon Sep 17 00:00:00 2001 From: Jukka Kurkela Date: Fri, 3 Jan 2020 20:56:42 +0200 Subject: [PATCH] Determine if data is sorted (#6885) * Determine if data is sorted * Short circuit getMinMax when sorted * Docs --- docs/general/data-structures.md | 2 +- docs/general/performance.md | 4 ++ src/core/core.controller.js | 3 +- src/core/core.datasetController.js | 86 +++++++++++++++++++----------- 4 files changed, 62 insertions(+), 33 deletions(-) diff --git a/docs/general/data-structures.md b/docs/general/data-structures.md index 770f1f28c..70bed1cc2 100644 --- a/docs/general/data-structures.md +++ b/docs/general/data-structures.md @@ -25,7 +25,7 @@ data: [{x:'2016-12-25', y:20}, {x:'2016-12-26', y:10}] data: [{x:'Sales', y:20}, {x:'Revenue', y:10}] ``` -This is also the internal format used for parsed data. Property names are matched to scale-id. In this mode, parsing can be disabled by specifying `parsing: false` at chart options or dataset. If parsing is disabled, data must be in the formats the associated chart type and scales use internally. +This is also the internal format used for parsed data. Property names are matched to scale-id. In this mode, parsing can be disabled by specifying `parsing: false` at chart options or dataset. If parsing is disabled, data must be sorted and in the formats the associated chart type and scales use internally. ## Object diff --git a/docs/general/performance.md b/docs/general/performance.md index 3e5669b12..5a43c6ac0 100644 --- a/docs/general/performance.md +++ b/docs/general/performance.md @@ -28,6 +28,10 @@ new Chart(ctx, { }); ``` +## Provide ordered data + +If the data is unordered, Chart.js needs to sort it. This can be slow in some cases, so its always a good idea to provide ordered data. + ## Specify `min` and `max` for scales If you specify the `min` and `max`, the scale does not have to compute the range from the data. diff --git a/src/core/core.controller.js b/src/core/core.controller.js index 90b103bca..ecc8af2c2 100644 --- a/src/core/core.controller.js +++ b/src/core/core.controller.js @@ -809,7 +809,8 @@ class Chart { order: dataset.order || 0, index: datasetIndex, _dataset: dataset, - _parsed: [] + _parsed: [], + _sorted: false }; } diff --git a/src/core/core.datasetController.js b/src/core/core.datasetController.js index a79cf1f56..8ed4310f5 100644 --- a/src/core/core.datasetController.js +++ b/src/core/core.datasetController.js @@ -478,11 +478,18 @@ helpers.extend(DatasetController.prototype, { const me = this; const {_cachedMeta: meta, _data: data} = me; const {iScale, vScale, _stacked} = meta; - let offset = 0; - let i, parsed; + const iScaleId = iScale.id; + let sorted = true; + let i, parsed, cur, prev; + + if (start > 0) { + sorted = meta._sorted; + prev = meta._parsed[start - 1]; + } if (me._parsing === false) { meta._parsed = data; + meta._sorted = true; } else { if (helpers.isArray(data[start])) { parsed = me._parseArrayData(meta, data, start, count); @@ -492,9 +499,17 @@ helpers.extend(DatasetController.prototype, { parsed = me._parsePrimitiveData(meta, data, start, count); } + for (i = 0; i < count; ++i) { - meta._parsed[i + start] = parsed[i + offset]; + meta._parsed[i + start] = cur = parsed[i]; + if (sorted) { + if (prev && cur[iScaleId] < prev[iScaleId]) { + sorted = false; + } + prev = cur; + } } + meta._sorted = sorted; } if (_stacked) { @@ -502,9 +517,7 @@ helpers.extend(DatasetController.prototype, { } iScale._invalidateCaches(); - if (vScale !== iScale) { - vScale._invalidateCaches(); - } + vScale._invalidateCaches(); }, /** @@ -624,33 +637,21 @@ helpers.extend(DatasetController.prototype, { * @private */ _getMinMax: function(scale, canStack) { - const chart = this.chart; const meta = this._cachedMeta; - const metaData = meta.data; - const ilen = meta._parsed.length; - const stacked = canStack && meta._stacked; - const indices = getSortedDatasetIndices(chart, true); + const {data, _parsed} = meta; + const sorted = meta._sorted && scale === meta.iScale; + const ilen = _parsed.length; const otherScale = this._getOtherScale(scale); + const stack = canStack && meta._stacked && {keys: getSortedDatasetIndices(this.chart, true), values: null}; let max = Number.NEGATIVE_INFINITY; let {min: otherMin, max: otherMax} = getUserBounds(otherScale); - let i, item, value, parsed, stack, min, minPositive, otherValue; + let i, item, value, parsed, min, minPositive, otherValue; min = minPositive = Number.POSITIVE_INFINITY; - for (i = 0; i < ilen; ++i) { - item = metaData[i]; - parsed = meta._parsed[i]; - value = parsed[scale.id]; - otherValue = parsed[otherScale.id]; - if ((item && item.hidden) || isNaN(value) || - otherMin > otherValue || otherMax < otherValue) { - continue; - } - if (stacked) { - stack = { - keys: indices, - values: parsed._stacks[scale.id] - }; + function _compute() { + if (stack) { + stack.values = parsed._stacks[scale.id]; // Need to consider individual stack values for data range, // in addition to the stacked value min = Math.min(min, value); @@ -663,11 +664,34 @@ helpers.extend(DatasetController.prototype, { minPositive = Math.min(minPositive, value); } } - return { - min: min, - max: max, - minPositive: minPositive - }; + + function _skip() { + item = data[i]; + parsed = _parsed[i]; + value = parsed[scale.id]; + otherValue = parsed[otherScale.id]; + return ((item && item.hidden) || isNaN(value) || otherMin > otherValue || otherMax < otherValue); + } + + for (i = 0; i < ilen; ++i) { + if (_skip()) { + continue; + } + _compute(); + if (sorted) { + break; + } + } + if (sorted) { + for (i = ilen - 1; i >= 0; --i) { + if (_skip()) { + continue; + } + _compute(); + break; + } + } + return {min, max, minPositive}; }, /** -- 2.47.2