Поиск одинаковых строк в двух файлах Опции

[*оля*]

а алгоритм volvo? Что в нем неясного?

Для некоторого упрощения: можно просто читать каждую строку из первого файла искать ее во втором.

Скажем, MD5 (с использованием System.Security.Cryptography он вычисляется в 3 строки).
вот это не понятно мне

[volvo]

Ну смотри. Существует такой алгоритм хеширования - Wiki- > MD5

Так вот, подобный хеш можно получить из любой строки, используя доступные из PascalABC.NET ДотНет-овские классы, а не писать функции для его вычисления самостоятельно:

uses 
  System.Collections.Generic, System.Security.Cryptography;

var
  prov:System.Security.Cryptography.MD5CryptoServiceProvider; 
  // это надо будет еще проинициализировать в основной программе
  
function CalcHash(s: string):string;
var
  a: array of byte;
  sb: System.Text.StringBuilder;
begin
  a := System.Text.Encoding.UTF8.GetBytes(s);
  a := prov.ComputeHash(a);
  sb := new System.Text.StringBuilder;
  foreach b: byte in a do sb.Append(b.ToString('x2').ToLower());

  CalcHash:= sb.ToString;
end;

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

Но это - уже реализация. Что в алгоритме-то непонятно?

[*оля*]

Ну смотри. Существует такой алгоритм хеширования - Wiki- > MD5
...
Но это - уже реализация. Что в алгоритме-то непонятно?

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

[*оля*]

выдает такую ошибку: Ошибка времени выполнения: В экземпляре объекта не задана ссылка на объект.
в строке
a := prov.ComputeHash(a);
я наверное что-то не дописала...что бы это могло быть?

[volvo]

А я предупреждал:

// это надо будет еще проинициализировать в основной программе

В самом начале основной программы надо инициализировать этот объект:

prov := new System.Security.Cryptography.MD5CryptoServiceProvider;

, только после этого его можно использовать. Обрати внимание, точно так же перед использованием внутри функции инициализируется System.Text.StringBuilder. Любой обзект перед тем, как к нему обращаться, нужно создать...

[*оля*]

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

[Lapp]

2 volvo:
я все же не понимаю, в чем тут пойнт применения хэшей. Почему нельзя сравнивать сами строки? В задаче нет ничего про секьюрити или там сжатие.. Сравнение строк может быть эффективнее использования хэшей в конечном итоге. Большинство строк начинаются с неравных символов - они сразу отметаются в самом начале. А для вычисления хэша всегда нужно прочитать всю строку. Зачем?

[volvo]

Только ради экономии памяти. Прочитать все строки файла в память (а строка может быть длинной), или хранить только хеш (фиксированной, причем небольшой) длины - это две большие разницы. И разницы эти тем больше, чем больше размеры файлов, с которыми нужно работать и чем длиннее в них строки.

В принципе, можно обойтись и без хеширования, конечно; надо будет прогнать пару тестов на больших файлах, посмотреть, насколько быстро MD5 вообще вычисляется, и насколько программа начинает подтормаживать, когда ей проходится работать со строками, а не их хешами... Если торможения не будет (или будет незначительное) - то работать с полными строками.

[Lapp]

Только ради экономии памяти.

да, про память я как-то уже забыл тут.. Прикинул, что 1500 строк (по максимум 255 символов) берут не больше трети мега - и забыл..

Да, конечно, если нужно сжимать - то хэш. Но, судя по началу темы ("лишь бы работало")) - скорее всего не нужно.. Сравнить скорость двух подходов: с хэшированием и непосредственным чтением из файла - это действительно интересно. Результат, впрочем, будет сильно зависеть от системного дискового кэша..

[*оля*]

идея сравнить 2 метода очень интересная )))

[*оля*]

Берешь файл. Один... Построчно читаешь его в переменную типа String, и запоминаешь в List<String> ее хеш.

можно спросить, каким образом сохранить в List<String>? (

[volvo]

У него есть метод Add:

var
  L: System.Collections.Generic.List<string>;

... 
  // Инициализируем список:
  L := new System.Collections.Generic.List<string>;

  // Каким-то образом получаем строку, которую надо сохранить (назовем ее st)

  L.Add(st); // и заносим строку в список

За дополнительной информацией о .NET-овских контейнерах - сюда: MSDN -> System.Collections.Generic Namespace

[*оля*]

У него есть метод Add:

var
  L: System.Collections.Generic.List<string>;

... 
  // Инициализируем список:
  L := new System.Collections.Generic.List<string>;

  // Каким-то образом получаем строку, которую надо сохранить (назовем ее st)

  L.Add(st); // и заносим строку в список

а потом,для поиска тоже свой метод есть?

[volvo]

Естественно. Есть метод Find, есть FindAll (для поиска всех совпадений по заданному критерию), есть метод Contains, позволяющий определить просто есть ли в списке заданный элемент, есть IndexOf (чтобы определить индекс элемента, совпадающего с искомой строкой)... Методов - валом...

Мне кажется, или тема уже вышла далеко за рамки раздела "Задачи"? Теперь здесь в основном обсуждаются .NET-овские фишки. Может перенести в "Другие языки"? (я понимаю, что язык тот же, но... Туда и шарписты заходят, может помогут чем).

[*оля*]

Естественно. Есть метод Find, есть FindAll (для поиска всех совпадений по заданному критерию), есть метод Contains, позволяющий определить просто есть ли в списке заданный элемент, есть IndexOf (чтобы определить индекс элемента, совпадающего с искомой строкой)... Методов - валом...

Мне кажется, или тема уже вышла далеко за рамки раздела "Задачи"? Теперь здесь в основном обсуждаются .NET-овские фишки. Может перенести в "Другие языки"? (я понимаю, что язык тот же, но... Туда и шарписты заходят, может помогут чем).

спасибо, все, с .NET-овскими фишками вопросов больше нет)
теперь другое... мы считаем хеш сразу для всей строки, а как посчитатеь его не сразу для всей, а для каждого слова в строке отдельно?

[*оля*]

что не так в программе?

 var
rand8: array[0..255] of integer;
st: string;
line: string;
F: text;
f_name: string;

procedure init;
var
i: integer;
begin
randomize;
for i:=0 to 255 do
rand8[i]:=random(255);
end;

function h(st: string): integer;
Var
Sum: longint;
I: integer;
Begin
For i:=0 to length(st) do
Sum := sum + ord(st[i]) xor rand8[i];
H:=sum mod 256;
end;

begin
writeln('введите имя файла');
readln(f_name);
assign(f,f_name);
reset(f);
while not eof(f) do begin
readln(line);
st:=line;
init;
h(st);
writeln (h(st));
end;
close(f);
end. 

.

[*оля*]

все, нашла ошибку, сорри