Сортировка миллионов целых чисел

В прошлую пятницу меня поразило вопрос интервью с сортировкой, с которым мне никогда не приходилось иметь дело.

  

Разработайте свой собственный алгоритм сортировки.

     
  1. Он не может использовать другие классы для справки.
  2.   
  3. Он должен иметь возможность сортировать массив из миллионов целых чисел в размере.
  4.   
  5. Он должен быть как можно быстрее.
  6.   

Например:

int[] old = {5434, 3454, 2, 0, 356, 896, 7324, 888, 99, 78365, 111};  
int highestNumber = 78365;  

Будет

int[] new = {0, 2, 99, 111, 356, 888, 896, 3454, 5434, 7324, 78365};

Я провел ночь, пытаясь придумать свой собственный метод, чтобы сделать это. И это то, что я придумал.

public class Main {
    public static void main(String[] args) {
        int[] twentyMillion = new int [20000000];
        for (int i = 0; i < a.length; i++) {
            twentyMillion [i] = new Random().nextInt(20000000);
        }
        sortByAccendPro(twentyMillion , 20000000);
    }

    /**
     * Jasz sort algorithim.
     * 
     * @param {int[]} twentyMillion - array of twenty million random ints.
     * @param {int} highestNumber - Highest number to sort to.
     */
    public void sortByAccendPro(int[] twentyMillion, int highestNumber ) {
        int[] rangePosition = new int[twentyMillion.length];
        int[] newArray = new int[twentyMillion.length];
        int[] range = new int[highestNumber];
        long time = System.nanoTime();
        for (int i = 0; i < twentyMillion.length; i++) {
            rangePosition[i] = twentyMillion[i];
            range[twentyMillion[i]]++;
        }
        for (int i = range.length - 1, past = twentyMillion.length; i >= 0; i--) {
            range[i] = past - range[i];
            past = range[i];
        }
        for (int i = 0; i < twentyMillion.length; i++) {
            newArray[range[rangePosition[i]]] = twentyMillion[i];
            range[rangePosition[i]]++;
        }
        System.out.println("time = " + (System.nanoTime() - time));
    }
}

Шаги:

  1. Первый цикл имеет диапазон чисел. Например, если rangeArray идет от 0 до 3 000 000, он увеличивает каждый случай каждого числа, которое он находит в этом массиве. Поэтому каждый раз, когда он находит 2,750,000, он увеличивает эту позицию в rangeArray.

  2. Второй цикл работает назад от максимального положения в rangeArray. Так что, если размер составляет 3 000 000, и у него есть 100 000 случаев из 3 000 000, это говорит о том, что 3 000 000 начнут с 2,900,000 и достигнут максимума.

  3. Третий цикл возвращается назад через основной массив, захватывая один и тот же индекс в массиве диапазонов и подключая его в правильной позиции в newArray.

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

Какой алгоритм это напоминает и что я могу сделать, чтобы сделать его лучше?

44 голоса | спросил Xjasz 18 Maypm15 2015, 21:48:32

3 ответа


28

Алгоритм, который вы реализовали, называется подсчет сортировки , Его временная стоимость линейна по размеру ввода - быстрее, чем может получить любой алгоритм сортировки на основе сравнения. (За счет того, что они также линейны в разнице максимального и минимального элементов на входе.) Поздравляем, если вы придумали эту идею самостоятельно. Поскольку они уже дают вам наибольшее количество в массиве в качестве дополнительного ввода, кажется очень вероятным, что они хотели увидеть этот алгоритм. (Конечно, вы можете найти максимум в линейном времени, если необходимо.)

Заметки о вашем коде:

  • Массив rangePosition инициализируется точной копией twentyMillion, а затем только когда-либо читается. Почему вы создали его вместо того, чтобы напрямую использовать twentyMillion?
  • Если twentyMillion содержит отрицательное число, ваша реализация взорвется. Может быть, вы просто забыли упомянуть, что все входы гарантированно будут неотрицательными? В противном случае вам также нужно знать минимальное значение и нормализовать свои ключи к этому. (Это также может помочь вам сэкономить, если минимум намного больше нуля.)
  • Если highestNumber чрезвычайно велик, у вас возникнет проблема. Например, вы, вероятно, не сможете выделить new int[Integer.MAX_VALUE], не получив OutOfMemoryError. (И если вы допускаете отрицательные числа на входе, вам может понадобиться только массив больше , чем Integer.MAX_VALUE!) И даже если вы можете выделить его, итерации по нему будет навсегда. Если вы хотите, чтобы ваш код был более надежным, вы могли бы решить какой-то эвристический вопрос: требует ли комбинация twentyMillion.length и highestNumber накладные расходы на сортировку счета или вы будете лучше использовать алгоритм O на основе сравнения ( n  log ( n )).
  • twentyMillion - плохое имя переменной, которая не обязательно должна содержать массив длиной 20 М.
