java - 在一组 4 个数字中查找出现次数最多的最有效算法

Question

我正在逐字节读取四个文件，并比较所有这四个字节，从这四个字节中得出最后一个字节。它的工作方式是:

1. 如果所有字节都是0，则输出0
2. 如果除 1 个字节之外的所有字节都是 0，则输出奇数字节输出(如果字节是 0, 0, 1, 0，那么我将输出1)
3. 如果2个字节是0，那么我随机输出一个非0字节
4. 如果 1 个字节是 0，那么我输出其他 3 个中出现次数最多的字节，否则如果出现平局，我从该集合中输出一个随机字节
5. 如果所有字节都不是0，那么我输出出现次数最多的字节，否则如果出现平局，我从该集合中输出一个随机字节

需要注意的重要一点是，“随机”并不一定是字面上的随机，我可以选择最方便的。

所以我对此进行了一些思考，但我仍然无法想出从这些数字中获取输出的绝对最快的方法。我注意到的一件事是，如果我读取的前两个字节相同且非零，那么我可以跳过接下来的两个字节，只输出前两个字节之一。如果前三个字节是0，那么我可以输出最后一个字节。我还可以用第一个字节和第二个字节检查第三个字节，看它们是否相等，这样我就可以避免进入第 4 个字节，但我需要它尽可能高效。我需要运行这个算法大约 80 亿次，所以每一点都很重要 =)

那么无论如何，最有效的方法是什么？ (伪代码？或其他)

这是程序的样子(至少是它的外壳):

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;

public class reconstructerv2 {
   public static void main(String[] args) throws IOException {

      FileInputStream in1 = null;
      FileInputStream in2 = null;
      FileInputStream in3 = null;
      FileInputStream in4 = null;
      FileOutputStream out = null;  

      try {
         in1 = new FileInputStream("1.dd");
         in2 = new FileInputStream("2.dd");
         in3 = new FileInputStream("3.dd");
         in4 = new FileInputStream("4.dd");
         BufferedInputStream in1b = new BufferedInputStream(in1);
         BufferedInputStream in2b = new BufferedInputStream(in2);
         BufferedInputStream in3b = new BufferedInputStream(in3);
         BufferedInputStream in4b = new BufferedInputStream(in4);
         out = new FileOutputStream("final.dd");
         int a;
         int b;
         int c;
         int d;
         int o; 

         while ((a = in1.read()) != -1) {
            b = in2.read();
            if (a == b && a != 0)
               o = a;
            else {
               c = in3.read();
               d = in4.read();
            }
            System.out.println((byte) c);
            out.write((byte) o);
         }
      } finally {
         if (in1 != null) {
            in1.close();
            in2.close();
            in3.close();
            in4.close();
         }
         if (out != null) {
            out.close();
         }
      }
   }
}

编辑:80 亿，而不是 800 万

EDIT2:正如评论中所指出的，由于同步，我不能跳过读取字符。

Answer 1

If all bytes are 0, then output 0

输出a+b+c+d。

If all but 1 byte are 0, then output the odd-byte-out (If the bytes were 0,0,1,0, then I would output a 1)

同上。这已经为您节省了一个案例。如果任意三个字节为零，则输出和。

If 2 bytes are 0, then I randomly output one of the non-0 bytes If 1 byte is 0, then I output the most occurring byte from the other 3, or otherwise in case of a tie I output a random byte from that set If all bytes are non-0, then I output the most occurring byte, or otherwise in case of a tie I output a random byte from that set

这些案例其实都是一样的。输出出现次数最多的非零字节，或者在出现平局时输出一个随机字节。

所以实际上只有两种情况需要考虑:至少三个零字节，以及两个或更少。

事实上所有情况都是一样的。您可以将上面的第二种解决方案应用于所有情况。根本不将它们分开可能会更快。

但首先在那些 FileInputStreams 周围添加了 BufferedInputStreams。