Chào mừng các bạn
»»-((¯`·(¯`vŽ¯)--»*** MasterSpy *** «--(¯`vŽ¯)·`¯))-«« - Thuật toán - Cấu trúc dữ liệu
ღLONELYღ
  Home
  => Cách tạo một trang web cho riêng mình !
  => Một số địa chỉ trang web hay dành cho bạn, ....cho tôi !
  => 5 bước cơ bản để diệt tận gốc Spyware
  => 10 điều “lính mới” nên biết
  => 10 bước để lập kế hoạch cho nghề nghiệp tương lai của bạn
  => 15 LỜI KHUYÊN HỌC TIẾNG ANH
  => 21 kho lưu dữ liệu miễn phí trên Internet
  => PHƯƠNG PHÁP XỬ LÝ LOGIC VỊ TỪ
  => 50 cuốn sách văn học cần đọc
  => Những bài học từ Adam Khoo
  => Dùng Admodify.net để quản trị và phục hồi Exchange 2003
  => Cuộc đời của Albert Einstein
  => Cảnh giác với hacker và keylogger!
  => Phần mềm miễn phí giúp bảo vệ computer khi online
  => Học thi - cần ăn uống hợp lý
  => Hacker “oánh” mỗi PC chỉ mất 39 giây
  => Xác định nguyên nhân máy tính tự khởi động !
  => Diệt virus Autorun
  => Bấm dây mạng !
  => Bảo vệ mắt khi sử dụng máy tính !
  => Blog ra đời như thế nào?
  => Bài tập Pascal kiểu bản ghi !
  => Hướng dẫn ôn tập lập trình Pascal căn bản !
  => Cách Diệt Virus
  => Cách gỡ bỏ thủ công Symantec Antivirus an toàn (Phần I)
  => Tổng hợp các lệnh ngoài DOS
  => Cài HIREN BOOTCD vào ổ cứng để cứu hộ
  => Cài windows media player 11 ( không cần active window)
  => Cấu hình mạng ADSL cho người dùng tại nhà
  => Thiết Lập Sevice trong windows XP (giúp máy chạy nhanh hơn)
  => Giới Thiệu Centos
  => Chẩn đoán lỗi của màn hình !
  => Chọn DNS truy cập mạng !
  => Kinh nghiệm phòng chống virus, spyware
  => Trắc nghiệm nghiệp vụ kế toán bằng tiếng Anh !
  => Hướng dẫn chụp hình bằng webcam
  => Tổng Hợp Code Dùng Trong Việc Tạo BLOG
  => Công dụng của các dịch vụ trong Windows
  => Sử dụng Popcap game mãi mãi !
  => Cử nhân CNTT không làm CNTT
  => Tìm hiểu DNS.Các bước thiết lập khi mới đăng ký tên miền
  => Làm DNS server online
  => Nội dung định nghĩa về vật chất của Lê Nin
  => Đọc và ... suy nghĩ !
  => Đôi điều về bảo mật hệ thống mạng trong công ty!
  => Khắc phục lỗi 999 Error của Yahoo
  => Chuyển dữ liệu của ổ C từ FAT32 thành NTFS
  => Gỡ password CMOS bằng cách nào?
  => Phần I: Cơ bản về lỗi "màn hình xanh" trong Windows
  => Tổng quan về Group Policy - từ đơn giản đến phức tạp !
  => Gửi nhiều file qua Yahoo Mail
  => Từ XP cài Hacao Linux 2.16 Pro (file ISO) vào đĩa cứng (LiveCD)
  => Chịu thuế và không chịu thuế
  => Hội thảo qua mạng với NetMeeting
  => HOST Free
  => Hướng dẫn download trên megaupload
  => KGB nén File từ 450MB còn 1.43MB rất tiện chia sẻ file trên mạng
  => Khắc phục rớt mạng liên tục
  => Kiến trúc Oracle
  => Thành công trên giảng đường đại học
  => Kỹ thuật Photoshop cơ bản !
  => Kinh nghiệm học tiếng ANH
  => KInh nghiệm học TOÁN CAO CẤP
  => Đôi điều về quá trình làm luận văn (Phần 2)
  => Làm theme cho Blog 360
  => Chia sẻ những điều học được từ cách làm việc theo nhóm
  => Vạch kế hoạch cho tương lai
  => Các Lệnh Cơ Bản trong LINUX
  => Lịch sử các nước ĐẾ QUỐC
  => Lịch sử Việt Nam
  => Links những trang web hay
  => Tạo mail server online bằng IP Động
  => Tự làm giao diện cho Yahoo Mash!
  => Mấy điểm cần tránh
  => Hỏi về IPHONE
  => Máy tính không khởi động từ ổ đĩa cứng!...?
  => MIÊU TẢ SẢN PHẨM MÁY IN hp1320
  => Phá Deep Freeze - Cướp lấy password!!!
  => Những "tuyệt chiêu" chọn mua laptop cũ
  => NHỮNG NGUYÊN TẮC CƠ BẢN CỦA BÁO CHÍ
  => Tìm hiểu nhân của hệ điều hành Linux
  => Sửa lỗi NTLDR is missing
  => Ổ cứng chóng hỏng vì... điều hòa nhiệt độ
  => Những phím tắt thông dụng trong Photoshop 7.0
  => Phím tắt trong WORDS
  => Bí mật của PHỤ NỮ
  => Hướng dẫn post hình lên mạng, và 1 số website để upload hình
  => Chương trình quản lý số điện thoại !
  => Quản lý các mạng Windows dùng script - Phần 2: Hoàn chỉnh script -
  => Cấu hình cho máy in N2500
  => Xóa nick của mình trong Friend List của người khác
  => Rollback Rx Pro:
  => User và pass của một số router
  => Giải pháp sao lưu trực tuyến miễn phí (Phần cuối)
  => Vài điều về Scanner
  => Chọn hệ điều hành của bạn
  => Làm server online tận dụng đường truyền ADSL
  => Thuật toán - Cấu trúc dữ liệu
  => So sánh Oracle và SQL Server ?
  => Cấu hình các công nghệ bảo vệ mạng Windows XP SP2 trên một máy tính
  => Tổng quan về tiết kiệm điện khi sử dụng máy tính !
  => Phần IV: Xử lý sự cố phần cứng
  => CÁC VẤN ĐỀ VỀ SỨC KHỎE PHỤ NỮ
  => Sử dụng phím tắt với Internet Explorer 7
  => SỰ PHÁT TRIỂN CỦA SINH VẬT
  => Nguồn gốc máng cỏ giáng sinh
  => Sưu tầm câu đố !
  => SVCHOST
  => Phòng chống virus cho mạng máy tính doanh nghiệp: kinh nghiệm thực tế
  => Các lệnh căn bản trong ngôn ngữ html
  => Sức mạnh của card đồ họa !
  => Cách tải Nhạc nét
  => Triết học và tâm sự của các nhà giáo
  => Phát triển chiều cao
  => Tăng tốc toàn bộ máy tính bằng tay
  => Tăng tốc WinXP
  => Chống mất cắp cho laptop với Laptop Alarm
  => Tạo file ghost!
  => Tạo một CSS layout từ một bản thiết kế (Phần 1 đến 8)
  => Tạo nick ảo trong Yahoo Messenger
  => Tết Đoan Ngọ bắt đầu từ giữa trưa
  => Thói quen tốt: Nghĩ vậy mà không phải vậy
  => Thomas Edison & những phát minh vĩ đại -
  => Windows Vista: các thủ thuật nhỏ khi sử dụng
  => Thủ thuật Blog 360
  => Thủ thuật Internet Explorer 7
  => Thủ thuật tăng tốc cho Windows
  => Thủ thuật Visual basic
  => Thủ thuật Yahoo! Messenger
  => Yahoo Messenger
  => Khám phá mạng xã hội Yahoo! Mash
  => Mẹo tìm kiếm
  => Tìm kiếm trong Excel
  => Tóc hợp khuôn mặt
  => Tokyo - Một chuyến đi
  => Mười quy luật then chốt về Bảo mật
  => Tổng hợp tất cả các kỹ thuật vượt tường lửa
  => Trang trí USB
  => Thuật toán - Cấu trúc dữ liệu CRC (Cyclic Redundancy Check)
  => Các Tuyệt kỹ khiến phái nữ phải ngã lòng
  => CÁCH UP ẢNH QUA HOST TẠI DIỄN ĐÀN
  => Quản lý danh sách bạn chat trong Yahoo! Messenger
  => Error Doctor 2007
  => TuneUp Utilities® 2007
  => Bộ gõ tiếng Việt: Unikey
  => Hướng dẫn viết bài
  => Tường lửa mới trong Windows Vista và Windows Server Longhorn
  => Web 2.0 không chỉ là công nghệ
  => Các website hữu ích về du học bậc sau đại học tại Hoa Kỳ
  => Wi-fi và an toàn thông tin
  => Thuật toán - Cấu trúc dữ liệu So khớp chuỗi với các ký tự wildcard
  => Xóa địa chỉ và homepage
  => USB không cho ghi
  => Yêu cầu của Quản trị mạng
  => Cách Add Feed trong Blog 360
  => Cách tạo theme trong suốt
  => Đề cương KT-Chính Trị
  Contact
  Guestbook
  Story
  Kiếm tiền thật dễ dàng

