• Vui lòng đọc nội qui diễn đàn để tránh bị xóa bài viết
  • Tìm kiếm trước khi đặt câu hỏi

Sử dụng BitArray thay mảng bool[] lớn để tiết kiệm bộ nhớ

Các mẹo vặt linh tinh không thuộc các nhóm trên

Điều hành viên: tungcan5diop, QUANITGROBEST

Hình đại diện của người dùng
vo_minhdat2007
Quản trị
Quản trị
Bài viết: 2227
Ngày tham gia: CN 17/07/2005 1:40 am
Has thanked: 13 time
Been thanked: 87 time
Liên hệ:

Sử dụng BitArray thay mảng bool[] lớn để tiết kiệm bộ nhớ

Gửi bàigửi bởi vo_minhdat2007 » T.Ba 29/05/2012 5:59 pm

Thủ thuật: Sử dụng BitArray
Tác giả: vo_minhdat2007
Mô tả: Sử dụng BitArray thay vì dùng mảng bool[] với số lượng lớn để tiết kiệm khoảng 8 lần bộ nhớ.



Như chúng ta biết, kiểu bool (Boolean) chứa 1 trong 2 giá trị là true hoặc false, nghĩa là 1bit là có thể biểu diễn được. Tuy nhiên thực tế, kiểu bool của C# lại sử dụng đến 1 byte để lưu trữ, và bỏ phí 7bit còn lại. BitArray sẽ giải quyết được vấn đề ấy.

Trước tiên, mời các bạn xem phân tích do mình test dưới đây (có đính kèm code ở cuối bài):

Hình ảnh


Đối với các ngôn ngữ như C# hay Java, mỗi biến không đơn thuần bằng kích thước đã định, mà còn có phần phía trước lưu các thông tin của object đó (thường gọi là Overhead). Trong trường hợp này, mảng boolean có overhead size là 28 byte, và BitArray có overhead size là 82byte. Trong bài viết này mình bỏ qua overhead và chỉ quan tâm phần chứa dữ liệu.

Như chúng ta thấy, với mỗi phần tử tăng lên trong mảng bool[], kích thước bộ nhớ sử dụng lại tăng thêm 1 byte. Trong khi đó, BitArray có bộ nhớ cố định và tăng lên mỗi 32 phần tử. Điều này có thể giải thích như sau: BitArray sẽ khai báo một danh sách kiểu 4 byte (int) và dùng 32bit này để lưu lần lượt, khi hết thì khai báo thêm. Như vậy, BitArray sử dụng hoàn toàn bộ nhớ được cấp, không bỏ phí 7bit/phần tử như mảng bool[].

Về thời gian thực hiện, việc truy cập bool[] có nhanh hơn gần gấp đôi với 1.000.000 phần tử, nhưng thực sự con số này không đáng kể, nhưng các toán tử khác như Not (đảo giá trị toàn bộ), Xor, ... lại nhanh hơn hẳn.

