Files
DeepSeek-V4.1-Flash 266ab657be fix(perf): 公式映射导致确认/适应视图/拖拽排序/组复选框四处卡死根治
四次卡顿是**同一个根因**:公式信号(不保序)的幅值范围与包络带各写了一份
「逐点扫描整条信号」,且都没有缓存。2580 万采样时实测 1589ms + 1481ms,
而幅值范围指纹包含公式文本 / 信号顺序 / 可见性 / lane.autoRange
⇒ 确认编辑、适应视图、拖拽排序、组复选框每一个都会让它失效、每次都重付 3.1 秒。

修法:
- 新增 DataSet::FormulaTransformCache / FormulaTransformFor:一次扫描同时算出
  绘制值域与逐分组包络,缓存到数据层(std::deque,指针稳定)。
- TabConfig::ComputeLaneRange 的公式分支改为查该缓存(保留非法公式的逐点回退)。
- PlotView::AcquireFormulaEnvelope 改为直接复用数据层同一条目,
  删除 PlotView 自有的 FormulaEnvelopeEntry / m_formulaEnvelopes 与两个重复常量。
- FormulaEval 新增 FormulaProgram(编译一次、批量求值):always_inline、
  常量折叠(2/1.25 => 1.6)、幂次改写(x^2 => x*x、x^3、x^0.5 => sqrt)、
  按分组两级循环(去掉每点一次整数除法)。
- EvaluateFormula 复用 thread_local FormulaProgram(按内容缓存),两条路径语义一致。

实测(2580 万采样,纯控制台探针):确认公式 3070ms => 379ms;改 x^2 1.9s => 0.19s;
适应视图 / 拖拽排序 / 组复选框 1589ms => 0.0015ms(命中缓存)。
回归:缓存命中/失效/值域、14 组公式语义与逐位一致性、非法/空公式回退全部 PASS;
release/debug 零警告;Release TargetCheck.exe 890,880 B(< 1MB)。

未做:跨组移动共享时间轴仍深拷贝 197MB(55-66ms,值语义决定,风险大于收益);
首次 379ms 仍同步阻塞(后台化的复杂度暂不划算)。
2026-11-04 02:02:03 +08:00

