Самый быстрый способ получить число в хвосте строки

Question

Учитывая, что у нас есть строка этого типа "XXXXXXX XXXXX 756", "XXXXX XXXXXX35665", (X является символом), который является быстрым способом получить число в конце строки?

РЕДАКТИРОВАТЬ: ну, это просто для забавы вопрос. Решить это довольно просто, но я хочу знать самый быстрый алгоритм для архивирования этого. Качни это!

Answer 1

В C быстрый однократный алгоритм O (n) (не видит отрицательных знаков):

int suffixedNumber(char* string) {
  int result = 0;
  char ch;
  while (ch = *string++)
    // Check whether <= '9' first, because most characters are > '9'.
    result = (ch <= '9' && ch >= '0') ? 10*result + (ch - '0') : 0;
  return result;
}

Если у вас все в порядке с goto с, вы можете получить алгоритм на 20% быстрее, который (в порядке важности):

1. возвращает -1, если в конце string
2. избегает проверки конца строки, когда ch >= '0'
3. избегает сброса result в ноль, когда ch не числовой
4. избегает умножения result на десять, когда число начинается
5. избегает установки result в ноль в начале

int suffixedNumber(char* string) {
  int result;
  char ch;

  nonnumber: // STATE: Waiting for the start of a number.
  ch = *string++;
  if (ch > '9') goto nonnumber; // Decide this boundary first (> '9' most frequent)
  if (ch < '0') {               // Decide this boundary next
    if (ch == '\0') return -1;  // Decide this boundary last  ('\0' least frequent)
    goto nonnumber;
  }
  result = ch - '0';

  number:    // STATE: In the middle of a number.
  ch = *string++;
  if (ch > '9') goto nonnumber;    // Decide this boundary first (> '9' most frequent)
  if (ch < '0') {                  // Decide this boundary next
    if (ch == '\0') return result; // Decide this boundary last  ('\0' least frequent)
    goto nonnumber;
  }
  result = 10*result + (ch - '0');

  goto number;
}

Answer 2

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

numDigits = 0
number = 0

while(numDigits <> length and characterAt[length - numDigits] is a digit)
   number = number + (parseCharacterAt[length - numDigits] * (10 ^ numDigits))
   numDigits = numDigits + 1
end while

if(numDigits is 0)
  Error ("No digits at the end")

else return number

Примечание: (10 ^ numDigits) можно легко оптимизировать с помощью другой переменной.

Answer 3

извлечение номера хвоста

    str="XXXXXx....XXXX333"; 
    parseInt(str.match(/\d*$/)

если требуется точка с плавающей запятой, то

    parseInt(str.match(/\d|\.*$/)

увеличение номера хвоста:

    str.replace(/(\d*)$/,function(){return parseInt(arguments[0])+1;})

Answer 4

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

string s = "XXXXX XXXXXX35665";
int i = s.Length;
while (--i >= 0 && Char.IsNumber(s[i]));
s=s.Substring(i + 1);

должно помочь ... ??

Answer 5

с указанием проблемы:

Мы хотим найти индекс последнего нецифрового символа

Рефлексия:

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

Реализация:

Линейный обратный поиск, возможно, включающий побитовый трюк для «векторизации» операций (сравнение нескольких символов одновременно) или использование многопоточности.

Answer 6

Я бы просто вызвал lastIndexOf ('X') вашего объекта String и продолжил бы оттуда.Не беспорядочная петля.

Answer 7

используйте регулярное выражение:

/^.+?(\d+)$/

и возьмите первую группу захвата совпадений (\ d +)

Правка: , если вы не можете использовать регулярные выражения, FASTEST WAY будет примерно таким:

i = string.len
while i > 0:
  break if string[i].isNotNum
  i--
end

out = substring(string, i,string.len)

Answer 8

Не зная языка или контекста, если бы число цифр или символов фиксированной длины, что бы делала простая подстрока, в противном случае регулярное выражение соответствует последовательным цифрам (т. Е. /\d+/).

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