Делфи. Вопросы возникающие в ходе обучения

[PAV]

Опишите дальнейший ход алгоритма словами: что в принципе нужно сделать. Затем продумайте, как это сделать технически: какие структуры данных завести и как с ними работать. Последним шагом уже оформите это в виде кода.

[Student2007]

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

[Student2007]

ничего конструктивного не придумал... Если пробовать приклеить третий байт, то получится число явно выходящее за пределы 65535.. и формировать такой массив как-то не логично, как и не логично формировать массив из чисел размером в 4 байта.

[Student2007]

Значит что я сделал... Создал список, элементами которого являются:
указатель номер строки, индекс массива (WordBuf), позиция символа в строке, ну и укзатель на следующий элемент этого списка.
В процессе заполнения массива LinesCount формируется и этот список.
Далее, я обрабатываю этот список и исключаю из него элементы, в которых значение, полученное по индексу массива, меньше чем половина всех строк.
**
Следующим этапом я планирую отсортировать этот список по полю указателя номера строки. После этого отсортирую элементы с одинаковым указателем на номер строки по полю позиции символа в строке. Таким образом, элементы выстроятся друг за другом в том порядке, в каком они следуют в обрабатываемой строке.
После этого полученную цепочку обработаю так, что бы следующие друг за другом байты (позиция которых изменяется с шагом 1) интерпретировались как блоки байтов. Полученные блоки и будут регулярными выражениями..
Единственный минус такого способа, что размер второго списка 200 * количество строк. Если строк будет 1000, то элементов в списке до обработки будет 200 000 .. После обработки количество элементов в нем существенно сократится.

Добавлено спустя 1 час 38 минут 31 секунду:

сортировка по номерам столбцов даже не нужна, потому что они изначально отсортированы.

Добавлено спустя 36 минут 40 секунд:

как оказалось позиции элементов сортировать тоже не надо, жаль я медленно думаю.. Осталось только обработать последовательность самой короткой строки... Кстати элементы и строки идут как в стеке:)

[Student2007]

вобщем да, получил я результат работы:), вот только его надо обрабатывать:

Цитата:

6179 796C 6C69 6961 6179 796C 6C69 3F61 616C 6C65 6564 6420 206B 6B61 616B 6B20 2074 7465 6576 7669 6972 7270

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

Цитата:

6179 796C 6C69 6961 6179 796C 6C69
и
3F61 616C 6C65 6564 6420 206B 6B61 616B 6B20 2074 7465 6576 7669 6972 7270

затем убрать склееные байты:

Цитата:

6179 6C69 6179 6C69
и
3F61 6C65 6564 206B 6B61 6B20 7465 7669 7270

затем инвертировать пары байтов между собой:

Цитата:

7961 696C 7961 696C
(пишу уже один блок)

а после этого инвертировать порядок следования пар байтов (сначала 2 последних, потом 2 предвоследних и т.д.)

Цитата:

696C 7961 696C 7961

вот такие не хитрые операции))... Как думаете, следует ли работать с полученным блоком байтов как со строкой текста, или же применить другие операции?

[PAV]

Честно говоря, я мало что понял из написанного.

Не обязательно сразу формировать список, содержащий 200 000 элементов. Сначала можно только подсчитать пары байтов, а затем пройти по всем строкам еще раз, сохраняя позиции только для тех пар, которые встретились достаточно часто.

С третьим байтом предложение было следующим. Берем конкретную пару байтов ab, которая встречается достаточное количество раз. Перебираем все вхождения этой пары и подсчитываем количество вхождений всех возможных значений третьего байта. Для этого требуется массив (один или несколько) из 256 элементов. Проведя подсчеты, мы перебираем этот массив и определяем все тройки abc, которые встречаются необходимое количество раз. Сохраняем их (например, в списке).

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

[Student2007]

PAV в сообщении #208276 писал(а):

Не обязательно сразу формировать список, содержащий 200 000 элементов. Сначала можно только подсчитать пары байтов, а затем пройти по всем строкам еще раз, сохраняя позиции только для тех пар, которые встретились достаточно часто.

вполне логично, таким образом список изначально можно сократить, а вместе с ним и общее количество циклов... Сейчас подумаю над реализацией.

