Загрузите пятьдесят миллионов целых чисел как можно быстрее в Java

Я прохожу через Project Euler . Многие из проблем связаны с вычислением простых чисел: это тип кода, который может быть извлечен в отдельный класс и повторно использован.

При вычислении простых чисел можно быстро выполнить определенные методы, я смог ускорить процесс «получения простых чисел», используя список простых чисел на диске и загружая их. Это на порядок быстрее, чем любой расчет, но по-прежнему занимает примерно три минуты загрузки с SSD.

Что я сделал:

  1. Я взял общедоступный список первых пятидесяти миллионов простых чисел (некоторые проблемы действительно используют значительную часть этих чисел).
  2. Я написал программу для преобразования чисел из их текстового представления в двоичный код с помощью DataOutputStream Java. Файл представляет собой просто пятьдесят миллионов четырехбайтовых целых чисел в строке.
  3. Ниже приведен метод утилиты, загружающий каждое целое число в массив с помощью DataInputStream. Он дает правильные результаты, но медленный.

Есть ли способ ускорить процесс загрузки 50 000 000 целых чисел? Если мне нужно предварительно обработать данные по-разному, я готов это сделать.

 import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;

public class Test {

  public static int[] loadByQuantity(int argNumPrimes) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream("primes.bin"))) {
      for (int i = 0; i < primes.length; ++i) {
        primes[i] = in.readInt();
      }
    }
    catch (IOException ex) {
      throw new RuntimeException(ex);
    }
    return primes;
  }

}
78 голосов | спросил user31517 28 Jpm1000000pmSat, 28 Jan 2017 22:03:15 +030017 2017, 22:03:15

5 ответов


95

Ваш код немного грязный, а имя файла, жестко закодированное в вашей функции, не очень велико. Кроме того, «Венгерская нотация» (используя такие вещи, как arg, чтобы префикс ваших параметров функции - обратите внимание, это параметр, а не аргумент, кстати) ... не является обычным.

С другой стороны, я понимаю, что это упражнение для тестирования производительности ... и речь идет не о возможности возобновления кода.

Тем не менее, я знаю по опыту, что повторное использование произойдет, и ваш код будет нуждаться в некоторых изменениях.

Я также знаю, по опыту, что IO с отображением памяти намного быстрее в Java, чем другие формы ввода-вывода, поэтому я решил, что у меня будет удар по этой проблеме.

Я взял мой основной генератор, который я ранее просматривал в обзоре кода ( Thread Safe Prime Generator ), и я сгенерировал первые 50 000 000 простых чисел в файле в моей собственной системе, затем я проверил ваш код на него (и после изменения имени файла на параметр он работал).

Из интереса, генерация и запись в файл простых чисел заняла около 5 минут на моем компьютере - 311 секунда - большая часть из которых, вероятно, была временем ввода-вывода.

Затем я преобразовал вашу функцию в:

public static int[] loadByQuantity(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream(fname))) {
        for (int i = 0; i < primes.length; ++i) {
            primes[i] = in.readInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

Единственное различие заключается в том, что имя файла теперь является параметром.

Затем я написал небольшую тестовую систему, чтобы узнать, как долго ваш код взял для меня:

public static void time(Supplier<int[]> task, String name) {
    long nanos = System.nanoTime();
    int[] primes = task.get();
    System.out.printf("Task %s took %.3fms\n", name, (System.nanoTime() - nanos) / 1000000.0);
    System.out.printf("Count %d\nFirst %d\nLast %d\n", primes.length, primes[0], primes[primes.length - 1]);
    System.out.println("----");
}

public static void main(String[] args) {
    int count = 50000000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
}

Затем я реализовал ту же функциональность, используя механизм NIO, специально использующий IO с отображением памяти: http://docs.oracle.com/javase/8/docs/api/java/nio/MappedByteBuffer.html

Этот тип IO предназначен для значительного уменьшения объема копий памяти из входного файла. Это также означает, что Java считывает содержимое из ОС без предварительного копирования его в пространство памяти Java.

Для типов последовательных IO эта проблема имеет, я ожидал, что улучшения производительности будут значительными.

Кроме того, MappedByteBuffer имеет методы getInt(), который также декодирует 4 байта в int для вас: http://docs.oracle.com/javase/8/docs/api/java/nio/ByteBuffer.html#getInt- -

Вот код, который я придумал. Обратите внимание: я использовал ту же обработку исключений, которую вы используете, а также ту же инициализацию массива. Я считаю, что вы должны исключать исключения из этих методов, а не просто обертывать их во время выполнения исключений:

public static int[] loadByNIO(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (FileChannel fc = FileChannel.open(Paths.get(fname))) {
        MappedByteBuffer mbb = fc.map(MapMode.READ_ONLY, 0, numPrimes * 4l);
        for (int i = 0; i < numPrimes; i++) {
            primes[i] = mbb.getInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

Затем я несколько раз запускал процесс в основном методе и сравнивал результаты:

public static void main(String[] args) {
    int count = 50_000_000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
}

Операция NIO, как и ожидалось, значительно быстрее ... 1500 раз быстрее

Task OP took 214163.250ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 141.511ms
Count 50000000
First 2
Last 982451653
----
Task OP took 214633.128ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 159.571ms
Count 50000000
First 2
Last 982451653
----

Я признаю, что он намного быстреечем я ожидал тоже .... но результаты верны.

Теперь я рекомендую вам поэкспериментировать с тем, как поместить эту концепцию в поток Java, вместо того, чтобы заполнять полные 50 000 000 в массив. По потоку результатов вы можете начать свое «реальное» вычисление раньше, без латентности необходимости читать все простые числа из файла. Например, рассмотрите, что вы можете сделать с логикой, например:

primes.stream().....

, где простые числа читали значения по запросу из файла.

Вот полный код, который я запускал:

package prperf;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.FileChannel.MapMode;
import java.nio.file.Paths;
import java.util.function.Supplier;

public class PrimeReader {

    public static int[] loadByQuantity(int argNumPrimes, String fname) {
        int numPrimes = Math.min(argNumPrimes, 50_000_000);
        int[] primes = new int[numPrimes];
        try (DataInputStream in = new DataInputStream(new FileInputStream(fname))) {
            for (int i = 0; i < primes.length; ++i) {
                primes[i] = in.readInt();
            }
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
        return primes;
    }

    public static int[] loadByNIO(int argNumPrimes, String fname) {
        int numPrimes = Math.min(argNumPrimes, 50_000_000);
        int[] primes = new int[numPrimes];
        try (FileChannel fc = FileChannel.open(Paths.get(fname))) {
            MappedByteBuffer mbb = fc.map(MapMode.READ_ONLY, 0, numPrimes * 4l);
            for (int i = 0; i < numPrimes; i++) {
                primes[i] = mbb.getInt();
            }
        } catch (IOException ex) {
            throw new RuntimeException(ex);
        }
        return primes;
    }

    public static void time(Supplier<int[]> task, String name) {
        long nanos = System.nanoTime();
        int[] primes = task.get();
        System.out.printf("Task %s took %.3fms\n", name, (System.nanoTime() - nanos) / 1000000.0);
        System.out.printf("Count %d\nFirst %d\nLast %d\n", primes.length, primes[0], primes[primes.length - 1]);
        System.out.println("----");
    }

    public static void main(String[] args) {
        int count = 50_000_000;
        time(() -> loadByQuantity(count, "primes.dat"), "OP");
        time(() -> loadByNIO(count, "primes.dat"), "NIO");
        time(() -> loadByQuantity(count, "primes.dat"), "OP");
        time(() -> loadByNIO(count, "primes.dat"), "NIO");
    }

}
ответил rolfl 29 Jam1000000amSun, 29 Jan 2017 00:06:30 +030017 2017, 00:06:30
51

Использование BufferedInputStream будет быстрым исправлением с меньшей модификацией текущего кода.

Причина, по которой методы readX DataInputStream /FileInputStream медленный - это то, что они каждый раз запрашивают IO. BufferedInputStream просто загружает кусок файла, чтобы уменьшить количество операций ввода-вывода. Другое решение - использовать метод read () для загрузки (целого или частичного) файла в массив байтов, а затем извлечь эти целые числа из массива байтов.

ответил Aria Ax 29 Jam1000000amSun, 29 Jan 2017 04:41:39 +030017 2017, 04:41:39
17

Рассмотрим файлы с отображением памяти

  

Отказ от ответственности: Это также для меня в первый раз, когда я играю с файлами с отображением памяти на Java. То, как я это делаю, может быть субоптимальным или даже хуже.

Я думаю, что Java DataInputStream имеет большие накладные расходы для переносимости и обработки ошибок, которые, вероятно, не нужны в вашей ситуации. Самый быстрый способ решить вашу проблему, о которой я могу думать, состоит в том, чтобы просто mmap() сохранить файл в памяти, предполагая, что он содержит упакованный массив из 32-битных целых чисел в собственном байтовом порядке хоста.

Это решение, которое я придумал.

static int[] load(final File file, final int n) throws IOException {
    try (final FileChannel channel = FileChannel.open(
            file.toPath(),
            StandardOpenOption.READ
    )) {
        final MappedByteBuffer mapping = channel.map(
            FileChannel.MapMode.READ_ONLY,
            0,                 // offset
            n * Integer.BYTES  // length
        );
        mapping.order(ByteOrder.nativeOrder());
        final IntBuffer integers = mapping.asIntBuffer();
        final int[] array = new int[n];
        integers.get(array);
        return array;
    }
}

Чтобы записать данные, я использовал следующую функцию.

static void store(final File file, final int[] array) throws IOException {
    try (final FileChannel channel = FileChannel.open(
            file.toPath(),
            StandardOpenOption.READ,
            StandardOpenOption.WRITE,
            StandardOpenOption.CREATE,
            StandardOpenOption.TRUNCATE_EXISTING
    )) {
        final MappedByteBuffer mapping = channel.map(
            FileChannel.MapMode.READ_WRITE,
            0,                            // offset
            array.length * Integer.BYTES  // length
        );
        mapping.order(ByteOrder.nativeOrder());
        final IntBuffer integers = mapping.asIntBuffer();
        integers.put(array);
    }
}

Я сравнивал функции с использованием массива из 50 М случайных целых чисел. После загрузки массива я также вычислил его сумму и распечатал ее, чтобы убедиться, что операция загрузки не оптимизирована. Результаты были получены с использованием оболочки time и, следовательно, также включают в себя генерацию случайных данных, запуск JVM и любые другие служебные данные. Результаты все еще очень ясны.

 implementation     store      load

data stream         5:54      1:31
memory mapping      0:01    < 0:01

Отдельные проблемы

Я уверен, что я не говорю вам ничего нового здесь, но для записи: Отмените логику для чтения массива целых чисел из файла из логики, которая интерпретирует эти целые числа (в виде простых чисел). Кроме того, не перекодируйте имя файла или размер массива в функцию, которая их загружает.

Не исключать камуфляж

Независимо от того, обрабатывает ли Java или заявляет о своей философии относительно исключений, хорошая идея открыта для обсуждения. Однако, учитывая, что он такой, как есть, я не думаю, что работа с системой полезна. Мы должны жить с тем, что имеем сейчас.

Остерегайтесь правил

Я только кратко посмотрел на Project Euler и не знаю их правил, но я не удивлюсь, если загрузка данных из внешних ресурсов будет считаться обманом. Конечно, если вы делаете это только ради собственного удовольствия, вы можете сами устанавливать свои правила.

ответил 5gon12eder 29 Jam1000000amSun, 29 Jan 2017 00:08:03 +030017 2017, 00:08:03
12

В случае простых чисел ваше исходное предположение неверно. Просеивание происходит быстрее, чем чтение с диска практически во всех случаях.

Взяв primesieve в качестве примера, для генерации первых 10 ^ 9 простых чисел требуется 0.05s на недавнем процессоре Intel. Чтобы быть «на порядок быстрее, чем любой расчет», вам нужно получить время чтения ниже 5 мс. Подход с отображением памяти не находится даже в том же городе, что и этот стадион.

Самая большая оптимизация - это Подлинное сито Эратосфена. Фальшивые версии, которые на самом деле пробное деление удивительно распространено. Наряду с колесом мод 30 вы должны опережать ввод-вывод в чистом java, хотя за чем-то высоко оптимизированным как primesieve.

[Изменить. Работа, выполненная в базовом показателе primesieve, эквивалентна генерации простых чисел. Дело в том, что практически всегда быстрее генерировать простые числа, а не пытаться их загрузить. (Подсчет используется в качестве эталона, потому что даже печать списка на экране занимает больше времени, чем просеивание). Вся предпосылка исходного кода заключается в том, что он будет на порядок быстрее, чем ввод-вывод, который является неправильным. Я только указывал, что существует гораздо больший алгоритмический прирост производительности.

Чтобы быть предельно ясным, это только в случае простых чисел. Загрузка миллионов любых целых чисел будет другим предложением, в котором все остальные ответы очень полезны.

Кроме того, в интересах ясности я бы не предложил привязку к языку, связанную с primesieve, используя сегментированное сито (overkill для такого небольшого числа простых чисел) или что-то еще безумное. Я только указываю, что простое сито и колесо, однопоточное, в чистой java, вероятно, будет более надежным, менее усугубляющим (никаких исключений I /O для беспокойства, файлы для добавления в проекты и т. Д.) И более результативными, чем читая их с диска. Точно так же, как «медленные» алгоритмы сортировки могут быть самыми быстрыми в случаях краев.

Что касается комментариев по пропускной способности памяти, здесь есть два безопасных предположения. 1) Список простых чисел будет использоваться для чего-то. 2) Если они генерируются «на лету», есть приличное изменение, они все равно будут в кеше, когда они будут использоваться.

Заключение о необходимости использования int, а не битового поля. Для такого небольшого списка простых чисел вы просто просеиваете массив массивов в любом случае. Даже если вы использовали сжатый список для экономии места по какой-либо причине и для заполнения массива, это было бы полным вопросом, потому что исходный вопрос - чтение простых чисел из текстового файла. Это круговая поездка к процессору и разбор номера, возможно, больше работы. ]

ответил Matthew Gauthier 29 Jam1000000amSun, 29 Jan 2017 02:37:03 +030017 2017, 02:37:03
3

BitSet

Один бит для каждого нечетного числа до 1 000 000 000, если он задан, просто. Это 50847533 простых чисел, не считая 2. Должно занимать около 64 МБ, против 200 МБ для массива целых чисел. Для любого нечетного числа вы делите на 2 и посмотрите на этот индекс.

Кстати, довольно простое сито Эратосфена должно занимать гораздо меньше трех минут, чтобы пролить миллиард чисел на Java, более чем на десять секунд. Этот пример делает именно это.

public static void main(String[] args) {
    int max = 1000000000;
    BitSet sieve = new BitSet(max/2+1);
    for(int i = 1; i < max/2; i++){
        sieve.set(i,true);
    }

    //the sieve
    for(int p = 3; p*p < max; p += 2){
        if(sieve.get(p/2)){
            for(int m = p*p; m < max; m += p+p){
                sieve.set(m/2,false);
            }
        }
    }

    //count primes and optionally print them out
    int primecount = 0;
    int last = 0;

    for(int p = 3; p < max; p += 2){
        if(sieve.get(p/2)){
            //System.out.println(p);
        }
    }
    System.out.println(primecount);
}

И Primesieve на два порядка быстрее, фактически оптимизируя.

ответил James Hollis 30 Jam1000000amMon, 30 Jan 2017 04:55:38 +030017 2017, 04:55:38

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132