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

Один действительно хакерский метод (с использованием C):

• создать новый массив всех значений, преобразованных в числа с плавающей запятой.
• выполнить сортировку с использованием битов мантиссы (значимости) для сравнение

В Java (из здесь ):

long bits = Double.doubleToLongBits(5894.349580349);

boolean negative = (bits & 0x8000000000000000L) != 0; 
long exponent = bits & 0x7ff0000000000000L >> 52;
long mantissa = bits & 0x000fffffffffffffL;

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

Если вы хотите попробовать более эффективный препроцесс-сортировку-постпроцесс, то обратите внимание, что целое число состоит не более чем из 10 десятичных цифр (пока без учета подписи).

Итак, двоично-десятичные данные для него умещаются в 64 бита. Сопоставьте цифру 0-> 1, 1-> 2 и т. Д. И используйте 0 в качестве терминатора NUL (чтобы гарантировать, что «1» окажется меньше «10»). По очереди сдвигайте каждую цифру, начиная с самой маленькой, в начало длинной. Отсортируйте длинные числа, которые будут отображаться в лексикографическом порядке от исходных целых чисел. Затем выполните обратное преобразование, сдвигая цифры по одной с начала каждой длинной:

uint64_t munge(uint32_t i) {
    uint64_t acc = 0;
    while (i > 0) {
        acc = acc >> 4;
        uint64_t digit = (i % 10) + 1;
        acc += (digit << 60);
        i /= 10;
    }
    return acc;
}

uint32_t demunge(uint64_t l) {
    uint32_t acc = 0;
    while (l > 0) {
        acc *= 10;
        uint32_t digit = (l >> 60) - 1;
        acc += digit;
        l << 4;
    }
}

Или что-то в этом роде. Поскольку в Java нет целых чисел без знака, вам придется немного его изменить. Он использует много рабочей памяти (в два раза больше размера ввода), но это все еще меньше, чем ваш первоначальный подход. Это может быть быстрее, чем преобразование в строки на лету в компараторе, но он использует больше пиковой памяти. Однако в зависимости от сборщика мусора он может потреблять меньше памяти и требовать меньшего сбора данных.

Pseudocode:

sub sort_numbers_lexicographically (array) {
    for 0 <= i < array.length:
        array[i] = munge(array[i]);
    sort(array);  // using usual numeric comparisons
    for 0 <= i < array.length:
        array[i] = unmunge(array[i]);
}

So, what are munge and unmunge?

munge is different depending on the integer size. For example:

sub munge (4-bit-unsigned-integer n) {
    switch (n):
        case 0:  return 0
        case 1:  return 1
        case 2:  return 8
        case 3:  return 9
        case 4:  return 10
        case 5:  return 11
        case 6:  return 12
        case 7:  return 13
        case 8:  return 14
        case 9:  return 15
        case 10:  return 2
        case 11:  return 3
        case 12:  return 4
        case 13:  return 5
        case 14:  return 6
        case 15:  return 7
}

Esentially what munge is doing is saying what order 4 bit integers come in when sorted lexigraphically. I'm sure you can see that there is a pattern here --- I didn't have to use a switch --- and that you can write a version of munge that handles 32 bit integers reasonably easily. Think about how you would write versions of munge for 5, 6, and 7 bit integers if you can't immediately see the pattern.

unmunge is the inverse of munge.

So you can avoid converting anything to a string --- you don't need any extra memory.

Исполняемый псевдокод (он же Python): thenumbers.sort (key = str) . Да, я знаю, что использование Python похоже на читерство - это просто слишком мощно ;-). А если серьезно, это также означает: если вы можете отсортировать массив строк лексикографически, как это внутренне присуще сортировке Python, тогда просто сделайте «ключевую строку» из каждого числа и отсортируйте этот вспомогательный массив (затем вы можете восстановить желаемый массив чисел с помощью преобразование str-> int или сортировка индексов с помощью индексации и т. д.); это известно как DSU (украсить, отсортировать, отменить украшение) и индексы , результаты

#!/usr/bin/perl

use strict;
use warnings;

my @x = ( 12, 2434, 23, 1, 654, 222, 56, 100000 );

print $_, "\n" for sort @x;

__END__

Некоторые тайминги ... Во-первых, с пустым @x:

C:\Temp> timethis s-empty
TimeThis :  Elapsed Time :  00:00:00.188

Теперь, с 10 000 случайно сгенерированных элементов:

