最近更新: 2010-05-16

就地(不用額外記憶體)把字串反向

前陣子,有位同事看了《約耳趣談軟體》(Joel On Software 中譯版),就作者提到面試人員教戰守則中的第一道程式問題向我請教。那道題目是「就地(不用額外記憶體)把字串反向」。同事不熟 C 語言,不了解作者為何說不懂指標的人,解這題一定會錯。所以跑來問我。

這道問題難就難在「不用額外記憶體」的條件。再者,就算面試者用了指標,我仍然可以就 C 語言的意義挑毛病,指出光用指標無法滿足「不用額外記憶體」的條件。如果只是從 C 語言的角度思考,僅用指標寫不出滿足條件的字串反向程式。面試者還要能從組合語言的角度思考,才能向出題者解釋他的程式確實滿足條件。

因為我了解指標,所以我會直接寫出下列字串反向程式。(OK, 如果主考官想找一個 C 語言程式設計人員,看到下列程式碼,九成就會直接錄用)

// strrev.c
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    char *f, *t, c;

    if (argc < 2) {
        puts("input one string");
        return 1;
    }
    
    f = t = argv[1];
    
    while (*t) 
        t++; 
    --t;
    
    while (t > f) {
        c = *f;
        *f++ = *t;
        *t-- = c;
    }
    puts(argv[1]);
    
    return 0;
}

上列程式透過指標指向字串 argv[1],利用指標搬移字元,所以不用建立額外的字串。

這段程式碼中,沒有出現任何一次 malloc(),看起來似乎滿足「不用額外記憶體」的條件了。但我還是可以挑毛病,「嘿,你定義了三個變數 f,t,c,這三個變數用了額外的記憶體」。

不要懷疑,從 C 語言的定義來說,那三個變數確實用了額外的記憶體。當你在函數內定義了區域變數時,就是在堆疊(stack)中配置記憶體儲存變數內容。編譯器會計算區域變數的總容量,在函數的進入點後,加入一段碼,令堆疊索引暫存器之定址增加等於區域變數總容量之值。如此一來,堆疊索引暫存器與堆疊基底暫存器之定址包住的記憶體區間,就是區域變數額外配置的記憶體。編譯器同樣會在函數的返回點前,加入一段碼,令堆置索引暫存器之定址減少相同之值。這表示釋出區域變數配置的記憶體。

所以光是懂指標,上列程式碼還無法讓我等挑惕者滿意。面試者必須要了解計算機架構(具組合語言的基礎)與 C 編譯器最佳化動作的意涵。才能更進一步地向出題者說明上列程式碼如何得以滿足「不用額外記憶體」的條件。如果你精通組合語言,你就可以用組合語言寫出完全不用額外記憶體的字串反向程式,連解釋都免了。

在平面記憶體定址機制中(float memory),每一個指標的大小就等於一個暫存器大小。同時,每一個暫存器的大小,也必定大於或等於該計算機中一個無修飾字元的大小 (即 char 等於 byte)。在上列程式中,只使用了兩個指標變數與一個字元變數,以現代 CPU 內含的暫存器數量來看,足夠提供三個暫存器儲存這三個變數的內容。基本上,只要啟用了 C 編譯器的最佳化選項中的暫存器使用最佳化項目,C 編譯器就可以在處理字串反向的程式區段中,找出三個暫存器儲存那三個變數的內容,連堆疊都不必使用。

以 gcc 編譯器為例,只要啟用第一級最佳化 (-O) 就足夠得到我們想要的結果。我利用 gcc 的組譯功能,得到上列 C 程式碼在第一級最佳化後實際產生的組合語言程式碼。下列:

$ gcc -S -O strrev.c
$ cat strrev.s
	.file	"strrev.c"
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"input one string"
	.text
.globl main
	.type	main, @function
main:
.LFB34:
	.cfi_startproc
	subq	$8, %rsp
	.cfi_def_cfa_offset 16
	cmpl	$1, %edi
	jg	.L2
	movl	$.LC0, %edi
	call	puts
	movl	$1, %eax
	jmp	.L3
.L2:
	addq	$8, %rsi
	movq	(%rsi), %rdx
	movq	%rdx, %rax
	cmpb	$0, (%rdx)
	je	.L5
.L10:
	addq	$1, %rax
	cmpb	$0, (%rax)
	jne	.L10
.L5:
	subq	$1, %rax
	cmpq	%rax, %rdx
	jae	.L7
.L8:
	movzbl	(%rdx), %ecx
	movzbl	(%rax), %edi
	movb	%dil, (%rdx)
	addq	$1, %rdx
	movb	%cl, (%rax)
	subq	$1, %rax
	cmpq	%rax, %rdx
	jb	.L8
.L7:
	movq	(%rsi), %rdi
	call	puts
	movl	$0, %eax
.L3:
	addq	$8, %rsp
	ret
	.cfi_endproc
.LFE34:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
	.section	.note.GNU-stack,"",@progbits

自標記 L5 起,C 編譯器就令暫存器 rax 為指標 t,令暫存器 rdx 為指標 f,令暫存器 rcx 的低位元組部份 cl 為變數 c。再使用暫存器 edi 的低位元組部份 dil 作為從兩指標間搬移字元的暫存器;也就是負責 *f = *t 此一記憶體間資料搬移動作的暫存器。

標記 L8 到 L7 之間的程式區段,就是 C 程式碼中,實際處理字串反向動作之 while ( t > f) {... } 的內容。這段程式碼只用了暫存器(4個),沒有使用任何額外的記憶體。故滿足題目的條件。

