Как преобразовать длинные Java как строки, сохраняя естественный порядок

Question

В настоящее время я смотрю на простую проблему программирования, которую было бы интересно оптимизировать - по крайней мере, для любого, кто считает, что программирование - это искусство :) Вот оно:

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

Кроме того, строковое представление должно соответствовать ^[A-Za-z0-9]+$. (Здесь я не слишком строг, но избегайте использования управляющих символов или чего-либо, что может вызвать головную боль при кодировании, недопустимо в XML, имеет разрывы строк или подобные символы, которые, безусловно, вызовут проблемы) *

Вот тестовый пример JUnit:

@Test
public void longConversion() {
    final long[] longs = { Long.MIN_VALUE, Long.MAX_VALUE, -5664572164553633853L,
            -8089688774612278460L, 7275969614015446693L, 6698053890185294393L,
            734107703014507538L, -350843201400906614L, -4760869192643699168L,
            -2113787362183747885L, -5933876587372268970L, -7214749093842310327L, };

    // keep it reproducible
    //Collections.shuffle(Arrays.asList(longs));

    final String[] strings = new String[longs.length];
    for (int i = 0; i < longs.length; i++) {
        strings[i] = Converter.convertLong(longs[i]);
    }

    // Note: Comparator is not an option
    Arrays.sort(longs);
    Arrays.sort(strings);

    final Pattern allowed = Pattern.compile("^[A-Za-z0-9]+$");
    for (int i = 0; i < longs.length; i++) {
        assertTrue("string: " + strings[i], allowed.matcher(strings[i]).matches());
        assertEquals("string: " + strings[i], longs[i], Converter.parseLong(strings[i]));
    }
}

а вот методы, которые я ищу

public static class Converter {
    public static String convertLong(final long value) {
        // TODO
    }

    public static long parseLong(final String value) {
        // TODO
    }
}

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

Кроме того, было бы неплохо, если бы это преобразование было

• как можно короче
• легко реализовать на других языках

РЕДАКТИРОВАТЬ: Я очень рад видеть, что два очень уважаемых программиста столкнулись с той же проблемой, что и я: использование «-» для отрицательных чисел не может работать, так как «-» не меняет порядок сортировки :

1. -0001
2. -0002
3. 0000
4. 0001
5. 0002

Answer 1

Хорошо, возьми два:

class Converter {
  public static String convertLong(final long value) {
    return String.format("%016x", value - Long.MIN_VALUE);
  }

  public static long parseLong(final String value) {
    String first = value.substring(0, 8);
    String second = value.substring(8);
    long temp = (Long.parseLong(first, 16) << 32) | Long.parseLong(second, 16);
    return temp + Long.MIN_VALUE;
  }
}

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

for (long aLong : longs) {
  String out = Converter.convertLong(aLong);
  System.out.printf("%20d %16s %20d\n", aLong, out, Converter.parseLong(out));
}

Выход:

-9223372036854775808 0000000000000000 -9223372036854775808
 9223372036854775807 ffffffffffffffff  9223372036854775807
-5664572164553633853 316365a0e7370fc3 -5664572164553633853
-8089688774612278460 0fbba6eba5c52344 -8089688774612278460
 7275969614015446693 e4f96fd06fed3ea5  7275969614015446693
 6698053890185294393 dcf444867aeaf239  6698053890185294393
  734107703014507538 8a301311010ec412   734107703014507538
 -350843201400906614 7b218df798a35c8a  -350843201400906614
-4760869192643699168 3dedfeb1865f1e20 -4760869192643699168
-2113787362183747885 62aa5197ea53e6d3 -2113787362183747885
-5933876587372268970 2da6a2aeccab3256 -5933876587372268970
-7214749093842310327 1be00fecadf52b49 -7214749093842310327

Как видите, Long.MIN_VALUE и Long.MAX_VALUE (первые две строки) верны, а остальные значения в основном совпадают.

Что это делает?

Предполагая, что у вас есть подписанные байтовые значения:

• -128 => 0x80
• -1 => 0xFF
• 0 => 0x00
• 1 => 0x01
• 127 => 0x7F

Теперь, если вы добавите 0x80 к этим значениям, вы получите:

• -128 => 0x00
• -1 => 0x7F
• 0 => 0x80
• 1 => 0x81
• 127 => 0xFF

правильный порядок (с переполнением).

По сути, вышеизложенное делает это с 64-разрядными знаковыми длинными значениями вместо 8-разрядных знаковых байтов.

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

return Long.parseLong(value, 16);

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

Answer 2

РЕДАКТИРОВАТЬ: Хорошо, поэтому просто добавление отрицательного знака для отрицательных чисел не работает ... но вы можете преобразовать значение в эффективно "беззнаковый" длинный, такой, что Long.MIN_VALUE соответствует "0000000000000000", и Long. MAX_VALUE отображается на "FFFFFFFFFFFFFFFF". Труднее читать, но получит правильные результаты.

В основном вам просто нужно добавить 2 ^ 63 к значению, прежде чем превратить его в шестнадцатеричное - но это может быть небольшой болью в Java из-за отсутствия беззнаковых длинных слов ... это может быть проще всего сделать с помощью BigInteger * * 1004

private static final BigInteger OFFSET = BigInteger.valueOf(Long.MIN_VALUE)
                                                   .negate();

public static String convertLong(long value) {
    BigInteger afterOffset = BigInteger.valueOf(value).add(OFFSET);
    return String.format("%016x", afterOffset);
}

public static long parseLong(String text) {
    BigInteger beforeOffset = new BigInteger(text, 16);
    return beforeOffset.subtract(OFFSET).longValue();
}

По общему признанию, это было бы не очень эффективно, но оно работает со всеми вашими тестами.

Answer 3

В RFC2550 есть методика - RFC от 1 апреля о проблеме Y10K с 4-значными датами - которая может быть применена для этой цели. По сути, каждый раз, когда целочисленное строковое представление увеличивается, требуя, чтобы для сохранения желаемого порядка сортировки добавлялась другая цифра, другая буква или другой (печатный) символ. Негативные правила более загадочны и дают строки, которые сложнее прочитать с первого взгляда ... но все же достаточно легко применять в коде.

Хорошо, для положительных чисел они все еще читаемы.

См:

http://www.faqs.org/rfcs/rfc2550.html

Answer 4

Если вам не нужна печатаемая строка, вы можете закодировать long в четыре символа после смещения значения на Long.MIN_VALUE (-0x80000000) для эмуляции беззнакового long:

public static String convertLong(long value) {
    value += Long.MIN_VALUE;
    return "" + 
        (char)(value>>48) + (char)(value>>32) + 
        (char)(value>>16) + (char)value; 
}

public static long parseLong(String value) {
    return (
        (((long)value.charAt(0))<<48) + 
        (((long)value.charAt(1))<<32) + 
        (((long)value.charAt(2))<<16) + 
        (long)value.charAt(3)) + Long.MIN_VALUE;
}

Использование суррогатных пар не является проблемой, поскольку естественный порядок строки определяется значениями UTF-16 в ее символах, а не значениями кодовой точки UCS-2.