在c中廣泛使用realloc（）

爲了提高計算速度，我需要在樹中存儲大量數據。一些節點應該包含裏面的點的平均屬性，另一些則不應該，例如典型的光節點只包含子節點和典型的常規節點的地址，這兩個地址加上一些信息。我正在尋找一種聰明的方式將這兩種節點存儲在同一棵樹中，使用最少的內存。在c中廣泛使用realloc（）

我正在使用c。我首先使用結構（node.properties，node.Left，nodeRight等）構建了我的樹，但它需要太多內存（如果您熟悉結構，您可能會找出原因），所以我有返回到我的樹的某種「在線」組織，將子節點的地址存儲在前兩個插槽中，並且（最終）將其餘信息存儲在以下插槽中。

所以我儘管有兩種方法。一種方法是預測節點的總數（容易）並分配足夠的內存以將所有節點存儲爲常規節點（2個用於子節點地址和1個用於信息的時隙）。另一種方法是在我們沿着樹走向時重新分配樹數組。

第一個問題：在效率方面廣泛使用realloc（）是否真的是件好事？

第二個問題：有沒有更聰明的方法（記憶方面）做到這一點？

來源

2012-03-10 Waribiki

訣竅是選擇你的重新分配算法，以儘可能避免它。傳統的觀點是以任意小的尺寸啓動它，並且每次需要重新分配（）它時，分配的內存量將增加一倍。假設你從1K開始，當它調整到2K，然後到4K，然後到8K，等等。 – 2012-03-10 23:27:05

我聽說一次'malloc'的現代實現在不同大小的舞臺上組織內存，'realloc'確實干擾了通過強制錯誤大小的區域進入錯誤的舞臺... – 2012-03-10 23:27:37

@KerrekSB我希望現代圖書館能夠解釋這一點，考慮到realloc它允許改變位置...... – 2012-03-10 23:47:58

好的，我認爲我找到了一個妥協方案。首先確定樹的大小，並分配大小爲2 X的節點數的指針數組。每個節點將有（1）[指向]一個整數數組，指向左子元素的索引，右子元素的索引和點的數量，以及（2）[指向]包含雙精度元素的數組的指針所有有用的信息。隨着例程構建樹，分配給「double」數組的空間將根據節點的類型進行計算。

到目前爲止，這是我能想到的「最便宜」的解決方案。但是如果你能說服我轉換（long）index_in_double的速度很快，那麼只能在數組中使用double。

來源

2012-03-11 12:09:22 Waribiki

爲了說明使用索引而不是指針的要點，請參見使用（短）int索引的this hash table implementation，保存一些寶貴的位。的tiny_find（）函數編譯成這個組件（GCC -O2）：

 .globl tiny_find 
     .type tiny_find, @function 
tiny_find: 
.LFB57: 
     .cfi_startproc 
     imull $98765, %edi, %ecx 
     movl $274877907, %edx 
     movl %ecx, %eax 
     mull %edx 
     movl $-1, %eax 
     shrl $6, %edx 
     imull $1000, %edx, %edx 
     subl %edx, %ecx 
     movzwl %cx, %ecx 
     movzwl table+4(,%rcx,8), %edx 
     cmpw $-1, %dx 
     je  .L12 
     movzwl %dx, %eax 
     testb $1, table+7(,%rax,8) 
     jne  .L19 
     jmp  .L13 
     .p2align 4,,10 
     .p2align 3 
.L21: 
     movzwl table+4(,%rax,8), %eax 
     cmpw $-1, %ax 
     je  .L20 
     movzwl %ax, %eax 
     testb $1, table+7(,%rax,8) 
     je  .L13 
.L19: 
     cmpl table(,%rax,8), %edi 
     jne  .L21 
.L13: 
     movzbl table+6(,%rax,8), %eax 
.L12: 
     rep 
     ret 
     .p2align 4,,10 
     .p2align 3 
.L20: 
     movl $-1, %eax 
     ret 
     .cfi_endproc 
.LFE57: 
     .size tiny_find, .-tiny_find

內環（步行鏈表）是L21和L13之間的部分。我不會說代碼是低效的。

來源

2012-03-11 16:44:34 wildplasser

在c中廣泛使用realloc（）

回答

相關問題