TimeThis :  Elapsed Time :  00:00:00.219

Это включает время, необходимое для генерации 10 000 элементов, но не время чтобы вывести их на консоль. Результат добавляет около секунды.

Так что сэкономим время программиста; -)

Возможная оптимизация: Вместо этого:

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

, которое вы можно умножить каждое число на (10 ^ N - log10 (число)), где N - число больше log10 любого из ваших чисел.

Если вы стремитесь к экономии места, я бы попытался просто проделать работу в функции сравнения вида

int compare(int a, int b) {
   // convert a to string
   // convert b to string
   // return -1 if a < b, 0 if they are equal, 1 if a > b
}

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

Вам определенно не нужно дополнять результат. Это не изменит порядок лексикографического сравнения, это будет более подвержено ошибкам и будет просто тратить циклы ЦП. Наиболее эффективным методом с точки зрения пространства было бы преобразование чисел в строки при их сравнении. Таким образом, вам не нужно будет выделять дополнительный массив, числа будут сравниваться на месте.

Вы можете быстро получить достаточно хорошую реализацию, просто преобразовав их в строки по мере необходимости. Строковка числа не особенно затратна, и, поскольку вы имеете дело только с двумя строками одновременно, вполне вероятно, что они будут всегда оставаться в кэше ЦП. Таким образом, сравнения будут намного быстрее, чем в случае, когда вы конвертируете весь массив в строки, поскольку их не нужно загружать из основной памяти в кеш. Люди часто забывают, что у ЦП есть кэш и что алгоритмы, которые выполняют большую часть своей работы в небольшой локальной области памяти, значительно выиграют от гораздо более быстрого доступа к кешу. На некоторых архитектурах кэш настолько быстрее памяти, что вы можете выполнять сотни операций с вашими данными за то время, которое потребовалось бы для их загрузки из основной памяти. Таким образом, выполнение дополнительной работы в функции сравнения может быть значительно быстрее, чем предварительная обработка массива. Особенно если у вас большой массив.

Попробуйте выполнить сериализацию и сравнение строк в функции компаратора и протестируйте это. Думаю, это будет неплохое решение. Пример псевдокода java-ish:

public static int compare(Number numA, Number numB) {
    return numA.toString().compare(numB.toString());
}

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

t получить значительную пользу. Вы не можете просто выполнить прямое сравнение битов, это дало бы вам другой порядок, чем лексикографическая сортировка. В любом случае вам нужно будет вычислить каждую цифру числа, поэтому проще всего сделать их строками. Может быть, есть какой-нибудь хитрый трюк, но каждый способ, который я могу придумать в своей голове, сложен, подвержен ошибкам и требует гораздо больше работы, чем она того стоит.

t получить значительную пользу. Вы не можете просто выполнить прямое сравнение битов, это дало бы вам другой порядок, чем лексикографическая сортировка. В любом случае вам нужно будет вычислить каждую цифру числа, поэтому проще всего сделать их строками. Может быть, есть какой-нибудь хитрый трюк, но каждый способ, который я могу придумать в своей голове, сложен, подвержен ошибкам и требует гораздо больше работы, чем она того стоит.

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

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

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

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

bool isLessThan(int a, int b)
{
    string aString = ToString(a);
    string bString = ToString(b);

    int charCount = min(aString.length(), bString.length())
    for (charIndex = 0; charIndex < charCount; charIndex++)
    {
        if (aString[charIndex] < bString[charIndex]) { return TRUE; }
    }

    // if the numbers are of different lengths, but identical
    // for the common digits (e.g. 123 and 12345)
    // the shorter string is considered "less"
    return (aString.length() < bString.length());
}

Я бы просто превратил их в строки, а затем отсортирую, а затем отсортирую с помощью strcmp, который выполняет сравнение lex.

В качестве альтернативы вы можете написать функцию «lexcmp», которая сравнивает два числа, используя% 10 и / 10, но это в основном то же самое, что и многократный вызов atoi, так что это плохая идея.

Поскольку вы упомянули Java, это фактический язык, о котором идет речь:

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

В частности:

Comparator<Integer> lexCompare = new Comparator<Integer>(){
   int compareTo( Integer x, Integer y ) {
      return x.toString().compareTo( y.toString() );
   }
};

Затем вы можете отсортировать массив следующим образом:

int[] array = /* whatever */;
Arrays.sort( array, lexCompare );

(Примечание: int / Integer несоответствие работает автоматически через автоматическую упаковку)