БЛОГ НА HUSL


Порядок на числах в виде строк

Автор вопроса: Stanislav Volodarskiy

Это задача, разминка для ума. Даны два целых числа в строковом виде, требуется их сравнить.

Самое простое – перевести строки в числа и сравнить их. Но значения строк могут быть слишком велики чтобы поместиться в ограниченное целое, если мы говорим про C++. Или перевод строк в числа может занять слишком много времени, если мы говорим про Питон.

Можно сравнивать непосредственно строки. На С++ получится что-то такое:

bool le(const std::string_view &a, const std::string_view &b) {
    if (a[0] == '-') {
        if (b[0] == '-') {
            return le(b.substr(1), a.substr(1));
        }
        return true;
    }
    if (b[0] == '-') {
        return false;
    }
    if (a.size() < b.size()) {
        return true;
    }
    if (a.size() > b.size()) {
        return false;
    }
    return a <= b;
}

Работает, но сложно устроено: надо проверить знаки и убрать их, если оба числа отрицательные. Потом надо сравнить длины строк. Только потом можно наконец сравнить сами строки.

Отсюда собственно задача: придумайте функцию, которая по строковому десятичному представлению целого числа, строит другую строку-ключ. Порядок ключей как строк должен совпасть с порядком исходных чисел.

Что надо написать внутри key, чтобы le упростилась до сравнения двух ключей?

std::string key(const std::string_view &a) {
    ???
}

bool le(const std::string_view &a, const std::string_view &b) {
    return key(a) <= key(b);
}

P.S. Примеры приведены на C++, потому что вопрос, который подал мне идею, был на С++. Но решать задачу можно на любом языке.


Источник

Ответы (4 шт):

Автор решения: Fox Fox 
import time

def f_compare_string_numbers(v_a: str, v_b: str) -> str:
 # Обработка знаков
 v_a_neg = v_a.startswith('-')
 v_b_neg = v_b.startswith('-')
 
 # Разные знаки
 if v_a_neg != v_b_neg:
  return f"{v_a} {'<' if v_a_neg else '>'} {v_b}"
 
 # Чистка чисел
 v_a_clean = v_a.lstrip('-').lstrip('0') or '0'
 v_b_clean = v_b.lstrip('-').lstrip('0') or '0'
 
 # Сравнение длин
 if len(v_a_clean) > len(v_b_clean):
  return f"{v_a} {'<' if v_a_neg else '>'} {v_b}"
 if len(v_b_clean) > len(v_a_clean):
  return f"{v_a} {'>' if v_a_neg else '<'} {v_b}"
 
 # Посимвольное сравнение
 for v_d_a, v_d_b in zip(v_a_clean, v_b_clean):
  if v_d_a > v_d_b:
   return f"{v_a} {'<' if v_a_neg else '>'} {v_b}"
  if v_d_b > v_d_a:
   return f"{v_a} {'>' if v_a_neg else '<'} {v_b}"
 
 return f"{v_a} == {v_b}"

# Пример использования
v_num1 = "-124546466430000464646464661248484848884808848484884848483663637373"
v_num2 = "-1245565656666666666666666666666666666666666666666777777777777777777777777777777777788888888888"
v_start = time.time()
v_result = f_compare_string_numbers(v_num1, v_num2)
v_time = time.time() - v_start

print(f"{v_result} ({v_time:.6f} сек)")

Результат: 0.000015 сек

→ Ссылка
Автор решения: Solt

Что-то лениво код писать. Но выглядит всё просто. Если мы пишем функцию нормализации для сравнения в виде key(a)<key(b), очевидно надо добить строки нулями слева до фиксированной длины. Минус переставить на начало, вместо плюса - любой символ с ASCII-кодом больше минуса, можно лишним нулём, он точно больше.

Если строки не фиксируем, давайте хотя бы зафиксируем длину числа, представляющего длину строки. Пусть будет 6. Добиваем длину строки до 6 знаков нулями. Префиксом ставим те же -/.(точка следом за минусом идёт в ASCII) потом длину, потом строку, которую уже можно не нормализовать.