Biển xanh ... cát trắng

 

Thuật toán - Cấu trúc dữ liệu
Skip List - đối thủ của cây cân bằng
Khi đề cập đến bài toán tìm kiếm chắc bạn đã ít nhiều biết đến cấu trúc cây cân bằng (balanced tree). Cấu trúc này cho phép thực hiện tìm kiếm với độ phức tạp trung bình là O(log2n). Tuy nhiên, để tránh tình trạng cây suy biến, ta phải cân bằng cây mỗi khi chèn một nút mới. Nói chung, cân bằng cây là một thao tác tương đối phức tạp do phải hoán chuyển nhiều nút và do đó cũng ảnh hưởng đến hiệu suất. Skip List giải quyết vấn đề này khá hiệu quả mà vẫn không ảnh hưởng đáng kể đến tốc độ của phép tìm kiếm.
SkipList được giáo sư William Pugh thuộc trường đại học MaryLand giới thiệu vào khoảng tháng 8 năm 1989 trong một bài báo tham dự hội nghị về thuật toán và cấu trúc dữ liệu tại Ottawa Canada.
Skip List là một danh sách liên kết đơn mở rộng
Skip List chỉ là một mở rộng của danh sách liên kết đơn mà chúng ta đã rất quen thuộc. Hình bên dưới minh họa một danh sách liên kết đơn được sắp xếp tăng dần theo khóa.
Để tìm vị trí của một phần tử x trong danh sách liên kết đơn (đã được sắp xếp), ta phải duyệt từ đầu danh sách cho đến khi gặp nút có khóa cần tìm hoặc gặp nút có khóa lớn hơn khóa cần tìm. Trường hợp xấu nhất là phải duyệt qua tất cả nút trong danh sách (trong trường hợp khóa cần tìm lớn hơn tất cả các khóa trong danh sách).
Ý tưởng sơ khởi của Skip List là: để tăng hiệu quả của phép tìm kiếm, ta sẽ thêm vào các con trỏ tại một vài nút cho phép trỏ đến những nút nằm ở “xa” hơn. Chẳng hạn như ở hình dưới đây, các nút 5, 9, 16, 25 sẽ có các con trỏ phụ trỏ đến nút kế tiếp thứ hai (hay nói cách khác là “nhảy” – skip – hai nút một lần)
Với cấu trúc kiểu này, bạn có thể dễ dàng cảm nhận được là trung bình ta sẽ tiết kiệm được một nửa số bước tìm kiếm so với danh sách liên kết đơn bình thường. Nhìn vào hình ảnh, bạn sẽ thấy danh sách của ta bây giờ giống như có hai tầng (level). Tầng 1 là danh sách bình thường. Tầng 2 ở trên cũng là một danh sách liên kết đơn gồm có 5, 9, 16, 25 (nhảy 2 nút).
Dĩ nhiên là chúng ta có thể thêm vào một tầng nữa gồm các phần tử 9,25 (nhảy 4 nút) như hình dưới đây:
Để tìm kiếm một phần tử, ta xuất phát từ tầng cao nhất, duyệt qua các nút ở tầng hiện tại cho đến khi nút kế tiếp có khóa lớn hơn nút cần tìm. Lúc đó ta sẽ giảm đi một tầng. Nếu tầng hiện tại là 1 mà nút kế tiếp có giá trị lớn hơn nút cần tìm thì có nghĩa là nút cần tìm không có trong danh sách.
Hình trên minh họa cho quá trình tìm kiếm giá trị khóa 18. Ta khởi đầu với tầng 3, ta lần theo các nút ở tầng 3 cho đến khi gặp nút 9. Ta thấy nút kế tiếp là 25 lớn hơn 18 nên ta sẽ “xuống” tầng 2. Theo con trỏ ở tầng 2, ta sẽ đến nút 16. Nút kế tiếp là 25 lớn hơn 18 nên ta sẽ “xuống” tầng 1. Theo con trỏ ở tầng 1 ta gặp nút 18 chính là khóa cần tìm.
Một cách cảm tính là nếu như mỗi tầng ta giảm đi một nửa số phần tử thì cấu trúc này sẽ cho thời gian tìm kiếm y hệt như cây nhị phân tìm kiếm. Tuy nhiên, cấu trúc mở rộng này cũng gặp cùng một vấn đề như cây nhị phân là khi chèn một phần tử mới vào, ta lại phải mất công biến đổi để đảm bảo được “cấu trúc” của nó.
Skip List là cấu trúc dữ liệu có xác suất
Điểm chính giúp tốc độ tìm kiếm trung bình được tăng lên là do chúng ta giảm số nút ở mỗi tầng (để thực hiện phép tìm kiếm bằng cách nhảy). Tính chất “cách đều” chỉ đảm bảo được hiệu quả tìm kiếm lúc nào cũng như nhau.
Như vậy ta chỉ cần đảm bảo một tính chất là: số phần tử ở tầng trên phải xấp xỉ bằng một nửa (không cần chính xác) của tầng dưới. Nếu có 3 tầng, 100% phần tử ở tầng 1, khoảng 50% phần tử ở tầng 2, khoảng 25% phần tử ở tầng 3 và cứ thế. (Số nút ở hai tầng cao nhất sẽ xấp xỉ bằng nhau)
Sự đơn giản hóa này sẽ khiến việc chèn một phần tử vào danh sách trở nên rất đơn giản. Quan trọng nhất là chúng ta sẽ không cần phải sắp xếp lại danh sách nữa.
Tuy nhiên, để tiện cài đặt, ta sẽ dùng thuật ngữ khác đi một tí. Thay vì nhìn danh sách theo tầng, ta sẽ dùng khái niệm cấp của nút. Nếu một nút chỉ có một con trỏ, nó sẽ có cấp 1, nếu có hai con trỏ, nó có cấp 2 và cứ thế. Một cách tổng quát, sẽ có khoảng 50% số nút có cấp 1, 25% số nút có cấp 2, 12.5% số nút có cấp 3 và cứ thế.
Để chèn một nút vào danh sách, ta phát sinh ngẫu nhiên cấp của nó theo nguyên tắc là 50% khả năng có cấp 1, 25% có cấp 2, 12.5% có cấp 3 và cứ thế. Sau đó, tìm vị trí cần chèn (theo thuật toán tìm kiếm) rồi chỉ việc điều chỉnh lại các con trỏ là xong.
Phát sinh ngẫu nhiên cấp của một nút
int GenerateLevel(int max_level)
{
  level=1;
  
while ((rand() < 0.5) && (level < max_level))
    level++;
  
return level;
}
Để hiểu hoạt động của hàm này, ta chú ý đến biểu thức
rand() < 0.5
Hàm rand() phát sinh một số thực không âm ngẫu nhiên nhỏ hơn một. Nghĩa là 0≤rand() <1. Xác suất để biểu thức rand()<0.5 đúng hoặc sai đều là 50%.
Dễ dàng thấy được là xác suất để (level = 1 là đúng) là 50%.
Để có level = 2, biểu thức rand()<0.5 phải sai với level = 1 và đúng với level = 2. Xác suất để có level = 1 là sai là 50% và xác suất để có level = 2 là đúng cũng là 50%. Vậy xác suất để có level = 2 là đúng là : 50%×50% = 25%.
Tương tự, để có level = 3, biểu thức rand()<0.5 phải sai với level = 1 và sai với level = 2 và đúng với level = 3. Xác suất để có điều này là: 50%×50%×50% = 12.5%.
Hàm này phụ thuộc vào giá trị max_level (số tầng tối đa của SkipList). Một cách cảm tính, từ cây nhị phân cân bằng, ta thấy rằng max_level nên là log2(n) với n là tổng số nút của danh sách. Để tránh bị phụ thuộc vào số lượng nút, ta có thể dùng hằng số log2(N) trong đó N là chặn trên của n. Trên thực tế max_level = 32 (cho một list có tối đa khoảng 2^32 ~ 4 tỷ nút) là đủ dùng cho hầu hết các trường hợp.
Tìm kiếm
SkipListNode* Search(SkipList *list, int searchKey)
{
  x = list->head;
  
// điều kiện dừng: (x->forward[i]->key >= searchKey) và (level=1)
  
for (i=list->level;i>1;i--)
     
while (x->forward[i]->key < searchKey)
        x = x->forward[i];
  x = x->forward[1];
  
if (x->key == searchKey)
     
return x;
  
else
     
return 0;
}
Chèn nút vào danh sách
void Insert(SkipList *list, int searchKey, int newValue)
{
  SkipListNode* update[max_level+1];
  //tìm vị trí nút cần chèn và ghi nhận các nút
  //trỏ đến vị trí này
  x = list->head;
  for (i=list->level;i>1;i--)
  {
     while (x->forward[i]->key < searchKey)
        x = x->forward[i];
     update[i] = x; //ghi nhận nút trỏ đến vị trí chèn
  }
  x = x->forward[1];
  
if (x->key == searchKey)
     x->value = newValue;
//cập nhật giá trị nút nếu khóa đã tồn tại
  
else
  {
     newLevel = GenerateLevel(max_level);
     
if (newLevel > list->level)
     {
        
for (i=list->level + 1;i<=newLevel;i++)
           update[i] = list->head;
           list->level = newLevel;
     }
     // tạo một nút mới với cấp = <newLevel>, khóa = <searchKey>
     x = makeNode(newLevel,searchKey,value);
     
// cập nhật các nút trỏ đến nút mới và các con trỏ forward của nút mới
   
  for (i=1;i<=newLevel;i++)
     {
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
     }
  }
}
Khởi tạo SkipList
SkipList rỗng bao gồm hai nút đặc biệt. Một nút head và nút tail (hay NIL). Cấp của SkipList lúc khởi tạo là 1. Khóa của tail phải luôn luôn lớn hơn khóa của tất cả các nút.
Xóa một nút
void Delete(SkipList * list, int searchKey)
{
  SkipListNode* update[max_level+1];
  
//tìm nút cần xóa và ghi nhận các nút
  //trỏ đến nút này
  SkipListNode *x = list->head;
  
for (i=list->level;i>1;i--)
  {
     
while (x->forward[i]->key < searchKey)
       x = x->forward[i];
     update[i] = x; //ghi nhận các nút trỏ đến nút cần xóa
  }
  x = x->forward[1];
  
if (x->key == searchKey)
  {
    
for (i=1;i<=list->level;i++)
    {
      
if (update[i]->forward[i] != x) break;
      update[i]->forward[i] = x->forward[i];
    }
    free(x);
    while ( (list->level > 1) && (list->head->forward[list->level] == 0) )
       list->level--;
  }
}
Một số bàn luận
 Thay vì giới hạn ở hằng số 50% cho biết số lượng nút cấp i+1 bằng khoảng 50% số lượng nút cấp i. Pugh đề nghị kết hợp một giá trị p < 1 vào SkipList để quy định tỷ lệ nút giữa các tầng. Nếu p=0.5, tầng i+1 sẽ có số nút bằng khoảng ½ so với tầng i. Nếu p=0.25, tầng i+1 sẽ có số nút bằng khoảng ¼ so với tầng i (nếu p=1/4, số nút cấp 1 sẽ là 75%, số nút cấp 2 là 25%×75% = 18.75%, số nút cấp 3 sẽ là: 25%×25%×75% = 4.6875%).
