如何知道數組的值是否由零組成？

嘿，如果你能得到一個更具描述性的標題，請編輯它。如何知道數組的值是否由零組成？

我正在寫一個小算法，涉及檢查矩陣中的值。比方說：

char matrix[100][100]; 
char *ptr = &matrix[0][0];

想象我填充基質與一對夫婦值（5或6）的1，如：

matrix[20][35]=1; 
matrix[67][34]=1;

我怎麼能知道的間隔的二進制值矩陣爲零，例如（在僞代碼中）

if((the value from ptr+100 to ptr+200)==0){ ... // do something

我想再次拿起c/C++。應該有選擇的一個幾百字節（這些都是彼此相鄰）的方式，並檢查它們的值都是零，而不必逐個檢查。（考慮char是一個字節）

來源

2010-02-09 fmsf

也許我誤解了這個問題，但是每當你想看'n'項目時，你都在看O（n）。在小於O（n）的時間內檢查'n'項目沒有魔法巫術方法。 – 2010-02-09 01:34:28

我知道，但是如果我能夠降低N，最終的價值總是會下降:)寶貴的時間，我正在和一些朋友進行一次小小的比賽，看看誰的速度更快。 – fmsf 2010-02-09 01:37:04

如果你像「char matrix [100] [100];」那樣初始化矩陣，它們不能保證全部爲0.嘗試「char matrix [100] [100] = {0};」 – Ponkadoodle 2010-02-09 01:57:02

你可以使用std :: find_if。

bool not_0(char c) 
{ 
    return c != 0; 
} 

char *next = std::find_if(ptr + 100, ptr + 200, not_0); 
if (next == ptr + 200) 
    // all 0's

您還可以使用粘合劑除去遊離功能（雖然我覺得粘合劑是很難讀）：

char *next = std::find_if(ptr + 100, ptr + 200, 
          std::bind2nd(std::not_equal_to<char>(), 0));

蕩，我只是注意到請求不被字節做到這一點字節。儘管隱藏，find_if仍然會逐字節地執行。你將不得不一一做這個，儘管使用更大的類型會有所幫助。這是我的最終版本。

template <class T> 
bool all_0(const char *begin, const char *end, ssize_t cutoff = 10) 
{ 
    if (end - begin < cutoff) 
    { 
     const char *next = std::find_if(begin, end, 
      std::bind2nd(std::not_equal_to<char>(), 0)); 
     return (next == end); 
    } 
    else 
    { 
     while ((begin < end) && ((reinterpret_cast<uintptr_t>(begin) % sizeof(T)) != 0)) 
     { 
      if (*begin != '\0') 
       return false; 

      ++begin; 
     } 

     while ((end > begin) && ((reinterpret_cast<uintptr_t>(end) % sizeof(T)) != 0)) 
     { 
      --end; 

      if (*end != '\0') 
       return false; 
     } 

     const T *nbegin = reinterpret_cast<const T *>(begin); 
     const T *nend = reinterpret_cast<const T *>(end); 

     const T *next = std::find_if(nbegin, nend, 
      std::bind2nd(std::not_equal_to<T>(), 0)); 
     return (next == nend); 
    } 
}

這樣做首先檢查數據是否足夠長，以使其值得更復雜的算法。我不是100％肯定這是必要的，但你可以調整最低限度的必要條件。

假設數據足夠長，它首先將開始和結束指針對齊，以匹配用於比較的類型的對齊方式。然後它使用新類型來檢查大部分數據。

我會建議使用：

all_0<int>(); // 32 bit platforms 
all_0<long>(); // 64 bit LP64 platforms (most (all?) Unix platforms) 
all_0<long long>() // 64 bit LLP64 platforms (Windows)

來源

2010-02-09 01:35:51

你可以投您的指針爲int *，然後每次檢查四個字節而不是一個。

來源

2010-02-09 01:34:06

我想這樣做是爲了增加一倍或甚至更多的字節數 – fmsf 2010-02-09 01:36:26

除了你需要保證'0.0'確實被存儲爲全零位。此外，現在您在某些處理器上有潛在的對齊問題。 – 2010-02-09 01:39:42

不要使用雙打，你會從整數/浮點轉換中獲得巨大的性能損失。但是，如果使用long long，則可能會在64位處理器上獲得更多性能。 – 2010-02-09 01:49:24

有沒有內置的語言功能來做到這一點，也沒有一個標準的庫函數來做到這一點。 memcmp()可以工作，但你需要第二個數組的所有零來比較;該陣列必須很大，並且在進行比較時也會消耗不必要的內存帶寬。

你自己寫這個函數，並不難。如果這確實是您的應用程序的瓶頸（您應該只能得出結論概要分析），然後重新組裝該函數。

來源

2010-02-09 01:34:56

您標記了這個C++，因此您可以使用指針作爲迭代器，並使用stl算法。的std ::最大。然後看看最大值是否爲0。

來源

2010-02-09 01:35:42

在簽名爲char的平臺上，如果所有非0字符都有高位設置。 – 2010-02-09 01:48:59

有沒有辦法告訴數組是否比高於通過檢查一個所有元素一個其他任何非零值。但是如果你從一個你知道全部爲零的數組開始，那麼你可以維護一個標誌來表示數組的零狀態。

std::vector<int> vec(SIZE); 
bool allzeroes = true; 

// ... 

vec[SIZE/2] = 1; 
allzeroes = false; 

// ... 

if(allzeroes) { 
    // ... 
}

來源

2010-02-09 01:45:59 wilhelmtell

保留數組中的元素0，將其設置爲全零。

使用memcmp比較兩個元素中的對應範圍。

來源

2010-02-09 02:17:15 EvilTeach

如何知道數組的值是否由零組成？

回答

相關問題