Самый быстрый способ суммировать целые числа в текстовом файле
Вопрос
Предположим, у вас есть большой текстовый файл ASCII со случайным неотрицательным целым числом в каждой строке, каждый в диапазоне от 0 до 1000 000 000. В файле 100 000 000 строк. Какой самый быстрый способ прочитать файл и вычислить сумму всех целых чисел?
Ограничение: у нас есть 10 МБ ОЗУ для работы. Размер файла составляет 1 ГБ, поэтому мы не хотим читать все это, а затем обрабатывать его.
Вот различные решения, которые я пробовал. Я нашел результаты довольно удивительными.
Что-нибудь быстрее, что я пропустил?
Обратите внимание: все значения времени, указанные ниже, предназначены для выполнения алгоритма в общей сложности 10 раз (запуск один раз и сброс; таймер запуска; запуск 10 раз; таймер остановки). Машина довольно медленная Core 2 Duo.
Метод 1: естественный подход
Первое, что нужно попробовать, это очевидный подход:
private long sumLineByLine() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String line;
long total = 0;
while ((line = br.readLine()) != null) {
int k = Integer.parseInt(line);
total += k;
}
br.close();
return total;
}
Обратите внимание, что максимально возможное возвращаемое значение составляет 10^17, что все еще легко вписывается в longтак что нам не нужно беспокоиться о переполнении.
На моей машине этот прогон 11 раз и дисконтирование первого запуска занимает около 92,9 секунды.
Способ 2: незначительная настройка
Вдохновленный комментарием к этому вопросу, я старался не создавать новый int k сохранить результат анализа строки и вместо этого просто добавить проанализированное значение непосредственно в total, Итак, это:
while ((line = br.readLine()) != null) {
int k = Integer.parseInt(line);
total += k;
}
становится так:
while ((line = br.readLine()) != null)
total += Integer.parseInt(line);
Я был уверен, что это не будет иметь никакого значения, и подумал, что весьма вероятно, что компилятор сгенерирует один и тот же байт-код для двух версий. Но, к моему удивлению, это немного сбрило время: у нас осталось 92,1 секунды.
Способ 3: ручной анализ целого числа
Что меня беспокоит в коде, так это то, что мы String в int, а затем добавить его в конце. Разве это не может быть быстрее добавить, как мы идем? Что произойдет, если мы разберем String сами? Что-то вроде этого...
private long sumLineByLineManualParse() throws NumberFormatException,
IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String line;
long total = 0;
while ((line = br.readLine()) != null) {
char chs[] = line.toCharArray();
int mul = 1;
for (int i = chs.length - 1; i >= 0; i--) {
char c = chs[i];
switch (c) {
case '0':
break;
case '1':
total += mul;
break;
case '2':
total += (mul << 1);
break;
case '4':
total += (mul << 2);
break;
case '8':
total += (mul << 3);
break;
default:
total += (mul*((byte) c - (byte) ('0')));
}
mul*=10;
}
}
br.close();
return total;
}
Это, я думал, может сэкономить немного времени, особенно с некоторыми оптимизациями битового сдвига для выполнения умножения. Но накладные расходы на преобразование в массив символов должны затмить любые выгоды: теперь это занимает 148,2 секунды.
Способ 4: обработка в двоичном формате
Последнее, что мы можем попробовать - это обработать файл как двоичные данные.
Разбор целого числа с фронта неудобен, если вы не знаете его длины. Разобрать его в обратном направлении гораздо проще: первая цифра, с которой вы сталкиваетесь, - это единицы, следующая - десятки и так далее. Так что самый простой способ приблизиться ко всему - это прочитать файл задом наперед.
Если мы выделим byte[] буфер (скажем) 8 МБ, мы можем заполнить его последними 8 МБ файла, обработать его, затем прочитать предыдущие 8 МБ и так далее. Мы должны быть немного осторожны, чтобы не испортить число, которое мы находимся в процессе анализа при переходе к следующему блоку, но это единственная проблема.
Когда мы сталкиваемся с цифрой, мы добавляем ее (соответственно умножаемую в соответствии с ее положением в цифре) к итоговому значению, а затем умножаем коэффициент на 10, чтобы мы были готовы к следующей цифре. Если мы сталкиваемся с чем-то, что не является цифрой (CR или LF), мы просто сбрасываем коэффициент.
private long sumBinary() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[8*1024*1024];
int mul = 1;
long total = 0;
while (lastRead>0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead-len);
raf.readFully(buf, 0, len);
lastRead-=len;
for (int i=len-1; i>=0; i--) {
//48 is '0' and 57 is '9'
if ((buf[i]>=48) && (buf[i]<=57)) {
total+=mul*(buf[i]-48);
mul*=10;
} else
mul=1;
}
}
raf.close();
return total;
}
Это работает за 30,8 секунды! Это увеличение скорости в 3 раза по сравнению с предыдущим лучшим.
Последующие вопросы
- Почему это намного быстрее? Я ожидал, что это победит, но не так впечатляюще. Это в основном накладные расходы на преобразование в
String? И все беспокойство за кулисами о наборах символов и тому подобное? - Можем ли мы сделать что-то лучше, используя
MappedByteBufferпомогать? У меня такое ощущение, что накладные расходы на вызов методов для чтения из буфера замедлили бы работу, особенно при чтении в обратном направлении из буфера. - Было бы лучше читать файл вперед, а не назад, но все же сканировать буфер назад? Идея заключается в том, что вы читаете первую часть файла, а затем сканируете в обратном направлении, но отбрасываете половину числа в конце. Затем, когда вы читаете следующую порцию, вы устанавливаете смещение так, чтобы вы читали с начала числа, от которого вы отказались.
- Есть ли что-то, о чем я не подумала, что может иметь существенное значение?
Обновление: более удивительные результаты
Сначала наблюдение. Это должно было случиться со мной раньше, но я думаю, что причина неэффективности Stringна основе чтения не так много времени, затрачиваемого на создание всех String объекты, но тот факт, что они такие недолговечные: у нас есть 100 000 000 из них для сборщика мусора. Это должно расстроить это.
Теперь некоторые эксперименты, основанные на ответах / комментариях, опубликованных людьми.
Я обманываю с размером буфера?
Одним из предложений было то, что с BufferedReader использует буфер по умолчанию 16 КБ, и я использовал буфер 8 МБ, я не сравниваю, как с как. Это должно быть быстрее, если вы используете больший буфер.
Вот такой шок. sumBinary() метод (метод 4) вчера выполнялся за 30,8 секунды с буфером 8 МБ. Сегодня код не изменился, направление ветра изменилось, и у нас 30,4 секунды. Если я уменьшу размер буфера до 16 КБ, чтобы увидеть, насколько медленнее он становится, он становится быстрее! Теперь он работает за 23,7 секунды. Псих. Кто видел это пришествие?!
Немного экспериментов показывает, что 16 КБ - это оптимально. Возможно, ребята из Java провели такие же эксперименты, и поэтому они пошли с 16KB!
Проблема связана с вводом / выводом?
Я тоже думал об этом. Сколько времени тратится на доступ к диску и сколько на перебор номера? Если это почти весь доступ к диску, как предполагает хорошо поддерживаемый комментарий к одному из предложенных ответов, то мы не сможем добиться значительного улучшения независимо от того, что мы делаем.
Это легко проверить, запустив код со всеми комментариями, касающимися разбора и обработки чисел, но с чтением по-прежнему без изменений:
private long sumBinary() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int mul = 1;
long total = 0;
while (lastRead > 0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead - len);
raf.readFully(buf, 0, len);
lastRead -= len;
/*for (int i = len - 1; i >= 0; i--) {
if ((buf[i] >= 48) && (buf[i] <= 57)) {
total += mul * (buf[i] - 48);
mul *= 10;
} else
mul = 1;
}*/
}
raf.close();
return total;
}
Теперь это выполняется за 3,7 секунды! Это не похоже на I/O, связанный со мной.
Конечно, некоторая скорость ввода-вывода будет зависеть от попаданий в дисковый кеш. Но дело не в этом: мы все равно тратим 20 секунд процессорного времени (это также подтверждается использованием Linux time команда), который достаточно большой, чтобы попытаться уменьшить его.
Сканирование вперед, а не назад
В своем первоначальном посте я утверждал, что есть веская причина сканировать файл назад, а не вперед. Я не очень хорошо объяснил это. Идея заключалась в том, что если вы сканируете число вперед, вы должны накопить общее значение отсканированного числа, а затем добавить его. Если вы сканируете в обратном направлении, вы можете добавить его к совокупному итогу по мере продвижения. Мое подсознание имело какой-то смысл для себя (об этом позже), но я упустил один ключевой момент, который был указан в одном из ответов: для сканирования в обратном направлении я делал два умножения за итерацию, но с для сканирования вперед вам нужен только один. Итак, я кодировал версию для сканирования вперед:
private long sumBinaryForward() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int fileLength = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int acc = 0;
long total = 0;
int read = 0;
while (read < fileLength) {
int len = Math.min(buf.length, fileLength - read);
raf.readFully(buf, 0, len);
read += len;
for (int i = 0; i < len; i++) {
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
total += acc;
acc = 0;
}
}
}
raf.close();
return total;
}
Это выполняется за 20,0 секунд, опережая версию с обратным сканированием на расстояние. Ницца.
Кэш умножения
Однако ночью я понял, что, хотя я выполнял два умножения на одну итерацию, была возможность использовать кэш для хранения этих умножений, чтобы я мог избежать их выполнения во время обратной итерации. Мне было приятно видеть, когда я проснулся, что у кого-то была такая же идея!
Дело в том, что в числах, которые мы сканируем, есть не более 10 цифр и только 10 возможных цифр, поэтому только 100 возможных значений от цифры до совокупного итога. Мы можем предварительно вычислить их, а затем использовать их в коде обратного сканирования. Это должно превзойти версию с прямым сканированием, потому что теперь мы полностью избавились от умножений. (Обратите внимание, что мы не можем сделать это с прямым сканированием, потому что умножение происходит от аккумулятора, который может принимать любое значение до 10^9. Только в обратном случае оба операнда ограничены несколькими возможностями.)
private long sumBinaryCached() throws IOException {
int mulCache[][] = new int[10][10];
int coeff = 1;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++)
mulCache[i][j] = coeff * j;
coeff *= 10;
}
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int mul = 0;
long total = 0;
while (lastRead > 0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead - len);
raf.readFully(buf, 0, len);
lastRead -= len;
for (int i = len - 1; i >= 0; i--) {
if ((buf[i] >= 48) && (buf[i] <= 57))
total += mulCache[mul++][buf[i] - 48];
else
mul = 0;
}
}
raf.close();
return total;
}
Это выполняется за 26,1 секунды. Разочаровывает, если не сказать больше. Чтение в обратном направлении менее эффективно с точки зрения ввода / вывода, но мы видели, что ввод / вывод здесь не является головной болью. Я ожидал, что это будет иметь большое положительное значение. Возможно, поиск в массиве такой же дорогой, как и умножения, которые мы заменили. (Я попытался сделать массив 16x16 и использовать битовые сдвиги для индексации, но это не помогло.)
Похоже, что сканирование вперед, где это.
Использование MappedByteBuffer
Следующее, что нужно добавить, это MappedByteBuffer, чтобы увидеть, если это более эффективно, чем использование сырых RandomAccessFile, Не нужно много изменений в коде.
private long sumBinaryForwardMap() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
byte buf[] = new byte[16 * 1024];
final FileChannel ch = raf.getChannel();
int fileLength = (int) ch.size();
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0,
fileLength);
int acc = 0;
long total = 0;
while (mb.hasRemaining()) {
int len = Math.min(mb.remaining(), buf.length);
mb.get(buf, 0, len);
for (int i = 0; i < len; i++)
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
total += acc;
acc = 0;
}
}
ch.close();
raf.close();
return total;
}
Это, кажется, немного улучшает ситуацию: сейчас у нас 19,0 секунд. Мы взяли еще одну секунду из наших личных лучших!
А как насчет многопоточности?
Один из предложенных ответов предполагает использование нескольких ядер. Мне немного стыдно, что этого не произошло со мной!
Ответ пришел на какую-то палку из-за предположения, что это проблема ввода-вывода. Это кажется немного резким, в свете результатов о I/O! Конечно, стоит попробовать в любом случае.
Мы сделаем это с помощью fork/join. Вот класс, представляющий результат вычисления для части файла, имея в виду, что может быть частичный результат слева (если мы начали с середины числа) и частичный результат справа (если буфер закончил половину через ряд). У класса также есть метод, позволяющий нам склеить два таких результата вместе в объединенный результат для двух смежных подзадач.
private class SumTaskResult {
long subtotal;
int leftPartial;
int leftMulCount;
int rightPartial;
public void append(SumTaskResult rightward) {
subtotal += rightward.subtotal + rightPartial
* rightward.leftMulCount + rightward.leftPartial;
rightPartial = rightward.rightPartial;
}
}
Теперь ключевой бит: RecursiveTask это вычисляет результат. Для небольших задач (менее 64 символов) он вызывает computeDirectly() рассчитать результат в одном потоке; для более крупных задач он разбивается на две части, решает две подзадачи в отдельных потоках, а затем объединяет результаты.
private class SumForkTask extends RecursiveTask<SumTaskResult> {
private byte buf[];
// startPos inclusive, endPos exclusive
private int startPos;
private int endPos;
public SumForkTask(byte buf[], int startPos, int endPos) {
this.buf = buf;
this.startPos = startPos;
this.endPos = endPos;
}
private SumTaskResult computeDirectly() {
SumTaskResult result = new SumTaskResult();
int pos = startPos;
result.leftMulCount = 1;
while ((buf[pos] >= 48) && (buf[pos] <= 57)) {
result.leftPartial = result.leftPartial * 10 + buf[pos] - 48;
result.leftMulCount *= 10;
pos++;
}
int acc = 0;
for (int i = pos; i < endPos; i++)
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
result.subtotal += acc;
acc = 0;
}
result.rightPartial = acc;
return result;
}
@Override
protected SumTaskResult compute() {
if (endPos - startPos < 64)
return computeDirectly();
int mid = (endPos + startPos) / 2;
SumForkTask left = new SumForkTask(buf, startPos, mid);
left.fork();
SumForkTask right = new SumForkTask(buf, mid, endPos);
SumTaskResult rRes = right.compute();
SumTaskResult lRes = left.join();
lRes.append(rRes);
return lRes;
}
}
Обратите внимание, что это работает на byte[]а не весь MappedByteBuffer, Причина в том, что мы хотим, чтобы доступ к диску был последовательным. Мы возьмем довольно большие чанки, разветвимся / соединимся, а затем перейдем к следующему чанку.
Вот метод, который делает это. Обратите внимание, что мы увеличили размер буфера до 1 МБ (ранее он был неоптимальным, но, кажется, более разумным).
private long sumBinaryForwardMapForked() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
ForkJoinPool pool = new ForkJoinPool();
byte buf[] = new byte[1 * 1024 * 1024];
final FileChannel ch = raf.getChannel();
int fileLength = (int) ch.size();
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0,
fileLength);
SumTaskResult result = new SumTaskResult();
while (mb.hasRemaining()) {
int len = Math.min(mb.remaining(), buf.length);
mb.get(buf, 0, len);
SumForkTask task = new SumForkTask(buf, 0, len);
result.append(pool.invoke(task));
}
ch.close();
raf.close();
pool.shutdown();
return result.subtotal;
}
Теперь вот душераздирающее разочарование: этот приятный многопоточный код теперь занимает 32,2 секунды. Почему так медленно? Я потратил довольно много времени на отладку этого, предполагая, что сделал что-то ужасно неправильно.
Оказывается, нужен был только один маленький твик. Я думал, что порог 64 между маленькой проблемой и большой проблемой был разумным; Оказывается, это было совершенно нелепо.
Думайте об этом так. Подзадачи имеют одинаковый размер, поэтому они должны быть выполнены в одно и то же время. Так что на самом деле нет смысла разбивать на куски больше, чем есть доступные процессоры. На машине, которую я использую, только с двумя ядрами, снижение до порогового значения 64 - это просто смешно: это просто увеличивает накладные расходы.
Теперь вы не хотите ограничивать вещи так, чтобы они использовали только два ядра, даже когда есть больше доступных. Возможно, правильнее всего было бы узнать количество процессоров во время выполнения и разбить их на множество частей.
В любом случае, если я изменю порог на 512 КБ (половину размера буфера), он завершится за 13,3 секунды. Переход к 128 КБ или 64 КБ позволит использовать больше ядер (до 8 или 16 соответственно) и не окажет значительного влияния на время выполнения.
Так что многопоточность имеет большое значение.
Это был довольно долгий путь, но мы начали с чего-то, что заняло 92,9 секунды, а сейчас мы сократились до 13,3 секунды... это в семь раз больше скорости исходного кода. И дело не в улучшении асимптотической (большой-ой) временной сложности, которая была линейной (оптимальной) с самого начала... все это касалось улучшения постоянного фактора.
Хороший день работы.
Я полагаю, мне следует попробовать использовать графический процессор дальше...
Постскриптум: генерация файла случайных чисел
Я сгенерировал случайные числа с помощью следующего кода, который я запустил и перенаправил в файл. Очевидно, я не могу гарантировать, что вы получите те же самые случайные числа, что и у меня:)
public static void genRandoms() {
Random r = new Random();
for (int i = 0; i < 100000000; i++)
System.out.println(r.nextInt(1000000000));
}
7 ответов
Я думаю, что есть другой способ сделать это.
Это классическая проблема многопроцессного программирования. На языке Си есть библиотека MPI, которая решает такие проблемы.
Идея состоит в том, чтобы разбить список целых чисел, например, на 4 части, и каждая часть суммируется различным процессом. После окончания процессы суммируются вместе.
В Java это можно сделать с помощью потоков (псевдопараллельность) и параллелизма Java.
Например, 4 разных темы, суммирующих 4 разных части списка. В конце они суммируются вместе.
Телефонные компании используют Grid Computers, которые используют эту технику параллельного программирования для суммирования своих транзакций.
Единственная проблема здесь (узкое место) - операция ввода-вывода. Чтение файла займет много времени. Если каким-то образом вы можете заставить несколько потоков читать разные части файла... Это очень сложный подход, и я думаю, что это не принесет много пользы, потому что диск не будет вращаться быстрее только потому, что он используется многими потоками, но есть другая техника выполнения подобных вещей. Вы можете прочитать больше об этом здесь: Доступ к файлу через несколько потоков и здесь Чтение одного файла с несколькими потоками : должно ускориться?
Вашим главным узким местом будет файл IO. Разбор и суммирование чисел не должны вносить вклад в алгоритм, поскольку это может быть сделано в отдельном потоке, пока File I/O ожидает диск.
Несколько лет назад я исследовал, как читать файлы максимально быстро, и наткнулся на несколько замечательных советов, которые я реализовал как процедуру сканирования, как показано ниже:
// 4k buffer size.
static final int SIZE = 4 * 1024;
static byte[] buffer = new byte[SIZE];
// Fastest because a FileInputStream has an associated channel.
private static void ScanDataFile(Hunter p, FileInputStream f) throws FileNotFoundException, IOException {
// Use a mapped and buffered stream for best speed.
// See: http://nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly
final FileChannel ch = f.getChannel();
long red = 0L;
do {
final long read = Math.min(Integer.MAX_VALUE, ch.size() - red);
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, red, read);
int nGet;
while (mb.hasRemaining() && p.ok()) {
nGet = Math.min(mb.remaining(), SIZE);
mb.get(buffer, 0, nGet);
for (int i = 0; i < nGet && p.ok(); i++) {
p.check(buffer[i]);
//size += 1;
}
}
red += read;
} while (red < ch.size() && p.ok());
// Finish off.
p.close();
ch.close();
f.close();
}
Вы можете настроить эту технику перед тестированием на скорость, так как она использует интерфейсный объект, называемый Hunter охотиться за данными.
Как вы можете видеть, этот совет был получен в 2008 году, и с тех пор в Java было много улучшений, поэтому это может и не дать улучшения.
добавленной
Я не проверял это, но это должно соответствовать вашим тестам и использовать ту же технику:
class Summer {
long sum = 0;
long val = 0;
public void add(byte b) {
if (b >= '0' && b <= '9') {
val = (val * 10) + (b - '0');
} else {
sum += val;
val = 0;
}
}
public long getSum() {
return sum + val;
}
}
private long sumMapped() throws IOException {
Summer sum = new Summer();
FileInputStream f = new FileInputStream(file);
final FileChannel ch = f.getChannel();
long red = 0L;
do {
final long read = Math.min(Integer.MAX_VALUE, ch.size() - red);
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, red, read);
int nGet;
while (mb.hasRemaining()) {
nGet = Math.min(mb.remaining(), SIZE);
mb.get(buffer, 0, nGet);
for (int i = 0; i < nGet; i++) {
sum.add(buffer[i]);
}
}
red += read;
} while (red < ch.size());
// Finish off.
ch.close();
f.close();
return sum.getSum();
}
Почему это намного быстрее?
Создание строки намного дороже, чем математика.
Можем ли мы сделать что-то лучше, чем с помощью справки MappedByteBuffer?
Немного да. Это то, что я использую. Это сохранить память в память копии. т.е. байт [] не требуется.
У меня такое ощущение, что накладные расходы на вызов методов для чтения из буфера замедляют процесс,
Методы становятся встроенными, если они просты.
особенно при чтении в обратном направлении из буфера.
Это не будет медленнее, на самом деле разбор вперед проще / быстрее, потому что вы используете один * вместо двух.
Было бы лучше читать файл вперед, а не назад, но все же сканировать буфер назад?
Я не понимаю, зачем вам вообще нужно читать задом наперед.
Идея заключается в том, что вы читаете первую часть файла, а затем сканируете в обратном направлении, но отбрасываете половину числа в конце. Затем, когда вы читаете следующую порцию, вы устанавливаете смещение так, чтобы вы читали с начала числа, от которого вы отказались.
звучит излишне сложно. Я прочитал бы за один проход, отображение памяти во всем файле за один раз. Нет необходимости использовать чанки, если размер файла не превышает 2 ГБ. и даже тогда я прочитал бы за один проход.
Есть ли что-то, о чем я не подумала, что может иметь существенное значение?
Если данные находятся в кеше на диске, это будет иметь большее значение, чем что-либо еще.
Вы можете пойти на больший размер буфера и более быстрое кодирование в String (в Unicode).
BufferedReader br = new BufferedReader(new InputStreamReader(
new FileInputStream(file), StandardCharsets.US_ASCII),
1_024_000_000);
Ваш метод устранения использования String с помощью двоичного InputStream/RandomAccessFile стоит того.
Тогда было бы неплохо, если бы исходные файлы были сжаты. Под Unix можно выбрать формат gzip, где xxx.txt.gz распаковывает xxx.txt, Это было бы читабельным с GZipInputStream, Преимущество заключается в ускорении передачи файлов в каталог сервера и из него.
Источник: http://nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly
Для лучшей производительности чтения Java нужно помнить четыре вещи:
- Минимизируйте операции ввода-вывода, читая массив за раз, а не байт за раз. Массив 8Kbyte - это хороший размер.
- Минимизируйте вызовы методов, получая данные за один раз, а не за один байт. Используйте индексирование массива, чтобы получить байты в массиве.
- Минимизируйте блокировки синхронизации потоков, если вам не нужна безопасность потоков. Либо сделайте меньше вызовов метода для поточно-безопасного класса, либо используйте не поточно-безопасный класс, такой как FileChannel и MappedByteBuffer.
- Минимизируйте копирование данных между JVM/OS, внутренними буферами и массивами приложений. Используйте FileChannel с отображением памяти или прямой или упакованный массив ByteBuffer.
Основываясь на этом комментарии: "Простое суммирование всех байтов происходит быстрее", я предлагаю вариант принятого ответа.
В принятом ответе предлагается разбить задачу на куски, вычислить сумму для каждого чака с помощью многопоточности и сложить их вместе в конце.
Эта идея может быть использована для уменьшения количества умножений до O(1) при обратном сканировании, без каких-либо поисков в таблице и без многопоточности (или комбинирования с многопоточностью). Просто воспользуйтесь преимуществом распределения умножения над сложением и добавьте все цифры в один аккумулятор, десятки в отдельный, сотни и тысячи в свои собственные аккумуляторы. Это не требует умножения вообще.
Этап сокращения, объединяющий результаты из нескольких потоков, также может быть выполнен с использованием аккумуляторов на место. Последний шаг вычисления итогов потребует умножения (или использования факта, что 10 имеет только два установленных бита и использует сдвиги битов и сложение), но достаточно только 9 умножений.
Здесь есть несколько вопросов.
- Любое решение, основанное на чтении строк, собирается обработать каждый символ дважды. Например, компиляторы этого не делают, они читают по одному символу за раз и отправляют его напрямую.
- Любое решение на основе
readLine()собирается создавать строки. - Вы используете разные размеры буфера.
- Вы используете разные технологии ввода / вывода.
- В некоторых случаях вы используете преобразование символов, а в других - нет.
- Вы слишком анализируете файл. Тебя не волнует, где находится пробел или сколько его там, если он отделяет числа друг от друга.
Мое решение:
BufferedInputStream bis = new BufferedInputStream(new FileInputStream(file), 8*1024*1024/2);
long total = 0;
int i;
while ((i = bis.read()) != -1)
{
byte b = (byte)i;
long number = 0;
while (b >= '0' && b <= '9')
{
number = number*10+b-'0';
if ((i = bis.read()) == -1)
break;
b = (byte)i;
}
total += number;
}