2024-08-12

BM25是一种常用的信息检索模型,用于评估查询中每个文档的相关性。以下是一个简单的Python实现:




import math
 
def bm25(query, document, k1=1.2, b=0.75):
    """
    Calculate BM25 score for a given query and document.
    :param query: A list of query terms.
    :param document: A string representing the document text.
    :param k1: A constant for term frequency normalization.
    :param b: A constant for field-length normalization.
    :return: BM25 score as a float.
    """
    score = 0.0
    dl = len(document)
    avgdl = math.fsum(len(word) for word in document.split()) / len(document.split())
    for term in query:
        fi = document.count(term)
        qfi = query.count(term)
        k = k1 * (1 - b + b * (dl / avgdl))
        score += (fi * (k1 + k * fi) / (k1 + k * (1 - b + b * (fi / avgdl)))) * (qfi ** 2)
    return score
 
# Example usage:
query = ["python", "search", "algorithm"]
document = "Python is a high-level programming language used for general-purpose programming. It is an interpreted language with dynamic semantics. Its design philosophy emphasizes code readability with its notable use of significant whitespace. The language provides constructs that enable clear programming on both small and large scales."
 
score = bm25(query, document)
print(f"BM25 Score: {score}")

这段代码定义了一个bm25函数,它接受查询词和文档作为输入,并返回BM25得分。在实例化时,我们使用了一个查询词列表和一个文档字符串。然后,我们打印出计算出的BM25得分。

2024-08-12



import numpy as np
 
class RRT:
    def __init__(self, x_bounds, y_bounds, obstacle_list):
        self.x_bounds = x_bounds
        self.y_bounds = y_bounds
        self.obstacle_list = obstacle_list
        # 其他初始化参数
 
    def nearest_neighbor(self, tree, point):
        distances = [self.euclidian_dist(node.position, point) for node in tree]
        min_dist_node = tree[distances.index(min(distances))]
        return min_dist_node
 
    def steer(self, from_node, to_point):
        # 这里应该实现向量对齐的函数
        pass
 
    def add_node(self, tree, new_node):
        tree.append(new_node)
 
    def extend_tree(self, start_node, target_point, tree, obstacle_list):
        nearest_node = self.nearest_neighbor(tree, target_point)
        steer_point = self.steer(nearest_node, target_point)
        if self.is_collision_free(nearest_node, steer_point, obstacle_list):
            new_node = Node(steer_point, nearest_node)
            self.add_node(tree, new_node)
            return new_node
        return None
 
    def is_collision_free(self, from_node, to_point, obstacle_list):
        # 这里应该实现无碰撞检查的函数
        pass
 
    def path_from_start(self, goal_node):
        path = []
        current_node = goal_node
        while current_node is not None:
            path.append(current_node.position)
            current_node = current_node.parent
        return path
 
    def plan(self, start_point, target_point):
        # 这里应该实现RRT路径规划的主循环
        pass
 
# 以下是辅助函数和Node类定义
class Node:
    def __init__(self, position, parent):
        self.position = np.array(position)
        self.parent = parent
 
    def __eq__(self, other):
        return np.array_equal(self.position, other.position)
 
# 其他辅助函数

这个伪代码实例提供了RRT算法的基本框架。在实际应用中,你需要实现具体的函数,如nearest_neighbor来找到最接近目标点的节点,steer来生成新的节点,is_collision_free来检查新节点是否与障碍物不碰撞,以及主循环函数plan来执行整个路径规划过程。这些函数的具体实现会依赖于你的应用环境和需求。

2024-08-12

最优控制LQR(Linear Quadratic Regulator)是一种常用的算法,用于在动态系统中找到使得系统输出信号的期望平方最小的控制输入。以下是一个简化的ROS中使用LQR进行轨迹规划的示例代码:




// ROS C++ 示例
#include <ros/ros.h>
#include <lqrrt_ros/LQR.h>
 
int main(int argc, char **argv) {
    ros::init(argc, argv, "lqr_example");
    ros::NodeHandle nh;
 
    // 初始化LQR对象
    lqrrt_ros::LQR lqr;
 
    // 设置系统矩阵和状态权重
    lqr.setA(Eigen::MatrixXd::Identity(2, 2)); // 状态转移矩阵
    lqr.setB(Eigen::MatrixXd::Identity(2, 1)); // 状态-控制矩阵
    lqr.setQ(Eigen::MatrixXd::Identity(2, 2)); // 状态权重矩阵
    lqr.setR(Eigen::MatrixXd::Identity(1, 1)); // 控制权重矩阵
 
    // 设置初始状态和终止条件
    lqr.setState(Eigen::Vector2d(0.0, 0.0)); // 初始状态
    lqr.setTermCond(100); // 迭代次数终止条件
 
    // 计算控制输入
    lqr.compute();
 
    // 打印结果
    ROS_INFO("LQR gains: K = %f, L = %f", lqr.getK(), lqr.getL());
 
    return 0;
}



