问题标签 [lookup-tables]

我已经实现了一个查找表来计算我系统中的正弦/余弦值。我现在需要反三角函数（arcsin/arccos）。

我的应用程序在嵌入式设备上运行，由于程序内存有限，我无法在该设备上为 arcsin 添加第二个查找表。所以我想到的解决方案是浏览正弦查找表以检索相应的索引。

我想知道这个解决方案是否比使用来自数学标准库的标准实现更有效。
有人已经对此进行了实验吗？

LUT 的当前实现是从 0 到 PI/2 的正弦值数组。存储在表中的值乘以 4096，以保持整数值对我的应用程序具有足够的精度。查找表的分辨率为 1/4096，它为我们提供了一个包含 6434 个值的数组。然后我有两个函数正弦和余弦，以弧度乘以 4096 作为参数。这些函数将给定的角度转换为第一象限中的相应角度，并读取表中的相应值。

我的应用程序在 dsPIC33F 上以 40 MIPS 运行，我使用 C30 编译套件。

假设我有一个声明如下的结构：

现在我想做的是从另一个结构中调用它，但我必须知道如何。我正在尝试做的事情（在我看来）如下所示：

我的最终目标是我想使用如下所示的代码，而不必创建对象的实例：

所以这个“查找表”将在另一个项目中创建并构建，然后从我的主项目中作为 dll 调用。由于我在其他地方构建 dll 并调用它，我希望我可以将 dll 加载到内存中一次，然后我可以从我的主项目中引用该内存。然后我将分配一部分内存，我的代码将只引用它，避免创建此查找表的各个实例（从而避免分配内存和存储新实例所需的时间开销）。从长远来看，我节省的时间将非常有益，所以我希望我能以某种方式让它发挥作用。

我希望这不会太令人困惑，但如果需要任何澄清，请告诉我。

编辑 这是在网站上使用的，所以我真的需要一个在所有连接中持续存在的对象，并且在最初加载代码时创建一次。同样的想法，但也许这会产生一个更简单的解决方案？

在我的数据库中，许多表都有“状态”字段，表示该特定实体所在的状态。有人告诉我，我们应该为这种事情使用查找表，但我不确定确切的机制。有人可以澄清这些观点吗？

1. 如何保持完整性？（即我如何确保只有状态表中的值进入其他表？）

2. 是状态名称进入其他表，还是状态表中的状态 ID 进入其他表？

我需要在 Access 中创建一个查找表，其中所有缩写都与一个值相关，如果缩写（在主表中）为空，那么我想显示“未知”

我得到了这些值，但我似乎无法让空值出现。

我的查找表如下所示：

但是当我按请求进行计数时，它只显示 A 和 D 的值，尽管我知道那里也有一些空白。

我究竟做错了什么？

我的学生访问表中有一个查找字段（宿舍）。当我在 MailMerge 中使用该表时，在 Word 中，查找字段显示为数字而不是宿舍。就好像关系在 MailMerge 中丢失了。有谁知道是否可以使用查找表实现 MailMerge，如果可以，如何实现？

考虑问题末尾的示例，每次GetName()调用函数时都会创建地图对象吗？
或者创建将被优化并创建为一些查找表？

我们有一组数据（只是地点的名称），但超过 25k+。有人问我是否有办法（总是有）搜索这些数据，然后根据用户输入从这些数据中返回一个值。

现在我的技能确实在于 XHTML 和 CSS，我可以涉足 JSP 和 JQuery，但我不确定最好的方法。我们能：

1. 将数据存储在访问数据库中，然后编写查询以根据用户输入选择值？然后需要在网页上显示此输出。不过，这需要用什么语言完成？

2. 我发现了一个我认为非常棒的 JQuery 'Quicksearch' 插件（http://lomalogue.com/jquery/quicksearch/super_table.html）

现在我喜欢 2) 的想法，因为它是在 JQuery 中完成的，但我认为这对于这种大小的数据是不可行的，尤其是因为页面会很大（尽管我假设一些数据可能被隐藏）。有没有更简单的方法？我错过了什么吗？

感谢这可能被认为是模糊的，所以很抱歉，但我不知道最好的方法是什么。

谢谢

存储查找日期选择（实际值或查找索引）的最佳方法是什么？以我的 iPhone 应用程序的 CoreData 为例。选项似乎是：

1）存储实际值（例如整数或浮点数） - 但是当用户从值的查找列表中修改他们的当前值时，代码必须确定这是第一个，并希望有一个匹配它们在当前查找值列表中的值。