ответил 5gon12eder 18 Maypm15 2015, 22:58:56
24

Это интервью, и вам была предоставлена ​​возможность похвастаться тем, что вы знаете. Если бы я «оценивал» ваше представление, каково было бы мое впечатление?

Не используйте вещи плохо. Ваш код здесь ужасен:

    for (int i = 0; i < a.length; i++) {
        twentyMillion [i] = new Random().nextInt(20000000);
    }

Создание нового Random внутри цикла - плохое использование класса. Создайте единый случайный экземпляр и повторно используйте его:

Random rand = new Random();
for (int i = 0; i < a.length; i++) {
    twentyMillion [i] = rand.nextInt(20000000);
}

Используйте константы для магических чисел .... 20 000 000 является константой и должны быть объявлены как таковые:

private static final int dataSize = 20_000_000;

Обратите внимание, что я использую _ там, чтобы показать, что я знаю, что он существует как функция языка (по крайней мере, с Java 7).

Затем я не вижу никаких функций Java-8. На собеседование я ожидал бы, что вы «wow» меня ... но в вашем коде нет ничего особенного. Например, легко выиграть будет создание входного массива:

    Random rand = new Random();
    int[] toSort = IntStream.generate(() -> rand.nextInt(dataSize))
                                   .limit(dataSize)
                                   .toArray();

Я бы, скорее всего, поместил это в метод, чтобы показать некоторые функциональные извлечения тоже:

private static final int[] generateData(int size) {
    Random rand = new Random();
    return IntStream.generate(() -> rand.nextInt(size))
                    .limit(size)
                    .toArray();
}

Правильно, это показывает некоторое знакомство с Java 8, некоторые языковые структуры, дисциплину кода и т. д.

Как насчет фактического алгоритма сортировки?

  

Как можно быстрее

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

На вопрос о задании «как можно быстрее» можно ответить только с точностью: «каковы ваши другие ограничения». Я бы подумал, что это «трюк».

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

ответил rolfl 19 Mayam15 2015, 00:25:37
10

То, что вы сделали, похоже на Bucket Sort, однако ваш точный алгоритм для меня является загадкой. Проблема с Bucket Sort заключается в том, что при сортировке произвольных целых чисел вам может понадобиться до 4Gi ведра. Это слишком много. С памятью 16GiB вы можете упаковать их в 4 массива new int[1<<30], но алгоритм будет довольно медленным (из-за плохой локальности памяти и гораздо большего объема данных бухгалтерского учета, чем для сортировки товаров) .

Итак, я предполагаю, что прибегу к Quick Sort для неограниченного диапазона. Для ограниченного диапазона ваш алгоритм в порядке.

 * @param {int} highestNumber - Highest number to sort to.

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

    int[] rangePosition = new int[twentyMillion.length];
    int[] newArray = new int[twentyMillion.length];
    int[] range = new int[highestNumber];
    long time = System.nanoTime();

Вы обманываете, начав измерение в середине алгоритма. Конечно, это не совсем середина, но все же.

Несмотря на ваши объяснения, я полностью потерял отношение к тому, как это работает. Наверное, не твоя вина. Поэтому я представлю свою (непроверенную, но тривиальную) версию вместо того, чтобы ее просматривать:

int[] counts = new int[highestNumber];
for (int x : twentyMillion) {
    ++counts[x];
}
int insertionIndex = 0;
for (int i = 0; i < counts.length; ++i) {
    for (int j = 0; j < counts[i]; ++j) {
        twentyMillion[insertionIndex++] = i;
    }
}
// No return value needed as the input array gets overwritten.

Похоже, вы заполняете newArray просто для удовольствия и не используете его и не возвращаете. Если JVM был умным и злым, он мог бы уменьшить весь ваш метод до двух линий nanoTime. В более простых случаях подобные вещи действительно происходят, поэтому не позволяйте вашим бенчмаркам игнорировать значения, которые нужно вычислить.

ответил maaartinus 18 Maypm15 2015, 23:18:17

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

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

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