Dưới đây là mẫu test trên, và bạn có thể tham khảo cách dùng BitArray:

  1. using System;
  2. using System.Collections.Generic;
  3. using System.ComponentModel;
  4. using System.Data;
  5. using System.Drawing;
  6. using System.Linq;
  7. using System.Text;
  8. using System.Windows.Forms;
  9. using System.IO;
  10. using System.Runtime.Serialization.Formatters.Binary;
  11. using System.Collections;
  12. using System.Diagnostics;
  13.  
  14. namespace BitArrayTest
  15. {
  16.     public partial class frmMain : Form
  17.     {
  18.  
  19.         #region Constructor
  20.  
  21.         public frmMain()
  22.         {
  23.             InitializeComponent();
  24.         }
  25.  
  26.         #endregion
  27.  
  28.         #region Methods
  29.  
  30.         public long getObjectSizeInMemory(object pObject)
  31.         {
  32.             long result = 0;
  33.  
  34.             using (Stream s = new MemoryStream())
  35.             {
  36.                 BinaryFormatter formatter = new BinaryFormatter();
  37.                 formatter.Serialize(s, pObject);
  38.                 result = s.Length;
  39.  
  40.                 s.Close();
  41.             }
  42.  
  43.             return result;
  44.         }
  45.  
  46.         #endregion
  47.  
  48.         #region UI Methods
  49.  
  50.         private void mButtonAnalyze_Click(object sender, EventArgs e)
  51.         {
  52.             // Process Report string
  53.             StringBuilder report = new StringBuilder();
  54.  
  55.             // Boolean array
  56.             {
  57.                 // 1 element
  58.                 bool[] bools = new bool[1];
  59.                 report.Append("Memory usage of bool[1]: ");
  60.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  61.  
  62.                 // 2 element
  63.                 bools = new bool[2];
  64.                 report.Append("Memory usage of bool[2]: ");
  65.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  66.  
  67.                 // 3 element
  68.                 bools = new bool[3];
  69.                 report.Append("Memory usage of bool[3]: ");
  70.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  71.  
  72.                 // 32 element
  73.                 bools = new bool[32];
  74.                 report.Append("Memory usage of bool[32]: ");
  75.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  76.  
  77.                 // 33 element
  78.                 bools = new bool[33];
  79.                 report.Append("Memory usage of bool[33]: ");
  80.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  81.  
  82.                 // 64 element
  83.                 bools = new bool[64];
  84.                 report.Append("Memory usage of bool[64]: ");
  85.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  86.  
  87.                 // 65 element
  88.                 bools = new bool[65];
  89.                 report.Append("Memory usage of bool[65]: ");
  90.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  91.  
  92.                 // 1000000 elements
  93.                 bools = new bool[1000000];
  94.                 report.Append("Memory usage of bool[1000000]: ");
  95.                 report.AppendLine(this.getObjectSizeInMemory(bools).ToString());
  96.  
  97.                 // Iterate through 1000000 elements
  98.                 bool temp;
  99.                 Stopwatch watch = new Stopwatch();
  100.                 watch.Start();
  101.  
  102.                 for (int i = 0; i < 1000000; i++)
  103.                 {
  104.                     temp = bools[i];
  105.                 }
  106.  
  107.                 watch.Stop();
  108.                 report.AppendLine();
  109.                 report.Append("Time to iterate through 1000000 elements: ");
  110.                 report.Append(watch.ElapsedTicks);
  111.                 report.AppendLine(" ticks.");
  112.  
  113.                 // Perform NOT operator on 1000000 elements
  114.                 watch.Reset();
  115.                 watch.Start();
  116.  
  117.                 for (int i = 0; i < 1000000; i++)
  118.                 {
  119.                     bools[i] = !bools[i];
  120.                 }
  121.  
  122.                 watch.Stop();
  123.                 report.Append("Time to perform NOT operator on 1000000 elements: ");
  124.                 report.Append(watch.ElapsedTicks);
  125.                 report.AppendLine(" ticks.");
  126.             }
  127.  
  128.             // Show boolean array report
  129.             this.mTextBooleanArray.Text = report.ToString();
  130.  
  131.             // Bit Array
  132.             report = new StringBuilder();
  133.  
  134.             {
  135.                 // 1 element
  136.                 BitArray bitArray = new BitArray(1);
  137.                 report.Append("Memory usage of new BitArray(1): ");
  138.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  139.  
  140.                 // 2 element
  141.                 bitArray = new BitArray(2);
  142.                 report.Append("Memory usage of new BitArray(2): ");
  143.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  144.  
  145.                 // 3 element
  146.                 bitArray = new BitArray(3);
  147.                 report.Append("Memory usage of new BitArray(3): ");
  148.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  149.  
  150.                 // 32 element
  151.                 bitArray = new BitArray(32);
  152.                 report.Append("Memory usage of new BitArray(32): ");
  153.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  154.  
  155.                 // 33 element
  156.                 bitArray = new BitArray(33);
  157.                 report.Append("Memory usage of new BitArray(33): ");
  158.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  159.  
  160.                 // 64 element
  161.                 bitArray = new BitArray(64);
  162.                 report.Append("Memory usage of new BitArray(64): ");
  163.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  164.  
  165.                 // 65 element
  166.                 bitArray = new BitArray(65);
  167.                 report.Append("Memory usage of new BitArray(65): ");
  168.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  169.  
  170.                 // 100000 element
  171.                 bitArray = new BitArray(1000000);
  172.                 report.Append("Memory usage of new BitArray(100000): ");
  173.                 report.AppendLine(this.getObjectSizeInMemory(bitArray).ToString());
  174.  
  175.                 // Iterate through 1000000 elements
  176.                 bool temp;
  177.                 Stopwatch watch = new Stopwatch();
  178.                 watch.Start();
  179.  
  180.                 for (int i = 0; i < 1000000; i++)
  181.                 {
  182.                     temp = bitArray.Get(i);
  183.                 }
  184.  
  185.                 watch.Stop();
  186.                 report.AppendLine();
  187.                 report.Append("Time to iterate through 1000000 elements: ");
  188.                 report.Append(watch.ElapsedTicks);
  189.                 report.AppendLine(" ticks.");
  190.  
  191.                 // Perform NOT operator on 1000000 elements
  192.                 watch.Reset();
  193.                 watch.Start();
  194.  
  195.                 bitArray.Not();
  196.  
  197.                 watch.Stop();
  198.                 report.Append("Time to perform NOT operator on 1000000 elements: ");
  199.                 report.Append(watch.ElapsedTicks);
  200.                 report.AppendLine(" ticks.");
  201.             }
  202.  
  203.             // Show report
  204.             this.mTextBitArray.Text = report.ToString();
  205.  
  206.         }
  207.  
  208.         #endregion
  209.  
  210.     }
  211. }
  212.  



Quay về “[.NET] Mẹo vặt khác”

Đang trực tuyến

Đang xem chuyên mục này: Không có thành viên nào trực tuyến.1 khách