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

[Student2007]

ewert
тоесть, как я понял, создать предварительно буфер из 201го байта (именно 200 байт я считываю с каждого файла), и начать заполнение не с нулевого байта, а с 1го по 200-отый.
А командой Move данные из этого буфера уже можно переносить в строковую переменную. Все правильно понял?

[ewert]

Не совсем. Имелся в виду буфер для чтения/записи. Примерно так:

var  buf: array[0..32*1024-1] of byte;
      arstr: array[1..1000] of string[200];
      fff: file;
      a: word;
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Reset(fff, 16*1024);
BlockRead(fff, buf[0], 2, err);
a:=0;
for i:=1 to 1000 do begin
    Move(buf[a], arstr[i][1], 200);
    arstr[i][0]:=#200;
    inc(a, 200);
    if a>=16*1024 then begin
        Move(buf[16*1024], buf[0], 16*1024);
        BlockRead(fff, buf[16*1024], 1, err);
        dec(a, 16*1024);
    end;
end;

(пардон, что на Паскале; как оформляются операции ввода-вывода в Дельфи, я просто не знаю).

[Student2007]

ewert
хм... Спасибо, завтра проанализирую... голова совсем не варит..

[PAV]

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

[Student2007]

предудущий листинг пока еще не разобрал... Появился вопрос: возможно ли передать в процедуру динамический массив в качестве параметра и что бы этот динамический массив обработался процедурой и изменился в соответствие с алгоритмом процедуры?

PAV
скорее всего да, нужно отсортировать в лексикографическом порядке. тоесть если в массиве 4 элемента:

Цитата:

ff 11 00 22 33 55 44 66 55 77 88
ff 33 33 99 55 43 22 11 00 44 33
ff 11 00 22 44 77 88 99 00 11 66
ff 11 01 88 66 44 77 22 11 00 77

то после сортировки элементов он будет выглядеть так:

Цитата:

ff 11 00 22 33 55 44 66 55 77 88
ff 11 00 22 44 77 88 99 00 11 66
ff 11 01 88 66 44 77 22 11 00 77
ff 33 33 99 55 43 22 11 00 44 33

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

type
  podbuf=array[1..11] of byte;
var
  MainBuf:array of podBuf;

соответственно доступ к ячейкам:

  что-то:=MainBuf[1,5] //например

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

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

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

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

[PAV]

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

Далее, если я понимаю правильно, то когда Вы переставляете местами две цепочки, то при этом копируется все содержимое, все 200 байт. Если это так, то совершенно излишне. Правильнее хранить указатели на эти массивы и менять местами их, а содержимое массивов при этом не трогать.

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

[ewert]

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

repeat
  finded:=false;
  for i:=1 to n-1 do begin
    good:=true;
    for k:=1 to 200 do
       if MainBuf[i,k]>MainBuf[i+1,k] then begin
         good:=false;
         break;
       end;
    if not good then begin
      SortMbuf:=MainBufer[i]; 
      MainBufer[i]:=MainBufer[i+1]; 
      MainBufer[i+1]:=SortMbuf; 
      finded:=true;
    end;
  end;
until not finded;

--------------------------------------------------
(пардон, зазевался в "if MainBuf[i,k]>MainBuf[i,k]")

[Student2007]

PAV, ewert
Спасибо... сейчас буду вдумываться и переделывать работу.. Да, с указателями оперировать логичней, чем постоянно копировать данные туда-сюда...
ewert

BlockRead(fff, buf[0], 2, err);

я так понимаю, в этой строчке читается блок из fff в buf[0], размер блока 400 байт (2*Length(buf[0])). Все правильно понял?

[ewert]

Нет. Читаются подряд два блока, размер которых заявлен командой Reset, в область памяти, начинающуюся с buf[0]. В переменной err возвращается к-во фактически считанных блоков (если не ошибаюсь).

(Я ж говорил, что в Дельфях не петрю и потому говорю на Паскале.)

Насчёт указателей. Да, перестановка указателей, конечно, гораздо эффективнее, чем перестановка самих записей (и тут даже не очень принципиально, считать ли указателем ссылку на динамическую память или просто индекс массива). Но -- немного усложняет логику.

[Student2007]

