регистронезависимый Pos

Question

Существует ли какая-либо сопоставимая функция, например Pos, которая не чувствительна к регистру в D2010 (Unicode)?

Я знаю, что могу использовать Pos (AnsiUpperCase (FindString), AnsiUpperCase (SourceString)), но это добавляет много времени обработки путем преобразования строк в верхний регистр при каждом вызове функции.

Например, в цикле 1000000 Pos занимает 78 мс, а преобразование в верхний регистр - 764 мс.

str1 := 'dfkfkL%&/s"#<.676505';
  for i := 0 to 1000000 do
    PosEx('#<.', str1, 1); // Takes 78ms

  for i := 0 to 1000000 do
    PosEx(AnsiUpperCase('#<.'), AnsiUpperCase(str1), 1); // Takes 764ms

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

Есть ли какая-либо другая функция, которая может быстрее, чем Pos +, преобразовывать строки в верхний регистр?

Answer 1

Встроенная функция Delphi для этого есть в AnsiStrings.ContainsText для AnsiStrings и StrUtils.ContainsText для строк Unicode.

Однако в фоновом режиме они используют логику, очень похожую на вашу логику.

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

Единственный способ обойти эти накладные расходы, это сделать эти преобразования вне цикла в максимально возможной степени.

Итак: следуйте собственному предложению, и у вас будет действительно хорошее решение.

- Йерун

Answer 2

Эта версия мой предыдущий ответ работает как в D2007, так и в D2010.

• В Delphi 2007 CharUpCaseTable составляет 256 байт
• В Delphi 2010 это 128 КБ (65535 * 2).

Причина: Char size. В более старой версии Delphi мой исходный код поддерживал только текущий набор символов локали при инициализации. Мой InsensPosEx примерно в 4 раза быстрее, чем ваш код. Конечно, можно идти еще быстрее, но мы потеряли бы простоту.

type
  TCharUpCaseTable = array [Char] of Char;

var
  CharUpCaseTable: TCharUpCaseTable;

procedure InitCharUpCaseTable(var Table: TCharUpCaseTable);
var
  n: cardinal;
begin
  for n := 0 to Length(Table) - 1 do
    Table[Char(n)] := Char(n);
  CharUpperBuff(@Table, Length(Table));
end;

function InsensPosEx(const SubStr, S: string; Offset: Integer = 1): Integer;
var
  n:            Integer;
  SubStrLength: Integer;
  SLength:      Integer;
label
  Fail;
begin
  Result := 0;
  if S = '' then Exit;
  if Offset <= 0 then Exit;

  SubStrLength := Length(SubStr);
  SLength := Length(s);

  if SubStrLength > SLength then Exit;

  Result := Offset;
  while SubStrLength <= (SLength-Result+1) do 
  begin
    for n := 1 to SubStrLength do
      if CharUpCaseTable[SubStr[n]] <> CharUpCaseTable[s[Result+n-1]] then
        goto Fail;
      Exit;
Fail:
    Inc(Result);
  end;
  Result := 0;
end;

//...

initialization
  InitCharUpCaseTable({var}CharUpCaseTable);

Answer 3

Я также столкнулся с проблемой преобразования FastStrings, которая использовала поиск Бойера-Мура (BM), чтобы набрать некоторую скорость, для D2009 и D2010. Так как многие из моих поисков ищут только один символ, и большинство из них ищет не алфавитные символы, моя версия SmartPos для D2010 имеет версию с перегрузкой с широким символом в качестве первого аргумента и выполняет простой цикл по строке чтобы найти это. Я использую верхний регистр обоих аргументов для обработки нескольких регистров без учета регистра. Я считаю, что для моих приложений скорость этого решения сопоставима с FastStrings.

Для случая 'string find' мой первый проход состоял в том, чтобы использовать SearchBuf, использовать верхний регистр и принять штраф, но я недавно изучал возможность использования реализации Unicode BM. Как вы, наверное, знаете, BM плохо или легко масштабируется до кодировок Unicode-пропорций, но есть реализация Unicode BM на Soft Gems . Это предшествует D2009 и D2010, но выглядит так, как если бы он конвертировался довольно легко. Автор Майк Лишке (Mike Lischke) решает проблему с прописными буквами, включая таблицу прописных букв Unicode размером 67 Кб, и это может оказаться слишком большим шагом для моих скромных требований. Поскольку мои строки поиска обычно короткие (хотя и не такие короткие, как ваш единственный трехсимвольный пример), накладные расходы на Unicode BM также могут быть ценой, которую не стоит платить: преимущество BM увеличивается с длиной искомой строки.