Для сравнения отрицательных чисел между собой результирующую строку (вместе с длиной) посимвольно выворачиваем по формуле с=9-с

Пример

a=1234567890
b=-1987654321111
key(a)=.0000101234567890
key(b)=-9999868012345678888

А на PHP я б вообще не думал:

return bccomp($a,$b);

Иногда бывают несравнимые вещи, которые надо как-то сравнить.

Алгоритм присвоения весов обычно такой - каждому критерию дают свои знакоместа по важности и каждый критерий вписывается со своим весом. Либо не знакоместа, а разряды в числе, если все критерии с их диапазонами можно уложить в число. Потом простая сортировка.

→ Ссылка
Автор решения: Serge3leo

функцию, которая по строковому десятичному представлению целого числа, строит другую строку-ключ

Базовое представление числа:

  • Положительные числа: p*o;
  • Отрицательные числа: m*n;

где число символов [pm] - равно абсолютной величине числа.

По сути, это представление полностью удовлетворяет условиям задачи. Однако, функция std::string key(const std::string_view &a) получится хотя и тривиальной, но достаточно длиной.

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

const std::string dsep = "'"s;  // Декоративный разделитель
void neg_digs(std::string& digs) {
    for (auto&& c: digs) {
        c = 'Z' - (c - '0');
    }
}
void strip0int(std::string& n) {
    // Заменяет все завершающие '0' на '+', т.е. для отрицательных чисел
    // получится, что завершающие 'Z' на '_'.
    static_assert('+' < '0');
    size_t last0 = n.size();
    while (0 < last0 && '0' == n[last0 - 1]) {
        last0--;
    }
    if (last0 + 1 < n.size()) {
        assert('0' == n[last0]);
        n[last0] = '+';
        n.resize(last0 + 1);
    }
}
std::string key(const std::string_view &a) {
    assert(a.size() > 0);
    static_assert('m' < 'n' && 'n' < 'o' && 'o' < 'p');
    char sign = 'p';
    size_t start = 0;
    std::string stop = "o"s + dsep;
    switch (a[0]) {
     case '-':
         sign = 'm';
         stop = "n"s + dsep;
     case '+':
         start = 1;
    }
    assert(a.find_first_not_of("0123456789"s, start) == std::string::npos);
    while (start < a.size() && '0' == a[start]) {
        start++;
    }
    size_t len = a.size() - start;
    std::string slen = (len ? std::to_string(len) : ""s);
    size_t slensize = slen.size();
    std::string tail(a.substr(start));
    strip0int(slen);
    strip0int(tail);
    if ('m' == sign) {
        neg_digs(slen);
        neg_digs(tail);
    }
    return std::string(slensize, sign) + stop + slen + dsep + tail;
}

Пример использования (ключи для ±гуголплекс синтезируем "на коленке" по причине невозможности их получения через заданный интерфейс):

int main() {
    size_t googolplex_npower = 100;
    std::string key_m_googolplex =
                        std::string(googolplex_npower + 1, 'm') + "n'Y"s +
                        std::string(googolplex_npower - 1, 'Z') + "Y'Y_"s;
    std::string key_googolplex =
                        std::string(googolplex_npower + 1, 'p') + "o'1"s +
                        std::string(googolplex_npower - 1, '0') + "1'1+"s;
    std::string googol = "1"s + std::string(100, '0');
    std::string tns[] = {"-"s + googol,
                         "-12345678901"s, "-1010"s, "-1000"s,
                         "-201"s, "-0200"s, "-199"s, "-1"s,
                         "-0"s, "000"s, "0"s, "+0"s,
                         "1"s, "199"s, "0200"s, "201"s,
                         "1000"s, "1010"s, "12345678901"s,
                         googol};
    std::string prev = key_m_googolplex;
    println("key of -googolplex = {}", key_m_googolplex);
    for (auto n: tns) {
        std::string kn = key(n);
        println("{:>14}: {}", n, kn);
        assert(prev <= kn);
        prev = kn;
    }
    println("key of googolplex = {}", key_googolplex);
    assert(prev <= key_googolplex);
    return 0;
}

