HiAsm
HiAsm
Вверх ↑
Форумы"Игра в слова"Теоретический вопрос про оптимизацию ← Ctrl123Ctrl →
Этот топик читают: Гость
Ответов: 8887
Рейтинг: 823
#16: 2017-05-26 17:04:09 ЛС | профиль | цитата
Tad писал(а):
И есть на все буквы алфавита.
Ржал, не могу!
Вовочка писал(а):
Карлик во-от с таким хххх!
карма: 19

0
Ответов: 817
Рейтинг: 52
#17: 2017-05-26 17:13:35 ЛС | профиль | цитата
Galkov писал(а):
Вот вам и весь сказ

Я даже не сомневаюсь, что именно так и есть, но хотелось бы понять что вы сказали.
карма: 1

0
Ответов: 16884
Рейтинг: 1239
#18: 2017-05-26 18:03:47 ЛС | профиль | цитата
-= DriveR =- писал(а):
но хотелось бы понять что вы сказали.

Схема от Galkov в 4-5 раз быстрее.
карма: 25
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Ответов: 5227
Рейтинг: 586
#19: 2017-05-26 19:32:26 ЛС | профиль | цитата
Есть в VBScript такой объект как Dictionary (если мне не изменяет память)
Так вот когда я делал тесты на похожую тематику то IC c StrList буквально не на много опередил.
Но разница в коде была очевидна, ПиСАТЬ было трудней и гораздо больше
карма: 4
Мой форум - http://hiasm.bbtalk.me/ схемы, компоненты...
0
Ответов: 9906
Рейтинг: 351
#20: 2017-05-26 23:17:52 ЛС | профиль | цитата
-= DriveR =- писал(а):
но хотелось бы понять что вы сказали.

Вот спрашивается, чего тут непонятного:
procedure THiAsmClass.doCalc;
var i,j,k,l:integer;
    ss:string;
begin
  ss := ToString(_Data);
  _hi_CreateEvent(_Data, @onIs, ss);
  i := 0; j := _Numb-1;
  k := StrComp(pchar(_Arr[i]), pchar(ss));
  l := StrComp(pchar(_Arr[j]), pchar(ss));
  if (k=0)or(l=0) then exit;
  if (k<0)and(l>0) then while (j-i)>1 do begin
    k := (i+j) div 2;
    l := StrComp(pchar(_Arr[k]), pchar(ss));
    if l=0 then exit;
    if l>0 then j := k
    else i := k;
  end;
  _hi_CreateEvent(_Data, @onNo, ss);
end;
Пять простеньких строк внутри цикла ......

Каждое сравнение уменьшает область (между i и j) поиска слова в отсортированном массиве в ДВА РАЗА.
Поэтому, сколько надо сделать сравнений для массива в 1000 слов ??? Десять.
А для массива в 2000 слов -- одиннадцать.
А для массива в 4000 слов -- двенадцать.
И т.д.. Это и есть логарифмическая асимптотика.

А сколько надо сделать сравнений для массива в 1000 слов полным перебором ???
Разницу чувствуете, или как

Редактировалось 3 раз(а), последний 2017-05-26 23:28:03
карма: 9

0
Ответов: 9906
Рейтинг: 351
#21: 2017-05-27 14:35:29 ЛС | профиль | цитата
Tad писал(а):
Быстрее всего получилось с перенаправлением по первой букве на свой список.

Если, опять же, говорить о теории -- то это называется хешированием словаря.

Вычисляется некоторый хэш для искомого слова, который является индексом для массива указателей.
Указателей на списки (массивы) слов с одинаковым хэшом.
Брать в качестве хэша первую букву слова, хоть и очень быстро, но не очень эффективно - сам же говорил, что на букву 'П' большая половина словаря падает.
Смысл хэширования - разбить весь словарь максимально равномерно по отдельным спискам.

Ну, например - CRC8... Если он более или менее равномерно распихает словарь по 256 спискам, то в каждом будет десяток-другой слов.
Если мы искали "полным перебором" - эффект будет впечатляющий.
А если "делением пополам" - то сэкономим аж 8 сравнений. И потеряем на вычислении хэша. Что лучше - смотреть надо более конкретно...

Можно брать нужное (10-12) количество битов от CRC16. Тут нужно отдельное изучение, с конкретным словарем, с оптимизацией алгоритмов, и т.п..
карма: 9

0
Разработчик
Ответов: 26061
Рейтинг: 2120
#22: 2017-05-27 14:50:57 ЛС | профиль | цитата
А еще можно добавить распределение искомых слов в словаре по частоте использования, а не по алфавиту
карма: 22

0
Ответов: 9906
Рейтинг: 351
#23: 2017-05-27 15:06:00 ЛС | профиль | цитата
Дело в том, что "еще" не получается, а получается - "вместо"

Предположим: 90% того, что мы говорим - не является матом (только к примеру - особо культурных просьба не обижаться!).
Тогда, проверка методом "полного перебора" прошелестит весь список "почти всегда".