Rõ ràng là vì các nút không cách đều nhau nên hiệu suất tìm kiếm sẽ không là hằng số. Nếu quá xui, chẳng hạn như trường hợp tất cả nút đều có cùng cấp, thì hiệu suất tìm kiếm sẽ bị giảm đáng kể. Tuy nhiên, bằng toán học, giáo sư Pugh đã tính ra được ràng khả năng xảy ra những trường hợp xấu như vậy là rất thấp. Chẳng hạn với một SkipList có 4096 nút, p=0.5, khả năng để một thời gian tìm kiếm chậm hơn 3 lần (so với thời gian tìm kiếm trung bình) là một phần 200 triệu !
Một điểm cần lưu ý nữa là khi số lượng nút càng lớn (điều thường xảy ra trong thực tế), hiệu quả trung bình của SkipList càng sát với hiệu suất của cây cân bằng. Pugh cũng đề nghị nên sử dụng p=0.25 trong đa số trường hợp. Nếu như chúng ta đặt nặng tính ổn định của SkipList thì Pugh đề nghị nên dùng p=0.5. Điểm thú vị là với p=0.25, một nút trung bình chỉ có 1.33 con trỏ (trong khi đó cây cân bằng có 2 con trỏ). Điều này làm cho SkipList sử dụng ít bộ nhớ hơn cây cân bằng.
Tài liệu tham khảo
 1) William Pugh, A Skip List Cook Book, 6/1990, Department of Computer Science, University of MaryLand, College Park.
 

 
Today, there have been 13 visitors (43 hits) on this page!
Đến với thành phố biển Vũng Tàu This website was created for free with Own-Free-Website.com. Would you also like to have your own website?
Sign up for free