Эффективность алгоритма... А Ты сможешь лучше??

← →
Ega23 © (2005-12-30 09:11) [80]

> "Необходимо" - значит можно сделать существенно лучше.

Ещё раз: что значит "существенно"?

← →
Sandman29 © (2005-12-30 09:23) [81]

Unknowing (29.12.05 16:21) [77]
Что лучше два цикла или как у мастера Sha множества. Потому как полагаю что для их обработки компилятор используют цикл.

Множества лучше. Для проверки на вхождение во множества используется не цикл, а одна машинная команда AND. Мастера, поправьте, если ошибаюсь.

← →
Unknowing (2005-12-30 09:23) [82]

> Ega23 © (30.12.05 09:11) [80]

Ну, как с сортировкой!! Можно пузырьковым методом: задача выполняется, но не эффективно, а можно быстрой сортировкой: задача выполняется, но уже существенно лучше.

← →
Bless © (2005-12-30 09:27) [83]

> Unknowing (30.12.05 09:23) [82]
>
>
> > Ega23 © (30.12.05 09:11) [80]
>
> Ну, как с сортировкой!! Можно пузырьковым методом: задача
> выполняется, но не эффективно, а можно быстрой сортировкой:
> задача выполняется, но уже существенно лучше.

:) Не факт. Боюсь ошибиться, но, имхо, на маленьких массивах быстрая сортировка может быть даже медленнее пузырьковой.

← →
Unknowing (2005-12-30 09:44) [84]

> Bless © (30.12.05 09:27) [83]

Джулиан Бакнелл (автор книги "Фундаментальные алгоритмы в Delphi")утверждает, что про пузырьковый метод можно смело забыть.

← →
Ega23 © (2005-12-30 09:49) [85]

> Джулиан Бакнелл (автор книги "Фундаментальные алгоритмы
> в Delphi")утверждает, что про пузырьковый метод можно смело
> забыть.

Я не знаю, кто такой Джулиан Бакнелл, но на множестве из пяти элементов пузырёк рулит.

Кстати, алгоритм QuickSort - это не бинарное ли дерево?

← →
Unknowing (2005-12-30 09:59) [86]

> Ega23 © (30.12.05 09:49) [85]

← →
Unknowing (2005-12-30 10:01) [87]

> Ega23 © (30.12.05 09:49) [85]

> Кстати, алгоритм QuickSort - это не бинарное ли дерево?

Это, скорее, я у Вас должен спрашивать! :)

← →
ferr © (2005-12-30 10:53) [88]

нет, сортировка с помощью бинарного дерева наз-ся "хипом", сортирующим деревом, пирамидальной

← →
ferr © (2005-12-30 10:58) [89]

Когда-то реализовывал всё это, вот такие результаты на 16 элементах:
Bubble 0.0025
Shaker 0.0025
Selection 0.0024
Insertion 0.0012
InsertionO 0.0013
QuickSort 0.0027
QuickSortO 0.0016
HeapSort 0.0027

← →
ferr © (2005-12-30 10:58) [90]

MergeSort 0.0015

← →
MasterPaleva © (2005-12-31 07:39) [91]

Алгоритм распознает все русские слова в тексте, включая слова, которые пишутся через тире ("где-то", например), находит самое длинное и короткое слово в предложении.

Текст для проверки: Где-то на изходной планете времена изменились, это ли то самое удивительное - то, что называется градусником.

Результат:
Самое длинное слово: 12 сим.
Самое короткое слово: 2 сим.
Всего слов: 15

function slov(st:string):string; var mas: array of string; i, j: integer; n, n2: integer; begin st:=st+" "; j:=0; n:=0; n2:=length(st); setlength(mas,1); for i:=1 to length(st) do begin // распознает только русские слова if (ord(st[i])>185+3+3) and (ord(st[i])<253+2+1) then begin //showmessage(st[i]+" / "+IntToStr(length(mas))); mas[j]:=mas[j]+st[i]; end else begin if st[i]="-" then begin if (st[i-1]<>" ") and (st[i+1]<>" ") then mas[j]:=mas[j]+st[i]; end else begin if mas[j]<>"" then begin if length(mas[j])>n then n:=length(mas[j]); if length(mas[j])<n2 then n2:=length(mas[j]); inc(j); setlength(mas, length(mas)+1); end; end; end; end; result:="Самое длинное слово: "+inttostr(n)+" сим. "#13#10+"Самое короткое слово: "+inttostr(n2)+" сим."#13#10+"Всего слов: "+inttostr(length(mas)-1); end;

← →
Джо © (2005-12-31 07:55) [92]

> [91] MasterPaleva © (31.12.05 07:39)

Бонч-Бруевич.

← →
Sha © (2005-12-31 11:15) [93]

> MasterPaleva © (31.12.05 07:39) [91]

Давай разбираться.

1. Оператор st:=st+" "; излишен, т.к. непустая ANSI-строка
оканчивается символом #0, который, по идее, является разделителем.

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

3. Также крайне неэффективны операторы типа mas[j]:=mas[j]+st[i];
Ведь тебе впоследствии будут нужны не сами данные, а только длина
текущего слова. Вот и подсчитывай ее в отдельной переменной. Намного
быстрее и понятнее.