2）存储查找索引 - 但是如果您想更改查找列表中的值范围，您可能会引入不匹配错误

如果我错过了另一种选择，有什么建议是最好的方法，或者另一种方法？

PS 例如，如果查找是“从 3.1、3.2 和 3.3 kg 中选择一个重量，那么如果这是选择的重量，您可以存储选项 (1) 3.1，但是对于选项 (2)，您可能只存储 0 (即一个索引）来表明它是用户想要的第一个选择。

我有几乎非规范化的现有表。没有针对事物列表状态、类型、国家/地区等的查找表……最初的设计只是为了简化应用程序对数据库的访问，因此这种非规范化没有性能原因。

这导致了包含大量重复数据的表，我想通过为各种状态/类型/国家列引入查找表来正确规范化。

是否有一些我可以在数据库（oracle）中做到这一点，对客户保持透明？应用程序将继续执行插入操作，但数据库会将内容映射到幕后的正确查找表。

我一直在尝试组合视图和触发器来进行映射，但感觉应该有一种更自动的方式来执行此操作。

考虑一个具有以下签名的查找函数，它需要为给定的字符串键返回一个整数：

进一步考虑，在编写函数的源代码时，编号为 N 的键值映射是预先知道的，例如：

因此，上述输入的函数的有效（但不完美！）实现将是：

还可以提前知道对于每个给定的键，该函数将在运行时被调用多少次（C>=1）。例如：

但是，此类调用的顺序未知。例如，上面可以描述运行时的以下调用序列：

或任何其他序列，前提是呼叫计数匹配。

还有一个限制 M，以最方便的任何单位指定，定义任何查找表和其他辅助结构可以使用的内存上限GetValue（这些结构是预先初始化的；该初始化不计入复杂性函数）。例如，M=100 个字符，或 M=256 sizeof(object reference)。

问题是，如何编写GetValue尽可能快的主体 - 换句话说，所有GetValue调用的总时间（请注意，我们知道总计数，以上所有内容）是最小的，对于给定的 N，C和M？

该算法可能需要 M 的合理最小值，例如 M >= char.MaxValue。它还可能要求 M 与某个合理的边界对齐——例如，它可能只是 2 的幂。它还可能要求 M 必须是某种 N 的函数（例如，它可能允许有效的 M=N，或 M=2N，...；或有效的 M=N，或 M=N^2， ...; ETC）。

该算法可以用任何合适的语言或其他形式来表达。对于生成代码的运行时性能约束，假设生成的代码GetValue将使用 C#、VB 或 Java（实际上，任何语言都可以，只要字符串被视为不可变的字符数组 - 即 O(1) 长度和 O (1) 索引，并且没有预先为它们计算的其他数据）。此外，为了简化这一点，假设所有键的 C=1 的答案被认为是有效的，尽管那些涵盖更一般情况的答案是首选。

关于可能方法的一些思考

对上述问题的第一个显而易见的答案是使用完美的哈希，但是寻找一个的通用方法似乎并不完美。例如，对于上面的示例数据，可以使用 Pearson 散列轻松生成一个最小完美散列表，但是每次调用 时都必须对输入键进行散列GetValue，并且 Pearson 散列必须扫描整个输入字符串。但实际上所有示例键的第三个字符都不同，因此只能将其用作散列的输入，而不是整个字符串。此外，如果要求 M 至少为char.MaxValue，则第三个字符本身将成为完美哈希。

对于一组不同的键，这可能不再适用，但仍有可能减少在给出精确答案之前考虑的字符数量。此外，在某些情况下，最小完美散列需要检查整个字符串，可以减少对子集的查找，或者通过使散列非最小来使其更快（例如不太复杂的散列函数？） （即 M > N） - 为了速度而有效地牺牲空间。

也可能是传统的散列一开始就不是一个好主意，而且更容易将主体构造GetValue为一系列条件，排列成第一个检查“最可变”的字符（那个在大多数键），并根据需要进行进一步的嵌套检查以确定正确答案。请注意，此处的“方差”可能会受到每个键将被查找的次数的影响 (C)。此外，最好的分支结构应该是什么并不总是很明显 - 例如，可能是“最可变”字符只能让您区分 100 个键中的 10 个，但对于剩余的 90 个键，需要额外检查无需区分它们，不以“最易变”的字符开头。然后，目标是确定完美的检查顺序。