Algorithm

本周选择的算法题是：2 Keys Keyboard。

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1: return 0
        for i in range(2, n):
            if n % i == 0:
                return i + self.minSteps(n // i)
        return n

Review

https://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

Guido van Rossum 曾经发过一篇文章解释 “为什么 TRE 不适合用在 Python 这门语言上”，主要观点：

TRE 不利于调试
TRE 并不是一个透明的优化，它会影响开发者的编程方式 - 相同代码在支持与不支持 TRE 的编译器下，可能得到不同的结果
1000 的递归深度已经够用了
Python 在意 “程序员” 的使用感受，相比递归、链表这些玩意儿，列表、序列更能显著提高他们的使用体验/感受

Python 的语言特性也不适合 TRE，比如如下代码：

def f(x):
    print('original')
    if x > 0:
        return f(x-1) # 指向的是下面的 f 函数
    return 0
  
g = f
  
def f(x):
    print('new')
    return x
  
print(g(5))
  
# original
# new
# 4

在 TRE 场景下，f 要跳到哪并不容易判断出来。

因此，Python 的解释器（CPython）没有内置对 TRE 的支持，即使你写了符合其他语言定义的尾递归模式代码，Python 解释器也不会进行优化，这意味着深度递归调用仍然会导致栈溢出。

另外：

After all TRE only addresses recursion that can easily be replaced by a loop. :-
— Guido van Rossum

比如以下函数的尾递归版本：

def factorial_tail_recursive(n, accumulator=1):
    if n == 0:
        return accumulator
    else:
        return factorial_tail_recursive(n-1, n*accumulator)

# 这种方法在Python中会导致RecursionError
print(factorial_tail_recursive(1000))

转换为迭代的版本：

def factorial_iterative(n):
    accumulator = 1
    while n > 0:
        accumulator *= n
        n -= 1
    return accumulator

# 推荐的方法，可以处理大数值而不会导致栈溢出
print(factorial_iterative(1000))

在 Python，采用迭代方法是更合适的选择。

Tip

LeiaPix，一个将静态图片转成 3D 动画效果的工具，效果还不错~

分享一段将 Rust 代码构建为通用 iOS 平台的 xcframework 脚本：

#!/usr/bin/env bash

set -e

# 基本配置
WORKING_DIR=$(dirname $(dirname "$0"))
TARGET_DIR="$WORKING_DIR/target"
MANIFEST_PATH="$WORKING_DIR/Cargo.toml"
FRAMEWORK_NAME="Rust"
XCFRAMEWORK_ROOT="$TARGET_DIR/$FRAMEWORK_NAME.xcframework"
HEADER_PATH="$WORKING_DIR/src/RustFoundation.h"

CRATE_NAME=$(grep --max-count=1 '^name =' "$MANIFEST_PATH" | cut -d '"' -f 2)
BUILD_PROFILE="release"
LIB_NAME="lib${CRATE_NAME}.a"

# M1 iOS simulator & Hardware iOS targets & Intel iOS simulator
cargo build --release --lib \
  --target aarch64-apple-ios-sim \
  --target aarch64-apple-ios \
  --target x86_64-apple-ios

# 先清理
rm -rf "$XCFRAMEWORK_ROOT"

# 构建 Common 目录
COMMON="$XCFRAMEWORK_ROOT/common/$FRAMEWORK_NAME.framework"
mkdir -p "$COMMON/Modules"
cp "$WORKING_DIR/build-scripts/ios-ingredient/module.modulemap" "$COMMON/Modules/"
mkdir -p "$COMMON/Headers"
cp "$HEADER_PATH" "$COMMON/Headers"

# 准备 iOS hardware 产物
mkdir -p "$XCFRAMEWORK_ROOT/ios-arm64"
cp -r "$COMMON" "$XCFRAMEWORK_ROOT/ios-arm64/$FRAMEWORK_NAME.framework"
cp "$TARGET_DIR/aarch64-apple-ios/$BUILD_PROFILE/$LIB_NAME" "$XCFRAMEWORK_ROOT/ios-arm64/$FRAMEWORK_NAME.framework/$FRAMEWORK_NAME"
chmod +x "$XCFRAMEWORK_ROOT/ios-arm64/$FRAMEWORK_NAME.framework/$FRAMEWORK_NAME"

# 准备 iOS simulator 产物，需要构建为 fat binary
mkdir -p "$XCFRAMEWORK_ROOT/ios-arm64_x86_64-simulator"
cp -r "$COMMON" "$XCFRAMEWORK_ROOT/ios-arm64_x86_64-simulator/$FRAMEWORK_NAME.framework"
lipo -create \
  -output "$XCFRAMEWORK_ROOT/ios-arm64_x86_64-simulator/$FRAMEWORK_NAME.framework/$FRAMEWORK_NAME" \
  "$TARGET_DIR/aarch64-apple-ios-sim/$BUILD_PROFILE/$LIB_NAME" \
  "$TARGET_DIR/x86_64-apple-ios/$BUILD_PROFILE/$LIB_NAME"
chmod +x "$XCFRAMEWORK_ROOT/ios-arm64_x86_64-simulator/$FRAMEWORK_NAME.framework/$FRAMEWORK_NAME"

rm -rf "$XCFRAMEWORK_ROOT/common"

# 设置 XCFramework 的元数据
cp "$WORKING_DIR/build-scripts/ios-ingredient/Info.plist" "$XCFRAMEWORK_ROOT/Info.plist"

由于是手动构建 xcframework，里面的 Info.plist 和 module.modulemap 两个文件提前写好，然后构建的时候复制过去即可，我是把它们放在 ios-ingredient 目录下，文件内容可以参考：

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
	<key>AvailableLibraries</key>
	<array>
		<dict>
			<key>LibraryIdentifier</key>
			<string>ios-arm64</string>
			<key>LibraryPath</key>
			<string>Rust.framework</string>
			<key>SupportedArchitectures</key>
			<array>
				<string>arm64</string>
			</array>
			<key>SupportedPlatform</key>
			<string>ios</string>
		</dict>
		<dict>
			<key>LibraryIdentifier</key>
			<string>ios-arm64_x86_64-simulator</string>
			<key>LibraryPath</key>
			<string>Rust.framework</string>
			<key>SupportedArchitectures</key>
			<array>
				<string>arm64</string>
				<string>x86_64</string>
			</array>
			<key>SupportedPlatform</key>
			<string>ios</string>
			<key>SupportedPlatformVariant</key>
			<string>simulator</string>
		</dict>
	</array>
	<key>CFBundlePackageType</key>
	<string>XFWK</string>
	<key>XCFrameworkFormatVersion</key>
	<string>1.0</string>
</dict>
</plist>

Info.plist

framework module Rust {
  umbrella header "RustFoundation.h"

  export *
  module * { export * }
}

module.modulemap

把头文件名称、位置，和构建的产物名替换一下即可使用，构建完的结构如下：

Algorithm

Review

Tip

Share