相关疑难解决方法(0)

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c) …

numpy.random.choice 允许从矢量加权选择,即

arr = numpy.array([1, 2, 3])
weights = numpy.array([0.2, 0.5, 0.3])
choice = numpy.random.choice(arr, p=weights) 

选择1概率为0.2,2选择概率为0.5,3选择概率为0.3.

如果我们想以矢量化的方式快速完成2D阵列(矩阵),每个行都是概率矢量,该怎么办？也就是说,我们想要一个随机矩阵的选择向量？这是超级慢的方式:

import numpy as np

m = 10
n = 100 # Or some very large number

items = np.arange(m)
prob_weights = np.random.rand(m, n)
prob_matrix = prob_weights / prob_weights.sum(axis=0, keepdims=True)

choices = np.zeros((n,))
# This is slow, because of the loop in Python
for i in range(n):
    choices[i] = np.random.choice(items, p=prob_matrix[:,i])

print(choices):

array([ 4.,  7.,  8.,  1.,  0.,  4.,  3.,  7.,  1., …

在JavaScript中对数字数组进行排序时,我意外地使用<而不是通常- - 但它仍然有效.我想知道为什么？

例:

var a  = [1,3,2,4]
a.sort(function(n1, n2){
    return n1<n2
})
// result is correct: [4,3,2,1]

一个不起作用的示例数组(感谢Nicolas的例子):

[1,2,1,2,1,2,1,2,1,2,1,2]

平衡二叉搜索树提供有O(log(n))保证的搜索时间.

Tango树实现了搜索,O(log(log(n))同时损害了每个节点的少量内存.虽然我从理论的角度理解log(n)并且log(log(n))产生了巨大的差异,但对于大多数实际应用来说,它几乎没有任何优势.

例如,即使对于像一个巨大的数字n = 10^20(就像几千PB级)之间的区别log(n) = 64和log(log(n)) = 6是相当微不足道的.那么Tango树有什么实际用途吗？

官方文档上是numpy 这么说的

返回给定形状和类型的新数组，而不初始化条目。

for np.empty，这意味着创建（分配）这个数组所花费的时间将是 O(1)，但一些简单的测试timeit表明情况并非如此：

>>> timeit.timeit(lambda: np.empty(100000000 ), number=10000)
0.2733485999999914
>>> timeit.timeit(lambda: np.empty(1000000000), number=10000)
0.8293009999999867

作为一个附带问题，未触及的np.empty数组中存在哪些值？它们都是非常小的值，但我希望它们只是该地址内存中存在的任何值。（示例数组：np.empty(2) = array([-6.42940774e-036, 2.07409447e-117])。这些看起来不像存储在内存中的东西）

这个问题出现在我的算法课上。这是我的想法：

我认为答案是否定的，具有O（n）的最坏情况时间复杂度的算法并不总是比O（n ^ 2）的最坏情况时间复杂度的算法快。

例如，假设我们有总时间函数S（n）= 99999999n和T（n）= n ^ 2。那么显然S（n）= O（n）和T（n）= O（n ^ 2），但是对于所有n <99999999，T（n）比S（n）更快。

这个推理有效吗？我有点怀疑，尽管这是一个反例，但它可能是错误观念的反例。

非常感谢！

任何算法示例我们何时比O(n logn)更喜欢Big O(n ^ 2)时间复杂度？我在某处看到过这个问题,但没有找到答案.