我正在尝试模拟很多 2 状态、3 符号(单向磁带)图灵机。每个模拟将有不同的输入,并将运行固定数量的步骤。该程序当前的瓶颈似乎是模拟器,在不停止的图灵机上占用大量内存。
任务是模拟大约 650000 个 TM,每个有大约 200 个非空白输入。我正在尝试的最大步数是 10 亿 (10**9)。
下面是我正在运行的代码。 vector<vector<int> > TM
是一个转换表。
vector<int> fast_simulate(vector<vector<int> > TM, string TM_input, int steps) {
/* Return the state reached after supplied steps */
vector<int> tape = itotape(TM_input);
int head = 0;
int current_state = 0;
int halt_state = 2;
for(int i = 0; i < steps; i++){
// Read from tape
if(head >= tape.size()) {
tape.push_back(2);
}
int cell = tape[head];
int data = TM[current_state][cell]; // get transition for this state/input
int move = data % 2;
int write = (data % 10) % 3;
current_state = data / 10;
if(current_state == halt_state) {
// This highlights the last place that is written to in the tape
tape[head] = 4;
vector<int> res = shorten_tape(tape);
res.push_back(i+1);
return res;
}
// Write to tape
tape[head] = write;
// move head
if(move == 0) {
if(head != 0) {
head--;
}
} else {
head++;
}
}
vector<int> res {-1};
return res;
}
vector<int> itotape(string TM_input) {
vector<int> tape;
for(char &c : TM_input) {
tape.push_back(c - '0');
}
return tape;
}
vector<int> shorten_tape(vector<int> tape) {
/* Shorten the tape by removing unnecessary 2's (blanks) from the end of it.
*/
int i = tape.size()-1;
for(; i >= 0; --i) {
if(tape[i] != 2) {
tape.resize(i+1);
return tape;
}
}
return tape;
}
在性能或内存使用方面有什么地方可以改进吗?即使减少 2% 也会产生显着差异。
最佳答案
确保在整个 TM 模拟期间没有分配发生。
在程序启动时预分配一个全局数组,它对于磁带的任何状态都足够大(例如 10^8 元素)。最初将机器放在该磁带阵列的开头。维护段 [0;当前机器模拟访问过的所有单元格的 R]:这使您可以避免在开始新模拟时清除整个磁带阵列。
对磁带元素使用足够的最小整数类型(例如,如果字母肯定少于 256 个字符,则使用 unsigned char
)。如果字母表非常小,您甚至可以切换到位集。这减少了内存占用并提高了缓存/RAM 性能。
避免在最内层循环中使用通用整数除法(它们很慢),仅使用二的幂除法(它们会变成移位)。作为最终的优化,您可以尝试从最内层循环中删除所有分支(对此有多种巧妙的技术)。
关于c++ - 提高 TM 模拟器的性能,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43074928/