Ну и причем тут "частота использования", спрашивается...
Задача у нас, насколько я понял, не только в том, чтобы быстро НАЙТИ, но и не менее быстро - НЕ НАЙТИ

Редактировалось 6 раз(а), последний 2017-05-27 15:19:05
карма: 9

0
Ответов: 16884
Рейтинг: 1239
#24: 2017-05-27 16:28:21 ЛС | профиль | цитата
Ну вообще-то матерных корней всего 7(или 11) и проверять нужно не на слово, а на наличие корня.

Редактировалось 1 раз(а), последний 2017-05-27 16:29:04
карма: 25
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Ответов: 8887
Рейтинг: 823
#25: 2017-05-27 17:01:36 ЛС | профиль | цитата
Tad,
"Слов немного, пять иль шесть,
Зато какие комбинации!" (с)А. Иванов
карма: 19

0
Ответов: 16884
Рейтинг: 1239
#26: 2017-05-27 17:18:02 ЛС | профиль | цитата
Леонид, заглянул в Википедию. Вроде уже к 6000 комбинаций приближаемся.
карма: 25
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Ответов: 9906
Рейтинг: 351
#27: 2017-05-28 10:13:35 ЛС | профиль | цитата
sla8a писал(а):
Посколько помню по скорости выполнения рейтинг такой:

Забыли самый главный фактор - тип алгоритма. Или, если хотите - его асимптотику.
Например, все помнят про сортировку. Асимптотика рекурсивной сортировки O(N*ln(N))
А асимптотика пузырькового метода O(N^2).
И, при достаточно большом N, рекурсивная сортировка, сделанная "на рассыпухе" как схема в HiAsm -- обойдет по скорости пузырьковую на IC.
И даже - сильно обойдет.

Так и у нас, с "поиском в словаре". Полный перебор - это одно (O(N)), а деление пополам - это другое (O(ln(N))).
Хотя, для второго случая, и необходима предварительная сортировка словаря.


Tad писал(а):
Схема от Galkov в 4-5 раз быстрее.

Как бы сравнивать быстродействие с разными асимптотиками - не есть правильно.
Результат очень сильно зависит от входных данных.
При малых объемах словаря - вполне может оказаться и наоборот.
А при больших:
Поиск делением пополам
Поиск полным перебором
Это, как бы, вовсе не "в 4-5 раз быстрее"
А теперь вспомним, что эксперимент - "это вам не баб щупать"... Измерим время "холостого хода": подадим событие мимо IC, скажем вместо onNo
И получится, что собственно поиск - лишь незначительная часть измеренного нами времени. Генерируем слово, а потом запоминаем его мы значительно дольше.
Так что это даже не в 100 раз, а примерно в 500-1000 раз быстрее...

Убедил, или нет


Вместо того, чтобы статистику мата обсуждать, подумали бы, в какой элемент присобачить аналогичный метод.
Вещь-то, простая, как сибирский валенок. А у нас ее нет.
Может в ArraySort ......

Редактировалось 4 раз(а), последний 2017-05-31 14:14:33
карма: 9

0
Разработчик
Ответов: 26061
Рейтинг: 2120
#28: 2017-05-28 10:32:45 ЛС | профиль | цитата
Galkov писал(а):
Может в ArraySort

А почему не в ArrayFind, вроде же мы тут поиск рассматриваем? Ну или создать отдельно компонент ArrayFindEx

Редактировалось 1 раз(а), последний 2017-05-28 10:33:17
карма: 22

0
Ответов: 16884
Рейтинг: 1239
#29: 2017-05-28 14:20:26 ЛС | профиль | цитата
За
nesco писал(а):
создать отдельно компонент ArrayFindEx

или ArrayFastFind

Редактировалось 1 раз(а), последний 2017-05-28 14:21:27
карма: 25
Немного терпения! Дежурный экстрасенс скоро свяжется с Вами!
0
Ответов: 2059
Рейтинг: 131
#30: 2017-05-28 19:30:38 ЛС | профиль | цитата
Galkov, да, всё правильно говорит, а толку?
Были такие компоненты - HashTableString и всё описанное делали, а толку что?
Хоть кто нибудь понял, как это работает?
Согласен, Galkov делает ликбез, за что ему почёт, почёт, почёт.

Но согласитесь господа товарищи - не в пипипип.. не в красную армию.
Galkov, это тебе и мне прозрачо, ....
Не научишь ведь так!

Будь проще (справедлив, понятен, и прост, а самое главное добр!!!) и народ за тобой потянется!
карма: 6

0
Форумы"Игра в слова"Теоретический вопрос про оптимизацию ← Ctrl123Ctrl →
Сообщение
...
Прикрепленные файлы
(файлы не залиты)
HiAsm Studio 2003 - 2020
Пользовательское соглашение | support@hiasm.com
Яндекс.Метрика