在 Java 中，如何有效地从字节数组的开头和结尾修剪 0

Question

出于我无法控制的原因，我需要解析一个巨大的文件，该文件的开头和结尾都有大量的空字节，以及一小部分实际有效的(最多 5 KB(。这是我想出的代码：

@NonNull
public static byte[] readFileToByteArray(@NonNull File file, boolean bTrimNulls) throws IOException {
byte[] buffer = new byte[(int) file.length()];
FileInputStream fis = null;
try {
fis = new FileInputStream(file);
if (fis.read(buffer) == -1) {
throw new IOException("EOF reached while trying to read the whole file");
}
} finally {
closeSafely(fis);
}
if (!bTrimNulls) {
return buffer;
}
int nFirstValidByteIndex = 0;
for (int i = 0; i < buffer.length; i++) {
if (buffer[i] != 0) {
nFirstValidByteIndex = i;
break;
}
}
int nLastValidByteIndex = 0;
for (int i = buffer.length - 1; i > 0; i--) {
if (buffer[i] != 0) {
nLastValidByteIndex = i;
break;
}
}
return copyBufferRange(buffer, nFirstValidByteIndex, nLastValidByteIndex + 1);
}

有没有更好的选择？

编辑：缓冲区中的有效字节对应于 XML 文件。

Answer 1

我认为您的解决方案相当有效。实际上，您正在从数组的两端查看前 1 的索引，然后创建一个数据子数组。

为什么你觉得你需要改进你的算法？

小心：过早的优化是编程中所有邪恶(或至少大部分(的根源，引用唐纳德·高德纳的话

Answer 2

您的代码的时间复杂度为 n，正如您所说，这对于大文件来说可能太多了。幸运的是，我们知道非零部分的最大大小为 m，因此我们可以以 m 为步长搜索文件。如果我们错过了(在有效载荷中间打了一个零(，我们需要重复它，直到找到它。因此，如果有效载荷中零的概率足够低，则复杂度约为 n/m。

import java.util.Arrays;
import java.util.Random;
class Test
{
public static int findNonZero(byte[] sparse, int max)
{
// looks quadratic but isn't in practice if the probability of zero in the payload is low, i.e. 1/256 for random values
for(int offset=0;offset<max;offset++)
{
for(int i=0;(i+offset)<sparse.length; i+=max)
{
if(sparse[i+offset]!=0)
{
return i+offset;                    
}
}
}
// in production code you could handle this differently but this is just an example
throw new RuntimeException("Nonzero value not found");
}
public static byte[] trim(byte[] sparse, int max)
{
int index = findNonZero(sparse, max);
// go to the left and go to the right until you find (max) zeroes
int from = ...
int to = ...
return Arrays.copyOfRange(sparse, from, to);        
}
public static void main(String[] args)
{
// create test data
int size = 5000;
byte[] test = new byte[1_000_000_000];
byte[] payload = new byte[size];
Random r = new Random();
r.nextBytes(payload);
payload[0]=(byte)(r.nextInt(Byte.MAX_VALUE-1)+1); // ensure start isnt zero
payload[payload.length-1]=(byte)(r.nextInt(Byte.MAX_VALUE-1)+1);  // ensure end isnt zero
System.arraycopy(payload, 0, test, r.nextInt(test.length-size), size);
System.out.println(Arrays.equals(payload,trim(test,size)));
}
}

我把最后一部分留给了你，你需要向左走，然后去右边，直到你找到(最大(零并确定从和到索引。

您可以通过将后续偏移设置得更远来进一步提高实际性能，例如 offset_1 = 0、offset_2 = max/2、offset_3 = 1/4 max、offset_4 = 3/4 max 等。

Answer 3

代码很好。对于非常大的文件，将使用有限的缓冲区，FileChannel， 带有 ByteBuffer 的 SeekableByteChannel。

只是代码可以更好一点。参数Path而不是File将更通用、更现代。

public static byte[] readFileToByteArray(@NonNull File file, boolean trimNulls)
throws IOException {
Path path = file.toPath();
byte[] content = Files.readAllBytes(path);
if (trimNulls) {
int start = 0;
while (start < content.length && content[start] == 0) {
++start;
}
int end = content.length;
while (end > start && content[end - 1] == 0) {
--end;
}
content = Arrays.copyOfRange(content, start, end);
}
return content;
}