Как я могу отсортировать числа лексикографически?
Вот сценарий.
Мне дан массив 'A' целых чисел. Размер массива не фиксирован. Функция, которую я должен написать, может быть вызвана один раз с массивом из нескольких целых чисел, а в другой раз она может даже содержать тысячи целых чисел. Кроме того, каждое целое число не обязательно должно содержать одинаковое количество цифр.
Я должен "отсортировать" числа в массиве так, чтобы в результирующем массиве были целые числа, упорядоченные лексикографическим образом (т.е. они отсортированы на основе их строковых представлений. Здесь "123" - строковое представление 123). Обратите внимание, что выходные данные должны содержать только целые числа, а не их строковые эквиваленты.
Например: если ввод:
[12 | 2434 | 23 | 1 | 654 | 222 | 56 | 100000]
Тогда вывод должен быть:
[1 | 100000 | 12 | 222 | 23 | 2434 | 56 | 654]
Мой первоначальный подход: я преобразовал каждое целое число в его строковый формат, затем добавил нули справа от него, чтобы все целые числа содержали одинаковое количество цифр (это был грязный шаг, так как он включал отслеживание и т. Д., Что сделало решение очень неэффективным), а затем сделал радикальная сортировка Наконец, я удалил дополненные нули, преобразовал строки обратно в их целые числа и поместил их в получившийся массив. Это было очень неэффективное решение.
Я был убежден, что решение не нуждается в заполнении и т. Д., И есть простое решение, где вам просто нужно каким-то образом обработать числа (некоторую битовую обработку?), Чтобы получить результат.
Какое космическое наиболее эффективное решение вы можете придумать? Время мудр?
Если вы даете код, я бы предпочел Java или псевдокод. Но если это вас не устраивает, любой такой язык должен подойти.
14 ответов
Исполняемый псевдокод (он же Python): thenumbers.sort(key=str), Да, я знаю, что использование Python - это как обман - он слишком силен;-). А если серьезно, это также означает: если вы можете отсортировать массив строк лексикографически, как это может сделать сортировка Python, то просто сделайте "ключевую строку" из каждого числа и отсортируйте этот вспомогательный массив (вы можете затем восстановить нужный массив чисел с помощью преобразование str->int или сортировка индексов через косвенное обращение и т. д.); это известно как DSU (Украсить, Сортировать, Украсить), и это то, что key= аргумент для сортировки Python реализует.
Более подробно (псевдокод):
- выделить массив символов **
auxдо тех пор, покаnumbersмассив - для меня от 0 до
length of numbers-1,aux[i]=stringify(numbers[i]) - выделить массив int
indicesодинаковой длины - для меня от 0 до
length of numbers-1,indices[i]=i - Сортировать
indicesиспользуя какcmp(i,j)strcmp(aux[i],aux[j]) - выделить массив int
resultsодинаковой длины - для меня от 0 до
length of numbers-1,results[i]=numbers[indices[i]] - тетсру
resultsнадnumbers - освободить каждого
aux[i], а такжеaux,indices,results
Поскольку вы упомянули, что речь идет о языке 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 рассогласование работает автоматически через автобокс)
Фактическая сортировка может быть выполнена любым алгоритмом, который вам нравится. Ключом к этой проблеме является нахождение функции сравнения, которая будет правильно определять, какие числа должны быть "меньше" других, согласно этой схеме:
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, так что не очень хорошая идея.
Мой соблазн был бы сказать, что преобразование int в строку будет происходить в коде компаратора, а не навалом. Хотя это может быть более элегантно с точки зрения кода, я должен сказать, что усилия по выполнению будут больше, поскольку каждое число может сравниваться несколько раз.
Я был бы склонен создать новый массив, содержащий как int, так и строковое представление (не уверен, что вам нужно дополнить версии строк для сравнения строк, чтобы получить заданный вами порядок), отсортировать его по строке и затем скопировать значения int возвращаются к исходному массиву.
Я не могу придумать умный математический способ сортировки, так как по вашему собственному утверждению вы хотите отсортировать лексикографически, поэтому для этого вам нужно преобразовать числа в строки.
Вам определенно не нужно дополнять результат. Это не изменит порядок лексикографического сравнения, оно будет более подвержено ошибкам и будет просто тратить циклы процессора. Наиболее эффективным с точки зрения пространства методом является преобразование чисел в строки при их сравнении. Таким образом, вам не нужно выделять дополнительный массив, числа будут сравниваться на месте.
Вы можете быстро получить достаточно хорошую реализацию, просто преобразовав их в строки по мере необходимости. Строкование числа не особенно дорого, и, поскольку вы имеете дело только с двумя строками одновременно, вполне вероятно, что они всегда будут оставаться в кэше ЦП. Таким образом, сравнение будет намного быстрее, чем в случае, когда вы преобразуете весь массив в строки, поскольку их не нужно загружать из основной памяти в кеш. Люди склонны забывать, что процессор имеет кэш и что алгоритмы, которые выполняют большую часть своей работы в небольшой локальной области памяти, значительно выиграют от гораздо более быстрого доступа к кэшу. На некоторых архитектурах кэш-память намного быстрее, чем память, поэтому вы можете выполнять сотни операций с вашими данными за то время, которое потребовалось бы для загрузки их из основной памяти. Таким образом, выполнение большей работы в функции сравнения может быть значительно быстрее, чем предварительная обработка массива. Особенно если у вас большой массив.
Попробуйте выполнить сериализацию и сравнение строк в функции компаратора и сравните это. Я думаю, что это будет довольно хорошее решение. Пример псевдокода java-ish:
public static int compare(Number numA, Number numB) {
return numA.toString().compare(numB.toString());
}
Я думаю, что любые причудливые, немного мудрые сравнения, которые вы могли бы сделать, должны быть примерно эквивалентны работе по преобразованию чисел в строки. Таким образом, вы, вероятно, не получите значительную выгоду. Вы не можете просто сделать прямой бит для сравнения битов, который бы дал вам другой порядок, чем лексикографический. В любом случае вам нужно будет уметь вычислять каждую цифру для числа, поэтому проще всего сделать из них строки. There may be some slick trick, but every avenue I can think of off the top of my head is tricky, error-prone, and much more work than it is worth.
Если все числа меньше 1E+18, вы можете привести каждое число к UINT64, умножить на десять и добавить одно, а затем умножить на десять, пока они не станут равными 1E+19. Тогда сортируйте их. Чтобы вернуть исходные числа, делите каждое число на десять, пока последняя цифра не станет ненулевой (она должна быть единицей), а затем разделите на десять еще раз.
Вопрос не указывает, как относиться к отрицательным целым числам в лексикографическом порядке сортировки. Представленные ранее строковые методы обычно сортируют отрицательные значения во фронт; например, { -123, -345, 0, 234, 78 } будут оставлены в этом порядке. Но если знак минус предполагалось игнорировать, порядок вывода должен быть { 0, -123, 234, -345, 78 }. Можно было бы адаптировать метод на основе строк для получения этого порядка с помощью несколько громоздких дополнительных тестов.
Как в теории, так и в коде может быть проще использовать компаратор, который сравнивает дробные части общих логарифмов двух целых чисел. То есть он будет сравнивать мантиссы из 10 основных логарифмов двух чисел. Компаратор на основе логарифма будет работать быстрее или медленнее, чем компаратор на основе строк, в зависимости от характеристик производительности процессора с плавающей запятой и качества реализаций.
Код Java, показанный в конце этого ответа, включает два логарифмических компаратора: alogCompare а также slogCompare, Первый игнорирует знаки, поэтому выдает {0, -123, 234, -345, 78} из { -123, -345, 0, 234, 78 }.
Числовые группы, показанные далее, являются выводом, произведенным программой Java.
Раздел "Дар Рэнд" показывает массив случайных данных dar как генерируется. Он читает поперек, а затем вниз, 5 элементов в строке. Обратите внимание, массивы sar, lara, а также lars изначально несортированные копии dar,
Раздел "Дар сортировки" dar после сортировки через Arrays.sort(dar);,
Раздел "sar lex" показывает массив sar после сортировки с Arrays.sort(sar,lexCompare);, где lexCompare похож на Comparator показано в ответе Джейсона Коэна.
Раздел "lar s log" показывает массив lars после сортировки по Arrays.sort(lars,slogCompare);, иллюстрирующий логарифмический метод, который дает тот же порядок, что и do 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's 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");
}
}
Если вы хотите попробовать лучший preprocess-sort-postprocess, то обратите внимание, что int - это максимум 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 нет беззнаковых целых, вам придется немного его изменить. Он использует много рабочей памяти (в два раза больше входных данных), но это все же меньше, чем ваш первоначальный подход. Это может быть быстрее, чем преобразование в строки на лету в компараторе, но он использует больше пиковой памяти. В зависимости от GC, он может использовать меньше памяти и потребовать меньшего сбора.
Псевдокод:
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,
Таким образом, вы можете избежать преобразования чего-либо в строку - вам не нужна дополнительная память.
#!/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
Это включает время, необходимое для генерации 10000 элементов, но не время вывода их на консоль. Выход добавляет около секунды.
Так что сэкономьте немного времени программиста;-)
Если вы стремитесь к космической эффективности, я бы попробовал просто выполнить работу в функции сравнения
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
}
Если он слишком медленный (наверняка, он медленнее, чем предварительная обработка), отследите где-нибудь преобразования, чтобы функция сравнения не выполняла их.
Один действительно хакерский метод (с использованием C) будет:
- генерировать новый массив всех значений, преобразованных в числа с плавающей точкой
- сделайте сортировку, используя биты мантиссы (значимости и) для сравнения
На Java ( отсюда):
long bits = Double.doubleToLongBits(5894.349580349);
boolean negative = (bits & 0x8000000000000000L) != 0;
long exponent = bits & 0x7ff0000000000000L >> 52;
long mantissa = bits & 0x000fffffffffffffL;
так что вы бы отсортировать по длинному mantissa Вот.
Возможная оптимизация: вместо этого:
Я преобразовал каждое целое число в его строковый формат, затем добавил нули справа, чтобы все целые числа содержали одинаковое количество цифр
Вы можете умножить каждое число на (10^N - log10(число)), причем N - это число больше, чем log10 любого из ваших чисел.