循環列表遍歷引擎

Question

我想在一個給定的輸入順序遍歷循環鏈表(v1->v2->v3)，可以說像

{v1,v3,v2,v2,v1,v3,v2,v1,v1,v3,v2,v2,v1,v2,v3}。

我編寫了下面的程序作爲3個節點的測試，並且想要遞增地爲8,64,512,4096等節點縮放。

我的實現理念要求下面的程序僅在Abstract State Machine上運行，它只接受下面的函數作爲處理輸入。我基本上希望在遍歷時儘量減少engine_spin_at_gear()的循環次數。我可能會在non-blocking模式下使用這樣一個瘋狂的abstraction來模擬/虛擬process-execution作爲engine-spin與測量單位爲rpm，但我真的很喜歡關於調試engine_spin_at_gear()函數的建議。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#define MILES 15 

struct package 
{ 
     // ... other members data ... 
     struct package *next; 
}*v1, *v2, *v3; 

int input_arr[MILES] = {1,3,2,2,1,3,2,1,1,3,2,2,1,2,3}; 

struct package *base(struct package *_vN) 
{ 
     if (_vN) 
       return _vN; 
     else 
       return NULL; 
} 

struct package *deliver(struct package *_vNP) 
{ 
     if (_vNP) 
       return base(_vNP->next); 
     else 
       return NULL; 
} 

void shift_gear(struct package *_feed) 
{ 
     _feed->next = NULL; 
} 

struct package *engine_spin_at_gear(struct package *_init_cycle0, int countSession) 
{ 
     while (countSession--) { 
       shift_gear(_init_cycle0); 
       return deliver(base(_init_cycle0)); 
     } 
     return NULL; 
} 

struct package *journey(struct package *_current_frame, int _start, int _end) 
{ 
     int rpm = (_end > _start)?_end-_start:_start-_end; 
     if (rpm) 
       return engine_spin_at_gear(_current_frame, rpm); 
     else 
       return v1; 
} 

struct package *ignition_phase(int _batteryS, int _chargedL) 
{ 
     return journey(v1, _batteryS, _chargedL); 
} 


void transmit_in_order(int*input_arr) 
{ 
     struct package *v6; 
     int i; 

     for (i=0; i<MILES-1; i++) { 
       v6 = ignition_phase(input_arr[i], input_arr[i+1]); 
       printf("%p\n", v6); 
     } 
} 

int main() 
{ 
     v1 = malloc(sizeof(struct package)); 
     v2 = malloc(sizeof(struct package)); 
     v3 = malloc(sizeof(struct package)); 

     v1->next = v2; 
     v2->next = v3; 
     v3->next = v1; 

     printf("v1=%p\tv2=%p\tv3=%p\n", v1, v2, v3); 
     transmit_in_order(input_arr); 
     return 0; 
} 

當我在Linux上運行我的程序的GCC可執行文件時，我得到以下輸出。

v1=0x918b008 v2=0x918b018 v3=0x918b028 
(nil) 
(nil) 
0x918b008 
(nil) 
(nil) 
(nil) 
(nil) 
0x918b008 
(nil) 
(nil) 
0x918b008 
(nil) 
(nil) 
(nil) 
(nil) 

或者，是否需要更改shift_gear()函數？我可以在保持scalability-factor完好的同時進行更多優化嗎？提前致謝。如果我想把所有這些功能放在C++中作爲Class Engine和Class Gearbox，你能告訴我一個原型嗎？

Answer 1

優化之外，你有input_arr一個問題：

int input_arr[MILES] = {1,3,2,2,1,3,2,1,1,3,2,2,1,2,3}; //has 15 elements 

雖然下面的循環需要16：

for (i=0; i<MILES-1; i++) { //[edited] so i goes from 0 to 13 
     v6 = ignition_phase(input_arr[i], input_arr[i+1]); //otherwise, i goes to 14, +1 == 15 - 1 too big 
     printf("%p\n", v6); 
} 

可以創建一個更大的陣列，或更早停止循環1遞增。

對此代碼：

struct package *engine_spin_at_gear(struct package *_init_cycle0, int countSession) 
{ 
     while (countSession--) { 
       shift_gear(_init_cycle0); // } 
       return deliver(base(_init_cycle0)); 
     } 
     return NULL; 
} //move this one to after shift_gear(_init_cycle0); 

如果收盤while循環}被移動到在評論表示？ （根據你的和查理的觀察）如果你在那裏保留return語句，你將永遠不會超過第一個循環。根據小的改動代碼

輸出的變化：
改變用於for (i=0; i<MILES; i++) {到for (i=0; i<MILES-1; i++) {

改變

while (countSession--) { 
     shift_gear(_init_cycle0); 
     return deliver(base(_init_cycle0)); 
} 

至後之後：

while (countSession--) { 
     shift_gear(_init_cycle0);} 
     return deliver(base(_init_cycle0)); 

//}

因此，似乎有一定的效果，但我不知道如何解釋這個輸出。即這些變化意味着什麼意義。

Answer 2

你提到擴展到更大的項目數，這裏是擴展到100某些部分，

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

typedef struct package_s 
{ 
    // ... other members data ... 
    struct package_s* next; 
} package; //being lazy, I avoid typing struct everywhere... 

#define HOWMANY (100) 
package* v[HOWMANY]; 

#define MILES 15 
int input_arr[MILES] = {1,3,2,2,1,3,2,1,1,3,2,2,1,2,3}; 

package* 
journey(package* _current_frame, int _start, int _end) 
{ 
    int rpm = (_end > _start) ? (_end-_start) : (_start-_end); 
    if (rpm) 
     return engine_spin_at_gear(_current_frame, rpm); 
    else 
     return v[0]; 
} 

package* 
ignition_phase(int _batteryS, int _chargedL) 
{ 
    return journey(v[0], _batteryS, _chargedL); 
} 

而這個修復解決掉input_arr結束（也許你想繞回至零？）

void 
transmit_in_order(int*input_arr) 
{ 
    package *v6; 
    int i; 

    for (i=0; i<MILES-2; i++) { 
     v6 = ignition_phase(input_arr[i], input_arr[i+1]); 
     printf("%p\n", v6); 
    } 
} 

而且主要爲v[n]配置的數量，

int main() 
{ 
    int ndx; 
    for(ndx=0; ndx<HOWMANY; ++ndx) 
    { 
     v[ndx] = malloc(sizeof(package)); 
    } 

    for(ndx=0; ndx<HOWMANY; ++ndx) 
    { 
     v[ndx]->next = v[(ndx+1)%HOWMANY]; 
     printf("v[%d]=%p\t", ndx, v[ndx]); 
    } 
    printf("\n", ndx, v[ndx]); 

    transmit_in_order(input_arr); 
    return 0; 
}