4. Буквы "Ё" и "ё", по-твоему, - иностранные?

5. Если строка начинается с "-", то возвращаемый функцией результат
зависит от старшего байта длины строки, т.к. делается попытка сравнения
(st[i-1]<>" ")

Успехов в новом году :)

← →
MasterPaleva © (2005-12-31 12:47) [94]

Sha © (31.12.05 11:15) [93]

> 3. Также крайне неэффективны операторы типа mas[j]:=mas[j]+st[i];
>
> Ведь тебе впоследствии будут нужны не сами данные, а только
> длина
> текущего слова. Вот и подсчитывай ее в отдельной переменной.
> Намного
> быстрее и понятнее.

Да массив вообще там не нужен для решения этой задачи. Предполагается, что впоследствии придется работать с данными, сортировать слова, проверять грамотность написания слов, переводить слова и т.д.

> 4. Буквы "Ё" и "ё", по-твоему, - иностранные?

Мда, портят всю картину.

function slov(st:string):string; var mas: array of string; i, j: integer; n, n2: integer; begin st:=st+" "; j:=0; n:=0; n2:=length(st); setlength(mas,1); for i:=1 to length(st) do begin if (ord(st[i])>186) and (st[i]<>"Ё") and (st[i]<>"ё") then begin mas[j]:=mas[j]+st[i]; end else begin if st[i]="-" then begin if (st[i+1]<>" ") then mas[j]:=mas[j]+st[i]; end else begin if mas[j]<>"" then begin if length(mas[j])>n then n:=length(mas[j]); if length(mas[j])<n2 then n2:=length(mas[j]); inc(j); setlength(mas, length(mas)+1); end; end; end; end; result:="Самое длинное слово: "+inttostr(n)+" сим. "#13#10+"Самое короткое слово: "+inttostr(n2)+" сим."#13#10+"Всего слов: "+inttostr(length(mas)-1); end;

← →
begin...end © (2005-12-31 13:11) [95]

> Sandman29 © (30.12.05 09:23) [81]

> Для проверки на вхождение во множества используется не цикл,
> а одна машинная команда AND.

Цикл не используется. Но и одной командой AND дело не обходится. Обычно используется либо команда BT, либо арифметические операции с последующим анализом флагов. Зависит это от многих факторов: является ли множество переменной или константой, какова его максимальная мощность, и т.д.

← →
Sha © (2005-12-31 16:34) [96]

> begin...end © (31.12.05 13:11) [95]
> Sandman29 © (30.12.05 09:23) [81]
> Sha © (28.12.05 19:54) [50]

Чтобы ускорить работу и оставить только BT, имеет смысл использовать
"полноразмерное" множество (set of char).

Для ускорения пролога и эпилога также хорошо бы объявить входной
параметр как const.

Т.о. процедура должна начинаться так:

procedure TelegramStatistics(const s: string; var wordcount, minlen, maxlen: integer); const characters: set of char= ["0".."9","A".."Z","a".."z","А".."Я","Ё","ё","а".."я"];

← →
Unknowing (2006-01-10 08:26) [97]

Рад снова всех приветствовать!!
Никак мне не дает покоя мой вопрос...:)

> Sha © (31.12.05 16:34) [96]

Каково Ваше мнение на предмет:

> -хорошо, но можно сделать иначе;
> или
> -плохо!! Необходимо сделать иначе!

← →
Igorek © (2006-01-10 08:52) [98]

> Unknowing (30.12.05 09:44) [84]
> > Bless © (30.12.05 09:27) [83]
> Джулиан Бакнелл (автор книги "Фундаментальные алгоритмы
> в Delphi")утверждает, что про пузырьковый метод можно смело
> забыть.

Интересно, а как автор предлагает сортировать большие сильно упорядоченные массивы?

> Unknowing (10.01.06 08:26) [97]

-плохо!! Необходимо сделать иначе!

Тут небыло хорошего варианта. Хорошего - в смысле как "в книге написано".

← →
Unknowing (2006-01-10 09:01) [100]

ато я теперь знаюкак правильно составлять телеграммы. Не ставить пробеллы. И платишь за одно слово. Гениально.

← →
Unknowing (2006-01-10 09:08) [102]

> Думкин © (10.01.06 09:05) [101]

Это не реальная задача!!!! Это, блин, для начинающих программировать!
> Igorek © (10.01.06 08:55) [99]

Не понял! Есть свой вариант?? Поясните!

Unknowing (28.12.05 16:35) [6] > Ega23 © (28.12.05 16:31) [3] Слова здесь все что между пробелами!! Задача посчитать стоимость телеграммы, которая считается из перечисленных параметров.

Я вас за язык не тянул, и за другие части тела тоже.

> Unknowing (10.01.06 09:08) [102]

Своего нету. Пока. :)
Хорошим вариантом я считаю полностью по-человечески расписанный конечный автомат. Он и по читабельности и по скорости будет близок к идеалу.

← →
Unknowing (2006-01-10 09:20) [105]

> Unknowing (10.01.06 09:20) [105]

Неужели ты думаешь я не видел [43] когда писал [104]?
И я имел ввиду конечный автомат в одной процедуре.

Эффективность алгоритма... А Ты сможешь лучше?? Найти похожие ветки