Algorithm
Review
1. App 如何通过注入动态库的方式实现极速编译调试？
  1. Injection for Xcode
Tips
Share

Algorithm

Leetcode 564: Find the Closest Palindrome: https://leetcode.com/problems/find-the-closest-palindrome/

https://dreamume.medium.com/leetcode-564-find-the-closest-palindrome-c5661c8d7411

Review

iOS 开发高手课戴铭

App 如何通过注入动态库的方式实现极速编译调试？

Injection for Xcode

John Holdsworth 开发了一个叫作 Injection 的工具可以动态地将 Swift 或 Objective-C 的代码在已运行的程序中执行，以加快调试速度，同时保证程序不用重启

作者已经开源了这个工具，地址是https://github.com/johnno1962/InjectionIII 。使用方式就是 clone 下代码，构建 InjectionPluginLite/InjectionPlugin.xcodeproj ；删除方式是，在终端里运行下面这行代码：

rm -rf ~/Library/Application\ Support/Developer/Shared/Xcode/Plug-ins/InjectionPlugin.xcplugin

构建完成后，我们就可以编译项目。这时添加一个新的方法：

- (void)injected {
    NSLog(@"I've been injected: %@", self);
}

然后在这个方法中添加一个断点，按下 ctrl + = ，接下来你会发现程序运行时会停到断点处，这样你的代码就成功地被运行中的 App 执行了。那么，Injection 是怎么做到的呢？

Injection 会监听源代码文件的变化，如果文件被改动了，Injection Server 就会执行 rebuildClass 重新进行编译、打包成动态库，也就是 .dylib 文件。编译、打包成动态库后使用 writeSting 方法通过 Socket 通知运行的 App。writeString 的代码如下：

- (BOOL)writeString:(NSString *)string {
    const char *utf8 = string.UTF8String;
    uint32_t length = (uint32_t)strlen(utf8);
    if (write(clientSocket, &length, sizeof length) != sizeof length ||
        write(clientSocket, utf8, length) != length)
        return NO;
    return YES;
}

Server 会在后台发送和监听 Socket 消息，实现逻辑在 InjectionServer.mm 的 runInBackground 方法里。Client 也会开启一个后台去发送和监听 Socket 消息，实现逻辑在 InjectionClient.mm里的 runInBackground 方法里

Client 接收到消息后会调用 inject(tmpfile: String) 方法，运行时进行类的动态替换。inject(tmpfile: String) 方法的具体实现代码，你可以点击这个链接查看

inject(tmpfile: String) 方法的代码大部分都是做新类动态替换旧类。inject(tmpfile: String) 的入参 tmpfile 是动态库的文件路径，那么这个动态库是如何加载到可执行文件里的呢？具体的实现在 inject(tmpfile: String) 方法开始里，如下：

let newClasses = try SwiftEval.instance.loadAndInject(tmpfile: tmpfile)

你先看下 SwiftEval.instance.loadAndInject(tmpfile: tmpfile) 这个方法的代码实现：

