C std::vector ve ArrayList Java ve diğer birçok dilde dinamik olarak tahsis edilen dizi kendi formuna sahip. Dinamik bir dizi uzay bittiğinde, daha büyük bir alana yeniden alır ve eski değerleri yeni diziye kopyalanır. Dizi boyutu büyüyor nasıl bir soru böyle bir dizi performans merkezidir. Her zaman tek geçerli push sığdırmak için yeterince büyük büyümek varsa, her zaman yeniden bitireceğiz. Sense dizi boyutu Çift Kişilik veya 1.5 x diyelim çarp anlamına geliyor.

İdeal büyüme faktörü var mı? 2x? 1.5 x? İdeal tarafından matematiksel olarak haklı, en iyi performans dengeleme ve bellek israf yani. Teorik olarak fark ediyorum ki, uygulama bu uygulama biraz bağımlı olduğunu iter Olası herhangi bir dağıtım olabilir göz önüne alındığında. Ama eğer bu "genellikle" en iyi ya da en iyi biraz sıkı kısıtlama içinde kabul edilir. bir değeri varsa merak ediyorum

Bu bir yerde bir kağıt olduğunu duydum, ama bulamıyor oldum.

1.5 en az C (Bu muhtemelen çalışma sistemi olacak nesneleri konumlandırmak nereye yönetilen diller için geçerli değil) uygulanan iki tercih, neden okuma yıllar önce hatırlıyorum.

Mantık şudur:

1. 16-bayt ayırma ile başlar söylüyorlar.
2. Daha fazla ihtiyacınız olduğunda, size 32 bayt ayırma, 16 bayt boş. Bu 16 bayt bellek içinde bir delik bırakır.
3. Daha fazla ihtiyacınız olduğunda, 64 bayt 32 bayt boşaltma ayrılamadı. Bu 48 baytlık delik ise 16 ve 32 bitişik olsaydı () bırakır.
4. Daha fazla ihtiyacınız olduğunda, 128 bayt, 64 bayt boşaltma ayrılamadı. Bu 112 baytlık bir delik (tüm önceki tahsisatı bitişik varsayarak) bırakır.
5. Ve böylece ve benzeri.

Fikir, 2x bir genişleme ile sonuçlanan delik daha sonraki tahsisi için yeniden kullanmak için yeterince büyük olacak o zaman anlamı yok. 1.5 x bir ayırma kullanarak, bunun yerine, biz var:

1. 16 bayt ile başlar.
2. Daha fazla ihtiyacınız olduğunda, 24 bayt ayırma, serbest zaman 16, 16-bayt bir delik bırakarak.
3. Daha ihtiyacın olursa, 36 bayt ayırma, serbest 24, 40 baytlık bir delik bırakarak.
4. Daha fazla ihtiyacınız olduğunda, 54 bayt ayırma, serbest 76 baytlık bir delik bırakarak 36.
5. Daha fazla ihtiyacınız olduğunda, 81 bayt ayırma, serbest 130 baytlık bir delik bırakarak 54.
6. Daha ihtiyacın olursa, 130 bayt delik 122 bayt (yuvarlama) kullanın.