Функция PosEx из Share.pas

Вверх ↑

Форумы ПрочееФункция PosEx из Share.pas ← Ctrl1 2 3 4 567 8 9 10 11 12Ctrl →

Этот топик читают: Гость

Разработчик

Ответов: 26170

Рейтинг: 2127

#76: 2010-04-22 14:22:56 ЛС | профиль | цитата

Tad писал(а):

спасибо Alex2

А кто это

------------ Дoбавленo в 14.22:
Насколько быстродействие ASM выше при 64 кб текстах

Результаты сравнения есть

карма: 22

Ответов: 16884

Рейтинг: 1239

#77: 2010-04-22 14:34:21 ЛС | профиль | цитата

nesco писал(а):

А кто это ?

Это изобретатель велосипеда

Я думал, что ты там был.
code_17899.txt

nesco писал(а):

Насколько быстродействие ASM выше при 64 кб текстах

Несущественно - на 5-10 мс. (но стабильно меньше).

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

файлы: 1

code_17899.txt [1.4KB] [176]

Разработчик

Ответов: 4698

Рейтинг: 426

#78: 2010-04-22 15:12:55 ЛС | профиль | цитата

nesco, а почему бы в строке

#pas
if SubStr[i] <> S[Ps - lp + i] then
begin
  Ps := Ps + 1;
  Break;
end

Не заменить на

#pas
if SubStr[i] <> S[Ps - lp + i] then
begin
  Ps := Ps + BMT[ord(S[ps - lp + i])] - i + 1;
  Break;
end

Так будет еще быстрее, чем просто + 1

карма: 10

Мой сайт, Мои рассказы

Разработчик

Ответов: 26170

Рейтинг: 2127

#79: 2010-04-22 15:31:04 ЛС | профиль | цитата

Assasin писал(а):

Не заменить на

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

карма: 22

Разработчик

Ответов: 4698

Рейтинг: 426

#80: 2010-04-22 15:38:02 ЛС | профиль | цитата

nesco писал(а):

Но это нарушение алгоритма

Так мы гонимся не за соблюдением алгоритма, а за скоростью, а тут как раз смещение сразу, без лишних проверок, а значит быстрее
------------ Дoбавленo в 15.38:
Я поменял (а точнее изменил) только одну строчку, вот код, который я для себя написал (по твоему коду) для тренировки:

#pas
  function PosEx(const SubStr,Str:string; const offset:cardinal = 1):cardinal;
  var ln,p,i:integer;
      bmt:array[0..255] of integer;
  begin
    ln := length(SubStr);
    for i := 0 to 255 do bmt[i] := ln;
    for i := ln downto 1 do
     if bmt[ord(SubStr[i])] = ln then bmt[ord(SubStr[i])] := ln - i;
    Result := 0;
    p := integer(offset) + ln - 1;
    while p <= length(Str) do
     if SubStr[ln] <> Str[p] then p := p + bmt[ord(Str[p])]
     else for i := ln downto 1 do
      if SubStr[i] <> Str[p - ln + i] then begin
        p := p + bmt[ord(Str[p - ln + i])] - i + 1; //тута
        break;
      end else if i = 1 then begin
        Result := p - ln + 1;
        exit;
     end;
  end;

И он работает

карма: 10

Мой сайт, Мои рассказы

Ответов: 16884

Рейтинг: 1239

#81: 2010-04-22 15:41:41 ЛС | профиль | цитата

Assasin, а сам на практике пробовал или ты теоретик.
Висит прога.

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

Разработчик

Ответов: 26170

Рейтинг: 2127

#82: 2010-04-22 15:45:17 ЛС | профиль | цитата

Tad писал(а):

Висит прога

И у меня висит

карма: 22

Разработчик

Ответов: 4698

Рейтинг: 426

#83: 2010-04-22 15:51:45 ЛС | профиль | цитата

Как в мертвый?

У меня вот это прекрасно работает без мертвых
code_17901.txt
------------ Дoбавленo в 15.49:
И под обоими компилляторами

------------ Дoбавленo в 15.51:
И еще можно было спокойно обойтись без лишнего условия при составлении таблицы отступов

#pas
for i := 1 to lp do bmt[ord(SubStr[i])] := lp - i;

карма: 10

Мой сайт, Мои рассказы

файлы: 1 code_17901.txt [3.3KB] [168]

Разработчик

Ответов: 26170

Рейтинг: 2127

#84: 2010-04-22 15:55:12 ЛС | профиль | цитата

Assasin писал(а):

И еще можно было спокойно обойтись без лишнего условия при составлении таблицы отступов

Умник, млин. Это защита от "неправильных" слов и повторений, нужно обязательно.
Хватит эксперименты ставить. Берешь последнюю тестовую прогу, качаешь тестовый файл и вперед -- проверять. Остальные "умные" предложения можешь оставить себе до выяснения их работоспособности

