Подтвердить что ты не робот

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

Вот сценарий.

Мне присваивается массив "A" целых чисел. Размер массива не фиксирован. Функция, которую я должен написать, может быть вызвана один раз с массивом из нескольких целых чисел, а в другое время может содержать тысячи целых чисел. Кроме того, каждое целое число не должно содержать одинакового количества цифр.

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

Например:, если вход:

[12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000]

Тогда вывод должен быть:

[1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654]

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

Мне повезло, что решение не нуждается в дополнении и т.д., и есть простое решение, в котором вам просто нужно обрабатывать номера в некотором роде (некоторая обработка бит?), чтобы получить результат.

Каково наиболее эффективное решение пространства, о котором вы можете думать? Время-накрест?

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Более подробно (псевдокод):

  • выделяет массив char ** aux, пока массив numbers
  • для я от 0 до length of numbers-1, aux[i]=stringify(numbers[i])
  • выделить массив из int indices той же длины
  • для я от 0 до length of numbers-1, indices[i]=i
  • sort indices, используя cmp(i,j) strcmp(aux[i],aux[j])
  • выделить массив из int results той же длины
  • для я от 0 до length of numbers-1, results[i]=numbers[indices[i]]
  • memcpy results через numbers
  • освободите каждый aux[i], а также aux, indices, results

Ответ 2

Поскольку вы упомянули 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 работает автоматически через авто-бокс)

Ответ 3

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

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

Ответ 4

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

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());
}

Ответ 5

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

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

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

Ответ 6

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

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

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

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

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

Ответ 7

псевдокод:

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]);
}

Итак, что такое munge и unmunge?

munge отличается в зависимости от целого размера. Например:

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
}

В зависимости от того, что делает munge, нужно сказать, какой порядок состоит из 4-х битных целых чисел при сортировке лексиграфа. Я уверен, что вы видите, что здесь есть шаблон - мне не нужно было использовать переключатель --- и вы можете написать версию munge, которая легко справляется с 32-битными целыми числами. Подумайте о том, как писать версии munge для 5, 6 и 7-битных целых чисел, если вы не можете сразу увидеть шаблон.

unmunge является обратным к munge.

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

Ответ 8

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

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

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 не имеет unsigned ints, вам придется немного изменить его. Он использует много рабочей памяти (в два раза больше размера ввода), но это еще меньше, чем ваш первоначальный подход. Это может быть быстрее, чем преобразование в строки на лету в компараторе, но оно использует больше пиковой памяти. В зависимости от GC, он может отбросить свой путь за счет меньшего объема памяти и, тем не менее, потребовать меньше сбора.

Ответ 9

Если все числа меньше 1E + 18, вы можете отбросить каждое число до UINT64, умножить на десять и добавить один, а затем умножить на десять, пока они не будут как минимум 1E + 19. Затем сортируйте их. Чтобы вернуть исходные числа, разделите каждое число на десять, пока последняя цифра не будет равна нулю (она должна быть одна), а затем разделите ее на десять раз.

Ответ 10

В вопросе не указывается, как обрабатывать отрицательные целые числа в лексикографическом порядке сортировки. Строковые методы, представленные ранее, обычно сортируют отрицательные значения на фронте; например, {-123, -345, 0, 234, 78} будут оставлены в этом порядке. Но если знаки минус должны были быть проигнорированы, порядок вывода должен быть {0, -123, 234, -345, 78}. Можно было бы адаптировать строковый метод для создания этого порядка с помощью нескольких громоздких дополнительных тестов.

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

Код java, показанный в конце этого ответа, включает в себя два компаратора на основе логарифма: alogCompare и slogCompare. Первый игнорирует знаки, поэтому будет производить {0, -123, 234, -345, 78} из {-123, -345, 0, 234, 78}.

Ниже показаны следующие числовые группы: результат, созданный программой java.

В разделе "dar rand" показан массив случайных данных dar как сгенерированный. Он читает поперек, а затем вниз, по 5 элементов в строке. Обратите внимание, что массивы sar, lara и lars изначально являются несортированными копиями dar.

Раздел сортировки dar dar после сортировки через Arrays.sort(dar);.

