什麼是未優化此代碼？

Question

我寫上interviewstreet一個問題的解決方案，這是問題的描述：

https://www.interviewstreet.com/challenges/dashboard/#problem/4e91289c38bfd

下面是他們給出的解決方案：

https://gist.github.com/1285119

這裏是解決方案，我編碼：

#include<iostream> 
#include <string.h> 
using namespace std; 
#define LOOKUPTABLESIZE 10000000 
int popCount[2*LOOKUPTABLESIZE]; 
int main() 
{ 
int numberOfTests = 0; 
cin >> numberOfTests; 

for(int test = 0;test<numberOfTests;test++) 
{ 
    int startingNumber = 0; 
    int endingNumber = 0; 
    cin >> startingNumber >> endingNumber; 

    int numberOf1s = 0; 


    for(int number=startingNumber;number<=endingNumber;number++) 
    { 
     if(number >-LOOKUPTABLESIZE && number < LOOKUPTABLESIZE) 
     { 
      if(popCount[number+LOOKUPTABLESIZE] != 0) 
      { 
       numberOf1s += popCount[number+LOOKUPTABLESIZE]; 
      } 
      else 
      { 
       popCount[number+LOOKUPTABLESIZE] =__builtin_popcount (number); 
       numberOf1s += popCount[number+LOOKUPTABLESIZE]; 
      } 
     } 
     else 
     { 
     numberOf1s += __builtin_popcount (number); 
     } 
    } 
    cout << numberOf1s << endl; 

} 

} 

能否請你指出我WH在我的代碼錯了？它只能通過3/10的測試。時間限制是3秒。

Answer 1

什麼是未優化此代碼？

算法。您正在循環

for(int number=startingNumber;number<=endingNumber;number++) 

計算或查找每個中的1位數。這可能需要一段時間。

一個好的算法使用一點數學來計算O(log n)時間內所有數字中的1位數0 <= k < n。

Here是十進制計數擴張的0執行，修改，使其計數1位應該不難。

Answer 2

當你看到這樣一個問題時，你需要把它分解成簡單的部分。

例如，假設你知道有多少1S有在所有的數字[0, N]（我們稱之爲ones(N)），那麼我們有：

size_t ones(size_t N) { /* magic ! */ } 

size_t count(size_t A, size_t B) { 
    return ones(B) - (A ? ones(A - 1) : 0); 
} 

這種方法的優點是one可能是簡單的程序例如count，例如使用遞歸。因此，第一次天真的嘗試將是：

// Naive 
size_t naive_ones(size_t N) { 
    if (N == 0) { return 0; } 
    return __builtin_popcount(N) + naive_ones(N-1); 
} 

但是這可能太慢了。即使簡單地計算count(B, A)的值，我們也會計算兩次naive_ones(A-1)！

幸運的是，總有記憶化來這裏協助，而轉型是相當簡單：

size_t memo_ones(size_t N) { 
    static std::deque<size_t> Memo(1, 0); 
    for (size_t i = Memo.size(); i <= N; ++i) { 
     Memo.push_back(Memo[i-1] + __builtin_popcnt(i)); 
    } 
    return Memo[N]; 
} 

這可能是因爲這可以幫助，但在內存方面的成本可能是...癱瘓。啊。想象一下，對於計算ones(1,000,000)，我們將在64位計算機上佔用8MB內存！更稀疏的記憶化可以幫助（例如，僅memoizing每8個或16個計數）：

// count number of ones in (A, B] 
static unoptimized_count(size_t A, size_t B) { 
    size_t result = 0; 
    for (size_t i = A + 1; i <= B; ++i) { 
     result += __builtin_popcount(i); 
    } 
    return result; 
} 