ewert
Паскаль и Делфи практически одно и то же, просто я туплю:(... Сейчас вместо массива MainBufer пробую создать список... ох уж я и не люблю списки и динамические переменные, постоянные непонятки..

[Student2007]

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

[Student2007]

вот и очередная задачка появилась, связанная с поиском одинаковой последовательности байтов, при чем эта последовательность неизвестна. Пример:

Цитата:

45 23 78 97 ff d3 a5 b2 bb 78
cc 32 98 ff d3 d5 23 43 aa 00
cd 99 00 12 33 51 43 ff d3 00
00 22 33 44 55 66 77 88 33 22

как видно, тут есть один блок, состоящий из 2х байтов, который присутствует во всех строчках, кроме последней: ff d3. Для нахождения такой последовательности первое, что приходит - это решение "в лоб", тоесть:
сравнение первого символа первой строки со всеми символами второй, если совпадений не найдено, то поиск в третей строке, если совпадение найдено, то к первому символу добавляется второй и сравнивается в строке там где найдено совпадение, если совпадений с добавленным символом нет, то поиск продолжается снова с одним символом и так до последней строчки. Если после проверки последней строчки совпадений нет, то поис происходит уже со второго байта первой строки и т.д. Если блок найден, то этот блок ищется уже во всех оставшихся строчках и если он встречается более чем в 50% всех строк, то можно считать, что блок найден тот.
При не большом количестве строк поиск должен быть успешным вроде бы... Но если строк много, а строки длинные (200 байт), то обилие вложенных циклов существенно увеличит время нахождения таких блоков..
**
Из литературы на эту тему что можно почитать?
Вопрос темы звучит так: Алгоритм поиска последовательности байтов, которая встречается в 50и процентах всех строк.

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

я вот еще чуть подумал и придумал новый алгоритм, как думаете, он будет лучше вышенаписанного?
Суть заключается вот в чем, берется, сравнивается первая строка со второй:

MainBufA^[j]:=MainBufA^[j] and x[MainBufA^[j] xor Curr^.field1[j]];

(код, который вы мне порекомендовали)
Если сравниваемая строка полностью обнулилась, то такая последовательность нам не подходит.
следующим этапом вторую строку сдвигаем влево на один байт, тоесть было:

Цитата:

cc 32 98 ff d3 d5 23 43 aa 00

стало

Цитата:

32 98 ff d3 d5 23 43 aa 00 cc

и так до тех пор, пока не получим (для примера первую строку тоже напишу)

Цитата:

45 23 78 97 ff d3 a5 b2 bb 78
00 cc 32 98 ff d3 d5 23 43 aa

соответственно после очередного сравнения у нас будет

Цитата:

00 00 00 00 ff d3 00 00 00 00

Это то что найдено относительно второй строки. Далее последовательность ff d3 ищем в оставшихся строках..
Такой способ лучше первого?
Сдвиг скорее всего будет осуществляться опять же с использованием цикла...

[PAV]

Есть книга Билл Смит "Методы и алгоритмы вычислений на строках". Но ее не очень легко читать, а также там нет списка задач, которые решаются, чтобы их можно было быстро просмотреть. Возможно, что там есть что-то похожее, хотя я ее немного просмотрел и стал в этом сильно сомневаться.

Сходу можно придумать следующее: перебрать все последовательности некоторой длины и посчитать, в каком числе строк они встречаются. Единичные байты перебирать не очень интересно, так как наверняка подходящими окажутся очень много, а последовательности длины 3 требуют слишком много памяти. А вот пары байтов - то, что нужно, их всего 65536, хранить массив такого объема - вполне нормально. Одним проходом по строкам посчитайте для каждой пары, в скольких строках она встречается. Только будьте внимательны, так как если пара встречается несколько раз в одной строке, то посчитать ее нужно будет только один раз. Для этого понадобится еще один вспомогательный массив, в котором нужно хранить номер строки, в которой данная пара нашлась последний раз.

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

Проведя эту работу, Вы уже найдете все пары байтов, которые встречаются в половине всех строк. Но, наверное, в задаче требуется найти последовательность максимальной длины, верно? Если так, то начинаем перебирать все такие пары и пробуем дополнить их третьим байтом (а, может быть, сразу пробовать и четвертым). Причем, очевидно, что если мы рассматриваем пару ab, то третий байт c нужно пробовать только среди таких, чтобы пара bc тоже встречалась необходимое число раз.

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

Точнее говоря даже так. Организовать возможность быстрого перебора всех позиций, где содержится заданная пара байтов, будет все равно полезно, это должно сильно ускорить работу. И, конечно же, не нужно внешним циклом перебирать все возможные значения третьего байта c, а затем искать цепочки abc. Нужно перебирать все возможные пары ab, для каждой найденной пары смотреть третий байт и аналогично тому, с чего начинали, считать для каждого байта число строк, где эта последовательность abc встречается. Кстати, сразу же тут же можно подсчитывать все четверки abcd.

[Student2007]

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

А вот пары байтов - то, что нужно, их всего 65536

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

Добавлено спустя 41 секунду:

пока обдумываю предложенный вами алгоритм..

[PAV]

$256^2=2^{16}$