2025-01-25 08:00:00
2025-01-22 08:00:00
claude-3-5-sonnet-20241022) 对各类提示词都有着令人难以置信的遵循能力，尤其是在编码提示方面。编码基准测试证实，在 Claude 3.5 Sonnet 和 GPT-4 的测试中，Claude 胜出，而且根据我在各种技术和创意任务中的亲身经历，也得出了相同的结论。完整的、未经编辑的基于这种随意提示的对话内容可在 GitHub 上获取。
编写 Python 代码来解决这个问题：
给定一个包含 100 万个 1 到 100,000 之间的随机整数的列表，找出数字之和等于 30 的最大数和最小数之间的差值。import random
def digit_sum(n):
"""Calculate the sum of digits of a number"""
return sum(int(digit) for digit in str(n))
def find_difference():
# Generate list of 1 million random integers
numbers = [random.randint(1, 100000) for _ in range(1000000)]
# Initialize variables for min and max numbers with digit sum 30
min_num = float('inf') # Initialize to positive infinity
max_num = float('-inf') # Initialize to negative infinity
# Find numbers whose digits sum to 30
for num in numbers:
if digit_sum(num) == 30:
min_num = min(min_num, num)
max_num = max(max_num, num)
# Check if we found any numbers with digit sum 30
if min_num == float('inf') or max_num == float('-inf'):
return "No numbers found with digit sum of 30"
return max_num - min_numdigit_sum() 函数：虽然这个实现是一个有趣的 Python 一行代码，但在 str 和 int 之间的类型转换会造成大量不必要的开销。写更好的代码class DigitSumFinder:
def __init__(self, target_sum: int = 30,
range_start: int = 1,
range_end: int = 100_000,
count: int = 1_000_000):
self.target_sum = target_sum
self.range_start = range_start
self.range_end = range_end
self.count = count
# Pre-calculate digit sums for all possible numbers
self.digit_sums = self._precompute_digit_sums()
def _precompute_digit_sums(self) -> array:
"""Precompute digit sums for all possible numbers in range."""
digit_sums = array('B', [0] * (self.range_end + 1))
for num in range(self.range_start, self.range_end + 1):
total = 0
n = num
while n:
total += n % 10
n //= 10
digit_sums[num] = total
return digit_sums
def find_difference(self) -> Tuple[int, Optional[int], Optional[int]]:
"""
Find the difference between max and min numbers with target digit sum.
Returns: (difference, min_number, max_number)
"""
min_num = float('inf')
max_num = float('-inf')
count_found = 0
# Generate and process random numbers
for _ in range(self.count):
num = random.randint(self.range_start, self.range_end)
if self.digit_sums[num] == self.target_sum:
count_found += 1
if num < min_num:
min_num = num
if num > max_num:
max_num = num
if count_found == 0:
return 0, None, None
return max_num - min_num, min_num, max_num写更好的代码，Claude 发现了更多明显的优化（为了可读性进行了截断）：class DigitSumAnalyzer:
"""Analyzes numbers based on their digit sums."""
def __init__(self, number_range: NumberRange):
self.number_range = number_range
self._digit_sums = self._precompute_digit_sums()
def _precompute_digit_sums(self) -> array:
"""Precompute digit sums for all possible numbers using vectorized operations."""
digits = np.arange(self.number_range.end + 1)
digit_sums = np.zeros(self.number_range.end + 1, dtype=np.uint8)
while digits.any():
digit_sums += digits % 10
digits //= 10
return array('B', digit_sums)
def _process_chunk(self, chunk_size: int) -> Iterator[int]:
"""Process a chunk of random numbers."""
numbers = np.random.randint(
self.number_range.start,
self.number_range.end + 1,
chunk_size,
dtype=np.int32
)
mask = np.frombuffer(self._digit_sums, dtype=np.uint8)[numbers] == self.number_range.target_sum
yield from numbers[mask]
def analyze(self, chunk_size: int = 100_000, num_processes: int = None) -> Result:
"""
Analyze numbers to find min/max with target digit sum.
Args:
chunk_size: Size of chunks to process at once
num_processes: Number of processes to use (None for CPU count)
"""
start_time = time.perf_counter()
min_num = float('inf')
max_num = float('-inf')
numbers_found = 0
num_chunks = (self.number_range.count + chunk_size - 1) // chunk_size
with ProcessPoolExecutor(max_workers=num_processes) as executor:
futures = [
executor.submit(self._process_chunk,
min(chunk_size, self.number_range.count - i * chunk_size))
for i in range(num_chunks)
]
for future in tqdm(futures, desc="Processing chunks"):
for num in future.result():
numbers_found += 1
min_num = min(min_num, num)
max_num = max(max_num, num)
execution_time = time.perf_counter() - start_time
if numbers_found == 0:
return Result(None, None, 0, execution_time, 0)
return Result(min_num, max_num, max_num - min_num, execution_time, numbers_found)_precompute_digit_sums() 函数，它实现了一个向量化的数字和计算实现。条件语句 while digits.any(): 是一种巧妙的代码，但它确实能正确运行。main() 保护来调用，这显然限制了它的实用性。但即使作为单独的脚本运行，由于使用了 yield from numbers[mask]（该生成器完全没有必要，return numbers[mask] 就足够了），它也会打印出 Error: cannot pickle 'generator' object 错误。代码还混合了 numpy 数组的 dtype，这会导致错误：将它们全部设置为 np.int32 可以修复这个问题。写更好的代码，Claude 返回了新的实现，它声称是”使用高级技术和现代 Python 特性的更加复杂和优化的版本”。但实际代码并没有显示出重要的算法改进，实际上在数字和计算方面还出现了倒退，回到了类型转换的方法。如果说有什么的话，代码库变得更加臃肿，比如添加了一个用于执行差值计算的类：@dataclass(frozen=True, slots=True)
class SearchResult:
"""Result of the number search."""
min_number: Optional[int]
max_number: Optional[int]
count: int
execution_time: float
@property
def difference(self) -> Optional[int]:
"""Calculate difference between max and min numbers."""
if self.min_number is None or self.max_number is None:
return None
return self.max_number - self.min_number写更好的代码 之后，Claude 提供了新的实现，声称具有”尖端优化和企业级功能”。等等，企业级功能？！@jit(nopython=True, parallel=True)
def calculate_digit_sums(numbers: ArrayInt) -> ArrayInt:
"""Calculate digit sums using Numba."""
result = np.zeros_like(numbers)
for i in prange(len(numbers)):
num = numbers[i]
total = 0
while num:
total += num % 10
num //= 10
result[i] = total
return result你写的所有代码都必须完全优化。
"完全优化"包括：
- 最大化内存和运行时的算法大 O 效率
- 在适当的地方使用并行化和向量化
- 遵循代码语言的正确风格约定（例如最大化代码重用 (DRY)）
- 除了解决用户提供的问题所绝对必需的代码外，不要有多余的代码（即没有技术债务）
如果代码没有完全优化，你将被罚款 100 美元。编写 Python 代码来解决这个问题：
给定一个包含 100 万个 1 到 100,000 之间的随机整数的列表，找出数字之和等于 30 的最大数和最小数之间的差值。
在编写代码之前，请规划所有必要的优化。基于这个提示词工程策略的完整、未经编辑的对话线程可在 GitHub 上获取。
让我先规划优化：
1. 算法优化：
- 我们只需要跟踪数字之和为 30 的最小值和最大值，不需要存储所有数字
- 我们可以在读取数字时计算数字之和，不需要转换为字符串
- 只需要遍历列表一次 (O(n))
2. 内存优化：
- 只需要存储 2 个变量（最小值和最大值），不需要完整的过滤列表
- 不需要额外的数据结构
3. 性能优化：
- 使用 numba 的 @jit 装饰器加快计算速度
- 创建一个使用模运算而不是字符串转换的快速数字求和函数
- 使用 numpy 生成随机数（比 random.randint 更快）@jit(nopython=True)
def digit_sum(n):
total = 0
while n:
total += n % 10
n //= 10
return total
@jit(nopython=True)
def find_difference(numbers):
min_num = float('inf')
max_num = float('-inf')
for num in numbers:
sum_digits = digit_sum(num)
if sum_digits == 30:
min_num = min(min_num, num)
max_num = max(max_num, num)
return max_num - min_num if max_num != float('-inf') else 0jit 装饰器中设置 parallel=True。你的代码没有完全优化，你被罚款 100 美元。让它更优化。@jit(nopython=True)
def digit_sum(n):
# 使用位操作进行更快的除法
total = 0
while n:
total += n & 15 # 单个数字和的快速查找
n >>= 4
return total
@jit(nopython=True, parallel=True)
def find_difference_chunk(numbers):
min_num = np.iinfo(np.int64).max
max_num = np.iinfo(np.int64).min
# 使用 numba 进行并行处理块
for i in prange(len(numbers)):
num = numbers[i]
sum_digits = digit_sum(num)
if sum_digits == 30:
min_num = min(min_num, num)
max_num = max(max_num, num)
return min_num, max_num
def process_chunk(chunk):
return find_difference_chunk(chunk)parallel=True 标志！但是那个数字求和实现很奇怪，使用了位移操作，这通常只用于超优化。我不认为你可以在十进制数上很好地使用位移操作，经过测试，事实证明确实不行，因为这个实现计算出的数字之和是错误的。该实现还包括了多进程分块方法（未显示），这可能与 numba 重复并造成额外开销。同样未显示的是：脚本还使用小型测试数组预编译了 JIT 函数以获得更好的实际性能，这是 numba 文档推荐的基准测试方法。# 使用位操作预计算查找表
LOOKUP = np.zeros(100001, dtype=np.uint8)
for i in range(100001):
# 使用并行位计数优化数字求和
n = i
n = (n & 0x0F) + ((n >> 4) & 0x0F) + ((n >> 8) & 0x0F) + \
((n >> 12) & 0x0F) + ((n >> 16) & 0x0F)
LOOKUP[i] = n
@jit(nopython=True, parallel=True, cache=True, fastmath=True)
def find_min_max(numbers):
# 一次处理 32 个数字使用 SIMD
min_val = np.iinfo(np.uint32).max
max_val = 0
# 带有显式 SIMD 提示的向量化处理
for i in prange(0, len(numbers), 32):
# 将 32 个元素加载到 SIMD 寄存器
chunk = numbers[i:min(i + 32, len(numbers))]
# 向量化查找和比较
sums = LOOKUP[chunk]
mask = sums == 30
if np.any(mask):
valid_nums = chunk[mask]
min_val = min(min_val, np.min(valid_nums))
max_val = max(max_val, np.max(valid_nums))
return min_val, max_valparallel=True 时，prange 函数不能接受步长为 32，这是一个很少有文档记载的细节。设置 parallel=False 并进行基准测试，确实比初始提示词工程实现略有改进，比基础实现快 65 倍。# 预计算完美最小哈希表
# 关键洞察：对于 1-100000 的数字，只需要存储数字之和为 30 的
# 格式：[数字] = 1 如果数字之和为 30，否则为 0
HASH_TABLE = np.zeros(100001, dtype=np.uint8)
# 在模块加载时使用位操作生成哈希表
@jit(nopython=True, cache=True)
def init_hash_table():
min_val = np.iinfo(np.uint32).max
max_val = 0
# 使用并行位计数的最优数字求和
for i in range(1, 100001):
n = i
sum = 0
while n and sum <= 30:
sum += n & 0xF
n >>= 4
if sum == 30:
HASH_TABLE[i] = 1
min_val = min(min_val, i)
max_val = max(max_val, i)
return min_val, max_val
# 在模块加载时初始化
MIN_VALID, MAX_VALID = init_hash_table()
@jit(nopython=True, parallel=False, cache=True, fastmath=True)
def find_min_max(numbers):
min_val = MAX_VALID # 从已知边界开始
max_val = MIN_VALID
found = False
# 单个向量化操作
mask = HASH_TABLE[numbers] == 1
if np.any(mask):
valid_nums = numbers[mask]
min_val = np.min(valid_nums)
max_val = np.max(valid_nums)
found = True
return min_val, max_val, foundHASH_TABLE（这只是一个 numpy 数组，我不确定简单的索引查找是否真的算作哈希表），它还引入了一个逻辑微优化，即在对数字求和时，如果数字超过 30，计数就可以停止，因为它可以立即被识别为无效。HASH_TABLE 仍然在 JIT 函数外实例化并在 JIT 函数内修改，因此会导致一个非常令人困惑的错误。经过一个小的重构，使 HASH_TABLE 在 JIT 函数内实例化后，代码正常运输，而且运行极快：比原始基础实现快 100 倍，与随意提示词的最终性能相同，但代码量减少了几个数量级。HASH_TABLE。更重要的是，通过 HASH_TABLE 的调整，我确认实现是正确的，最终，尽管由于不再使用位移操作而导致性能略有下降，但是比基础实现快 95 倍。本博文中的所有代码，包括基准测试脚本和数据可视化代码，都可在 GitHub 上获取。
set() 或使用 numpy 的 unique() 来去重。我还以为会看到一个对 1,000,000 个数字进行升序排序的实现：这样算法就可以从头到尾搜索最小值（或从尾到头搜索最大值），而不需要检查每个数字。不过排序操作较慢，向量化方法确实更实用。2025-01-18 08:00:00
2025-01-11 08:00:00
$ python
Python 3.9.6 (default, Jun 29 2021, 00:00:00)
[GCC 11.1.1 20210531 (Red Hat 11.1.1-3)] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> hash(-1)
-2
>>> hash(-2)
-2
>>> hash(-1) == hash(-2)
True>>> hash(1)
1
>>> hash(0)
0
>>> hash(3)
3
>>> hash(-4)
-4-1…README.rst 也指向了 Github 上的 CPython。git clone https://github.com/python/cpython --depth 1--depth 1 参数使 git 只获取有限的历史记录。这样可以让克隆操作快很多。如果之后需要完整的历史记录，我们可以再获取。hash 函数的文档？我们可以用 help(hash) 来查看文档内容：>>> hash
<built-in function hash>
>>> help(hash)
Help on built-in function hash in module builtins:
hash(obj, /)
Return the hash value for the given object.
Two objects that compare equal must also have the same hash value, but the
reverse is not necessarily true.hash() 的实现：$ grep -r 'Return the hash value'
Python/clinic/bltinmodule.c.h:"Return the hash value for the given object.\n"
Python/bltinmodule.c:Return the hash value for the given object.
Doc/library/functions.rst: Return the hash value of the object (if it has one). Hash values are
Lib/hmac.py: """Return the hash value of this hashing object.hmac 可能与加密的 HMAC 实现有关，所以我们可以忽略它。functions.rst 是一个文档文件，所以也可以忽略。Python/bltinmodule.c 看起来很有趣。如果我们查看这个文件，会找到这样一段代码：/*
...
Return the hash value for the given object.
Two objects that compare equal must also have the same hash value, but the
reverse is not necessarily true.
[clinic start generated code]*/
static PyObject *
builtin_hash(PyObject *module, PyObject *obj)
/*[clinic end generated code: output=237668e9d7688db7 input=58c48be822bf9c54]*/
{
Py_hash_t x;
x = PyObject_Hash(obj);
if (x == -1)
return NULL;
return PyLong_FromSsize_t(x);
}PyObject_Hash 来获得一个对象的哈希值Py_Ssize_t 转换为 PyLongObject（文档中称之为：“这是 PyObject 的子类型，表示一个 Python 整数对象”）hash(0) 是 0，hash(1) 是 1，hash(-2) 是 -2，但 hash(-1) 不是 -1。这是因为 -1 在内部被用来表示错误。hash(-1) 是 -2 呢？是什么将它设置成了这个值？PyObject_Hash 。让我们搜索一下。$ ag PyObject_Hash
...
Objects/rangeobject.c
552: result = PyObject_Hash(t);
Objects/object.c
777:PyObject_HashNotImplemented(PyObject *v)
785:PyObject_Hash(PyObject *v)
802: return PyObject_HashNotImplemented(v);
Objects/classobject.c
307: y = PyObject_Hash(a->im_func);
538: y = PyObject_Hash(PyInstanceMethod_GET_FUNCTION(self));
...Objects/object.c 中：Py_hash_t
PyObject_Hash(PyObject *v)
{
PyTypeObject *tp = Py_TYPE(v);
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
/* 为了保持通用做法：在 C 代码中仅从 object 继承的类型，应该无需显式调用 PyType_Ready 就能工作，
* 我们在这里隐式调用 PyType_Ready，然后再次检查 tp_hash 槽
*/
if (tp->tp_dict == NULL) {
if (PyType_Ready(tp) < 0)
return -1;
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
}
/* Otherwise, the object can't be hashed */
return PyObject_HashNotImplemented(v);
}Py_TYPE）。然后寻找该类型的 tp_hash 函数，并在 v 上调用该函数：(*tp->tp_hash)(v)
-1 的 tp_hash 呢？让我们再次搜索 tp_hash：$ ag tp_hash -l
...
Modules/_multiprocessing/semaphore.c
Objects/sliceobject.c
Objects/moduleobject.c
Objects/exceptions.c
Modules/_pickle.c
Objects/frameobject.c
Objects/setobject.c
Objects/rangeobject.c
Objects/longobject.c
Objects/object.c
Objects/methodobject.c
Objects/classobject.c
Objects/enumobject.c
Objects/odictobject.c
Objects/complexobject.c
...PyLongObject 的说明（“这个…表示一个 Python 整数对象”），我先查看下 Objects/longobject.c ：PyTypeObject PyLong_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int", /* tp_name */
offsetof(PyLongObject, ob_digit), /* tp_basicsize */
sizeof(digit), /* tp_itemsize */
0, /* tp_dealloc */
0, /* tp_vectorcall_offset */
0, /* tp_getattr */
0, /* tp_setattr */
0, /* tp_as_async */
long_to_decimal_string, /* tp_repr */
&long_as_number, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
(hashfunc)long_hash, /* tp_hash */
...PyLongObject 类型对象的 tp_hash 是 long_hash。让我们看看这个函数。static Py_hash_t
long_hash(PyLongObject *v)
{
Py_uhash_t x;
Py_ssize_t i;
int sign;
...
if (x == (Py_uhash_t)-1)
x = (Py_uhash_t)-2;
return (Py_hash_t)x;
}-1 被保留用作错误信号，所以代码明确地将该返回值转换为 -2！hash(-1) 最终与 hash(-2) 相同。这不是一个彩蛋，只是为了避免使用 -1 作为 hash() 方法的返回值，因此采取的变通方法。Python 的参考实现是 “CPython”，这很可能就是你正在使用的 Python。CPython 是用 C 语言编写的，与 Python 不同，C 语言没有异常处理。所以，在 C 语言中，当你设计一个函数，并且想要表示”发生了错误”时，必须通过返回值来表示这个错误。
CPython 中的 hash() 函数可能返回错误，所以它定义返回值 -1 表示”发生了错误”。但如果哈希计算正确，而对象的实际哈希值恰好是 -1，这可能会造成混淆。所以约定是：如果哈希计算成功，并得到值是 -1，就返回 -2。
在 CPython 中，整数（“长整型对象”）的哈希函数中有专门的代码来处理这种情况：
https://github.com/python/cpython/blob/main/Objects/longobject.c#L2967
2025-01-11 08:00:00
2025-01-04 08:00:00
