0

我有一个小程序可以读取包含类 C 宏的输入文件。该处理分两遍进行：第一遍搜索宏定义并存储它们，第二遍搜索宏调用并扩展/替换它们。

这一切都很好，但它很耗时。目前，这就是我的做法：

foreach token in file:
    foreach macro in macroDefinitions:
        if token equals macro.name:
            expand()
        endif
    end foreach
endforeach

在这个伪示例中，“token”是源文件中的一个单词，“macro”是第一次传递的宏定义。大约有 20 000 个宏定义和 1800 个输入文件，总共需要处理大约 600 000 行（每行被分成 n 个标记）。这意味着总比较计数是（令牌计数）*（宏定义计数）。我怎样才能加快速度？我错过了什么，还是我真的必须做所有这些比较？

有关其他信息，标记是 String[] 数组中的字符串，宏是 ArrayList 类型的列表中的宏对象。我可以用其他类型的数据结构加快这个过程吗？

4

5 回答 5

1

我建议创建一个脚本，例如Perl实际上执行文件处理并使用ProcessBuilderJava从您的代码中调用该脚本。 为每个问题使用最好的工具。

于 2013-04-16T10:38:17.817 回答
1

You need to use a Map that maps from a macro name to its definition.

In pseudo-code:

for each token in file:
    if this is a macro defininition:
        name, definition <- parse definition
        map.put(name, definition)

for each token in file:
    if map.contains(token):
        definition <- map.get(token):
        expand definition

(Update - You can get rid of the contains call and just call get and then test for null. It is worth reading the javadocs to get a better understanding of how the Map, TreeMap and HashMap APIs work.)

Typical implementations of Map use either a balanced binary tree or a hash table, and have lookup and insert operations that have complexity O(logN) or O(1) (under normal circumstances).

于 2013-04-16T10:53:17.457 回答
0

将宏定义放在 aMap中将大大减少查找宏所需的时间。

于 2013-04-16T10:39:36.650 回答
0

编辑：如果您可以添加密钥，Klas Lindbäck 解决方案会更好。如果你不能，那么我提出的搜索算法将是提高搜索速度的一种方法。

您可以添加一些搜索算法，例如二进制搜索，这将大大改善搜索结果

于 2013-04-16T10:41:40.267 回答
0

您可以使用HashSet包含宏定义名称的 a，并且对于每个标记，检查它是否包含在集合中：

for(String token : token) {
    if(macroNamesSet.contains(token)) {
        expand();
    }
}

The contains method thake O(1) time. So overall and once the set of macro names has been created, it takes (count of tokens) time.

于 2013-04-16T10:43:40.653 回答