lxl66566

我一直不明白，第 k 大的数的正解为什么时间复杂度是 O(n)。看快排代码，二分递归代码一眼就是 O(nlog n)，一看题解，全都说证明在算法导论，自己看书。 我看不懂书，因此想尝试做一个 benchmark，通过数据规模增长和 benchmark 用时来判断其时间复杂度。

1. 生成足够数量的随机数。后续所有测试都在这样同一个相对随机的数据上进行。
2. find_kth_largest 函数为 leetcode 题解（基于快速排序的选择方法） 改写为 rust 版本的结果。

注：find_kth_largest 函数本身没有 clone；我在 benchmark 之前就进行了数据 clone。

测试结果为（已排序，否则 cargo test 输出的排序为 10 100 1000 10000 50 500 5000）：

lxl66566

import { Bench } from "tinybench";

const bench = new Bench({
	time: 1000,
});

// This will not change the origin array
function partition<T>(
	arr: readonly T[],
	predicate: (item: T) => boolean,

lxl66566

import ctypes
import math

import numpy as np
import scipy.io.wavfile as wavfile

# 加载DLL
soundtouch_dll = ctypes.CDLL("soundtouch_dll-2.3.3/SoundTouchDLL_x64.dll")

# 定义函数原型

lxl66566

use std::fs::OpenOptions;
use std::io::Write;
use std::path::PathBuf;

fn main() -> std::io::Result<()> {
    let functions_dir = PathBuf::from("src/functions");
    let mut out = String::from("use clap::Command;\n");
    let entries = std::fs::read_dir(&functions_dir)?;

    let filenames: Vec<_> = entries

lxl66566

use crate::error::Result;
use curp::client::ClientApi;
use futures::{future::BoxFuture, FutureExt};
use pin_project::pin_project;
use std::future::Future;
use std::task::Poll;
use std::{pin::pin, sync::Arc};
use tonic::Status;
use xlineapi::{
    command::{Command, CommandResponse, KeyRange, SyncResponse},

lxl66566

import win32com.client

excel = win32com.client.GetActiveObject("Excel.Application")
wb = excel.ActiveWorkbook
sheet = wb.ActiveSheet

selected = excel.Selection
columns = selected.Columns.Count
out = open("output.typ", "w", encoding="utf-8")
out.write(f"#table(columns: {columns}, ")

lxl66566

#let get_text(knt) = {
  let temp = knt.at("body", default: false)
  if temp == false { temp = knt.at("text") }
  temp
}
#let get_text2(knt) = {
  knt.at("body", default: knt.at("text", default: "anything"))
}
#let get_text3(knt) = {
  knt.at("body", default: knt.at("text"))