Это определенно ситуация, когда потребуется сравнение с некоторыми реальными примерами для конкретных приложений, прежде чем включать Unicode BM в мои собственные приложения.

Редактировать: некоторые базовые тесты показывают, что я был прав, опасаясь решения "Unicode Tuned Boyer-Moore". В моей среде UTBM приводит к увеличению кода, увеличению времени. Я мог бы рассмотреть возможность его использования, если мне понадобятся некоторые дополнительные функции, предоставляемые этой реализацией (обработка суррогатов и поиск только по целым словам).

Answer 4

Вот тот, который я написал и использовал в течение многих лет:

function XPos( const cSubStr, cString :string ) :integer;
var
  nLen0, nLen1, nCnt, nCnt2 :integer;
  cFirst :Char;
begin
  nLen0 := Length(cSubStr);
  nLen1 := Length(cString);

  if nLen0 > nLen1 then
    begin
      // the substr is longer than the cString
      result := 0;
    end

  else if nLen0 = 0 then
    begin
      // null substr not allowed
      result := 0;
    end

  else

    begin

      // the outer loop finds the first matching character....
      cFirst := UpCase( cSubStr[1] );
      result := 0;

      for nCnt := 1 to nLen1 - nLen0 + 1 do
        begin

          if UpCase( cString[nCnt] ) = cFirst then
            begin
              // this might be the start of the substring...at least the first
              // character matches....
              result := nCnt;

              for nCnt2 := 2 to nLen0 do
                begin

                  if UpCase( cString[nCnt + nCnt2 - 1] ) <> UpCase( cSubStr[nCnt2] ) then
                    begin
                      // failed
                      result := 0;
                      break;
                    end;

                end;

            end;


          if result > 0 then
            break;
        end;


    end;
end;

Answer 5

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

Answer 6

Библиотека кодов джедаев имеет StrIPos и ​​тысячи других полезных функций, дополняющих RTL Delphi. Когда я еще много работал в Delphi, JCL и его визуальный брат JVCL были одними из первых вещей, которые я добавил в только что установленный Delphi.

Answer 7

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

Это не совсем удивительно, так как при тестировании обработки строки Unicode в Delphi 2009 я обнаружил, что процедура RTL Pos () значительно улучшилась после Delphi 7, что частично объясняется тем, что аспекты библиотек FastCode были включены в RTL в течение некоторого времени.

С другой стороны, библиотека FastStrings давно не была значительно обновлена. В тестах я обнаружил, что многие подпрограммы FastStrings фактически были перегружены эквивалентными функциями RTL (с несколькими исключениями, объясняемыми неизбежными накладными расходами, вызванными дополнительными усложнениями Unicode).

Обработка «Char-Wise» решения, представленного Стивом, является лучшей на сегодняшний день.

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

Это могут быть редкие случаи, но рутина Стива избегает их и лишь на 10% медленнее, чем уже довольно быстрый Pos + Uppercase (ваши результаты бенчмаркинга не совпадают с моими в этом отношении).

Answer 8

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

Answer 9

Вместо 'AnsiUpperCase' вы можете использовать Table, это намного быстрее. Я изменил мой старый код. Это очень просто и очень быстро. Проверьте это:

type
  TAnsiUpCaseTable = array [AnsiChar] of AnsiChar;

var
  AnsiTable: TAnsiUpCaseTable;

procedure InitAnsiUpCaseTable(var Table: TAnsiUpCaseTable);
var
  n: cardinal;
begin
  for n := 0 to SizeOf(TAnsiUpCaseTable) -1 do
  begin
    AnsiTable[AnsiChar(n)] := AnsiChar(n);
    CharUpperBuff(@AnsiTable[AnsiChar(n)], 1);
  end;
end;

function UpCasePosEx(const SubStr, S: string; Offset: Integer = 1): Integer;
var
  n              :integer;
  SubStrLength   :integer;
  SLength        :integer;
label
  Fail;
begin
  SLength := length(s);
  if (SLength > 0) and (Offset > 0) then begin
    SubStrLength := length(SubStr);
    result := Offset;
    while SubStrLength <= SLength - result + 1 do begin
      for n := 1 to SubStrLength do
        if AnsiTable[SubStr[n]] <> AnsiTable[s[result + n -1]] then
          goto Fail;
      exit;
Fail:
      inc(result);
    end;
  end;
  result := 0;
end;

initialization
  InitAnsiUpCaseTable(AnsiTable);
end.