Выдача:

key of -googolplex = mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm \
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm \
mmmmmmmmmmmmmmn'YZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ \
ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ \
ZZZZZZZZY'Y_
-10000000000000000000000000000000000000000000000000000 \
000000000000000000000000000000000000000000000000: mmmn'YZY'Y_
  -12345678901: mmn'YY'YXWVUTSRQZY
         -1010: mn'V'YZYZ
         -1000: mn'V'Y_
          -201: mn'W'XZY
         -0200: mn'W'X_
          -199: mn'W'YQQ
            -1: mn'Y'Y
            -0: mn'Z'
           000: po'0'
             0: po'0'
            +0: po'0'
             1: po'1'1
           199: po'3'199
          0200: po'3'2+
           201: po'3'201
          1000: po'4'1+
          1010: po'4'1010
   12345678901: ppo'11'12345678901
100000000000000000000000000000000000000000000000000000 \
00000000000000000000000000000000000000000000000: pppo'101'1+
key of googolplex = pppppppppppppppppppppppppppppppppp \
pppppppppppppppppppppppppppppppppppppppppppppppppppppp \
pppppppppppppo'100000000000000000000000000000000000000 \
000000000000000000000000000000000000000000000000000000 \
00000001'1+

P.S.

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

P.P.S.

Ключи от чисел общего вида не равных нулям и бесконечностям являются конкатенацией: знака, экспоненты, представленной ключом целого числа, и нормализованной мантиссы (у мантиссы всегда завершающие '0' заменяются на '+' ('Z' на '_'), для отрицательных чисел: экспонента берётся со знаком минус, а цифры мантиссы инвертируются). "+0", "-0", "+inf" и "-inf" имеют особенные представления, естественно, для "±nan(n)" и "±snan(n)" ключи не определены.

Ограничение на формат входных данных, грубо говоря: %g или {}, связано с тем, что бы не возникало необходимости сложения экспоненты в текстовом представлении с числом знаков целой части мантиссы.

Забавно, что требования на упорядоченность и простоту реализации, опять вызывают необходимость взять "логарифм". Т.е. если для целых чисел базовое кодирование применялось для длины представления длины числа, то для чисел общего вида базовое кодирование используется для длины представления длины представления длины числа. ? Обобщённый ключ гуголплекса: "Ppppo'101'1+'1+", заметно короче его же ключа для целых чисел. ?