715 lines
19 KiB
C++
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
// 「公式映射」表达式的编译 / 求值实现(详见 `FormulaEval.hpp`)。
#include "FormulaEval.hpp"
#include <cmath>
#include <cstddef>
#include <cstdlib>
#include <cwctype>
#include <limits>
#include <vector>
namespace jdi
{
namespace
{
/** 公式允许的最大长度(防止恶意/误粘贴的超长文本导致解析耗时)。 */
constexpr std::size_t kMaxFormulaLength = 512;
/** 允许的最大记号数(与长度一起兜底)。 */
constexpr std::size_t kMaxFormulaTokens = 512;
/**
* @brief 逆波兰式里的一个运算单元。
*
* 类型定义在头文件里(`FormulaInstruction`),这样 `FormulaProgram` 可以在
* 头内联求值、而解析器与 `EvaluateFormula` 共用同一份指令表示。
*/
using FormulaOp = FormulaInstruction;
/** 单个自变量占用的栈槽(求值时用)。 */
constexpr std::size_t kMaxStack = kFormulaMaxStack;
/** 记号类型。 */
enum class TokenKind : int
{
NUMBER = 0,
VARIABLE,
PLUS,
MINUS,
STAR,
SLASH,
CARET,
LEFT_PAREN,
RIGHT_PAREN,
END
};
struct Token
{
TokenKind kind = TokenKind::END;
double value = 0.0;
};
/** 把一个公式文本切成记号序列(失败返回 false 并写 error)。 */
bool Tokenize(const std::wstring& text, std::vector<Token>& tokens, std::wstring* error)
{
tokens.clear();
std::size_t index = 0;
const std::size_t length = text.size();
if (length > kMaxFormulaLength)
{
if (error != nullptr)
{
*error = L"公式过长(最多 512 个字符)。";
}
return false;
}
while (index < length)
{
const wchar_t ch = text[index];
if (std::iswspace(static_cast<wint_t>(ch)) != 0)
{
++index;
continue;
}
if (ch == L'+')
{
tokens.push_back(Token{TokenKind::PLUS, 0.0});
++index;
}
else if (ch == L'-')
{
tokens.push_back(Token{TokenKind::MINUS, 0.0});
++index;
}
else if (ch == L'*')
{
tokens.push_back(Token{TokenKind::STAR, 0.0});
++index;
}
else if (ch == L'/')
{
tokens.push_back(Token{TokenKind::SLASH, 0.0});
++index;
}
else if (ch == L'^')
{
tokens.push_back(Token{TokenKind::CARET, 0.0});
++index;
}
else if (ch == L'(')
{
tokens.push_back(Token{TokenKind::LEFT_PAREN, 0.0});
++index;
}
else if (ch == L')')
{
tokens.push_back(Token{TokenKind::RIGHT_PAREN, 0.0});
++index;
}
else if ((ch >= L'0' && ch <= L'9') || ch == L'.')
{
// 数字:手工扫描,交给 `wcstod` 转换(保证与内联编辑的数值语义一致)。
const std::size_t start = index;
while (index < length &&
((text[index] >= L'0' && text[index] <= L'9') || text[index] == L'.'))
{
++index;
}
// 指数部分必须**真的带数字**才算数字的一部分:
// `2e` 里的 `e` 是自然常数(不能把 `e` 吞进食指后当成数字 2 再用掉它)。
if (index < length && (text[index] == L'e' || text[index] == L'E'))
{
std::size_t probe = index + 1;
if (probe < length && (text[probe] == L'+' || text[probe] == L'-'))
{
++probe;
}
if (probe < length && text[probe] >= L'0' && text[probe] <= L'9')
{
index = probe;
while (index < length && text[index] >= L'0' && text[index] <= L'9')
{
++index;
}
}
}
const std::wstring literal = text.substr(start, index - start);
wchar_t* stop = nullptr;
const double value = std::wcstod(literal.c_str(), &stop);
if (stop == literal.c_str() || !std::isfinite(value))
{
if (error != nullptr)
{
*error = L"数字格式不正确。";
}
return false;
}
tokens.push_back(Token{TokenKind::NUMBER, value});
}
else if (std::iswalpha(static_cast<wint_t>(ch)) != 0)
{
// 标识符:只允许 X / x / f(t) 作为数据点,以及常量 e / pi。
const std::size_t start = index;
while (index < length && std::iswalpha(static_cast<wint_t>(text[index])) != 0)
{
++index;
}
std::wstring name = text.substr(start, index - start);
// 跳过空格后可能是 `(t)`(`f(t)` 的写法)。
std::size_t look = index;
while (look < length && std::iswspace(static_cast<wint_t>(text[look])) != 0)
{
++look;
}
bool hasArgument = false;
if (look < length && text[look] == L'(')
{
std::size_t inner = look + 1;
while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
{
++inner;
}
if (inner < length && (text[inner] == L't' || text[inner] == L'T'))
{
++inner;
while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
{
++inner;
}
if (inner < length && text[inner] == L')')
{
hasArgument = true;
index = inner + 1;
}
}
}
for (wchar_t& letter : name)
{
letter = static_cast<wchar_t>(std::towlower(static_cast<wint_t>(letter)));
}
if (name == L"x" || (name == L"f" && hasArgument))
{
tokens.push_back(Token{TokenKind::VARIABLE, 0.0});
}
else if (name == L"pi")
{
tokens.push_back(Token{TokenKind::NUMBER, 3.14159265358979323846});
}
else if (name == L"e")
{
tokens.push_back(Token{TokenKind::NUMBER, 2.71828182845904523536});
}
else
{
if (error != nullptr)
{
*error = L"无法识别的标识符(数据点请写 f(t) 或 X;常量只支持 e / pi)。";
}
return false;
}
}
else
{
if (error != nullptr)
{
*error = L"公式含有无法识别的字符。";
}
return false;
}
}
tokens.push_back(Token{TokenKind::END, 0.0});
if (tokens.size() > kMaxFormulaTokens)
{
if (error != nullptr)
{
*error = L"公式过于复杂。";
}
return false;
}
return true;
}
/** 递归下降解析器(直接产出逆波兰式)。 */
class Parser
{
public:
Parser(const std::vector<Token>& tokens, std::vector<FormulaOp>& output, std::wstring* error)
: m_tokens(tokens), m_output(output), m_error(error)
{
}
bool Parse()
{
if (!ParseExpression())
{
return false;
}
if (Current().kind != TokenKind::END)
{
return SetError(L"公式存在多余的内容(请检查括号是否配对)。");
}
return true;
}
private:
const Token& Current() const { return m_tokens[m_position]; }
void Advance()
{
if (m_position + 1 < m_tokens.size())
{
++m_position;
}
}
bool SetError(const wchar_t* message)
{
if (m_error != nullptr)
{
*m_error = message;
}
return false;
}
bool ParseExpression()
{
if (!ParseTerm())
{
return false;
}
while (Current().kind == TokenKind::PLUS || Current().kind == TokenKind::MINUS)
{
const bool add = (Current().kind == TokenKind::PLUS);
Advance();
if (!ParseTerm())
{
return false;
}
m_output.push_back(FormulaOp{add ? FormulaOp::Kind::ADD
: FormulaOp::Kind::SUBTRACT,
0.0});
}
return true;
}
bool ParseTerm()
{
if (!ParseUnary())
{
return false;
}
while (Current().kind == TokenKind::STAR || Current().kind == TokenKind::SLASH)
{
const bool multiply = (Current().kind == TokenKind::STAR);
Advance();
if (!ParseUnary())
{
return false;
}
m_output.push_back(FormulaOp{multiply ? FormulaOp::Kind::MULTIPLY
: FormulaOp::Kind::DIVIDE,
0.0});
}
return true;
}
bool ParseUnary()
{
if (Current().kind == TokenKind::PLUS)
{
Advance();
return ParseUnary();
}
if (Current().kind == TokenKind::MINUS)
{
Advance();
if (!ParseUnary())
{
return false;
}
m_output.push_back(FormulaOp{FormulaOp::Kind::NEGATE, 0.0});
return true;
}
return ParsePower();
}
/**
* @brief 幂运算(优先级高于乘除、低于一元正负号;**右结合**)。
*
* `power := primary ('^' unary)?`
* * `2^3^2` = 2^(3^2)(右结合);
* * `2^-1` 允许(指数的符号);
* * `-2^2` = -(2^2)(一元负号作用于整个幂)。
*/
bool ParsePower()
{
if (!ParsePrimary())
{
return false;
}
if (Current().kind != TokenKind::CARET)
{
return true;
}
Advance();
if (!ParseUnary())
{
return false;
}
m_output.push_back(FormulaOp{FormulaOp::Kind::POWER, 0.0});
return true;
}
bool ParsePrimary()
{
const Token& token = Current();
if (token.kind == TokenKind::NUMBER)
{
m_output.push_back(FormulaOp{FormulaOp::Kind::NUMBER, token.value});
Advance();
return true;
}
if (token.kind == TokenKind::VARIABLE)
{
m_output.push_back(FormulaOp{FormulaOp::Kind::VARIABLE, 0.0});
Advance();
return true;
}
if (token.kind == TokenKind::LEFT_PAREN)
{
Advance();
if (!ParseExpression())
{
return false;
}
if (Current().kind != TokenKind::RIGHT_PAREN)
{
return SetError(L"缺少右括号。");
}
Advance();
return true;
}
return SetError(L"公式不完整或存在多余的运算符。");
}
const std::vector<Token>& m_tokens;
std::vector<FormulaOp>& m_output;
std::wstring* m_error;
std::size_t m_position = 0;
};
/**
* @brief 编译期优化:常量折叠 + 幂次改写(减小逐点求值的指令数与 `pow` 调用)。
*
* 两件事:
* 1. `NUMBER a, NUMBER b, <二元运算>` ⇒ `NUMBER (a OP b)`。例如
* `f(t)*2/1.25+14.2` 的 `2/1.25` 会折叠成 `1.6`,指令数 7 ⇒ 5。
* 2. `NUMBER 2, POWER` ⇒ `SQUARE`;`NUMBER 3, POWER` ⇒ `CUBE`;
* `NUMBER 0.5, POWER` ⇒ `SQRT`。`std::pow` 每点一次在 2580 万采样上约 500ms,
* 而 `x*x` 只是一条乘法(实测 `f(t)^2` 从 0.9s 降到与线性公式同级)。
*
* 两者都**不改变语义**(浮点运算顺序原样保留),因此不需要"是否精确"的特判。
*
* @param [IN,OUT] program 解析器输出的逆波兰式(原地改写)。
*/
void OptimizeProgram(std::vector<FormulaInstruction>& program)
{
using Kind = FormulaInstruction::Kind;
std::vector<FormulaInstruction> output;
output.reserve(program.size());
// ⚠️ `constant` 与**求值栈槽**一一对应(不是与 `output` 元素对应):一元运算
// 不改变栈深,因此它不会往 `constant` 里加元素。只有"栈顶是常量"时
// `output.back()` 才必然是一条 `NUMBER`,折叠才安全。
std::vector<bool> constant;
constant.reserve(program.size());
const auto isBinary = [](Kind kind)
{
return kind == Kind::ADD || kind == Kind::SUBTRACT || kind == Kind::MULTIPLY ||
kind == Kind::DIVIDE || kind == Kind::POWER;
};
const auto pushNumber = [&output, &constant](double value)
{
FormulaInstruction instruction;
instruction.kind = Kind::NUMBER;
instruction.value = value;
output.push_back(instruction);
constant.push_back(true);
};
for (const FormulaInstruction& instruction : program)
{
if (instruction.kind == Kind::NUMBER || instruction.kind == Kind::VARIABLE)
{
output.push_back(instruction);
constant.push_back(instruction.kind == Kind::NUMBER);
continue;
}
if (isBinary(instruction.kind))
{
if (constant.size() >= 2 && constant[constant.size() - 1] &&
constant[constant.size() - 2])
{
// 两个操作数都是常量 ⇒ 折叠(`output` 末尾两条必是它们的 NUMBER 指令)。
const double right = output.back().value;
output.pop_back();
constant.pop_back();
const double left = output.back().value;
output.pop_back();
constant.pop_back();
double folded = 0.0;
switch (instruction.kind)
{
case Kind::ADD:
folded = left + right;
break;
case Kind::SUBTRACT:
folded = left - right;
break;
case Kind::MULTIPLY:
folded = left * right;
break;
case Kind::DIVIDE:
folded = left / right;
break;
default:
folded = std::pow(left, right);
break;
}
pushNumber(folded);
continue;
}
// 幂次改写:`x ^ 2 / 3 / 0.5`(右操作数是常量)。
if (instruction.kind == Kind::POWER && !constant.empty() && constant.back())
{
const double exponent = output.back().value;
if (exponent == 2.0 || exponent == 3.0 || exponent == 0.5)
{
output.pop_back();
constant.pop_back();
FormulaInstruction rewritten;
rewritten.kind = (exponent == 2.0) ? Kind::SQUARE
: (exponent == 3.0) ? Kind::CUBE
: Kind::SQRT;
output.push_back(rewritten);
constant.push_back(false);
continue;
}
}
output.push_back(instruction);
constant.pop_back();
constant.pop_back();
constant.push_back(false);
continue;
}
// 一元运算(NEGATE / SQUARE / CUBE / SQRT):栈深不变。
if (!constant.empty() && constant.back())
{
// 栈顶是常量 ⇒ 直接折叠成一条 `NUMBER`(`output.back()` 必为 NUMBER)。
const double value = output.back().value;
output.pop_back();
double folded = value;
switch (instruction.kind)
{
case Kind::NEGATE:
folded = -value;
break;
case Kind::SQUARE:
folded = value * value;
break;
case Kind::CUBE:
folded = value * value * value;
break;
default:
folded = std::sqrt(value);
break;
}
pushNumber(folded);
continue;
}
// 非常量:保留指令,栈顶保持"非常量"(本来就如此)。
output.push_back(instruction);
}
program.swap(output);
}
} // namespace
FormulaProgram::FormulaProgram(const std::wstring& text)
{
if (text.empty())
{
return;
}
std::vector<Token> tokens;
std::wstring error;
if (!Tokenize(text, tokens, &error))
{
return;
}
Parser parser(tokens, m_instructions, &error);
if (!parser.Parse())
{
m_instructions.clear();
return;
}
// 常量折叠 + 幂次改写(`x^2` ⇒ `x*x`):逐点求值的指令数与 `pow` 调用都随之减少。
OptimizeProgram(m_instructions);
// ⚠️ 编译期栈深校验:`Evaluate()` 不做运行期边界检查(性能),因此这里必须拒绝
// 深层嵌套的表达式(它们会回退到带检查的 `EvaluateFormula()`,结果一致)。
std::size_t depth = 0;
std::size_t maximumDepth = 0;
for (const FormulaInstruction& instruction : m_instructions)
{
switch (instruction.kind)
{
case FormulaInstruction::Kind::NUMBER:
case FormulaInstruction::Kind::VARIABLE:
++depth;
if (depth > maximumDepth)
{
maximumDepth = depth;
}
break;
case FormulaInstruction::Kind::NEGATE:
break;
default:
if (depth >= 2)
{
--depth;
}
break;
}
}
if (maximumDepth > kFormulaMaxStack)
{
m_instructions.clear();
return;
}
m_valid = true;
}
bool ValidateFormula(const std::wstring& text, std::wstring* error)
{
if (error != nullptr)
{
error->clear();
}
if (text.empty())
{
return true;
}
std::vector<Token> tokens;
if (!Tokenize(text, tokens, error))
{
return false;
}
std::vector<FormulaOp> program;
Parser parser(tokens, program, error);
if (!parser.Parse())
{
return false;
}
return true;
}
double EvaluateFormula(const std::wstring& text, double x)
{
// 逐点路径(绘制 / 统计 / 派生烘焙)与批量路径共用**同一份**编译结果:
// 线程内按**内容**缓存一条 `FormulaProgram`(含同一套编译期优化)。
// ⚠️ 不能只比指针(SSO 下等长改公式会复用旧程序,见历史记录)。
static thread_local FormulaProgram cachedProgram;
static thread_local std::wstring cachedText;
static thread_local bool cached = false;
if (!cached || cachedText != text)
{
cachedProgram = FormulaProgram(text);
cachedText = text;
cached = true;
}
if (!cachedProgram.Valid())
{
return x; // 空 / 非法:不做映射(保证波形照常显示)
}
return cachedProgram.Evaluate(x);
}
std::wstring NormalizeFormulaText(const std::wstring& text)
{
std::wstring output;
output.reserve(text.size() + 8);
const std::size_t length = text.size();
std::size_t index = 0;
while (index < length)
{
const wchar_t ch = text[index];
if (std::iswalpha(static_cast<wint_t>(ch)) == 0)
{
output.push_back(ch);
++index;
continue;
}
const std::size_t start = index;
while (index < length && std::iswalpha(static_cast<wint_t>(text[index])) != 0)
{
++index;
}
std::wstring name = text.substr(start, index - start);
// 已经是 `f(t)`:跳过随后的 `(t)`,整体原样输出(统一写成小写形式)。
std::size_t look = index;
while (look < length && std::iswspace(static_cast<wint_t>(text[look])) != 0)
{
++look;
}
bool hasArgument = false;
if (look < length && text[look] == L'(')
{
std::size_t inner = look + 1;
while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
{
++inner;
}
if (inner < length && (text[inner] == L't' || text[inner] == L'T'))
{
++inner;
while (inner < length && std::iswspace(static_cast<wint_t>(text[inner])) != 0)
{
++inner;
}
if (inner < length && text[inner] == L')')
{
hasArgument = true;
index = inner + 1;
}
}
}
std::wstring lowered = name;
for (wchar_t& letter : lowered)
{
letter = static_cast<wchar_t>(std::towlower(static_cast<wint_t>(letter)));
}
// 数据点:`X` / `x` / `f(t)`(含 `F(T)`)一律写成规范形式 `f(t)`。
// ⚠️ **单独的 `f` 不归一化**:它不是合法写法(用户 2026-11-03 明确要求),
// 原样输出交给 `ValidateFormula` 报错,而不是悄悄当成 `f(t)` 接受。
if (lowered == L"x" || (lowered == L"f" && hasArgument))
{
output += L"f(t)";
}
// 常量统一为小写(`E` / `Pi` / `PI` → `e` / `pi`)。
else if (lowered == L"e")
{
output += L"e";
}
else if (lowered == L"pi")
{
output += L"pi";
}
else
{
output += name;
}
}
return output;
}
} // namespace jdi