你正在看着每一个给你的角色O(n)
,因为您比较每个字符的下一个 (maximum) 五个字符,这给你一个常数c
:
var data = get_input();
var compare = { `A`, `T`, `G`, `A`, `T` } // or whatever
var MAX_LOOKAHEAD = compare.length
var n
var c
for(n = data_array.length; n < size; i++) { // Has runtime O(n)
for(c = 0; c < MAX_LOOKAHEAD; c++) { // Maximum O(c)
if( compare[c] != data[i+c] ) {
break;
} else {
report( "found match at position " + i )
}
}
}
很容易看出这个运行O(n*c)
次。自从c
非常小,可以忽略 - 而且我认为无法摆脱该常量 - 这导致总运行时间为O(n)
.
好消息:
您可以通过并行化来加快速度。例如。你可以把它分成k
间隔并让多个线程通过给它们适当的开始和结束索引来为您完成工作。这可以给你一个线性加速比.
如果您这样做,请确保将交叉点视为特殊情况,因为如果您的间隔将一场比赛分成两部分,您可能会错过一场比赛。
E.g. n = 50000
:
4个线程的分区:(n/10000) - 1 = 4
。第 5 个线程不会有很多事情要做,因为它只是处理交叉点,这就是为什么我们不需要考虑它的 (在我们的例子中很小) 高架。
1 10000 20000 40000 50000
|-------------------|-------------------|-------------------|-------------------|
| <- thread 1 -> | <- thread 2 -> | <- thread 3 -> | <- thread 4 -> |
|---| |---| |---|
|___________________|___________________|
|
thread 5
它可能是这样的:
var data;
var compare = { `A`, `T`, `G`, `A`, `T` };
var MAX_LOOKAHEAD = compare.length;
thread_function(args[]) {
var from = args[0];
var to = args[1];
for(n = from ; n < to ; i++) {
for(c = 0; c < MAX_LOOKAHEAD; c++) {
if( compare[c] != data[i+c] ) {
break;
} else {
report( "found match at position " + i )
}
}
}
}
main() {
var data_size = 50000;
var thread_count = 4;
var interval_size = data_size / ( thread_count + 1) ;
var tid[]
// This loop starts the threads for us:
for( var i = 0; i < thread_count; i++ ) {
var args = { interval_size * i, (interval_size * i) + interval_size };
tid.add( create_thread( thread_function, args ) );
}
// And this handles the intersections:
for( var i = 1; i < thread_count - 1; i++ ) {
var args = { interval_size * i, (interval_size * i) + interval_size };
from = (interval_size * i) - compare.length + 1;
to = (interval_size * i) + compare.length - 1;
for(j = from; j < to ; j++) {
for(k = 0; k < MAX_LOOKAHEAD; k++) {
if( compare[k] != data[j+k] ) {
break;
} else {
report( "found match at position " + j )
}
}
}
}
wait_for_multiple_threads( tid );
}