const std::string ddot = ","s;  // Декоративная десятичная запятая ('^' - для отрицательных)
void neg_key(std::string& key) {
    for (auto&& c: key) {
        if ('m' <= c && c <= 'p') {
            c = 'p' - (c - 'm');
        } else if ('+' <= c && c <= '9') {
            c = 'Z' - (c - '0');
        } else if ('Z' - 9 <= c && c <= '_') {
            c = '0' + ('Z' - c);
        }
    }
}
void strip0fix(std::string& n) {
    // Удаляет все завершающие '0'
    // Добавляет '+' в конец
    assert("+"s < ddot && ddot < "0"s);
    size_t last0 = n.size();
    while (0 < last0 && ('0' == n[last0 - 1] || ddot[0] == n[last0 - 1])) {
        last0--;
    }
    if (last0 < n.size() || ddot[0] == n[last0]) {
        assert('0' == n[last0] || ddot[0] == n[last0]);
        n[last0] = '+';
        n.resize(last0 + 1);
    } else if (n.size() && '0' <= n[n.size() - 1]) {
        n = n + "+"s;
    }
}
std::string gkey(const std::string &a) {
    assert(a.size() > 0);
    static_assert('M' < 'P' && 'p' < 'z' && '0' < 'm' &&
                  '/' < 'm' && 'p' < '~');
    std::string sign = "P"s;
    size_t start = 0;
    switch (a[0]) {
     case '-':
         sign = "M"s;
     case '+':
         start = 1;
    }
    if (start < a.size() && ('i' == std::tolower(a[start]) ||
                             'n' == std::tolower(a[start]))) {
        // TODO: inf, Infinity, NaN, NAN(123), ...
        return sign + ("M"s == sign ? "/"s : "~"s) + a.substr(start);
    }
    while (start < a.size() && '0' == a[start]) {
        start++;
    }
    std::string mant;
    std::string kexp;
    size_t pexp = a.find_first_of("eE"s, start);
    if (std::string::npos != pexp) {
        assert((start + 1 == pexp ||
                (start + 1 < pexp && '.' == a[start + 1])) && "Не реализовано");
        mant = a.substr(start, 1) + ddot;
        if (start + 2 < pexp) {
            mant += a.substr(start + 2, pexp - start - 2);
        }
        kexp = key(a.substr(pexp + 1));
        if ("n''" == kexp) {
            kexp = "o''"s;  // -0 => +0
        }
    } else {
        std::string i;
        std::string f;
        size_t pdot = a.find('.', start);
        if (std::string::npos != pdot) {
            i = a.substr(start, pdot - start);
            f = a.substr(pdot + 1);
        } else {
            i = a.substr(start);
            f = ""s;
        }
        ssize_t exp;
        if (i.size()) {
            assert('0' != i[0]);
            mant = i.substr(0, 1) + ddot + i.substr(1) + f;
            exp = ssize_t(i.size()) - 1;
        } else {
            size_t fstart = 0;
            while (fstart < f.size() && '0' == f[fstart]) {
                fstart++;
            }
            if (fstart < f.size()) {
                mant = f.substr(fstart, 1) + ddot + f.substr(fstart + 1);
                exp = -(fstart + 1);
            } else {
                mant = ""s;
                exp = 0;
            }
        }
        kexp = key(std::to_string(exp));
    }
    assert(mant.find_first_not_of("0123456789"s + ddot) == std::string::npos);
    strip0fix(mant);
    if (mant.size()) {
        if ("M"s == sign) {
            neg_key(kexp);
            neg_digs(mant);
        }
        return sign + kexp + dsep + mant;
    }
    return sign + ("M"s == sign ? "z"s : "0"s);
}

Примеры:

                                         -inf: M/inf
-1e10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000: Mmmmn'YZY'Y_'Y_
  -1.18973149535723176508575932662800702e4932: Mmn'V'VQWX'Y^YRQSWYVQUWUSXWYSTUZRUSUQWXTTXRZZSZX_
                     -1.7976931348623157e+308: Mmn'W'WZR'Y^SQSTQWYWVRTXWYUS_
                                       -1e100: Mmn'W'Y_'Y_
                                 -12345678901: Mmn'X'YZ'Y^XWVUTSRQZY_
                            -1.2345678901e+10: Mmn'X'YZ'Y^XWVUTSRQZY_
                                        -1010: Mmn'Y'W'Y^ZY_
                                        -1000: Mmn'Y'W'Y_
                                      -201.01: Mmn'Y'X'X^ZYZY_
                                    -201.0100: Mmn'Y'X'X^ZYZY_
                                      -2.01e2: Mmn'Y'X'X^ZY_
                                         -201: Mmn'Y'X'X^ZY_
                                        -0200: Mmn'Y'X'X_
                                         -199: Mmn'Y'X'Y^QQ_
                                           -1: Mn'''Y_
                                          -1.: Mn'''Y_
                                         -1.0: Mn'''Y_
                                        -1e+0: Mn'''Y_
                                        -1e-0: Mn'''Y_
                                         -1e0: Mn'''Y_
                                        -1.e0: Mn'''Y_
                                       -1.0e0: Mn'''Y_
                                      -0.0100: Mpo'1'2'Y_
                                        -0.01: Mpo'1'2'Y_
                                       -1.e-2: Mpo'1'2'Y_
                                     -1.00e-2: Mpo'1'2'Y_
                                      -5e-324: Mpo'3'324'U_