# Python 示例
import numpy as np
from lqrrt import LQR
 
# 初始化LQR对象
lqr = LQR()
 
# 设置系统矩阵和状态权重
lqr.setA(np.eye(2))  # 状态转移矩阵
lqr.setB(np.eye(2))  # 状态-控制矩阵
lqr.setQ(np.eye(2))  # 状态权重矩阵
lqr.setR(np.eye(1))  # 控制权重矩阵
 
# 设置初始状态和终止条件
lqr.setState(np.array([0.0, 0.0]))  # 初始状态
lqr.setTermCond(100)  # 迭代次数终止条件
 
# 计算控制输入
lqr.compute()
 
# 打印结果
print(f"LQR gains: K = {lqr.getK()}, L = {lqr.getL()}")



% MATLAB 示例
A = eye(2); % 状态转移矩阵
B = eye(2); % 状态-控制矩阵
Q = eye(2); % 状态权重矩阵
R = eye(1); % 控制权重矩阵
 
% 初始化LQR对象
lqr = lqr(A, B, Q, R);
 
% 设置初始状态和终止条件
x0 = [0; 0]; % 初始状态
lqr.setTermCond('MaxIters', 100); % 迭代次数终止条件
 
% 计算控制输入
[K, L] = lqr(lqr, x0);
 
% 打印结果
fprintf('LQR gains: K = %f, L = %f\n', K, L);

以上代码仅展示了如何初始化LQR对象、设置系统矩阵和权重、计

2024-08-12

Paxos算法是一种一致性协议,被广泛应用于分布式系统中以实现数据的一致性和可靠性。Paxos算法解决的是分布式系统中的一致性问题,即如何就某个值达成一致,即使系统中有可能发生消息丢失、网络分化(network partition)、节点失效等问题。

Paxos算法的核心是接受提案(Proposal)和接受值(Accepted Value)。在Paxos算法中,有三种角色:

  1. Proposer(提议者):提出提案。
  2. Acceptor(接受者):可以接受提案并在以后表决。
  3. Learner(学习者):只接收最终决定的值。

Paxos算法的精华在于它的安全性和活性保证,确保在各种可能的系统故障情况下仍能够正确地达成一致,并且保证最终能够得到一个值。

以下是Paxos算法的简化版本的伪代码描述:




Paxos(Proposer, Acceptor, Learner) {
  while (true) {
    // Proposer 发送 Prepare 请求
    Proposer.Prepare();
 
    // Acceptor 收到 Prepare 请求后,如果还没有响应过任何Prepare请求,则发送Promise
    Acceptor.onPrepare(Proposer.ProposalNumber) {
      if (Acceptor.ReceivedPrepareRequest) {
        return Acceptor.ResponseWithHighestProposalNumber;
      } else {
        Acceptor.ReceivedPrepareRequest = true;
        return Acceptor.ResponseWithHighestProposalNumber;
      }
    }
 
    // Proposer 收到 Promises 后,如果存在已经被Promise的ProposalNumber,则提交该ProposalNumber
    Proposer.onPromises(AcceptorResponses) {
      if (AcceptorResponses.HasChosenProposalNumber) {
        Proposer.SubmitValue(AcceptorResponses.ChosenProposalNumber);
      } else {
        Proposer.SubmitNewProposal();
      }
    }
 
    // Acceptor 收到 Proposer 的提案后,如果该提案号是最高的,则接受该提案
    Acceptor.onProposal(ProposalNumber, Value) {
      if (ProposalNumber >= Acceptor.HighestProposalNumber) {
        Acceptor.HighestProposalNumber = ProposalNumber;
        Acceptor.ChosenProposalNumber = ProposalNumber;
        Acceptor.AcceptedValue = Value;
        return 'Accepted';
      } else {
        return 'Rejected';
      }
    }
 
    // Learner 只接受 Acceptor 已经接受的提案
    Learner.Learn() {
      return Acceptor.AcceptedValue;
    }
  }
}