а с третьим байтом - я до сих пор не могу понять, что надо сделать.. Я так понимаю, надо линейно найти сначала в одной строке пару байтов, после того как она найдена попробовать интерпретировать следующий байт как индекс массива a[0..255] и в нужном месте увеличить значение элемента на один (пусть будет a[10], параллельно с этим запоминать и номера строк. потом сделать это же для второй строки и так далее.
после того как прошлись по всем строкам сверить значение а[10] со значением по индексу LinesCount[первая склееная пара байтов, если значения счетчиков одинаковые, то обнулить значения в a[0..255] а так же в массиве индекса строк и пробовать дополнить четвертым байтом. И так до тех пор, пока не значения счетчиков не станут разными..
Помоему, тут больше циклов, если бы мы сформировали список из элементов встречающихся в более 50%, а потом бы скорректировали указатели таким образом, что бы выводить элементы с конца списка.. а что бы убрать склеенные байты - производить обратную операцию от склеивания:

byteBuf[1]:=curr2^.IndexArray;

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

Добавлено спустя 5 минут 31 секунду:

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

Цитата:

fa a9 93 34 3f и так далее

получим

Цитата:

fa 93

4 - теряем..

по потере видно, что начался другой блок байтов[/b]

Добавлено спустя 1 минуту 34 секунды:

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

Добавлено спустя 1 минуту 29 секунд:

я Ваш вариант реализации просто не до конца понимаю, поэтому пытаюсь объяснить свой, вдруг он по эффективности такой же как и Ваш?

Добавлено спустя 3 минуты 53 секунды:

если потерю байта вовремя выявить, то будет корректно выведен и первый блок, и следующие за ними. Как вариант (особо не вдумывался пока, пока не скорректировал указатели) - контроллировать значения на стыке байтов, если они будут разными, то это будет границей блоков, а это будет означать, что последний 2 байты надо без изменений скопировать в byteBuf

[Student2007]

PAV в сообщении #208276 писал(а):

Не обязательно сразу формировать список, содержащий 200 000 элементов. Сначала можно только подсчитать пары байтов, а затем пройти по всем строкам еще раз, сохраняя позиции только для тех пар, которые встретились достаточно часто.

при тысяче файлов и длине строки 200 байт пр первом проходе (заполнение массива LinesCount) будет сделано 199000 циклов. При втором проходе (формирование списка, а так же повторный проход для считывания linesCount) + 199000... Что-то ни чего не выиграл , хотя подход более изящный:) и внутри циклов всяко меньше операций, чем если бы пришлось создавать, а потом удалять лишние элементы списка..
Регулярные выражения я наконец-таки получил, но к сожалению не вашим методом...

[Student2007]

кстати совсем не обязательно делать 199000 циклов... Возможно, это число будет сведено до половины в самом худшем случае:).. В лучшем случае сведено к единице:).. Поскольку мы ищем последовательность, которая встречается максимально часто, то в ходе заполнения массива LinesCount можно ввести переменную, которая будет хранить максимальное число строк, в которых встретилась какая-либо комбинация.. При формировании списка можно воспользоваться сравнением с этим максимальным значением текущего элемента LinesCount[WordBuf], как только сравнение будет ИСТИНА из цикла в 199000 можно будет выйти:)

[sp.caster]

как в делфи нарисовать дугу??? arc ???

[Student2007]

не, то что я написал - не работает как надо ..
sp.caster
я графику вообще не использую, так что помочь не смогу.

[sp.caster]

да, arc. Вот токо почемуто не получается у меня нормально нарисовать через arc облако.

[Student2007]

пишу тут, так как вопрос пустяковый. Вобщем в чем суть.
Есть код:

procedure TForm1.Button5Click(Sender: TObject);
type
  TPb=^Tb;
  Tb=record
    all:string;
    next:TPb;
    back:TPb;
  end;

var


  {переменные для работы со списками}
  currB, headB,nodeB,  hvostB:TPb;

так вот, подразумевается, что изначально списки пустые и нужны, что бы работать только в пределах одной процедуры. Вопрос в том, что hvostB изначально получается не равным NIL, а указывает на какой-то адрес. Но при его заполнении я ориентируюсь на переменную hvostB, что бы заполнять (если hvostB не равно NIL) или не заполнять (если hvostB=NIL) поле back (содержит адрес предыдущего элемента). ну собственно вопрос: корректно ли, если я в начале процедуры напишу так:

begin
  hvostB:=NIL;

Вроде тогда всё работает, но вдруг так делать нельзя?

[kahey]

Здравствуйте.
У меня следующий вопрос.
Я написал несколько программ, которы приведены здесь
http://rznusl.ucoz.ru/load/
мне бы желательно как-то их протестирывать.
Там несколько программ, меня главным образом интересуют программы для работы с большими числами (раздел "вспомогательные программы").

[Ed_Em]

kahey в сообщении #227140 писал(а):

Здравствуйте.
У меня следующий вопрос.
Я написал несколько программ, которы приведены здесь
http://rznusl.ucoz.ru/load/
мне бы желательно как-то их протестирывать.
Там несколько программ, меня главным образом интересуют программы для работы с большими числами (раздел "вспомогательные программы").

Еще один велосипед?
Есть же http://gmplib.org/, http://www.shoup.net/ntl/ и многие другие...