乍看之下很簡單的一道問題,確實能看出面試者對指標與計算機架構的理解程度。就是要懂這些基礎知識,才能說明你的程式碼真的沒有使用額外的記憶體。

樂多舊網址: http://blog.roodo.com/rocksaying/archives/12418697.html

樂多舊回應
未留名 (#comment-20803977)
Mon, 31 May 2010 14:21:45 +0800
受教了
謝謝囉
未留名 (#comment-21329915)
Mon, 18 Oct 2010 00:58:49 +0800
搜尋時突然看到這問題
覺得滿有趣的
這樣應該可以吧


int main(int argc, char **argv)
{
while(*argv[1])
argv[1]++;

argv[1]--;

while(*argv[1]) {
printf("%c", *argv[1]);
argv[1]--;
}
argv[1]++;

return 0;
}
未留名 (#comment-21330073)
Mon, 18 Oct 2010 01:47:49 +0800
你只是從尾巴往前把字串中的字元印出來而已,並沒有把字串中的字元順序反轉過來。


未留名 (#comment-21331065)
Mon, 18 Oct 2010 13:15:57 +0800
天阿~~~我亂入了~~~
版主涉獵的東西還真廣阿~~~~
從底層到UI
工作一年的倦怠...在半夜12點看了版主的部落格
我又燃起一股熱情
不過我還在想有辦法不宣告變數寫一個void strrev(char *p)嗎
未留名 (#comment-21334117)
Tue, 19 Oct 2010 16:34:52 +0800
可以啊,用 inline assembly 寫,只用暫存器,不用變數。

組合語言碼可以用本文教的方式,讓 gcc 幫你產生出來。

:p
未留名 (#comment-21337349)
Thu, 21 Oct 2010 00:11:42 +0800
hi
我後來有寫一個遞迴版的
想一想好像不符合不使用額外記憶體
stack會長大....
發現自己看到這題目一直執著於不宣告變數

#include

void strrev(char *p)
{
if (*(p + 1))
strrev(p + 1);
while (*(p + 1)) {
*p ^= *(p + 1);
*(p + 1) ^= *p;
*p ^= *(p + 1);
p++;
}
}


int main(int argc, char **argv)
{
strrev(argv[1]);

printf("%s\n", argv[1]);

return 0;
}
跟版主交流一下
使用-O效果如何也不清楚
沒trace過gcc inline 的組語
GCC-Inline-Assembly-HOWTO 努力學習中
未留名 (#comment-21339017)
Thu, 21 Oct 2010 17:23:43 +0800
我記得在其他地方看過用遞迴解法的文章。但是遞迴法一定不合格。

在程式語言中,遞迴法就是在用記憶體消除程式碼的複雜度。編譯器最佳化也不能幫你改變這項結果。
未留名 (#comment-21667021)
Wed, 16 Mar 2011 23:44:16 +0800
混在一起後,少宣告一個int
交換用XOR algorithm

#include

int main(int argc, char **argv) {
char *f, *t;

if (argc < 2) {
puts("input one string");
return 1;
}

f = t = argv[1];

while (*t)
t++;
--t;

while (t > f) {
*f ^= *t;
*t ^= *f;
*f++ ^= *t--;
}
puts(argv[1]);

return 0;
}
yuri@hotmail.com(tiara) (#comment-22615772)
Thu, 13 Sep 2012 16:52:21 +0800
C++的泛型解法

template
void reverse(RandomItr first, RandomItr last)
{
while(first < last) std::swap(*first++, *(--last));
}

使用方法

char A[] = "jljljiohoskjbmjbkja";
reverse(std::begin(A), std::end(A));

不過STL已經提供了更精緻的版本,我們不用再重造輪子
std::reverse(std::begin(A), std::end(A));即可

石頭大不太喜歡C++的template,我倒是對他能夠將算法抽象化的能力感到很興奮
未留名 (#comment-22615840)
Thu, 13 Sep 2012 17:44:32 +0800
本文的問題重點在於「解釋你的程式不用額外記憶體」。

用 C++ STL 回答的話,答題者必須把 template 的內容列出來,
證明這個 template 不會使用額外記憶體,我想這反而是自找麻煩了。

至於「我不太喜歡C++的template」的印象,這只是比較性的態度差異。
事實上,如同你的說法,我也很喜歡它的抽象化能力。

但是其他的程式語言,如Ruby, Python也提供同樣的抽象能力,而且門檻使用更低。
我從不諱言 template 的高門檻,因此我對 C++ template 所表現出的喜好度就沒那麼明顯了。
未留名 (#comment-22615904)
Thu, 13 Sep 2012 19:16:06 +0800
補充說明,「就地(不用額外記憶體)把字串反向」是《約耳趣談軟體》的作者 Joel 在書中提到的題目。
他書中說明出題目的是要測試面試者對計算機系統的具體知識、微觀知識。
並不是看面試者對演算法的抽象知識、宏觀知識。

在這個題旨下,使用指標以外的語法並不合適,因為答題者必須花更多的功夫證明他的用法合乎題旨。
yuri@hotmail.com(tiara) (#comment-22616344)
Fri, 14 Sep 2012 03:10:48 +0800
>如Ruby, Python也提供同樣的抽象能力,而且門檻使用更低。
但是執行速度沒那麼理想
至於template門檻高,我覺得還好
撇開那些複雜無比的TMP技巧,其實還滿容易理解和使用的

我發現很多不理解template的人大多都不清楚那些東西可以在
編譯期完成,那些必須在執行期間完成,只要能突破這關
剩下的只是一些語法問題和比較瑣碎的知識而已

另外,玩玩haskell對於理解recursive會有很大的幫助