序言
心若有陽光，你便會看見這個世界有那么多美好值得期待和向往。
決定開一個算法專欄，希望能幫助大家很好的了解算法。主要深入解析每個算法，從概念到示例。
我們一起努力，成為更好的自己！
今天第3講，講一下排序算法的選擇排序（Selection Sort）
1 基礎介紹
查找算法是很常見的一類問題，主要是將一組數(shù)據(jù)按照某種規(guī)則進行排序。
以下是一些常見的查找算法及其應用場景：
- 布隆過濾器（Bloom Filter）：適用于判斷一個元素是否存在于一個大規(guī)模的數(shù)據(jù)集中，時間復雜度為O(1)，但有一定的誤判率。
- 二分查找（Binary Search）：適用于有序數(shù)組中查找元素，時間復雜度為O(log n)；
- 哈希表查找（Hash Table）：適用于快速查找和插入元素，時間復雜度為O(1)，但需要額外的存儲空間；
- 線性查找（Linear Search）：適用于無序數(shù)組中查找元素，時間復雜度為O(n)；
- 插值查找（Interpolation Search）：適用于有序數(shù)組中查找元素，時間復雜度為O(log log n)，但是對于分布不均勻的數(shù)據(jù)集效果不佳；
- 斐波那契查找（Fibonacci Search）：適用于有序數(shù)組中查找元素，時間復雜度為O(log n)，但需要額外的存儲空間；
- 樹表查找（Tree Search）：適用于快速查找和插入元素，時間復雜度為O(log n)，但需要額外的存儲空間；
- B樹查找（B-Tree）：適用于大規(guī)模數(shù)據(jù)存儲和查找，時間復雜度為O(log n)，但需要額外的存儲空間；
一、布隆過濾器介紹
1.1 原理介紹
布隆過濾器（Bloom Filter）是一種概率型數(shù)據(jù)結(jié)構(gòu)，用于快速判斷一個元素是否可能存在于一個集合中，同時具有高效的插入和查詢操作。它的原理基于位數(shù)組和哈希函數(shù)。
布隆過濾器的核心是一個位數(shù)組（bit array）或稱為位向量（bit vector），用于表示元素的存在狀態(tài)。初始時，所有位都被置為0。
布隆過濾器使用一系列不同的哈希函數(shù)（hash functions），這些哈希函數(shù)將輸入的元素映射為位數(shù)組中的不同位置。哈希函數(shù)的數(shù)量和定義根據(jù)具體的應用場景而定，通常會選擇一些獨立的哈希函數(shù)。
插入元素時，將元素經(jīng)過哈希函數(shù)的映射，得到一系列位數(shù)組中的位置，然后將這些位置的位設置為1，表示對應的元素存在于布隆過濾器中。
查詢元素時，將要查詢的元素經(jīng)過哈希函數(shù)的映射，得到一系列位數(shù)組中的位置，然后檢查這些位置的位是否都為1。
如果有任何一個位置的位為0，則可以確定該元素一定不存在于布隆過濾器中；如果所有位置的位都為1，則該元素可能存在于布隆過濾器中，但不是確定存在。
因此，布隆過濾器的查詢結(jié)果可能會有誤判，即將不存在的元素誤判為存在，但不會將存在的元素誤判為不存在。
優(yōu)點
由于布隆過濾器使用位數(shù)組和哈希函數(shù)，具有以下特點：
空間效率高：布隆過濾器只需使用位數(shù)組存儲元素的存在狀態(tài)，不需要存儲元素本身，因此占用的空間相對較小。
查詢效率高：布隆過濾器查詢的時間復雜度是常數(shù)級別的，與集合中元素的數(shù)量無關(guān)。
插入效率高：布隆過濾器插入的時間復雜度也是常數(shù)級別的。
缺點
然而，布隆過濾器也存在一些缺點：
誤判率（False Positive）：布隆過濾器的查詢結(jié)果可能會有誤判，將不存在的元素誤判為存在。
不支持元素的刪除：布隆過濾器的設計目標是快速判斷元素的存在性，不支持元素的刪除操作。
難以擴展：一旦布隆過濾器被創(chuàng)建，就很難動態(tài)地調(diào)整其大小。
總的來說，布隆過濾器適用于對查詢效率要求較高、可以容忍一定的誤判率以及元素不經(jīng)常變動的場景，如緩存、防止緩存擊穿、爬蟲的去重等應用。
圖解原理
以下是一個簡單的圖解布隆過濾器的示意圖：
圖表示一個初始狀態(tài)的布隆過濾器，位數(shù)組中的所有位都被初始化為0。
接下來，我們插入一個元素 "apple" 和 "orange"，假設我們選擇了三個哈希函數(shù)，并且得到的哈希值分別為 1、5 和 7。我們將對應的位設置為1，表示這些位置上的元素存在。
?現(xiàn)在，我們查詢元素 "apple" 和 "banana"。根據(jù)哈希函數(shù)得到的位位置分別為 1、4 和 7。我們檢查這些位置上的位，如果其中有任何一個位為0，則可以確定該元素不存在于布隆過濾器中；如果所有位置上的位都為1，則該元素可能存在于布隆過濾器中。
根據(jù)圖示，我們可以確定 "apple" 可能存在于布隆過濾器中，因為對應的位置上的位都為1。而 "banana" 可能不存在于布隆過濾器中，因為其中一個位置上的位為0。
這就是布隆過濾器的基本原理。
通過使用位數(shù)組和哈希函數(shù)，布隆過濾器可以快速判斷一個元素是否可能存在于一個集合中，具有高效的插入和查詢操作。
1.2 復雜度?
布隆過濾器的時間和空間復雜度如下：
時間復雜度：
- 插入操作的時間復雜度是O(k)，其中k是哈希函數(shù)的數(shù)量。
- 查詢操作的時間復雜度也是O(k)。
空間復雜度：
- 布隆過濾器的空間復雜度主要取決于位數(shù)組的大小和哈希函數(shù)的數(shù)量。通常情況下，位數(shù)組的大小取決于預期的元素數(shù)量和期望的誤判率。位數(shù)組的大小會隨著元素數(shù)量的增加而增加，以及期望的誤判率的降低而增加。
1.3使用場景
布隆過濾器適用于以下場景：
數(shù)據(jù)量大，但內(nèi)存有限：由于布隆過濾器只需要使用位數(shù)組來表示元素存在狀態(tài)，相對于其他數(shù)據(jù)結(jié)構(gòu)，它具有較小的內(nèi)存占用。這使得它在內(nèi)存有限的情況下能夠存儲大量的元素。
快速判斷元素是否存在：布隆過濾器可以在常數(shù)時間內(nèi)判斷一個元素是否可能存在于集合中，無需實際存儲元素本身，這使得它具有非常高的查詢效率。它可以用于加速對大型數(shù)據(jù)集或數(shù)據(jù)庫的查詢操作。
容忍一定的誤判率：布隆過濾器的查詢結(jié)果可能會有誤判，將不存在的元素誤判為存在（即假陽性）。因此，它適用于那些可以容忍一定誤判率的應用場景。例如，網(wǎng)頁爬蟲可以使用布隆過濾器來去重，避免重復爬取相同的網(wǎng)頁；緩存系統(tǒng)可以使用布隆過濾器來判斷某個數(shù)據(jù)是否已經(jīng)緩存，從而避免無謂的IO操作。
不需要刪除操作：布隆過濾器不支持元素的刪除操作。一旦元素被插入到布隆過濾器中，就無法刪除。因此，它適用于那些不需要頻繁刪除元素的場景。
需要注意的是，布隆過濾器在某些情況下可能會出現(xiàn)誤判，將不存在的元素誤判為存在。因此，在一些對準確性要求很高的場景下，布隆過濾器可能不適用。
二、代碼實現(xiàn)
2.1 Python 實現(xiàn)
代碼示例
import math
import mmh3
from bitarray import bitarray
class BloomFilter:
def __init__(self, num_items, false_positive_rate):
self.num_items = num_items
self.false_positive_rate = false_positive_rate
self.bit_array_size = self.calculate_bit_array_size(num_items, false_positive_rate)
self.num_hash_functions = self.calculate_num_hash_functions(self.bit_array_size, num_items)
self.bit_array = bitarray(self.bit_array_size)
self.bit_array.setall(0)
def calculate_bit_array_size(self, num_items, false_positive_rate):
numerator = num_items * math.log(false_positive_rate)
denominator = math.log(2) ** 2
return int(-(numerator / denominator))
def calculate_num_hash_functions(self, bit_array_size, num_items):
numerator = (bit_array_size / num_items) * math.log(2)
return int(numerator)
def add(self, item):
for seed in range(self.num_hash_functions):
index = mmh3.hash(item, seed) % self.bit_array_size
self.bit_array[index] = 1
def contains(self, item):
for seed in range(self.num_hash_functions):
index = mmh3.hash(item, seed) % self.bit_array_size
if self.bit_array[index] == 0:
return False
return True代碼講解
現(xiàn)在逐行解釋代碼的各個部分：
導入所需的模塊：代碼使用了?
math?模塊來進行數(shù)學計算，mmh3?模塊用于實現(xiàn)哈希函數(shù)，bitarray?模塊用于表示位數(shù)組。
BloomFilter?類的初始化方法：在初始化過程中，我們需要指定預期的元素數(shù)量?num_items?和期望的誤判率?false_positive_rate。根據(jù)這兩個參數(shù)，我們通過調(diào)用?calculate_bit_array_size?和?calculate_num_hash_functions?方法來計算位數(shù)組的大小和哈希函數(shù)的數(shù)量。然后，我們創(chuàng)建一個位數(shù)組?bit_array，并將所有位初始化為0。
calculate_bit_array_size?方法：根據(jù)預期元素數(shù)量和期望的誤判率，使用公式?-num_items * log(false_positive_rate) / (log(2) ** 2)?計算位數(shù)組的大小，并將結(jié)果轉(zhuǎn)換為整數(shù)。
calculate_num_hash_functions?方法：根據(jù)位數(shù)組的大小和預期元素數(shù)量，使用公式?(bit_array_size / num_items) * log(2)?計算哈希函數(shù)的數(shù)量，并將結(jié)果轉(zhuǎn)換為整數(shù)。
add?方法：用于向布隆過濾器中添加元素。對于每個元素，我們使用不同的種子值（從0到num_hash_functions-1）來計算哈希值，并將對應的位數(shù)組位置設置為1。
contains?方法：用于檢查元素是否存在于布隆過濾器中。對于每個元素，我們使用與添加操作相同的種子值來計算哈希值，并檢查對應的位數(shù)組位置。如果任何一個位置上的位為0，則可以確定元素不存在于布隆過濾器中；否則，我們認為元素可能存在于布隆過濾器中。這就是一個簡單的布隆過濾器的 Python 實現(xiàn)。你可以根據(jù)自己的需求進行調(diào)整和擴展。請注意，這個實現(xiàn)中并沒有考慮動態(tài)調(diào)整布隆過濾器大小或刪除元素的功能。
測試代碼
import random
def generate_random_string(length):
letters = "abcdefghijklmnopqrstuvwxyz"
return ''.join(random.choice(letters) for _ in range(length))
num_items = 1000
false_positive_rate = 0.01
bloom_filter = BloomFilter(num_items, false_positive_rate)
# 添加元素
for _ in range(num_items):
item = generate_random_string(10)
bloom_filter.add(item)
# 檢查元素是否存在
positive_count = 0
for _ in range(1000):
item = generate_random_string(10)
if bloom_filter.contains(item):
positive_count += 1
false_positive_rate_actual = positive_count / 1000
print("實際誤判率:", false_positive_rate_actual)我們首先定義了預期的元素數(shù)量?
num_items?和期望的誤判率?false_positive_rate。然后，我們創(chuàng)建了一個?BloomFilter?實例并使用?add?方法向布隆過濾器中添加了隨機生成的元素。接下來，我們使用?
contains?方法進行隨機測試。我們隨機生成了1000個字符串，并檢查它們是否存在于布隆過濾器中。我們計算了實際的誤判率，即在這1000個隨機字符串中錯誤判斷為存在的比例，并將其打印出來。測試結(jié)果會輸出一個實際的誤判率，應該接近于設定的期望誤判率。
請注意，由于布隆過濾器的特性，即使在沒有添加的情況下，也可能會有一定的誤判率。因此，實際誤判率可能略高于設定的期望誤判率。
運行結(jié)果
實際誤判率: 0.0092.2Java實現(xiàn)
代碼示例
import java.util.BitSet;
import java.util.Random;
public class BloomFilter {
private BitSet bitSet;
private int size;
private int numHashFunctions;
private Random random;
public BloomFilter(int expectedNumItems, double falsePositiveRate) {
size = calculateBitSetSize(expectedNumItems, falsePositiveRate);
numHashFunctions = calculateNumHashFunctions(size, expectedNumItems);
bitSet = new BitSet(size);
random = new Random();
}
public void add(String item) {
for (int i = 0; i < numHashFunctions; i++) {
int hash = hash(item, i);
bitSet.set(hash, true);
}
}
public boolean contains(String item) {
for (int i = 0; i < numHashFunctions; i++) {
int hash = hash(item, i);
if (!bitSet.get(hash)) {
return false;
}
}
return true;
}
private int hash(String item, int seed) {
random.setSeed(seed);
return Math.abs(random.nextInt()) % size;
}
private int calculateBitSetSize(int expectedNumItems, double falsePositiveRate) {
int size = (int) Math.ceil((expectedNumItems * Math.log(falsePositiveRate)) / Math.log(1.0 / (Math.pow(2.0, Math.log(2.0)))));
return size;
}
private int calculateNumHashFunctions(int size, int expectedNumItems) {
int numHashes = (int) Math.ceil((size / expectedNumItems) * Math.log(2.0));
return numHashes;
}
}代碼講解
解釋一下以上代碼的各個部分：
BloomFilter?類的構(gòu)造函數(shù)：在構(gòu)造函數(shù)中，我們傳入預期的元素數(shù)量?expectedNumItems?和期望的誤判率?falsePositiveRate。然后，我們使用?calculateBitSetSize?和?calculateNumHashFunctions?方法計算位集合的大小和哈希函數(shù)的數(shù)量。接著，我們創(chuàng)建一個位集合?bitSet，并初始化一個?Random?對象。
add?方法：用于向布隆過濾器中添加元素。對于每個元素，我們使用不同的種子值（從0到numHashFunctions-1）來計算哈希值，并將對應的位設置為1。
contains?方法：用于檢查元素是否存在于布隆過濾器中。對于每個元素，我們使用與添加操作相同的種子值來計算哈希值，并檢查對應的位是否為1。如果任何一個位為0，則可以確定元素不存在于布隆過濾器中；否則，我們認為元素可能存在于布隆過濾器中。
hash?方法：用于計算哈希值。我們使用種子值作為隨機數(shù)種子，并使用?Random?對象生成一個哈希值。然后，我們對哈希值取絕對值，并對位集合大小取模，以確保哈希值在位集合范圍內(nèi)。
calculateBitSetSize?方法：根據(jù)預期元素數(shù)量和期望的誤判率，使用公式?(expectedNumItems * log(falsePositiveRate)) / log(1.0 / (Math.pow(2.0, Math.log(2.0))))?計算位集合的大小，并返回結(jié)果。
calculateNumHashFunctions?方法：根據(jù)位集合的大小和預期元素數(shù)量，使用公式?(size / expectedNumItems) * log(2.0)?計算哈希函數(shù)的數(shù)量，并返回結(jié)果。這是一個簡單的布隆過濾器的 Java 實現(xiàn)。你可以根據(jù)自己的需求進行調(diào)整和擴展。注意，這個實現(xiàn)中沒有考慮動態(tài)調(diào)整布隆過濾器大小或刪除元素的功能。
測試代碼
public class Main {
public static void main(String[] args) {
int expectedNumItems = 1000;
double falsePositiveRate = 0.01;
BloomFilter bloomFilter = new BloomFilter(expectedNumItems, falsePositiveRate);
// 添加元素
bloomFilter.add("apple");
bloomFilter.add("banana");
bloomFilter.add("orange");
// 檢查元素是否存在
System.out.println(bloomFilter.contains("apple")); // 輸出: true
System.out.println(bloomFilter.contains("banana")); // 輸出: true
System.out.println(bloomFilter.contains("orange")); // 輸出: true
System.out.println(bloomFilter.contains("grape")); // 輸出: false
System.out.println(bloomFilter.contains("melon")); // 輸出: false
}
}運行結(jié)果
true
true
true
false
false三、圖書推薦
圖書名稱：
- 《漫畫算法：小灰的算法之旅》
圖書介紹
本書是《漫畫算法：小灰的算法之旅》的續(xù)作，通過主人公小灰的心路歷程，用漫畫的形式講述了多個數(shù)據(jù)結(jié)構(gòu)、算法及復雜多變的算法面試題目。
第1章介紹了幾種典型的排序算法，包括選擇排序、插入排序、希爾排序、歸并排序、基數(shù)排序。
第2章介紹了“樹”結(jié)構(gòu)的高級應用，包括二叉查找樹、AVL樹、紅黑樹、B樹和B+樹。
第3章介紹了“圖”結(jié)構(gòu)的概念，以及深度優(yōu)先遍歷、廣度優(yōu)先遍歷、單源最短路徑、多源最短路徑算法。
第4章介紹了“查找”相關(guān)的算法和數(shù)據(jù)結(jié)構(gòu)，包括二分查找算法、RK算法、KMP算法，以及“跳表”這種用于高效查找的數(shù)據(jù)結(jié)構(gòu)。
第5章介紹了多種職場上流行的算法面試題目及詳細的解題思路，例如螺旋遍歷二維數(shù)組、尋找數(shù)組中第k大元素、求股票交易的更大收益等。
等不及的小伙伴，可以點擊下方鏈接，先睹為快：漫畫算法2
?參與方式?
圖書數(shù)量：本次送出 4?本 ? ?。?！??????
活動時間：截止到 2023-08-11?12:00:00抽獎方式：
- 評論區(qū)隨機抽取小伙伴！
留言內(nèi)容，以下方式都可以：
- 根據(jù)文章內(nèi)容進行高質(zhì)量評論
參與方式：關(guān)注博主、點贊、收藏，評論區(qū)留言?
中獎名單?
???? 獲獎名單????
?中獎名單：請關(guān)注博主動態(tài)文章來源：http://www.zghlxwxcb.cn/news/detail-631507.html
名單公布時間：2023-08-11?下午文章來源地址http://www.zghlxwxcb.cn/news/detail-631507.html
到了這里，關(guān)于【算法系列 | 7】深入解析查找算法之—布隆過濾器的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