В разделе "sar lex" показан массив sar после сортировки с Arrays.sort(sar,lexCompare);, где lexCompare похож на Comparator, показанный в ответе Джейсона Коэна.

В разделе "lar s log" показан массив lars после сортировки по Arrays.sort(lars,slogCompare);, иллюстрирующий метод на основе логарифма, который дает тот же порядок, что и lexCompare, и другие строковые методы.

В разделе "lar a log" показан массив lara после сортировки по Arrays.sort(lara,alogCompare);, иллюстрирующий метод на основе логарифма, который игнорирует знаки минус.

dar rand    -335768    115776     -9576    185484     81528
dar rand      79300         0      3128      4095    -69377
dar rand     -67584      9900    -50568   -162792     70992

dar sort    -335768   -162792    -69377    -67584    -50568
dar sort      -9576         0      3128      4095      9900
dar sort      70992     79300     81528    115776    185484

 sar lex    -162792   -335768    -50568    -67584    -69377
 sar lex      -9576         0    115776    185484      3128
 sar lex       4095     70992     79300     81528      9900

lar s log    -162792   -335768    -50568    -67584    -69377
lar s log      -9576         0    115776    185484      3128
lar s log       4095     70992     79300     81528      9900

lar a log          0    115776   -162792    185484      3128
lar a log    -335768      4095    -50568    -67584    -69377
lar a log      70992     79300     81528     -9576      9900

Ниже приведен код Java.

// Code for "How can I sort numbers lexicographically?" - jw - 2 Jul 2014
import java.util.Random;
import java.util.Comparator;
import java.lang.Math;
import java.util.Arrays;
public class lex882954 {
// Comparator from Jason Cohen answer
    public static Comparator<Integer> lexCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            return x.toString().compareTo( y.toString() );
        }
    };
// Comparator that uses "abs." logarithms of numbers instead of strings
    public static Comparator<Integer> alogCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
            Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
            Double xf=xl-xl.intValue();
            return xf.compareTo(yl-yl.intValue());
        }
    };
// Comparator that uses "signed" logarithms of numbers instead of strings
    public static Comparator<Integer> slogCompare = new Comparator<Integer>(){
        public int compare( Integer x, Integer y ) {
            Double xl = (x==0)? 0 : Math.log10(Math.abs(x));
            Double yl = (y==0)? 0 : Math.log10(Math.abs(y));
            Double xf=xl-xl.intValue()+Integer.signum(x);
            return xf.compareTo(yl-yl.intValue()+Integer.signum(y));
        }
    };
// Print array before or after sorting
    public static void printArr(Integer[] ar, int asize, String aname) {
        int j;
        for(j=0; j < asize; ++j) {
            if (j%5==0)
                System.out.printf("%n%8s ", aname);
            System.out.printf(" %9d", ar[j]);
        }
        System.out.println();
    }
// Main Program -- to test comparators
    public static void main(String[] args) {
        int j, dasize=15, hir=99;
        Random rnd = new Random(12345);
        Integer[] dar = new Integer[dasize];
        Integer[] sar = new Integer[dasize];
        Integer[] lara = new Integer[dasize];
        Integer[] lars = new Integer[dasize];

        for(j=0; j < dasize; ++j) {
            lara[j] = lars[j] = sar[j] = dar[j] = rnd.nextInt(hir) * 
                rnd.nextInt(hir) * (rnd.nextInt(hir)-44);
        }
        printArr(dar, dasize, "dar rand");
        Arrays.sort(dar);
        printArr(dar, dasize, "dar sort");
        Arrays.sort(sar, lexCompare);
        printArr(sar, dasize, "sar lex");
        Arrays.sort(lars, slogCompare);
        printArr(lars, dasize, "lar s log");
        Arrays.sort(lara, alogCompare);
        printArr(lara, dasize, "lar a log");
    }
}

Ответ 11

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

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
}

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

Ответ 12

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

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

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

Ответ 13

#!/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 элементов, но не время вывода их на консоль. Результат добавляется примерно через секунду.

Итак, сохраните некоторое время программиста; -)

Ответ 14

Один действительно взломанный метод (с использованием C) будет:

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

В Java (от здесь):

long bits = Double.doubleToLongBits(5894.349580349);

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

поэтому вы можете сортировать по длинному mantissa здесь.