algorithm - 为每个输入重现相同数字的功能

Question

假设您有一些由 2 列和 10 亿行组成的数据，例如：

0,0
1,0
2,3
3,2
etc

我想创建一个函数，如果给定来自第一列的输入，它将始终给出第 2 列中的内容，以便它将值从第一列映射到第二列，就像它在数据中出现的方式一样。

第 1 列从 0 到 1E9 连续（十亿）

第 2 列只能是 {0,1,2,3}

我不想只将数据存储在数组中。我想要可以计算此地图的代码。

有任何想法吗？

提前致谢

Answer 1

如果键很密集，一维数组应该没问题，其中 weights[key] = weight

否则，如果键是稀疏的，则诸如字典之类的查找结构将起作用。

不确定您是否还需要关于随机部分的帮助，但累积总和和 rand(sum(weights)) 将随机选择权重较大的数字。

为清晰起见编辑权重是数组

Answer 2

假设@munch1324 是正确的，问题是：

给定 1000 个数据点的集合，动态生成与数据集匹配的函数。

那么是的，我认为这是可能的。但是，如果您的目标是让函数更紧凑地表示数据收集，那么我认为您不走运。

这里有两种可能性：

分段定义函数

int function foo(int x)
{
  if (x==0) return 0;
  if (x==1) return 0;
  if (x==2) return 3;
  if (x==3) return 4;
  ...
}

多项式插值

可以拟合 N 个数据点以精确匹配 N-1 次多项式。

给定 1000 个数据点的集合，使用您最喜欢的方法求解 999 度多项式的 1000 个系数。

你得到的函数将是：

int[] c; // Array of 1000 polynomial coefficients that you solved for when given the data collection
...
int function foo(int x)
{
  return c[999]*x^999 + c[998]*x^998 + ... + c[1]*x + c[0];
}

这有明显的问题，因为您要存储 1000 个系数，并且会遇到将 x 值提高到如此高的幂的数值问题。

如果您正在寻找更高级的东西，拉格朗日多项式将为您提供适合所有数据点的最小次数多项式。