А когда свои новшества проверишь на тестовй проге, вот тогда и делай выводы о их работоспособности и скорости исполнения

карма: 22

Разработчик

Ответов: 4698

Рейтинг: 426

#85: 2010-04-22 16:06:16 ЛС | профиль | цитата

nesco писал(а):

Это защита от "неправильных" слов

По конкретнее на примерах

nesco писал(а):

и повторений

Так я же заменил i := lp downto 1 на i := 1 to lp, или я что то опять не понял?

nesco писал(а):

Остальные "умные" предложения можешь оставить себе

Твое право...

карма: 10

Мой сайт, Мои рассказы

Ответов: 4641

Рейтинг: 334

#86: 2010-04-22 16:11:05 ЛС | профиль | цитата

[flood]

nesco писал(а):

Остальные "умные" предложения можешь оставить себе до выяснения их работоспособности

я тут мимо проходил.
nesco, ну грубо то как высказался.... почти послал Assasin -на , ....

[/flood]

карма: 1

Время верстки: %cr_time% Текущее время: %time%

Ответов: 16884

Рейтинг: 1239

#87: 2010-04-22 16:12:28 ЛС | профиль | цитата

Assasin, еще раз повторюсь
ТО что ты выложил под Delphi висит, под FPC не компилится

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

Разработчик

Ответов: 26170

Рейтинг: 2127

#88: 2010-04-22 16:31:16 ЛС | профиль | цитата

Assasin писал(а):

По конкретнее на примерах

Есть тестовый пример, дальше следуешь инструкциям

nesco писал(а):

Берешь последнюю тестовую прогу, качаешь тестовый файл и вперед -- проверять

В конце концов, ты уже не ребенок. Мне надоело мусолить одно и тоже по десять раз. Страшно надоело, сначала Tad-y вталкивал, что он не то тестирует, теперь тебе объяснять, что все это уже прошли и вариант с

Assasin писал(а):

обойтись без лишнего условия при составлении таблицы отступов

тоже
Вот потому я и написал

nesco писал(а):

Остальные "умные" предложения можешь оставить себе до выяснения их работоспособности

на тестовом примере

Assasin писал(а):

Так я же заменил i := lp downto 1 на i := 1 to lp, или я что то опять не понял?

УУУУУУУУ.. Да сколько можно. Я про что тебя спрашивал

nesco писал(а):

или ты еще чего-то поменял

Что, я должен твой код размусоливать, делать мне больше нечего, ткни пальцем, где поменял, вот я и спросил
------------ Дoбавленo в 16.27:
А вообще-то смещение должно идти с конца, на этом и построен алгоритм, от lp до 1, а ты весь цикл перезаписываешь повторные символы, и где прирост быстродействия, а условие, кстати, запрещает перезаписывать повторы. Вывод: если ничего не имеем в плюсах, то нафиг оно нужно
------------ Дoбавленo в 16.31:
Ravilr, а как ты себя будешь чувствовать, когда вчера мусолили, муслоли, сделали, наконец-то, а тут прихоит молодой гений, и снова наступает на те же грабли

Причем, даже не удосужевшись стянуть тестовый пример и проверить свои нововведения

карма: 22

Ответов: 16884

Рейтинг: 1239

#89: 2010-04-22 16:59:18 ЛС | профиль | цитата

Assasin писал(а):

Так будет еще быстрее, чем просто + 1

Нифига себе ускорение.
Ну у меня тест на 80-ти мб-ой строке
код от nesco -
Первая тройка - поиск подстроки из 74-х символов
Вторая тройка - поиск одиночного, заведомо отсутствующего символа(искал "$"

Самый оптимальный вариант NewPosEx(Asm) ИМХО

код от Assasin - результата не дождался. Висяк - прервал на 20-ой минуте.
Спорьте дальше.

карма: 25

Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!

файлы: 1

pos.png [3.2KB] [299]

Разработчик

Ответов: 26170

Рейтинг: 2127

#90: 2010-04-22 17:05:15 ЛС | профиль | цитата

Tad писал(а):

поиск одиночного, заведомо отсутствующего символа(искал "$"

Ты что, его часто ищешь

То что ты проверял, в реальной жизни имеет очень маленькую вероятность. И это никаким боком не отражает оптимальность кода

И в этом случае я с тобой категорически не согласен, особенно, с применением самопального asm кода. Мы проверяем на Delphi4, этот же код скомпилированный на Delph7 будет еще оптимальнее

карма: 22

Форумы ПрочееФункция PosEx из Share.pas ← Ctrl1 2 3 4 567 8 9 10 11 12Ctrl →


Сообщение ...
Прикрепленные файлы (файлы не залиты)