快速查找数组中元素的数量

Question

我有一个数组，大小可以达到10000.它只包含1/2/3/4。我需要找出阵列中有多少个1s，2s，3s和4s。最快的做法是什么？我的使用语言是Java。我的一段代码 -

for(int i=0; i<myArray.length;i++){ 
      int element = myArray[i]; 
      if(element == 1){ 
       onesCount++; 
      } 
      else if(element == 2){ 
       twosCount++; 
      } 
      else if(element == 3){ 
       threesCount++; 
      } 
      else 
       foursCount++; 
} 

我希望有一个很好的解决方案。

Answer 1

int count[5]; //initialize this to 0 
for(int i = 0; i<n; i++) 
{ 
count[array[i]]+=1; 
} 

Answer 2

您可以在数组中使用一次。

只要有自己的四个要素，分别代表你的价值观之一（1/2/3/4）的数组和原始数组中的每个元素，你的“伯爵”阵列中增加了计数，在相应的地方。 这将使它O（n）。

Answer 3

如果您可以改为使用地图或自定义类。如果你不能遍历整个数组。如果你现在不用担心性能问题，那么我只需要进行迭代。

Answer 4

您将拥有用于数组条目的单独计数器。每个将在一个新的匹配数量递增被发现，所以你必须访问每一个指数至少一次，也就是说，你将有一个算法O（n）的时间工作。开关语句可能是首选，而不是多个if-else语句：

int[] array = new int[10000]; 
// ... populate array 
int[] counters = new int[4]; 

for (int i = 0; i < array.length; i++) 
{ 
    int temp = array[i]; 
    switch (temp) { 
    case 1: 
     counters[0]++; 
     break; 
    case 2: 
     counters[1]++; 
     break; 
    case 3: 
     counters[2]++; 
     break; 
    case 4: 
     counters[3]++; 
     break; 
    default: 
     // to do. 
    } 
} 

Answer 5

没有解决方案比您的解决方案更好。可以更灵活，但不会更快。一切都必须至少通过整个阵列。

的性能优化的唯一区域是通过跟踪计数器作为阵列被更新，以避免在执行此操作，例如。如果这是值得的麻烦（可能不是）取决于你需要多久做一次这样的事情，这个数组有多大，以及你需要做什么。

Answer 6

如果您使用的是Java 7，则可以使用Fork/Join Framework。 的复杂性仍然是O（N）...但它可能更快的大阵

Answer 7

如果开关的版本（deporter）或游牧的版本不是最好的，试试这个：

for (int i = 0; i < myArray.length; i++) { 
    int element = myArray[i]; 
    if (element > 2) { 
     if (element == 4) { 
      foursCount++; 
     } else 
      threesCount++; 
    } else { 
     if (element == 2) 
      twosCount++; 
     else 
      onesCount++; 
    } 
} 

它可以节省少量的比较。但这取决于真实的数据。如果你对数据感到幸运，那么简单的版本可能会做得更好。

除此之外，采用并行始终是值得大数据一试。

Answer 8

我不认为你会得到比这更快：

final int[] counts = new int[5]; 
final int length = array.length - 1; 
for (int i = 0; i < length; i++) { 
    counts[array[i]]++; 
} 

注意的是，在为循环，array.length未被引用。它被放到一个本地final int中，这样可以避免在每次迭代中对array.length进行解引用。

我为基准此与使用一个开关此方法..case语句，只有局部堆栈变量：

int count1 = 0; 
    int count2 = 0; 
    int count3 = 0; 
    int count4 = 0; 

    for (int i = array.length - 1; i >= 0; i--) { 
     switch (array[i]) { 
     case 1: 
      count1++; 
      break; 
     case 2: 
      count2++; 
      break; 
     case 3: 
      count3++; 
      break; 
     case 4: 
      count4++; 
      break; 
     } 
    } 

结果是第一种方法花了17300纳秒，而switch..case方法了79800个纳秒。 [更新：忘了划分纳秒十。我运行每种方法10次。]

注意：我做基准测试之前先提醒虚拟机。