В информатике структуры данных необходимы для эффективного хранения и организации данных. Хотя базовые структуры данных, такие как массивы, связанные списки и деревья, широко используются, существует несколько дополнительных структур данных, которые могут обеспечить специализированную функциональность и повысить производительность для конкретных случаев использования. В этой статье мы рассмотрим различные дополнительные структуры данных, а также приведем примеры кода, демонстрирующие их реализацию и использование.

1. Фильтр Блума.
   Фильтр Блума — это вероятностная структура данных, используемая для проверки того, является ли элемент членом набора. Он обеспечивает эффективный способ определения членства, но с небольшой вероятностью ложных срабатываний. Вот простая реализация на Python:

from bitarray import bitarray
import mmh3
class BloomFilter:
    def __init__(self, size, num_hash_functions):
        self.size = size
        self.num_hash_functions = num_hash_functions
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
    def add(self, item):
        for seed in range(self.num_hash_functions):
            index = mmh3.hash(item, seed) % self.size
            self.bit_array[index] = 1
    def contains(self, item):
        for seed in range(self.num_hash_functions):
            index = mmh3.hash(item, seed) % self.size
            if self.bit_array[index] == 0:
                return False
        return True

1. Список пропуска.
   Список пропуска – это структура данных, позволяющая выполнять операции быстрого поиска, вставки и удаления. Это альтернатива сбалансированным деревьям поиска с сопоставимыми характеристиками производительности. Вот простая реализация на C++:

#include <iostream>
#include <cstdlib>
struct Node {
    int value;
    Node forward;
};
class SkipList {
    Node* header;
    int max_level;
    float probability;
public:
    SkipList(int max_level, float probability) : max_level(max_level), probability(probability) {
        header = new Node();
        header->forward = new Node*[max_level];
        std::memset(header->forward, 0, sizeof(Node*) * max_level);
    }
    void insert(int value) {
        Node* update[max_level];
        Node* current = header;
        for (int i = max_level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        current = current->forward[0];
        if (current == nullptr || current->value != value) {
            int level = random_level();
            if (level > max_level) {
                for (int i = max_level; i < level; i++) {
                    update[i] = header;
                }
                max_level = level;
            }
            current = new Node();
            current->value = value;
            current->forward = new Node*[level];
            std::memset(current->forward, 0, sizeof(Node*) * level);
            for (int i = 0; i < level; i++) {
                current->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = current;
            }
        }
    }
    bool search(int value) {
        Node* current = header;
        for (int i = max_level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
        }
        current = current->forward[0];
        return current && current->value == value;
    }
    void remove(int value) {
        Node* update[max_level];
        Node* current = header;
        for (int i = max_level - 1; i >= 0; i--) {
            while (current->forward[i] && current->forward[i]->value < value) {
                current = current->forward[i];
            }
            update[i] = current;
        }
        current = current->forward[0];
        if (current && current->value == value) {
            for (int i = 0; i < max_level; i++) {
                if (update[i]->forward[i] != current) {
                    break;
                }
                update[i]->forward[i] = current->forward[i];
            }
            delete[] current->forward;
            delete current;
            while (max_level > 1 && header->forward[max_level - 1] == nullptr) {
                max_level--;
            }
        }
    }
private:
    int random_level() {
        int level = 1;
        while (rand() < probability * RAND_MAX && level < max_level) {
            level++;
    }
        return level;
    }
};
int main() {
    SkipList skipList(4, 0.5);
    skipList.insert(10);
    skipList.insert(5);
    skipList.insert(15);
    skipList.insert(20);
    std::cout << "Search 10: " << (skipList.search(10) ? "Found" : "Not Found") << std::endl;
    std::cout << "Search 5: " << (skipList.search(5) ? "Found" : "Not Found") << std::endl;
    std::cout << "Search 15: " << (skipList.search(15) ? "Found" : "Not Found") << std::endl;
    std::cout << "Search 20: " << (skipList.search(20) ? "Found" : "Not Found") << std::endl;
    skipList.remove(15);
    std::cout << "Search 15 after removal: " << (skipList.search(15) ? "Found" : "Not Found") << std::endl;
    return 0;
}

В этой статье мы рассмотрели две дополнительные структуры данных: фильтр Блума и список пропуска. Фильтр Блума обеспечивает эффективный способ проверки членства в наборе с небольшой вероятностью ложных срабатываний, а список пропуска обеспечивает быстрый поиск, вставку и удаление. Понимая и используя эти дополнительные структуры данных, разработчики могут повысить производительность и эффективность своих программ в различных сценариях.

Включив эти расширенные структуры данных в свой набор инструментов программирования, вы сможете более эффективно решать сложные проблемы и оптимизировать производительность своих приложений.