@objc func loadAndInject(tmpfile: String, oldClass: AnyClass? = nil) throws -> [AnyClass] {
    print("???? Loading .dylib - Ignore any duplicate class warning...")
    // load patched .dylib into process with new version of class
    guard let dl = dlopen("\(tmpfile).dylib", RTLD_NOW) else {
        throw evalError("dlopen() error: \(String(cString: dlerror()))")
    }
    print("???? Loaded .dylib - Ignore any duplicate class warning...")

    if oldClass != nil {
        // find patched version of class using symbol for existing

        var info = Dl_info()
        guard dladdr(unsafeBitCast(oldClass, to: UnsafeRawPointer.self), &info) != 0 else {
            throw evalError("Could not locate class symbol")
        }

        debug(String(cString: info.dli_sname))
        guard let newSymbol = dlsym(dl, info.dli_sname) else {
            throw evalError("Could not locate newly loaded class symbol")
        }

        return [unsafeBitCast(newSymbol, to: AnyClass.self)]
    }
    else {
        // grep out symbols for classes being injected from object file

        try injectGenerics(tmpfile: tmpfile, handle: dl)

        guard shell(command: """
            \(xcodeDev)/Toolchains/XcodeDefault.xctoolchain/usr/bin/nm \(tmpfile).o | grep -E ' S _OBJC_CLASS_\\$_| _(_T0|\\$S).*CN$' | awk '{print $3}' >\(tmpfile).classes
            """) else {
            throw evalError("Could not list class symbols")
        }
        guard var symbols = (try? String(contentsOfFile: "\(tmpfile).classes"))?.components(separatedBy: "\n") else {
            throw evalError("Could not load class symbol list")
        }
        symbols.removeLast()

        return Set(symbols.flatMap { dlsym(dl, String($0.dropFirst())) }).map { unsafeBitCast($0, to: AnyClass.self) }

在这段代码中，你是不是看到你所熟悉的动态库加载函数 dlopen 了呢？

guard let dl = dlopen("\(tmpfile).dylib", RTLD_NOW) else {
    throw evalError("dlopen() error: \(String(cString: dlerror()))")
}

如上代码所示，dlopen 会把 tmpfile 动态库文件载入运行的 App 里，返回指针 dl。接下来，dlsym 会得到 tmpfile 动态库的符号地址，然后就可以处理类的替换工作了。dlsym 调用对应代码如下：

guard let newSymbol = dlsym(dl, info.dli_sname) else {
    throw evalError("Could not locate newly loaded class symbol")
}

当类的方法都被替换后，我们就可以开始重新绘制界面了。整个过程无需重新编译和重启 App，至此使用动态库方式极速调试的目的就达成了

Tips

间接移动的例子

http://thbecker.net/articles/rvalue_references/section_10.html

由于（复杂和有争议的）右值引用的讨论，标准委员会决定了移动构造和移动赋值操作，即右值引用对拷贝构造和拷贝赋值操作有覆盖效果，当用户不提供时应该通过编译器产生。这看着像一个自然正确的事情，考虑编译器总是对普通的拷贝构造和拷贝赋值操作做相同的事情。在 2010 年秋，Scott Meyers 在 comp.lang.c++ 发布一个消息，他解释编译器如何产生移动构造可以一种严重的方式破坏现存的代码

委员会然后决定这将导致警告，且它限制自动生成移动构造和移动赋值操作使得它很少、几乎不可能破坏现存的代码。这个事情最后的状态描述在 Scott Meyer 的书《Effective Modern C++》的第 17 条

间接移动依然是个争议的问题直到标准的完成（见 Dave Abrahams 的论文）。讽刺的是，为什么委员会首次考虑间接移动的唯一原因是尝试解决右值引用和第 9 节的异常问题。这个问题随后用一种更好的办法通过新的 noexcept 关键字解决。在 noexcept 解决方案提出之前的几个月，间接移动还没有看到曙光。现在，没问题了

作为 C++ 专家，你需要理解右值的细节。否则，你放弃了这个工具的完整理解。你可以自我安慰，但，在你的日常编程中，你将只需要记住关于右值引用的三件事情：

通过重载一个函数如下
```
void foo(X& x); // lvalue reference overload
void foo(X&& x); // rvalue reference overload
```
你可在编译期间区分“foo 函数用的是左值还是右值？“主要的应用程序重载一个类的拷贝构造和拷贝赋值操作来实现移动语义。如果你这么做，确保注意异常处理，且尽可能使用新的 noexcept 关键字
std::move 使它的参数变成右值
std::forward 允许你获得完美转发如果你使用第 8 节的 factory 函数例子

Jensen 不等式

https://brilliant.org/wiki/jensens-inequality/#statement-of-jensens-inequality

Jensen 不等式是一个关于函数凸性的不等式。我们首先坐如下定义：

一个函数在区间 I 上是凸的如果在它的图像（I 区间）上任意两点间的线段位于图形之上，如凸函数 $ f(x) = x^{2} $
一个函数在区间 I 上是凹的如果在它的图像（I 区间）上任意两点间的线段位于图形之下，如凸函数 $ f(x) = -x^{2} $

Jensen 不等式的描述

Jensen 不等式的描述如下

Jensen 不等式定理 设一个实值函数 f 在区间 I 上是凸的。设 $ x_ {1}, \ldots, x_ {n} \in I $ 且 $ \omega_ {1}, \ldots, \omega_ {n} \ge 0 $。则我们有

$ \frac{\omega_ {1} f(x_ {1}) + \omega_ {2} f(x_ {2}) + \cdots + \omega_ {n} f(x_ {n})}{\omega_ {1} + \omega_ {2} + \cdots + \omega_ {n}} \ge f( \frac{\omega_ {1}x_ {1} + \omega_ {2}x_ {2} + \cdots + \omega_ {n}x_ {n}}{\omega_ {1} + \omega_ {2} + \cdots + \omega_ {n}}) $

如果 f 是凹的，不等式的方向相反

特别地如果我们让 $ \omega_ {1} = \omega_ {2} = \cdots = \omega_ {n} = 1 $，我们得到不等式

$ \frac{f(x_ {1}) + f(x_ {2}) + \cdots + f(x_ {n})}{n} \ge f(\frac{x_ {1} + x_ {2} + \cdots + x_ {n}}{n}) $

证明：

我们首先证明如下描述

$ P \Longleftrightarrow Q $，P、Q 定义如下

P: $ \forall x_ {1}, \ldots, x_ {n} \in I $ 且 $ \forall \omega_ {1}, \ldots, \omega_ {n} \ge 0 $ 如下式子成立

$ \frac{\omega_ {1}f(x_ {1}) + \omega_ {2} f(x_ {2}) + \cdots + \omega_ {n}f(x_ {n})}{\omega_ {1} + \omega_ {2} + \cdots + \omega_ {n}} \ge f(\frac{\omega_ {1}x_ {1} + \omega_ {2}x_ {2} + \cdots + \omega_ {n}x_ {n}}{\omega_ {1} + \omega_ {2} + \cdots + \omega_ {n}}) $

Q: $ \forall x_ {1}, \ldots, x_ {n} \in I $ 且 $ \forall \lambda_ {1}, \ldots, \lambda_ {n} \ge 0 $ 且 $ \sum^{n}_ {i=1} \lambda_ {i} = 1 $ 如下式子成立

$ \sum^{n}_ {i=1} \lambda_ {i}f(x_ {i}) \ge f(\sum^{n}_ {i=1} \lambda_ {i}x_ {i}) $

证明：

先简单地设 $ \lambda_ {i} = \frac{\omega_ {i}}{\sum^{n}_ {r=1} \omega_ {r}}, i = 1, 2, \ldots, n $

我们使用归纳法证明 Q 是真的

当 n = 1 时显然为真

当 n = 2 时是凸函数的定义

对 $ n \ge 3 $，我们先假设 $ \lambda_ {n} \in (0, 1) $（如果 $ \lambda_ {n} = 1 $，则显然成立，且如果 $ \lambda_ {n} = 0 $ 也是显然成立的

现在，我们继续假设 k = 2 和 k = n - 1 时是真的

$ \begin{aligned} f(\sum^{n}_ {i=1} \lambda_ {i}x_ {i}) &= f((1 - \lambda_ {n})(\sum^{n-1}_ {i=1} \mu_ {i} x_ {i}) + \lambda_ {n}x_ {n}) \qquad ( \mu_ {i} = \frac{\lambda_ {i}}{1 - \lambda_ {n}}, i = 1, 2, \ldots, n - 1, \sum^{n-1}_ {i=1} \mu_ {i} = 1) \\ &\le (1 - \lambda_ {n}) f(\sum^{n-1}_ {i=1} \mu_ {i} x_ {i}) + \lambda_ {n}f(x_ {n}) \\ &\le (\sum^{n-1}_ {i=1}(1 - \lambda_ {n}) \mu_ {i} f(x_ {i})) + \lambda_ {n}f(x_ {n}) \\ &= \sum^{n}_ {i=1} \lambda_ {i} f(x_ {i}) \end{aligned} $

我们如何检查一个函数是凸的还是凹的？我们不能总是画图来确定。最好的方法是使用积分。一个函数 f 在区间 I 上是凸的当且仅当 $ f^{\prime \prime}(x) \ge 0, \forall x \in I $ 且是凹的则 $ f^{\prime \prime}(x) \le 0, \forall x \in I $。精确地描述如下

定理设 $ f: I \to \mathbb{R} $ 为一个可两次微分的函数，则

f 在区间 I 上是凸的当且仅当 $ f^{\prime \prime}(x) \ge 0 \forall x \in I $
f 在区间 I 上是凹的当且仅当 $ f^{\prime \prime}(x) \le 0 \forall x \in I $

如果我们把 Jensen 不等式用在 $ f(x) = x^{2} $ 上，我们选择 $ x_ {1} = 1, x_ {2} = 2, \ldots, x_ {n} = n $，则

$ \begin{aligned} \frac{f(x_ {1}) + f(x_ {2}) + \cdots + f(x_ {n})}{n} &\ge f(\frac{x_ {1} + x_ {2} + \cdots + x_ {n}}{n}) \\ \frac{f(1) + f(2) + \cdots + f(n)}{n} &\ge f(\frac{1 + 2 + \cdots + n}{n}) \\ \frac{1^{2} + 2^{2} + \cdots + n^{2}}{n} &\ge f(\frac{\frac{n(n+1)}{2}}{n}) \\ \frac{\frac{n(n+1)(2n+1)}{6}}{n} &\ge f(\frac{n+1}{2}) \\ \frac{(n+1)(2n+1)}{6} &\ge (\frac{n+1}{2})^{2} \\ n &\ge 1 \end{aligned} $

Jensen 不等式的特殊形式

AM-GM 不等式是 Jensen 不等式的一个特殊形式：

$ \frac{\sum^{n}_ {i=1} a_ {i}}{n} \ge \sqrt[n]{\sum^{n}_ {i=1} a_ {i}} $

证明：

考虑函数 $ f(x) = \log{x} \forall x > 0 $

有 $ f^{\prime \prime}(x) = \frac{-1}{x^{2}} < 0 $。则 f(x) 为凹函数。这样使用 Jensen 不等式我们有

$ \begin{aligned} f(\frac{\sum^{n}_ {i=1}a_ {i}}{n}) & \ge \frac{\sum^{n}_ {i=1} f(a_ {i})}{n} \\ \Rightarrow \log{(\frac{\sum^{n}_ {i} a_ {i}}{n})} &\ge \frac{\sum^{n}_ {i=1} \log{a_ {i}}}{n} \end{aligned} $

通过 log 函数的性质，我们有

$ \begin{aligned} \log{(\frac{\sum^{n}_ {i=1}a_ {i}}{n})} &\ge \frac{\sum^{n}_ {i=1} \log{a_ {i}}}{n} \\ &= \frac{\log{a_ {1}} + \log{a_ {2}} + \cdots + \log{a_ {n}}}{n} \\ &= \frac{\log{(a_ {1}a_ {2}a_ {3} \cdots a_ {n})}}{n} \\ &= \log{(\prod^{n}_ {i=1}a_ {i})^{\frac{1}{n}}} \end{aligned} $

则得证

例子

证明对所有 $ n \in N, \sqrt{1^{2} + 1} + \sqrt{2^{2} +1} + \cdots + \sqrt{n^{2} + 1} \ge \frac{n}{2} \sqrt{n^{2} + 2n + 5} $

我们可定义函数 $ f(x) = \sqrt{x^{2}+1} $。我们易知该函数可两次微分，且是凸函数

现在我们用 Jensen 不等式且 $ x_ {1} = 1, x_ {2} = 2, \ldots, x_ {n} = n $，我们有

$ \begin{aligned} \frac{f(x_ {1}) + f(x_ {2}) + \cdots + f(x_ {n})}{n} &\ge f(\frac{x_ {1} + x_ {2} + \cdots + x_ {n}}{n}) \\ \frac{f(1) + f(2) + \cdots + f(n)}{n} &\ge f(\frac{1+2+ \cdots + n}{n}) \\ \frac{\sqrt{1^{2}+1} + \sqrt{2^{2} +1} ++ \cdots \sqrt{n^{2} + 1}}{n} &\ge f(\frac{n(n+1)/2}{n}) \\ &= f(\frac{n+1}{2}) \\ &= \sqrt{(\frac{n+1}{2})^{2} + 1} \\ &= \frac{1}{2} \sqrt{n^{2} + 2n + 5} \end{aligned} $

因此得证

Jensen 不等式的应用

设 a,b,c 为正实数满足 $ \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = a + b + c $。如果如下表达式的最大值为 $ \frac{m}{n} $ 的形式，m, n 为互质的正整数，则 m + n 为多少？

$ \frac{1}{(2a+b+c)^{2}} + \frac{1}{(2b+c+a)^{2}} + \frac{1}{(2c+b+a)^{2}} $

证明：

$ \begin{aligned} \frac{1}{a} + \frac{1}{b} + \frac{1}{c} &= a + b + c \\ \Rightarrow \frac{ab+bc+ca}{abc(a+b+c)} &= 1 \\ \Rightarrow (ab+bc+ca)^{2} &= 3abc(a+b+c) \\ \Rightarrow \frac{3}{ab+bc+ca} &= \frac{ab+bc+ca}{abc(a+b+c)} = 1 \end{aligned} $

或 $ \frac{9}{16(ab+bc+ca)} = \frac{3}{16} $

需要证明 $ \frac{1}{(2a+b+c)^{2}} + \frac{1}{(2b+c+a)^{2}} + \frac{1}{(2c+b+a)^{2}} \le \frac{9}{16(ab+bc+ca)} $

使用 AM-GM 不等式得

$ (2a+b+c)^{2} = (a+b+c+a)^{2} \ge 4(a+b)(a+c) $

这样 $ \begin{aligned} \frac{1}{(2a+b+c)^{2}} + \frac{1}{(2b+c+a)^{2}} + \frac{1}{(2c+b+a)^{2}} &\le \frac{a+b+c}{2(a+b)(a+c)(b+c)} \le \frac{9}{16(ab+bc+ca)} \\ \Rightarrow a^{2}b + ab^{2} + b^{2}c + bc^{2} + c^{2}a + ca^{2} &\ge 6abc \end{aligned} $

通过 AM-GM 不等式易知这是成立的，则得证

Weekly 068

Table of Contents