CodingTour
ARTS #218 | 又长了一岁

一个愉快而特别的日子,生日是一个反思过去、展望未来的好时机,希望在新的一年里能够实现自己的目标,收获更多的快乐~

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 动画效果的工具,效果还不错~

Share

分享一段将 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

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