Paxos算法的复杂性在于它的严格条件和数学证明,确保了在各种可能的系统故障情况下,该算法仍能够正确地达成一致。因此,理解和掌握Paxos算法对于分布式系统的开发者来说是至关重要的。

2024-08-12

由于原始代码较为复杂且涉及版权问题,我们提供一个简化版本的核心函数实现,用于演示如何在MATLAB中实现LEACH聚类算法。




function [cluster_centers, cluster_assignments] = leach_clustering(data, num_clusters, max_iterations)
    % LEACH聚类算法实现
    % data: 输入数据矩阵,每行是一个样本
    % num_clusters: 期望的聚类数目
    % max_iterations: 最大迭代次数
 
    num_samples = size(data, 1);
    cluster_centers = data(randperm(num_samples, num_clusters), :); % 随机初始化聚类中心
    cluster_assignments = zeros(num_samples, 1); % 初始化样本到聚类的映射
    energy = inf; % 初始化能量
 
    for iter = 1:max_iterations
        % 更新每个样本的聚类赋值
        for i = 1:num_samples
            distances = sum((data(i, :) - cluster_centers) .^ 2, 2);
            [dummy, closest_cluster] = min(distances);
            cluster_assignments(i) = closest_cluster;
        end
        
        % 更新聚类中心的位置
        for j = 1:num_clusters
            cluster_indices = (cluster_assignments == j);
            if any(cluster_indices)
                cluster_centers(j, :) = mean(data(cluster_indices, :), 1);
            end
        end
        
        % 计算能量
        energy_new = sum(distances);
        if energy_new < energy
            energy = energy_new;
        else
            % 如果能量增加,则提前终止迭代
            break;
        end
    end
end

这个简化版本的函数实现了LEACH聚类算法的核心步骤,包括初始化聚类中心、迭代更新聚类赋值和聚类中心,并提供了能量计算来检测算法是否提前终止迭代。这个示例展示了如何在MATLAB中实现一个简单的聚类算法,并且可以作为进一步开发和应用聚类算法的起点。

2024-08-12



// 引入JSEncrypt库
const JSEncrypt = require('jsencrypt').JSEncrypt;
 
// 公钥,请替换为实际的公钥字符串
const publicKey = `-----BEGIN PUBLIC KEY-----
...
-----END PUBLIC KEY-----`;
 
// 创建JSEncrypt实例
const encryptor = new JSEncrypt();
 
// 设置公钥
encryptor.setPublicKey(publicKey);
 
// 需要加密的数据
const data = "这是需要加密的数据";
 
// 使用公钥进行加密
const encrypted = encryptor.encrypt(data);
 
console.log('加密数据:', encrypted);
 
// 输出加密结果,可以发送给服务器

这段代码展示了如何在Node.js环境中使用JSEncrypt库进行公钥加密。首先引入JSEncrypt库,然后设置公钥,接着使用公钥对数据进行加密,最后输出加密结果。这是一个典型的非对称加密的应用场景,在需要保护数据安全性的场景中非常有用。

2024-08-11



package main
 
import (
    "fmt"
    "github.com/emirpasic/gods"
    "github.com/emirpasic/gods/lists/singlylinkedlist"
)
 
func main() {
    // 创建一个单向链表
    list := singlylinkedlist.New()
 
    // 往链表中添加元素
    list.Add(1)
    list.Add("a")
    list.Add(2)
    list.Add("b")
 
    // 遍历链表并打印元素
    for i := 0; i < list.Size(); i++ {
        fmt.Println(list.Value(i))
    }
 
    // 使用迭代器来遍历链表
    iterator := list.Iterator()
    for iterator.Next() {
        fmt.Println(iterator.Value())
    }
}

这段代码演示了如何使用singlylinkedlist库创建一个单向链表,并展示了如何添加元素、遍历链表以及使用迭代器进行遍历。这是一个简单的数据结构示例,对于学习Go语言中的算法和数据结构有很好的教育意义。

2024-08-11

在Web前端面试中,算法问题通常会涉及数据结构、排序、搜索和动态编程等方面。以下是几个在前端面试中可能会遇到的算法问题及其解决方案:

  1. 实现一个快速排序函数:



function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    }
    const pivot = arr[Math.floor((arr.length - 1) / 2)];
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}
  1. 实现一个二分搜索函数:



function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}
  1. 实现一个斐波那契数列函数:



function fibonacci(n) {
    const memo = [0, 1];
    const helper = (n) => {
        if (memo[n] != null) return memo[n];
        return memo[n] = helper(n - 1) + helper(n - 2);
    };
    return helper(n);
}

这些例子展示了快速排序、二分搜索和斐波那契数列的递归解决方案,以及使用记忆化递归(也称为记忆化搜索)的方式来优化斐波那契数列的计算。在实际的前端面试中,可能还会涉及到更复杂的算法问题,需要面试者具备解决常见数据结构与算法问题的能力。

2024-08-11



package main
 
import (
    "fmt"
    "time"
)
 
// 定义一个雪花算法的结构体
type SnowFlake struct {
    // 42位的时间戳
    timestampShift uint64
    // 10位的机器ID
    machineIDShift uint64
    // 12位的序列号
    sequenceShift uint64
    // 机器ID
    machineID uint16
    // 序列号
    sequence uint16
    // 上次生成ID的时间戳
    lastTimestamp int64
}
 
// 初始化雪花算法的参数
func NewSnowFlake(machineID uint16) *SnowFlake {
    return &SnowFlake{
        timestampShift: 22,
        machineIDShift: 12,
        sequenceShift: 0,
        machineID:     machineID,
        sequence:      0,
        lastTimestamp: 0,
    }
}
 
// 生成新的ID
func (s *SnowFlake) NextID() int64 {
    // 获取当前时间戳
    currentTimestamp := time.Now().UnixNano() / 1e6
    // 如果当前时间小于上次时间戳,则抛出错误
    if currentTimestamp < s.lastTimestamp {
        panic("current timestamp is less than last timestamp")
    }
    // 如果时间戳相同,序列号自增
    if currentTimestamp == s.lastTimestamp {
        s.sequence = (s.sequence + 1) & 4095
        if s.sequence == 0 {
            // 如果序列号达到上限,等待下一个毫秒
            for currentTimestamp <= s.lastTimestamp {
                currentTimestamp = time.Now().UnixNano() / 1e6
            }
        }
    } else {
        s.sequence = 0
    }
    // 更新最后时间戳
    s.lastTimestamp = currentTimestamp
    // 返回新ID
    return (currentTimestamp<<s.timestampShift) | (int64(s.machineID)<<s.machineIDShift) | int64(s.sequence)
}
 
func main() {
    // 初始化雪花算法
    snowflake := NewSnowFlake(1)
    // 生成并打印10个ID
    for i := 0; i < 10; i++ {
        id := snowflake.NextID()
        fmt.Printf("Generated ID: %d\n", id)
    }
}

这段代码实现了雪花算法的核心函数,包括初始化和生成新ID。在main函数中,我们创建了雪花算法的实例,并通过循环生成并打印了10个ID。这个简单的实现可以作为学习和实践雪花算法的起点。

2024-08-11



package main
 
import (
    "fmt"
    "hash/crc32"
    "sort"
    "strconv�"
)
 
// 使用一致性哈希实现负载均衡
type HashRing []int // 使用int类型的key来模拟IP地址
 
func (r HashRing) Len() int           { return len(r) }
func (r HashRing) Less(i, j int) bool { return r[i] < r[j] }
func (r HashRing) Swap(i, j int)      { r[i], r[j] = r[j], r[i] }
 
func (r HashRing) GetNode(key string) int {
    hash := int(crc32.ChecksumIEEE([]byte(key)))
    idx := sort.Search(len(r), func(i int) bool { return r[i] >= hash })
    if idx == len(r) {
        idx = 0
    }
    return r[idx]
}
 
func main() {
    // 初始化一个有3个节点的hash环
    ring := HashRing{}
    for i := 0; i < 3; i++ {
        ring = append(ring, int(crc32.ChecksumIEEE([]byte(strconv.Itoa(i)))))
    }
    sort.Sort(ring)
 
    // 使用一致性哈希算法选择节点
    key := "my_data_key"
    node := ring.GetNode(key)
    nodeIp := fmt.Sprintf("%d.%d.%d.%d", node>>24, node>>16&0xFF, node>>8&0xFF, node&0xFF)
    fmt.Printf("Key '%s' should be stored at node %s\n", key, nodeIp)
}

这段代码首先定义了一个HashRing类型来表示一致性哈希环,并实现了排序接口。然后,它演示了如何初始化这个环,并使用GetNode方法来根据给定的键值选择节点。最后,在main函数中,我们演示了如何使用这个算法来选择存储给定键的节点。这个例子简单直观,有助于理解一致性哈希算法在负载均衡中的应用。