-6.475175119438025110924438958227646552e-4966: Mpo'4'4966'T^VSUYSUYYQVWRZXUYYZQXVVWRQURXXSTVTUUX_
                                           -0: Mz
                                         -0.0: Mz
                                          000: P0
                                            0: P0
                                           +0: P0
                                         0.00: P0
 6.475175119438025110924438958227646552e-4966: Pmn'V'VQTT'6,475175119438025110924438958227646552+
                                       5e-324: Pmn'W'WXV'5+
                                       0.0100: Pmn'Y'X'1+
                                         0.01: Pmn'Y'X'1+
                                        1.e-2: Pmn'Y'X'1+
                                      1.00e-2: Pmn'Y'X'1+
                                            1: Po'''1+
                                           1.: Po'''1+
                                          1.0: Po'''1+
                                         1.00: Po'''1+
                                          1e0: Po'''1+
                                         1e+0: Po'''1+
                                         1e-0: Po'''1+
                                         1.e0: Po'''1+
                                        1.0e0: Po'''1+
                                          199: Ppo'1'2'1,99+
                                         0200: Ppo'1'2'2+
                                       2.01e2: Ppo'1'2'2,01+
                                          201: Ppo'1'2'2,01+
                                     201.0100: Ppo'1'2'2,0101+
                                       201.01: Ppo'1'2'2,0101+
                                         1000: Ppo'1'3'1+
                                         1010: Ppo'1'3'1,01+
                                  12345678901: Ppo'2'10'1,2345678901+
                              1.2345678901e10: Ppo'2'10'1,2345678901+
                                        1e100: Ppo'3'1+'1+
                      1.7976931348623157e+308: Ppo'3'308'1,7976931348623157+
   1.18973149535723176508575932662800702e4932: Ppo'4'4932'1,18973149535723176508575932662800702+
1e10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000: Ppppo'101'1+'1+
                                          inf: P~inf
→ Ссылка
Автор решения: Qwertiy

https://godbolt.org/z/sboM1jjas

#include <iostream>
#include <string>
#include <compare>

using namespace std;

strong_ordering cmp(const string_view &a, const string_view &b)
{
  bool inv = false;

  if (a[0] == '-')
    if (b[0] == '-')
      inv = true;
    else
      return strong_ordering::less;
  else if (b[0] == '-')
    return strong_ordering::greater;

  auto res = a.length() <=> b.length();
  if (res == 0) res = a <=> b;
  return inv ? 0 <=> res : res;
}

int main()
{
  cout << (cmp("128", "256") < 0) << endl;
  cout << (cmp("-128", "128") < 0) << endl;
  cout << (cmp("128", "-128") > 0) << endl;
  cout << (cmp("128", "100") > 0) << endl;
  cout << (cmp("128", "1280") < 0) << endl;
  cout << (cmp("1280", "128") > 0) << endl;
  cout << (cmp("128", "128") == 0) << endl;
  cout << (cmp("-128", "-100") < 0) << endl;
  cout << (cmp("-128", "-1280") > 0) << endl;
  cout << (cmp("-1280", "-128") < 0) << endl;
  cout << (cmp("-128", "-128") == 0) << endl;

  return 0;
}

При желании функцию сравнения можно сократить, впрочем сравнений в неё станет выполняться чуть больше:

https://godbolt.org/z/TrfevEnjT

strong_ordering cmp(const string_view &a, const string_view &b)
{
  auto res = (b[0] == '-') <=> (a[0] == '-');
  if (res != 0) return res;
  res = a.length() <=> b.length();
  if (res == 0) res = a <=> b;
  return a[0] == '-' ? 0 <=> res : res;
}

то надо написать внутри key, чтобы le упростилась до сравнения двух ключей?

Думаю, так делать не надо, поскольку текущее сравнение во многих случаях отработает гораздо быстрее - если длины строк или знаки чисел различаются, то сравнение выполнится за O(1), а если совпадают, то за O(min(len(a), len(b))), а ключ невозможно построить быстрее, чем O(n), соответственно сравнение по ключам будет всегда работать за O(max(len(a), len(b))). На разницу между min и max тоже стоит обратить внимание.

→ Ссылка

licensed under cc by-sa 3.0 with attribution.