// something like this... be wary it's not tested. 
size_t memo16_ones(size_t N) { 
    static std::vector<size_t> Memo(1, 0); 
    size_t const n16 = N - (N % 16); 
    for (size_t i = Memo.size(); i*16 <= n16; ++i) { 
     Memo.push_back(Memo[i-1] + unoptimized_count(16*(i-1), 16*i); 
    } 
    return Memo[n16/16] + unoptimized_count(n16, N); 
} 

然而，儘管它能夠減少存儲成本，它並沒有解決的主要速度問題：我們必須至少使用__builtin_popcount B次！對於B的大數值，這是一個殺手。

---

上述解決方案機械，他們並不需要一個思想盎司。事實證明，面試不是關於編寫代碼，而是關於思考。

我們可以更有效地解決這個問題，而不是愚蠢地枚舉所有整數直到B？

讓我們來看看我們的大腦（相當驚人的花樣機）拿起考慮前幾個條目時：

N bin 1s ones(N) 
0 0000 0 0 
1 0001 1 1 
2 0010 1 2 
3 0011 2 4 
4 0100 1 5 
5 0101 2 7 
6 0110 2 9 
7 0111 3 12 
8 1000 1 13 
9 1001 2 15 
10 1010 2 17 
11 1011 3 20 
12 1100 2 22 
13 1101 3 25 
14 1110 3 28 
15 1111 3 32 

發現一個模式？我這樣做）;範圍8-15構建完全像0-7，但每行多一個=>它就像換位。而且這也很合乎邏輯，不是嗎？

因此，ones(15) - ones(7) = 8 + ones(7),ones(7) - ones(3) = 4 + ones(3)和ones(1) - ones(0) = 1 + ones(0)。

好了，讓我們這樣的公式：

• 提醒：ones(N) = popcount(N) + ones(N-1)（幾乎）定義
• 我們現在知道，ones(2**n - 1) - ones(2**(n-1) - 1) = 2**(n-1) + ones(2**(n-1) - 1)

讓我們隔離ones(2**n)，它更容易對付，請注意popcount(2**n) = 1：

• 重新組合：ones(2**n - 1) = 2**(n-1) + 2*ones(2**(n-1) - 1)
• 使用的定義：ones(2**n) - 1 = 2**(n-1) + 2*ones(2**(n-1)) - 2
• 簡化：ones(2**n) = 2**(n-1) - 1 + 2*ones(2**(n-1))，與ones(1) = 1。

快速完整性檢查：

1 = 2**0 => 1 (bottom) 
2 = 2**1 => 2 = 2**0 - 1 + 2 * ones(1) 
4 = 2**2 => 5 = 2**1 - 1 + 2 * ones(2) 
8 = 2**3 => 13 = 2**2 - 1 + 2 * ones(4) 
16 = 2**4 => 33 = 2**3 - 1 + 2 * ones(8) 

看起來像它的作品！

---

雖然我們沒有完成。 A和B可能不一定是2的冪，並且如果我們必須從2**n到2**n + 2**(n-1)仍然是O（N）！另一方面，如果我們設法以基數2表示數字，那麼我們應該能夠利用我們新獲得的公式。主要優點是表示中只有log2（N）位。

讓我們挑一個例子，瞭解它是如何工作的：13 = 8 + 4 + 1

1 -> 0001 
4 -> 0100 
8 -> 1000 
13 -> 1101 

...然而，計數不只是單純的總和：

ones(13) != ones(8) + ones(4) + ones(1) 

讓我們表達出來的「換位」戰略，而不是條款：

ones(13) - ones(8) = ones(5) + (13 - 8) 

ones(5) - ones(4) = ones(1) + (5 - 4) 

好，容易與一點遞歸的事。

#include <cmath> 
#include <iostream> 

static double const Log2 = log(2); 

// store ones(2**n) at P2Count[n] 
static size_t P2Count[64] = {}; 

// Unfortunately, the conversion to double might lose some precision 
// static size_t log2(size_t n) { return log(double(n - 1))/Log2 + 1; } 

// __builtin_clz* returns the number of leading 0s 
static size_t log2(size_t n) { 
    if (n == 0) { return 0; } 
    return sizeof(n) - __builtin_clzl(n) - 1; 
} 

static size_t ones(size_t n) { 
    if (n == 0) { return 0; } 
    if (n == 1) { return 1; } 

    size_t const lg2 = log2(n); 
    size_t const np2 = 1ul << lg2; // "next" power of 2 

    if (np2 == n) { return P2Count[lg2]; } 

    size_t const pp2 = np2/2; // "previous" power of 2 

    return ones(pp2) + ones(n - pp2) + (n - pp2); 
} // ones 

// reminder: ones(2**n) = 2**(n-1) - 1 + 2*ones(2**(n-1)) 
void initP2Count() { 
    P2Count[0] = 1; 

    for (size_t i = 1; i != 64; ++i) { 
     P2Count[i] = (1ul << (i-1)) - 1 + 2 * P2Count[i-1]; 
    } 
} // initP2Count 

size_t count(size_t const A, size_t const B) { 
    if (A == 0) { return ones(B); } 

    return ones(B) - ones(A - 1); 
} // count 

並有demonstration：

int main() { 
    // Init table 
    initP2Count(); 
    std::cout << "0: " << P2Count[0] << ", 1: " << P2Count[1] << ", 2: " << P2Count[2] << ", 3: " << P2Count[3] << "\n"; 

    for (size_t i = 0; i != 16; ++i) { 
     std::cout << i << ": " << ones(i) << "\n"; 
    } 

    std::cout << "count(7, 14): " << count(7, 14) << "\n"; 
} 

勝利！

注：丹尼爾·費舍爾指出，這無法說清負數（但假設兩個補充它可以從他們的肯定計推斷）。